[antlr-interest] semantic predicate hoisting :)

[Terence Parr]

Hooray!  I have an initial implementation of the combined LL(*) and 
semantic predicate hoisting mechanism.  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) ;)

Consider the following seemingly simply grammar:

a : A B
   | A C
   | b
   | c
   | ID
   | Z;

b : {p1}? ID ;
c : {p2}? ID ;

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).

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.

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.  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 :)

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

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

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

Ter
PS	 The LL(*) + hoisting algorithm and implementations are so clean and 
beautiful that I'm doing the happy dance in my office!


 
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/
 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dec-1.pdf
Type: application/pdf
Size: 16758 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20040604/d7a9729a/dec-1.pdf
-------------- next part --------------

--
CS Professor & Grad Director, University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com
Cofounder, http://www.knowspam.net enjoy email again!
Cofounder, http://www.peerscope.com pure link sharing