Re: OT: LALR(1)

[Hans Aberg]

At 16:26 +0200 2002/08/14, Magnus Ekhall wrote:
>Aslightly off topic short question:
>What is the abbreviation LALR(1) really short for?

This is explained in standard books on parsing and compiler construction,
such as Aho, Sethi & Ullman, "Compilers" (the "Dragon Book"), the Parsing
Techniques book http://www.cs.vu.nl/~dick/PTAPG.html, and Waite & Goos,
"Compiler Construction" (exact, but hard-to-read style too many).

The terminology is said to have been invented by Don Knuth (author of the
TeX program): In LR(n), the first letter, "L", stands for reading
direction, from Left to right, and the second letter, "R", stands for that
one obtains the Right-most parsing -- tokens are stacked and always reduced
at the right (also called bottom up parsing). Then n is the maximum of
lookahead tokens (but one may use less).

>From this terminology, one understands that Knuth had not yet realized that
there are languages where one does not read from left to right: When taking
that into account, "left" would more appropriately be "forward" and "right"
be "reverse".

As somebody else said, LALR(1) is short for "lookahead LR(1)", but I do not
know why it is named so. -- Perhaps because it is obtained from SLR(1)
("simple LR(1)") by taking some "right lookahead context" into account.

  Hans Aberg