[antlr-interest] LL(*) and PackRat

[Terence Parr]

On Nov 16, 2004, at 2:52 PM, Jason Aaron Osgood wrote:
> Hi Terence Parr-

Hi Jason :)

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

Thanks for keeping track.  Long time no see :)

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

Yeah, Bryan is one smart dude.  His packrat thing is cool.  His PEG 
(parser expr. grammars) have a nice new variant of a syn pred too.

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

Sriram Srinivasan compared the two for me in terms of speed.  Naturally 
memoizing is pretty slow, but boy is it powerful.  I'm pretty sure it's 
full context-free; you can get the ambiguous derivations too.  That is 
from memory.  A quick check of the paper would correct me I'm sure.

Anyway, LL(*) is essentially an automatic backtracking mechanism 
similar in principle to all of the recent increases in parsing power 
from the other camps.  We are starting to trade some speed for power 
now that machines kick butt! ;)  LL(*) degenerates to LL(k) for a fixed 
k if your grammar is LL(k).  If it is not LL(k), it searches further 
ahead to find tokens that will help it make choices.  I'm 99% sure it 
will be able to do some grammars LR(k) cannot, but LR will still be 
able to handle grammars LL(*) cannot such as left recursive grammars.  
So no strict ordering.  Anyhoo, you can look at the slides of my 
ANTLR2004 talk for more.

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

Yeah, this should make building grammars MUCH easier for everybody.

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

Yeah, it can be an order of magnitude slower according to Sriram, 
though still it's impressive as hell.

> 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#".

Yes, I've AGONIZED over this.  LL(*) is super cool, but the * means 
something in most search engines.  I note that C# returns 9 million 
results so it's probably ok, but LL(*) is less "findable".  LL(*) 
brings up LL Bean catalog.  "LL(*) parsing" brings up LL(k) etc... as 
you'd expect. :(  LL(\*) does not fix it.  I've been leaving variants 
of LL(*) on the web such as LL(star) and LL-star.  Google finds 
LL(star) actually.  4th item is my LL(*) lecture.  "LL(star) parsing" 
puts it first.  Putting actual quotes around "LL(star) parsing" gets 
you 2 pages, both are mine.  I note it does not find my "blog" entries 
on LL(*) parsing however.

Hmm...I'm leaning towards LL(star), but boy it's tough to get a unique 
symbol given the LL term.  I deliberately left off the E in "antler" to 
make ANTLR for uniqueness.  Foresight, eh?  That was back in the late 
80's ;)

Anybody have another name or "spelling"?  I'd like LL in there, but 
that's the problem term!  By the way, people thought of the basic idea 
back in the 70's calling it LL-regular, but that is actually totally 
different.  When I search for LL-regular it actually picks up my blog 
entry.  Damn!

Ter
--
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!





 
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/