[antlr-interest] Problem with ambiguous grammar

[Thomas Woelfle]

Hi Gavin,

the problem is as you described it. Unfortunately I cannot change the 
input language. I think it is the same class of problem as the known "if 
then if then else" problem. But in this case I think I cannot use 
syntactic predicates to get rid of that warning as described in the 
ANTLR book, can't I?

You are right. ANTLR will do the correct thing by consuming the 
END_COMPUTE token early. All I wanted to have is to get rid of the 
warnings without enabling backtracking.

Thanks for your help,
Thomas
> 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.
>


-- 
Interactive Objects Software GmbH
Basler Strasse 61
79100 Freiburg, Germany

Phone:  +49 761 400 73 0
mailto:thomas.woelfle at interactive-objects.com


------------------------------------------------------------------------

Interactive Objects' Legacy Modernization Solutions 

Get Your Applications SOA-Ready!

See http://www.interactive-objects.com/ for more information.

------------------------------------------------------------------------


Interactive Objects Software GmbH | Freiburg | Geschäftsführer: Alberto Perandones, Andrea Hemprich
| AG Frbg. HRB 5810 | USt-ID: DE 197983057