CSc 4330/6330 Programming Language Concepts

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 "";
       }
   }
}