[antlr-interest] the nihilistic circle hoist

Terence Parr parrt at cs.usfca.edu
Tue Jan 4 11:07:12 PST 2011


On Jan 3, 2011, at 11:15 AM, Ron Burk wrote:

> After more tinkering, it appears there are two
> separate bugs. First, the code generated for
> predicate hoisting may simply be wrong when
> the "+" EBNF operator is used. The second
> is the more systemic problem that hoisted
> predicates can be executed in the wrong syntactic
> context.

That's not a bug but a limitation of Java and most other targets; I think the book has a good description. and let's look at the grammar then:

> The first bug can be seen in Wincent's original
> report:
> 
> grammar Simple;
> 
> FOO : 'foo' ;
> 
> section : element* EOF ;
> element : {P1}?=> pre ;
> pre : FOO+ ;

The DFA to predict entry or exit of element* is

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PastedGraphic-1.tiff
Type: image/tiff
Size: 10022 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20110104/8c53590f/attachment.tiff 
-------------- next part --------------


That seems correct to me.

> 
> The code generated for the previous grammar can
> consume no FOOs. But after changing FOO+ to FOO FOO*:
> 
> grammar hoist1;
> 
> FOO : 'foo' ;
> 
> section : element* EOF ;
> element : {P1}?=> pre ;
> pre : FOO FOO* ;

For this, element* gets the exact same prediction DFA.

> This grammar, though it should produce identical
> behavior to the previous one, does not. It correctly
> consumes one FOO for every 'pre'.

I get these results with 3.3.  Hmm... it looks like the decision for FOO FOO* and FOO+ also gets the same thing. which version are you using?

Ter

> It does, however,
> still suffer from the second bug, since 'pre' contains
> a predicate that will "taint" any unrelated nonterminal
> that uses it. E.g.:
> 
> ...
> unrelated : '(' pre ')' ;
> 
> This latter rule cannot match ( FOO FOO ) because
> 'pre' is executing predicate P1 in a completely unrelated
> syntactic context. (assume P1 = true).
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address



More information about the antlr-interest mailing list