[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