WAE Example - 8 steps to solving the problem

  • STEP 0: Get familiar with language being defined. In the case of WAE language, here are some valid expressions:
    {* 2 3};
    {* {+ 2 3} {- 9 7}};
    {if {+ 1 1} {+ 2 3} {- 9 7}};
    {if {- 1 1} {+ 2 3} {- 9 7}};
    {/ 2 0};
    
  • STEP 1: Identify tokens of the language; For WAE the tokens are:
    NUMBER e.g. 2, 3, 9, 7, 0, 43, 198
    LBRACE denoting {
    RBRACE denoting }
    SEMI denoting ;
    PLUS denoting +
    MINUS denoting -
    TIMES denoting *
    DIV denoting /
    IF denoting if
    
    Write regular expressions for each using ANTLR4 syntax (include regular expression for whitespace)
    fragment I : ('I'|'i') ;
    fragment F : ('F'|'f') ;
    NUMBER : ('0'..'9')+;
    LBRACE : '{';
    RBRACE : '}';
    SEMI : ';';
    PLUS : '+';
    MINUS : '-';
    TIMES : '*';
    DIV : '/';
    IF : I F;
    WS : [ \r\n\t]+ -> skip;
    
  • STEP 2: Devise a grammar (written in ANTLR4 syntax):
    wae : NUMBER
        | LBRACE PLUS wae wae RBRACE
        | LBRACE MINUS wae wae RBRACE
        | LBRACE TIMES wae wae RBRACE
        | LBRACE DIV wae wae RBRACE
        | LBRACE IF wae wae wae RBRACE;
    
  • STEP 3: Create barebones ANTLR4 grammar file, WAE.g4
    grammar WAE;
    // Grammar rules
    wae : NUMBER
        | LBRACE PLUS wae wae RBRACE
        | LBRACE MINUS wae wae RBRACE
        | LBRACE TIMES wae wae RBRACE
        | LBRACE DIV wae wae RBRACE
        | LBRACE IF wae wae wae RBRACE;
    // Lexer rules
    fragment I : ('I'|'i') ;
    fragment F : ('F'|'f') ;
    NUMBER : ('0'..'9')+;
    LBRACE : '{';
    RBRACE : '}';
    SEMI : ';';
    PLUS : '+';
    MINUS : '-';
    TIMES : '*';
    DIV : '/';
    IF : I F;
    WS : [ \r\n\t]+ -> skip;
    
    Now you are ready to verify that the grammar is indeed correct. Here is a sample terminal session:
    $ antlr4 WAE.g4
    $ javac *.java
    $ grun WAE wae -tokens
    {* 2 3}
    <CTRL-D>
    [@0,0:0='{',<'{'>,1:0]
    [@1,1:1='*',<'*'>,1:1]
    [@2,3:3='2',,1:3]
    [@3,5:5='3',,1:5]
    [@4,6:6='}',<'}'>,1:6]
    [@6,9:8='',,2:0]
    $ grun WAE wae
    {* {+ 2 3} {- 9 7}}
    <CTRL-D>
    $ grun WAE wae
    {if {- 1 1} {+ 2 3} {- 9 7}}
    <CTRL-D>
    $ grun WAE wae
    {if {- 1 1} {+ 2 3} {- 9 7}}
    <CTRL-D>
    $ grun WAE wae -tokens
    {* {+ 2 3 4} 2}
    <CTRL-D>
    [@0,0:0='{',<'{'>,1:0]
    [@1,1:1='*',<'*'>,1:1]
    [@2,3:3='{',<'{'>,1:3]
    [@3,4:4='+',<'+'>,1:4]
    [@4,6:6='2',,1:6]
    [@5,8:8='3',,1:8]
    [@6,10:10='4',,1:10]
    [@7,11:11='}',<'}'>,1:11]
    [@8,13:13='2',,1:13]
    [@9,14:14='}',<'}'>,1:14]
    [@10,16:15='',,2:0]
    line 1:10 extraneous input '4' expecting '}'
    
  • STEP 4: Design WAENode class to hold data of the expression tree
    public class WAENode {
    String nodetype; // "num", "plus', "minus", "multiply", "divide", "if"
      double value;
      WAENode child1, child2, child3;
      ...
      constructor, getters and setters
      ...
    }
    
  • STEP 5: Embed Java code in WAE.g4 to construct the expression tree:
    // name must match file name
    grammar WAE;
    // Grammar rules
    waeStart returns [WAENode value] :
        w=wae SEMI { $value = $w.value; };
    
    wae returns [WAENode value] :
        num=NUMBER
      { WAENode n = new WAENode();
        n.setNodeType("num");
        n.setValue(Double.parseDouble($num.text));
        $value = n;
      }
      | LBRACE PLUS w1=wae w2=wae RBRACE
      { WAENode n = new WAENode();
        n.setNodeType("plus");
        n.setChild1($w1.value);
        n.setChild2($w2.value);
        $value = n;
      }
      | LBRACE MINUS w1=wae w2=wae RBRACE
      { WAENode n = new WAENode();
        n.setNodeType("minus");
        n.setChild1($w1.value);
        n.setChild2($w2.value);
        $value = n;
      }
      | LBRACE TIMES w1=wae w2=wae RBRACE
      { WAENode n = new WAENode();
        n.setNodeType("multiply");
        n.setChild1($w1.value);
        n.setChild2($w2.value);
        $value = n;
      }
      | LBRACE DIV w1=wae w2=wae RBRACE
      { WAENode n = new WAENode();
        n.setNodeType("divide");
        n.setChild1($w1.value);
        n.setChild2($w2.value);
        $value = n;
      }
      | LBRACE IF w1=wae w2=wae w3=wae RBRACE
      { WAENode n = new WAENode();
        n.setNodeType("if");
        n.setChild1($w1.value);
        n.setChild2($w2.value);
        n.setChild3($w3.value);
        $value = n;
      }
      ;
    // Lexer rules
    // fragments are not tokens
    fragment I : ('I'|'i') ;
    fragment F : ('F'|'f') ;
    //tokens
    NUMBER : ('0'..'9')+;
    LBRACE : '{';
    RBRACE : '}';
    SEMI : ';';
    PLUS : '+';
    MINUS : '-';
    TIMES : '*';
    DIV : '/';
    IF : I F;
    //White Space
    WS : [ \r\n\t]+ -> skip;
    
  • STEP 6: Write the main program that sets up the interpreter, calls the parser, and displays the tree.
    import org.antlr.v4.runtime.CharStreams;
    import org.antlr.v4.runtime.CharStream;
    import org.antlr.v4.runtime.CommonTokenStream;
    import org.antlr.v4.runtime.BailErrorStrategy;
    //import org.antlr.v4.runtime.ANTLRErrorStrategy;
    import java.io.*;
    import java.util.*;
    import java.lang.*;
    
    public class WAE {
    
      static boolean evalError = false;
    
      static public void main(String argv[]) {    
        System.out.print("WAE> ");
        do {
          String input = readInput().trim();
          if (input.equals("exit")) 
            break;
          else input += ";";
          try {
            CharStream in = CharStreams.fromString(input);
            WAELexer lexer = new WAELexer(in);
            CommonTokenStream tokens = new CommonTokenStream(lexer);
            WAEParser parser = new WAEParser(tokens);
            parser.setErrorHandler(new BailErrorStrategy());
            WAENode tree = (WAENode) parser.waeStart().value;
            Integer level = new Integer(1);
            displayTree(tree,level);
          } catch (Exception e) {
              System.out.println("\nSYNTAX ERROR\n");
              //e.printStackTrace();
            }
        } while (true); 
      }
    
      static void displayTree(WAENode t,Integer level) {
        for (int i=1; i<level.intValue(); i++)
          System.out.print("    ");
        System.out.print("NodeType="+t.getNodeType()+"  ");
        if (t.getNodeType().equals("num"))
          System.out.println("Value="+t.value);
        else if (t.getNodeType().equals("plus") || 
                 t.getNodeType().equals("minus") ||
                 t.getNodeType().equals("multiply") ||
                 t.getNodeType().equals("divide")) {
          System.out.println();
          int lval = level.intValue();
          lval++;
          level = new Integer(lval);
          displayTree(t.getChild1(),level);
          displayTree(t.getChild2(),level);
        }
        else {
          System.out.println("");
          int lval = level.intValue();
          lval++;
          level = new Integer(lval);
          displayTree(t.getChild1(),level);
          displayTree(t.getChild2(),level);
          displayTree(t.getChild3(),level);
        }
      }
    
      static String readInput() {
         try {
           StringBuffer buffer = new StringBuffer();
           System.out.flush();
           int c = System.in.read();
           while(c != ';' && c != -1) {
             if (c != '\n') 
               buffer.append((char)c);
             else {
               buffer.append(" ");
               System.out.print("WAE> ");
               System.out.flush();
             }
             c = System.in.read();
           }
           return buffer.toString().trim();
         } catch (IOException e) {
             return "";
           }
       }
    }
    
    Compile and run the main program, WAE.java

  • STEP 7: Once the expression tree is displayed properly, you can now proceed to add the code to evaluate the expression tree to print the value of the expression.
    import org.antlr.v4.runtime.CharStreams;
    import org.antlr.v4.runtime.CharStream;
    import org.antlr.v4.runtime.CommonTokenStream;
    import org.antlr.v4.runtime.BailErrorStrategy;
    //import org.antlr.v4.runtime.ANTLRErrorStrategy;
    import java.io.*;
    import java.util.*;
    import java.lang.*;
    
    public class WAE {
    
      static boolean evalError = false;
    
      static public void main(String argv[]) {    
        System.out.print("WAE> ");
        do {
          String input = readInput().trim();
          if (input.equals("exit")) 
            break;
          else input += ";";
          try {
            CharStream in = CharStreams.fromString(input);
            WAELexer lexer = new WAELexer(in);
            CommonTokenStream tokens = new CommonTokenStream(lexer);
            WAEParser parser = new WAEParser(tokens);
            parser.setErrorHandler(new BailErrorStrategy());
            WAENode tree = (WAENode) parser.waeStart().value;
            //Integer level = new Integer(1);
            //displayTree(tree,level);
            evalError = false;
            double answer = evalTree(tree);
            if (evalError)
              System.out.println("\nEVALUATION ERROR\n");
            else
              System.out.println("\nThe value is "+answer+"\n");
          } catch (Exception e) {
              System.out.println("\nSYNTAX ERROR\n");
              //e.printStackTrace();
            }
        } while (true); 
      }
    
      static double evalTree(WAENode t) {
        if (t.getNodeType().equals("num")) {
          return t.getValue();
        }
        else if (t.getNodeType().equals("plus")) {
          double v1 = evalTree(t.getChild1());
          if (evalError) return 0;
          double v2 = evalTree(t.getChild2());
          if (evalError) return 0;
          return v1+v2;
        }
        else if (t.getNodeType().equals("minus")) {
          double v1 = evalTree(t.getChild1());
          if (evalError) return 0;
          double v2 = evalTree(t.getChild2());
          if (evalError) return 0;
          return v1-v2;
        }
        else if (t.getNodeType().equals("multiply")) {
          double v1 = evalTree(t.getChild1());
          if (evalError) return 0;
          double v2 = evalTree(t.getChild2());
          if (evalError) return 0;
          return v1*v2;
        }
        else if (t.getNodeType().equals("divide")) {
          double v1 = evalTree(t.getChild1());
          if (evalError) return 0;
          double v2 = evalTree(t.getChild2());
          if (evalError) return 0;
          if (v2 != 0)
            return v1/v2;
          else {
            evalError = true;
            return 0;
          }
        }
        else if (t.getNodeType().equals("if")) {
          double v1 = evalTree(t.getChild1());
          if (evalError) return 0;
          if (v1 != 0)
            return evalTree(t.getChild2());
          else
            return evalTree(t.getChild3());
        }
        else { 
          evalError = true;
          return 0;
        }
      }
    
      static void displayTree(WAENode t,Integer level) {
        for (int i=1; i<level.intValue(); i++)
          System.out.print("    ");
        System.out.print("NodeType="+t.getNodeType()+"  ");
        if (t.getNodeType().equals("num"))
          System.out.println("Value="+t.value);
        else if (t.getNodeType().equals("plus") || 
                 t.getNodeType().equals("minus") ||
                 t.getNodeType().equals("multiply") ||
                 t.getNodeType().equals("divide")) {
          System.out.println();
          int lval = level.intValue();
          lval++;
          level = new Integer(lval);
          displayTree(t.getChild1(),level);
          displayTree(t.getChild2(),level);
        }
        else {
          System.out.println("");
          int lval = level.intValue();
          lval++;
          level = new Integer(lval);
          displayTree(t.getChild1(),level);
          displayTree(t.getChild2(),level);
          displayTree(t.getChild3(),level);
        }
      }
    
      static String readInput() {
         try {
           StringBuffer buffer = new StringBuffer();
           System.out.flush();
           int c = System.in.read();
           while(c != ';' && c != -1) {
             if (c != '\n') 
               buffer.append((char)c);
             else {
               buffer.append(" ");
               System.out.print("WAE> ");
               System.out.flush();
             }
             c = System.in.read();
           }
           return buffer.toString().trim();
         } catch (IOException e) {
             return "";
           }
       }
    }