[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