[antlr-interest] Problem with ambiguous grammar

[Jim Idle]

Thomas Woelfle wrote:
> Hi,
>
> I have a problem with following grammar:
>
> 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?
>   
Your problem is that these are basically two forms of the exact same 
thing. A common mistake is to take a language spec, where such things 
are distinguished and then try to distinguish these in ANTLR rules. You 
want to merge them and as you are making do distinction between the two 
forms, all you need do is:

imperative_statement
  : imperative_compute_statement
  ;
 
imperative_statement_list
  : compute_statement+
  ;

compute_statement
  : COMPUTE^ Identifier+ EQUAL Identifier
      (ON? SIZE ERROR compute_statement+)?
      END_COMPUTE?
  ;


Now, the compute statements that are part of a conditional computer are 
not allowed to have further conditions, so you want to either reject 
this with a semantic error at parse time, or at tree walking/semantic 
checking time. An error given in this form will make much more sense to 
your users:

imperative_statement
  : imperative_compute_statement
  ;
 
imperative_statement_list
  : compute_statement[true]+
  ;

compute_statement [ boolean conditionOK ]
  : COMPUTE^ Identifier+ EQUAL Identifier
      (ON? SIZE ERROR compute_statement[false]+ {if (!conditionOK) { /* semntic error here */ }  )?
      END_COMPUTE?
  ;

Now you will get:

Error: a conditional computer statement cannot itself contain 
conditional compute statements. (Or something better worded ;-)

Instead of:

Syntax error at 'SIZE' expected one of END_COMPUTE, COMPUTE, EOF



Jim