[antlr-interest] Bug in C output (may after other targets as well)

Wincent Colaiuta win at wincent.com
Tue Jul 3 02:52:59 PDT 2007


I think I've just discovered a bug in the C output; nothing major,  
just some missing parentheses. A quick glance reveals that they are  
also missing from the Java output templates, which means they are  
probably missing from the others as well...

Given a rule like this:

   BLOCKQUOTE : { COLUMN == 0 || LAST_TOKEN == BLOCKQUOTE }?=> '>' '  
'? ;

ANTLR generates a prediction condition like this:

   if ( (( synpred13(ctx) &&  COLUMN == 0 || LAST_TOKEN ==  
BLOCKQUOTE  )) )

Here the purpose of synpred13() is to check if the blockquote rule  
would succeed at this point.

Due to C operator precedence, there is a chance that this prediction  
could incorrectly evaluate to true. To make it totally clear:

   if (synpred && A || B)

Can evaluate to true even if synpred is false; this will happen  
whenever B is true. This is because && has a higher precendence than  
|| in C. The above is really equivalent to:

   if ((synpred && A) || B)

But to match the clear intent of the rule in the grammar we would need:

   if (synpred && (A || B))

So it seems that the C output template needs additional brackets  
around semantic predicates to guarantee that whatever is in the  
predicate will be evaluated as a single logical unit, regardless of  
the precedence of whatever operators may be inside it.

As a workaround, I can rewrite my predicates as follows:

   FOO: { (A || B) }?=> 'bar' ;

As I said above, I'm not sure if the right place to fix this is in  
the C output template. I've looked in there and I can't really see  
where this construct is defined (don't really know enough about  
StringTemplate)... I can see the following:

   // D F A  E X P R E S S I O N S

   andPredicates(left,right) ::= "( <left> && <right> )"

   orPredicates(operands) ::= "(<first(operands)><rest(operands):{o |  
||<o>}>)"

   notPredicate(pred) ::= "!( <evalPredicate(...)> )"

   evalPredicate(pred,description) ::= "<pred>"

   evalSynPredicate(pred,description) ::= "<pred>(ctx)"

Perhaps the extra parentheses need to be added there?

   andPredicates(left,right) ::= "( (<left>) && (<right>) )"

I tried making this change to a copy of C.stg and sticking that at  
the front of my CLASSPATH but it isn't picked up by ANTLR... (I know  
Ter has said this is possible... why wouldn't it work?)... In any  
case, I rebuilt ANTLR with the above change and it does indeed insert  
parentheses where they are needed:

   if ( (( (synpred13(ctx)) && ( COLUMN == 0 || LAST_TOKEN ==  
BLOCKQUOTE ) )) )

The Java templates also seem to be missing the parentheses:

   andPredicates(left,right) ::= "(<left>&&<right>)"

Seems like it would be a good idea to add parentheses there as well  
seeing as ANTLR can't make any assumptions about what will be in the  
predicates and what the precedence might be. I don't know enough  
StringTemplate syntax to understand the all the other snippets... the  
"orPredicates" one might need parentheses as well.

Cheers,
Wincent




More information about the antlr-interest mailing list