[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