[Mono-list] parse generator
09 Feb 2003 13:18:24 -0500
> Out of interest, why do you prefer LR(k) parsers over LL(k) parsers?
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.
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.