title: Antlr4 Precedence and Associativity
body: <p>I am intersting in parsing an expression such as <code>(B32|B5)&amp;B31</code>.
  My goal is to find out the order in which this expression gets evaluated. So my expected result will be <code>B2</code> then <code>|B5</code> and last of all <code>&amp;B31</code></p>
  
  <p>My expression can have special characters. with <code>*</code>, <code>=</code> and <code>{</code>. So the exp can be <code>B31*{A1,A2}|B35</code>. In this case I would expect <code>B31*{A1,A2}</code> as one token that gets evaluated first and then <code>B35</code>. </p>
  
  <p>I created the following grammar. </p>
  
  <pre><code>grammar Expr;   
  
  prog: (expr NEWLINE)* ;
  
  expr: '(' expr ')'
  | expr ('&amp;'|'|') expr
  | ID
  ;
  
  
  NEWLINE:'\r'? '\n' ; 
  
  // lexer/terminal rules start with an upper case letter
  ID
    :
      (
      'a'..'z'
      | 'A'..'Z'
      | '0'..'9' | ' '
      | ('+'|'-'|'*'|'/'|'_')
    | '='
    | '~'
    | '('
    | ')'
    | '{'
    | '}'
    | ','
    )+ 
    ;
  
  WS : [ \t]+ -&gt; skip ; 
  </code></pre>
  
  <p>I compiled the above <code>Expr.g4</code> with <code>-visitor</code> so that a visitor is generated.
  I then created a visitor class to walk through each expression and capture it in a list.</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Stack;
  
  import org.antlr.v4.runtime.tree.ParseTree;
  
  public class EvaluationVisitor extends ExprBaseVisitor&lt;Value&gt; {
  
    public List&lt;EvalExpression&gt; exprList = new ArrayList&lt;EvalExpression&gt;();
    public HashMap&lt;String, EvalExpression&gt; evalExprMap= new HashMap&lt;String, EvalExpression&gt;();
  
    public Value visitProg(ExprParser.ProgContext ctx) {
      return visitChildren(ctx);
    }
  
    public Value visitExpr(ExprParser.ExprContext ctx) {
      if (ctx.getChildCount() == 3) {
        String exprEval = ctx.getText();
        String leftExpr = ctx.getChild(0).getText();
        String token = ctx.getChild(1).getText();
        String rightExpr = ctx.getChild(2).getText();
        //System.out.println(" exprEval =" + exprEval);
        //System.out.println("&lt;" + leftExpr + "&gt; " + token + "  &lt;" + rightExpr + "&gt;");
        EvalExpression evalExprObj = new EvalExpression(exprEval, leftExpr, token, rightExpr);
        exprList.add(evalExprObj);
        evalExprMap.put(exprEval, evalExprObj);
      }
      return visitChildren(ctx);
    }
  
    public List&lt;EvalExpression&gt; getExprList() {
      return exprList;
    }
  
    public void setExprList(List&lt;EvalExpression&gt; exprList) {
      this.exprList = exprList;
    }
  
    public HashMap&lt;String, EvalExpression&gt; getEvalExprMap() {
      return evalExprMap;
    }
  
    public void setEvalExprMap(HashMap&lt;String, EvalExpression&gt; evalExprMap) {
      this.evalExprMap = evalExprMap;
    }
  
  }
  </code></pre>
  
  <p><code>EvalExpression</code> class is as follows</p>
  
  <pre><code>public class EvalExpression {
    private String expressionEvaluated;
    private String leftExpr;
    private String token;
    private String rightExpr;
  
  
    public EvalExpression(String expressionEvaluated, String leftExpr, String token,
        String rightExpr) {
      super();
      this.expressionEvaluated = expressionEvaluated;
      this.leftExpr = leftExpr;
      this.token = token;
      this.rightExpr = rightExpr;
    }
  
  
    public String getExpressionEvaluated() {
      return expressionEvaluated;
    }
  
  
    public void setExpressionEvaluated(String expressionEvaluated) {
      this.expressionEvaluated = expressionEvaluated;
    }
  
  
    public String getLeftExpr() {
      return leftExpr;
    }
  
  
    public void setLeftExpr(String leftExpr) {
      this.leftExpr = leftExpr;
    }
  
  
    public String getToken() {
      return token;
    }
  
  
    public void setToken(String token) {
      this.token = token;
    }
  </code></pre>
  
  <p><code>Value</code> is as follows</p>
  
  <pre><code>public class Value {
  
      public static Value VOID = new Value(new Object());
  
      final Object value;
  
      public Value(Object value) {
          this.value = value;
      }
  
      public Boolean asBoolean() {
          return (Boolean)value;
      }
  
      public Double asDouble() {
          return (Double)value;
      }
  
      public String asString() {
          return String.valueOf(value);
      }
  
      public boolean isDouble() {
          return value instanceof Double;
      }
  
      @Override
      public int hashCode() {
  
          if(value == null) {
              return 0;
          }
  
          return this.value.hashCode();
      }
  
      @Override
      public boolean equals(Object o) {
  
          if(value == o) {
              return true;
          }
  
          if(value == null || o == null || o.getClass() != value.getClass()) {
              return false;
          }
  
          Value that = (Value)o;
  
          return this.value.equals(that.value);
      }
  
      @Override
      public String toString() {
          System.out.println("---------Inside Value to String --------------");
          return String.valueOf(value);
      }
  }    
  </code></pre>
  
  <p>Now Finally I wrote a Test Program to print out the list of tokens and the order in which I need to look at them</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  import java.util.Stack;
  
  import org.antlr.v4.runtime.ANTLRInputStream;
  import org.antlr.v4.runtime.CharStream;
  import org.antlr.v4.runtime.CommonTokenStream;
  import org.antlr.v4.runtime.Token;
  import org.antlr.v4.runtime.TokenStream;
  import org.antlr.v4.runtime.tree.ParseTree;
  import org.antlr.v4.runtime.tree.ParseTreeWalker;
  import org.antlr.v4.runtime.tree.TerminalNode;
  
  import com.inmedius.antlr.ExprLexer;
  import com.inmedius.antlr.ExprParser;
  import com.inmedius.antlr.eval.EvalExpression;
  import com.inmedius.antlr.eval.EvaluationVisitor;
  import com.inmedius.antlr.eval.ExpressionTestVisitor;
  
  public class EvalExprTest {
  
    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
      // TODO Auto-generated method stub
      try {
        //String src = "(B1=p &amp; A4=p | A8=p) | (A6=p | ~A5=c)";
        String src = "(B32|B5)&amp;B31";
  
        CharStream stream = (CharStream) (new ANTLRInputStream(src));
        ExprLexer lexer = new ExprLexer(stream);
        TokenStream tokens = new CommonTokenStream(lexer);
  
        ExprParser parser = new ExprParser(new CommonTokenStream(lexer));
        ParseTree tree = parser.prog();
  
        if (!src.contains("&amp;") &amp;&amp; !src.contains("|")) {
          System.out.print("exp="  + src);
        } else {
          EvaluationVisitor visitor = new EvaluationVisitor();
          visitor.visit(tree);
  
          List&lt;EvalExpression&gt; exprOrderList = visitor.getExprList();
          HashMap&lt;String, EvalExpression&gt; evalMap = visitor.getEvalExprMap();
          for (EvalExpression eval : exprOrderList) {
            System.out.println(" Expr =" + eval.getRightExpr() + " "
                + eval.getToken());
            if (evalMap.get(eval.getLeftExpr()) == null) {
              System.out.println(" Expr =" + eval.getLeftExpr());
            }
          }
        }
  
      } catch (Exception e) {
        e.printStackTrace(System.out);
        throw e;
      }
  
    }
  
  }
  
  
  
        public String getRightExpr() {
          return rightExpr;
        }
  
  
        public void setRightExpr(String rightExpr) {
          this.rightExpr = rightExpr;
        }
  
  
      }
  </code></pre>
  
  <p>My question is when I run <code>EvalExprTest</code> and in the program I test it with <code>String src = "(B32|B5)&amp;B31"</code>. I get the following result. </p>
  
  <pre><code> Expr =B31 &amp;
   Expr =B5) |
   Expr =(B32
  </code></pre>
  
  <p>My goal was to get a precedence such that the expressions in the parenthesis would be evaluated first. But it always seems to walk through the tree from the right most expression and in this case it is <code>B31</code>.</p>
  
  <p>Can someone please help? Is grammar correct? The Visitor implementation is that correct?</p>