1

I'm trying to create an AST from this grammar rule

expression ::= term { + term }
term ::= factor { - factor }
factor ::= piece { / piece }
piece ::= element { * element }
element ::= ( expression ) | NUMBER | IDENTIFIER

I have my parser working with the given code below. Let's say my input is
3 * (5 + 2 / x - 1)

My output will be

3 :NUMBER  
*: SYMBOL  
( :SYMBOL  
5 : NUMBER  
+: SYMBOL  
2 : NUMBER  
/ :SYMBOL  
x : IDENTIFIER  
-: SYMBOL  
):SYMBOL  
1 : NUMBER  

the AST I want to build is like this

 *: SYMBOL

      3 : NUMBER

      +: SYMBOL

           5 : NUMBER

           -: SYMBOL

                /: SYMBOL

                    2 : NUMBER

                    x : IDENTIFIER

                1 : NUMBER

Does anyone have any idea to approach this? I'm doing this in Java. Thanks alot

Here is the code:

public class Main {

    public static void main(String args[]) throws FileNotFoundException {
    
    //Create a pattern to see if it matches the string
    String ID = "([a-z]|[A-Z])([a-z]|[A-Z]|[0-9])*";
    String SYM = "\\*|\\+|\\(|\\)|\\/|\\-|\\:=|\\;";
    String NUM = "\\d+";

    Pattern pt = Pattern.compile(ID);
    Pattern pt1 = Pattern.compile(SYM);
    Pattern pt2 = Pattern.compile(NUM);
    
    //Scan the text input file
    Scanner input = new Scanner(new File("Input.txt"));
   
    while(input.hasNext()){
      String token = input.nextLine();
      String ip[] = token.split("\\s+");
      System.out.println("Tokens:\n");

      for(int i = 0; i <ip.length; i++){
        Matcher m = pt.matcher(ip[i]);
        Matcher m1 = pt1.matcher(ip[i]);
        Matcher m2 = pt2.matcher(ip[i]);
        
         while(m1.find()){
          System.out.println(m1.group() + " :SYMBOL");
        } while(m2.find()){
          System.out.println(m2.group() + " :NUMBER");
        } while(m.find()){
          System.out.println(m.group() + " :IDENTIFIER");
        } 
      }
    }
  }
}
user16320675
  • 135
  • 1
  • 3
  • 9
Wesley
  • 11
  • 2
  • "How do I write a recursive descent parser?" is not a question which can be answered in a few paragraphs. You should seek out some basic tutorials, or perhaps a text like [this one](https://math.hws.edu/javanotes/c9/s5.html) (which I haven't examined in depth, but seems to cover the ground.) – rici Oct 21 '21 at 15:05
  • I think my answer on this is just what you need: Constructing an Abstract Syntax Tree with a list of Tokens https://stackoverflow.com/a/25106688/120163 – Ira Baxter Oct 24 '21 at 15:20

0 Answers0