[Mono-list] parse generator

Kunle Odutola kunle.odutola@virgin.net
Sun, 9 Feb 2003 21:09:21 -0000


> <snip/>
> > Out of interest, why do you prefer LR(k) parsers over LL(k) parsers?
> >
> > Kunle
>
> Yay!  A question I can use my compiler class for!
>
> To quote from the "Dragon" book ("Compilers: Principals, Techniques, and
> Tools" by Aho, Sethi, Ullman, 1988), page 221:
>
> 	There is a significant difference between LL and LR grammars.
> 	For a grammar to be LR(k), we must be able to recognize the
> 	occurrence of the right side of a production, having seen all of
> 	what is derived from that right side with k input symbols of
> 	lookahead.  This requirement is far less stringent than that for
> 	LL(k) grammars where we must be able to recognize the use of a
> 	production seeing only the first k symbols of what its right
> 	side derives.  Thus, LR grammars can describe more languages
> 	than LL grammars.

I understand the Dragon books point about LR grammars vs LL grammars. I made
a reference to it in an earlier message.

> To put it another way, an LR parser works by following the *reverse* of
> a right-recursive derivation.  This allows each input token to be a
> handle that can be used as part of the shift/reduce parsing process.
>
> An LL parser, on the other hand, effectively needs to read in the entire
> file before it can start applying any reductions to avoid ambiguities,
> leading to increased memory requirements and slower parsing.

Your conclusion about LL parsing efficiency is inaccurate IMHO. LL parsing
isn't inefficient compared to LR parsing (both can be implemented as
tablelookups or procedurally) unless the language in question requires
copious amounts of lookahead/backtracking. Most languages don't. C++
doesn't. C# doesn't.

The only references to comparative LR / LL performance that I have are old
(but still somewhat useful):

http://compilers.iecc.com/comparch/article/90-11-064
http://compilers.iecc.com/comparch/article/90-11-060
http://compilers.iecc.com/comparch/article/90-11-057 (PCCTS is ANTLR's
predecessor)

Many (most?) of the well-known commmercial compilers use hand-coded
recursive descent (RD) parsers. The ease of development, flexibility (esp in
error handling) and performance of RD parsers based on LL(k) grammars is an
oft-cited reason. All the same benefit that ANTLR provides.

Cheers,

Kunle

ANTLR C# codegen
www.antlr.org