[antlr-interest] Predicate hoisting/lowering confusion

Wincent Colaiuta win at wincent.com
Mon Jun 18 08:29:40 PDT 2007


I have a gated semantic predicate in a grammar which isn't behaving  
as expected.

Here is a reduced example grammar in which the hoisting/lowering  
behaviour has me totally baffled. I have a gated semantic predicate  
in one of the rules. Looking at the generated parser code I can see  
how it gets "hoisted" up into the DFA of a calling rule. The thing  
which puzzles me is that it is also being "lowered" down into a rule  
further down the chain, and most confusingly of all, the sense of the  
predicate is inverted in the lower rule:

   grammar Simple;

   FOO : 'foo' ;

   section : element* EOF ;
   element : {true}?=> pre ;
   pre : FOO+ ;

It can be seen that the gated semantic predicate ("true") is  
"hoisted" up into the DFA for the "section" rule:

   if ( (LA1_0==FOO) && (true)) {
       alt1=1;
   }

You can also see it in the "element" rule itself:

   if ( !(true) ) {
       throw new FailedPredicateException(input, "element", "true");
   }

But the thing which totally baffles me is that you see it in the  
"pre" rule too:

   if ( (LA2_0==FOO) ) {
       int LA2_2 = input.LA(2);
       if ( (!(true)) ) {
           alt2=1;
       }
   }

My confusion stems from two things: firstly, I don't understand why  
the predicate is being "lowered" into the "pre" rule; and secondly, I  
don't understand why the sense of the predicate is inverted ("!true"  
instead of "true"); as a result of this latter change the pre rule  
can never match for any input and will always throw an  
EarlyExitException.

Can someone help me to understand this? The behaviour and generated  
code is the same where rule "element" is more complex (multiple  
alternatives); I've just posted the single-alternative case because  
it is simpler.

Cheers,
Wincent



More information about the antlr-interest mailing list