[antlr-interest] Problem with ambiguous grammar

Gavin Lambert antlr at mirality.co.nz
Mon Aug 17 04:27:02 PDT 2009


At 20:47 17/08/2009, Thomas Woelfle wrote:
 >imperative_statement
 >  : imperative_compute_statement
 >  ;
 >
 >imperative_statement_list
 >  : imperative_statement+
 >  ;
 >
 >imperative_compute_statement
 >  : COMPUTE^ Identifier+ EQUAL Identifier END_COMPUTE?
 >  ;
 >
 >conditional_compute_statement
 >  : COMPUTE^ Identifier+ EQUAL Identifier
 >      (ON? SIZE ERROR imperative_statement_list)?
 >      END_COMPUTE?
 >  ;
[...]
 >ANTLR tells me that the rule 'imperative_compute_statement' has
 >more than one alternative to match the optional 'END_COMPUTE'.
 >Can anybody give me a hint on how to rewrite this grammar so
 >that the warning no longer appears?

The problem here, I think, is that a conditional_compute_statement 
that uses the SIZE ERROR clause contains an 
imperative_statement_list, which in turn contains an 
imperative_statement, then an imperative_computer_statement, which 
finally has an optional END_COMPUTE token.  And then back in 
conditional_compute_statement immediately following that, there's 
another optional END_COMPUTE token.  So ANTLR is warning that it's 
unclear whether an END_COMPUTE at that point in the input should 
be for the inner statement (the imperative_compute_statement in 
the SIZE ERROR block) or the outer statement (the 
conditional_compute_statement).

You can just ignore the warning, as ANTLR will (I think) default 
to matching it in the inner statement (similar to the "nested 
else" problem discussed on the wiki).

Another possibility is to introduce some kind of delimiters (eg. 
braces around the imperative_statement_list) so that it's obvious 
where one ends and the other resumes.  Of course, that would 
require changing the input language, which might not be an option.

There's probably also a way to resolve this through rule 
restructuring, but I'm not sure offhand what that would be.



More information about the antlr-interest mailing list