[antlr-interest] Expression grammars and *non*-ambiguities
Andrew Gacek
andrew.gacek at gmail.com
Mon Aug 6 06:29:45 PDT 2012
Suppose I am trying to parse an expression language with
multiplication, addition, and if-then-else where multiplication has
the highest precedence and if-then-else has the lowest. For example,
a + b * c is parsed as a + (b * c)
if a then b else c * d is parsed as if a then b else (c * d)
a * if b then c else d is parsed as a * (if a then b else c)
Note that in the last example, there is no ambiguity and thus no need
for precedence. I started with a grammar like the following:
expr: conditional;
conditional
: term
| 'if' expr 'then' expr 'else' expr
;
term: factor ('+' factor)*;
factor: atom ('*' atom)*;
atom
: INT
| '(' expr ')'
;
INT: ('0'..'9')+;
The problem with this grammar is that it rejects "a * if b then c else
d" since to the right of a multiplication must be an atom.
Alternatively, I've tried the following grammar which moves
if-then-else down to the atom level:
expr: term;
term: factor ('+' factor)*;
factor: atom ('*' atom)*;
atom
: INT
| '(' expr ')'
| 'if' expr 'then' expr 'else' expr
;
INT: ('0'..'9')+;
This grammar is rejected by ANTLR for ambiguities in the term and
factor rules. Is there an accepted way for encoding the parsing rules
for this kind of language? At it's core, the problem seems to be that
there is a *non*-ambiguity in "a * if b then c else d".
Thanks,
Andrew
More information about the antlr-interest
mailing list