[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