[antlr-interest] LL(*) and PackRat

Jason Aaron Osgood mrosgood at yahoo.com
Tue Nov 16 14:52:39 PST 2004



Hi Terence Parr-


It's exciting to see ANTLR still on the move.

I just read your ANTLR 2004 slides for LL(*) parsing.  I'm still
nursing the dream of learning enough about parsing to adapt the
interactive parsing algorithms from Harmonia (Tim Wagner et al) to
ANTLR.  (Phil Cook et al from UQ has some followup work.)

While digging around, I learned about Bryan Ford's Packrat Parsing
algorithm.  (There's a part to Java called Rats!  Very droll.)

Is there a comparison of LL(*) and Packrat parsing?  

I like how both are trying to simplify the development of grammars.  I
have a small head and really struggled to get some of my language
ideas working with ANTLR.  I ended up modifying my language to make
the implementation easier.  Not necessarily bad.  I just was trying to
solve a problem.

Since Packrat memoizes all the tokens, the heap usage can get pretty
big.  I have the impression that LL(*) won't have that characteristic.


One other thing: Googing for "LL(*)" will be somewhat problematic. 
Perhaps a synonym is in order?  No one should repeat Microsoft's
mistake with "C#".


Cheers, Jason Aaron Osgood / Seattle WA





 
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/
 





More information about the antlr-interest mailing list