ANTLR chaining 1 to 1 grammar rules together to solve conditionals

antlr4, conditional-statements

Solution

As already mentioned, the "chain" is needed to properly handle operator precedence. Without it, input like `1+2*3` would be parsed as:

     *
    / \
   +   3
  / \
 1   2

instead of:

  +
 / \
1   *
   / \
  2   3

Since ANTLR 4 supports direct left recursive rules:

foo
 : foo '?' foo
 | TOKEN
 ;

so not indirect left recursive rules:

foo
 : bar
 | TOKEN
 ;

bar
 : foo '?' foo
 ;

You can rewrite these rules as follows:

expression
 : '-' expression
 | '(' type_name ')' expression
 | expression ('*' | '/' | '%') expression
 | expression ('+' | '-') expression
 | expression ('<<' | '>>') expression
 | expression ('<' | '>' | '<=' | '>=') expression
 | expression ('!=' | '==') expression
 | expression '&' expression
 | expression '^' expression
 | expression '|' expression
 | expression '&&' expression
 | expression '||' expression
 | expression '?' expression ':' expression
 | IDENTIFIER
 | NUMBER
 ;

If the parser now stumbles upon an `expression`, it will first look for `('*' | '/' | '%')`, and if that's not there, it will look for `('+' | '-')`, etc. In other words, the alternatives placed first in the rule will get precedence over alternatives placed lower in the rule.

Now I know from your earlier question, Once grammar is complete, what's the best way to walk an ANTLR v4 tree?, that you're using a listener to "walk" the tree. If you create an `expression` rule as I just showed, you'd need to do a lot of manual inspections in your `enterExpression(...)` and `exitExpression(...)` methods to find out which of the alternatives matched an `expression`. This is where "labels" come in handy. You simply label each alternative in your `expression` rule:

expression
 : '-' expression                                  #unaryExpr
 | '(' type_name ')' expression                    #castExpr
 | expression ('*' | '/' | '%') expression         #multExpr
 | expression ('+' | '-') expression               #addExpr
 | expression ('<<' | '>>') expression             #...
 | expression ('<' | '>' | '<=' | '>=') expression 
 | expression ('!=' | '==') expression
 | expression '&' expression
 | expression '^' expression
 | expression '|' expression
 | expression '&&' expression
 | expression '||' expression
 | expression '?' expression ':' expression
 | IDENTIFIER
 | NUMBER
 ;

(note that when you label one, you must label them all!)

And then the base listener class will have `enter`- and `exit` method for all alternatives:

public void enterUnaryExpr(...)
public void exitUnaryExpr(...)

public void enterCastExpr(...)
public void exitCastExpr(...)

public void enterMultExpr(...)
public void exitMultExpr(...)

...

Problem

Original source