[antlr-interest] semantic predicate hoisting :)

[John D. Mitchell]

>>>>> "Terence" == Terence Parr <parrt at cs.usfca.edu> writes:
[...]

> Hooray!  I have an initial implementation of the combined LL(*) and
> semantic predicate hoisting mechanism.

YEA!!!

Do you happen to have a proof of correctness for this hoisting yet?

> The requirements are fairly nasty to handle difficult situations
> naturally, but I think my implementation covers them all nicely as
> opposed to the ad hoc hacking I did for PCCTS (uh...and ANTLR <3.0) ;)

How does it handle:

	* deeply nested semantic predicates?

	* recursive rules (which contain semantic predicates)?

[...]

> In rule a, you need to modulate the lookahead according to the
> alternatives and you also need to hoist predicates from two other rules
> and also realize that they conflict with an alt (ID) from rule a.
> Because the naked ID alt does not have a predicate, one needs to make one
> as !(other predicates).

Cool.

> A cool thing to notice that the DFA tests the lookahead before evaluating
> predicates.  That is a crucial rule: only eval predicates when syntactic
> context is consistent with the predicates original location.

Score!

> I have enclosed a small 16k PDF file showing the DFA ANTLR 3.0 core
> created to predicate the various alternatives of rule a.  Note that the
> DFA edges may be tokens (or characters) or predicates unlike a normal
> DFA.

How does this interact with syntactic predicates?


> Please notice that when the input is Z, only one symbol is examined and
> that only two symbols are used to resolve alts 1 and 2.  Something to
> remark on: no k maximum or other constant was specified anywhere!  The
> LL(*) algorithm just does the minimum necessary :)

I love this dynamism.

> Prediction is no longer a series of tests, but rather the exact alt to
> predict is discovered with one shot.

Please elaborate.  You're still, in essence, traversing the (LL*) DFA but
in an exact fashion rather than via approximations, right?


> Oh, the i=>alt notation means "DFA state i predicts alternative alt". :)

You might want to qualify the alt with the rule name to make that clear.

> Wooohoooo!  NOW, can I go home, John? (Mitchell's been bugging me for 9
> years to get hoisting back) <snicker>

Not until you clean your plate, mister!  :-)

Rock on,
	John


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
     http://docs.yahoo.com/info/terms/