[antlr-interest] uh oh...trouble in meaning of (..)=> pred!!!

Terence Parr parrt at cs.usfca.edu
Wed Mar 14 16:56:04 PDT 2007


Hi Loring, good thoughts.

Well, I tweaked things so that (...)=> forces itself into a gated sem  
pred whereas it used to be just a sem pred.  Backtracking mode uses  
plain sempred and so it doesn't order until the alts are ambig.  With  
the gated version of (...)=>, it always forces eval.

So, this grammar forces 'aa' to test pred for alt1 before choosing alt1:

z : (a d) => a
   | (b d) => b
   | ('a'|'b')+
   ;
a       :       'a' 'a' ;
b       :       'a' 'a' 'b' ;
d       :       '0'|'1' ;

Upon 'aab', it forces pred2, but does NOT test synpred for alt1 as  
the 'aab' makes alt 1 impossible to match.  Cool, eh?

So, the diff is from about an hour ago, is that this grammar always  
tests the pred for alt1.

y : ('a')=> 'a'
   | 'b'
   ;

it is still efficient.  Upon 'b', it does not test it!  Hooray for  
me. Whew.  was panicking for a second there!

I'll think this over and commit tomorrow.

Ter

On Mar 14, 2007, at 4:27 PM, Loring Craymer wrote:

> Ter--
>
> As a first step, predicates should not specify more
> tokens that the alternative being selected.  That
> would rule out the example grammar.
>
> As to the ordering problem:  the original expectation
> was that LL* "did not need no stinking syntactic
> predicates" and that automatic and silent elimination
> was a good thing since synpreds were a no-op.  Given
> that synpreds are sometimes needed in v3, I think that
> it makes more sense to always generate code for them
> but to issue an "extraneous synpred" warning so that
> the grammar developer can remove them.  [You could
> also add some machinery (a flag in the predicate
> object or some such) to turn off warnings for
> automatically generated synpreds (backtracking =
> true).]
>
> --Loring
>
> --- Terence Parr <parrt at cs.usfca.edu> wrote:
>
>> Hi.  Harmut submitted a bug report, which I have
>> converted to a parser:
>>
>> grammar T;
>>
>> x : (a d) => a
>>    | (b d) => b
>>    | ('a'|'b')+
>>    ;
>>
>> a       :       'a' 'a' ;
>> b       :       'a' 'a' 'b' ;
>> digit   :       '0'|'1' ;
>>
>> Basically, in the book and in my intentions,
>> predicates order the
>> alts.  The problem is that ANTLR's analysis doesn't
>> consider
>> syntactic predicates if it can figure out what to do
>> w/o them.
>> That's an optimization.  The problem is that you are
>> often specifying
>> the lookahead in the predicate that must be
>> evaluated.  Crap.  ANTLR
>> is not forcing those predicates in there.
>>
>> For semantic predicates, we have {...}? and {...}?=>
>> where the latter
>> forces backtracking.  Perhaps (...)=> should always
>> force
>> backtracking.  BUT, for backtracking=true, I add a
>> predicate to every
>> alt!  I guess for that backtracking mode, those
>> predicates should be
>> analogous to {...}? and manually specified (...)=>
>> should operate
>> like {..}?
>>
>> I have exactly 4 days to resolve this issue before
>> the book goes to
>> copy editing.  Anybody wanna help me think about
>> this?
>>
>> Ter
>>
>
>
>
>
> ______________________________________________________________________ 
> ______________
> Now that's room service!  Choose from over 150,000 hotels
> in 45,000 destinations on Yahoo! Travel to find your fit.
> http://farechase.yahoo.com/promo-generic-14795097



More information about the antlr-interest mailing list