[Mono-list] parse generator

[Jonathan Pryor]

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

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.

 - Jon