ANTLR assignment expression disambiguation

Question

The following grammar works, but also gives a warning:

test.g

grammar test;

options {
  language = Java;
  output = AST;
  ASTLabelType = CommonTree; 
}

program
  : expr ';'!
  ;

term: ID | INT
  ;

assign
  : term ('='^ expr)?
  ;

add : assign (('+' | '-')^ assign)*
  ;

expr: add
  ;

//   T O K E N S

ID  : (LETTER | '_') (LETTER | DIGIT | '_')* ;

INT : DIGIT+ ;

WS  :
    ( ' '
    | '\t'
    | '\r'
    | '\n'
    ) {$channel=HIDDEN;}
    ;

DOT : '.' ;

fragment
LETTER : ('a'..'z'|'A'..'Z') ;

fragment
DIGIT   : '0'..'9' ;

Warning

[15:08:20] warning(200): C:\Users\Charles\Desktop\test.g:21:34: 
Decision can match input such as "'+'..'-'" using multiple alternatives: 1, 2

As a result, alternative(s) 2 were disabled for that input

Again, it does produce a tree the way I want:

Input: 0 + a = 1 + b = 2 + 3;

ANTLR produces  | ... but I think it
this tree:      | gives the warning
                | because it _could_
  +             | also be parsed this
 / \            | way:
0   =           |  
   / \          |           +     
  a   +         |         /   \   
     / \        |        +     3  
    1   =       |     /     \     
       / \      |    +       =    
      b   +     |   / \     / \   
         / \    |  0   =   b   2  
        2   3   |     / \         
                |    a   1        

How can I explicitly tell ANTLR that I want it to create the AST on the left, thus making my intent clear and silencing the warning?

Answer 1

Charles wrote:

How can I explicitly tell ANTLR that I want it to create the AST on the left, thus making my intent clear and silencing the warning?

You shouldn't create two separate rules for assign and add. As your rules are now, assign has precedence over add, which you don't want: they should have equal precedence by looking at your desired AST. So, you need to wrap all operators +, - and = in one rule:

program
  :  expr ';'!
  ;

expr
  :  term (('+' | '-' | '=')^ expr)*
  ;

But now the grammar is still ambiguous. You'll need to "help" the parser to look beyond this ambiguity to assure there really is operator expr ahead when parsing (('+' | '-' | '=') expr)*. This can be done using a syntactic predicate, which looks like this:

(look_ahead_rule(s)_in_here)=> rule(s)_to_actually_parse

(the ( ... )=> is the predicate syntax)

A little demo:

grammar test;

options {
  output=AST;
  ASTLabelType=CommonTree; 
}

program
  :  expr ';'!
  ;

expr
  :  term ((op expr)=> op^ expr)*
  ;

op
  :  '+' 
  |  '-'
  |  '='
  ;

term
  :  ID 
  |  INT
  ;

ID  : (LETTER | '_') (LETTER | DIGIT | '_')* ;
INT : DIGIT+ ;
WS  : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;};

fragment LETTER : ('a'..'z'|'A'..'Z');
fragment DIGIT  : '0'..'9';

which can be tested with the class:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    String source =  "0 + a = 1 + b = 2 + 3;";
    testLexer lexer = new testLexer(new ANTLRStringStream(source));
    testParser parser = new testParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.program().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

And the output of the Main class corresponds to the following AST:

which is created without any warnings from ANTLR.