[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