CODEWITHSUNDEEP
javaparsingantlrcontext-free-grammar
Ryan
Ryan

Reputation: 2051

How to handle left associative grammar in ANTLR

I am using antlr to generate parser that produces abstract syntax tree. I got some problem about left associative operators. My grammar is like the following:

add_expr returns [ASTNode value]
    :a=mul_expr {$value = a;}
    (
        o = ('+' | '-') b = add_expr
        {
        $value = new AddNode(a, b, $o.text);
        }
    )?
    ;
mul_expr returns [ASTNode value]
    :a=term {$value = a;}
    (
        o = ('*' | '/') b = mul_expr
        {
        $value = new MultiplyNode(a, b, $o.text);
        }
    )?
    ;

The constructor of AddNode and MultiplyNode is like:

AddNote(ASTNode left, ASTNode right, String operatorr)

The problem is, for input a-b-c, it is parsed to something like a-(b-c), rather than (a-b)-c. Antlr does not accept left recursive grammar. How to modify the grammar to make the left associative syntax work in expression like a-b-c?

Upvotes: 1

Views: 1593

Answers (1)

Alexei Kaigorodov
Alexei Kaigorodov

Reputation: 13535

Parse a-b-c not as a-(b-c) and not as (a-b)-c but as a (-b) (-c), that is, 

additiveExpression 
:   multiplicativeExpression
    (   
        (   '+'
        |   '-'
        )
        multiplicativeExpression
     )*
;

The above rule is taken from Java grammar. Save the text and read with an editor, as browser may ignore line ends in it.

Upvotes: 1

Related Questions