File LR.html    Author McKeeman    Copyright © 2007    index

A Little Bottom-up History

For about 10 years after high level programming languages came into common use, various methods for automatic parsing were proposed. In 1957, the Fortran compiler inserted extra parentheses to implement arithmetic precedence. In 1963, Floyd expressed Algol 60 as an operator precedence grammar. In 1966, Wirth followed with simple precedence. Knuth's LR parsers proved to be the definitive solution. Knuth's paper was published in 1965 but did not actually appear until late 1966 because a journal snafu.

After LR appeared, the topical question changed from "how to" to matters of efficiency. The computers available to researchers in 1965 had microsecond cycle times and 32K words of memory. LR parsers powerful enough for useful languages just did not fit, either in time or space. In 1969, Frank DeRemer's MIT PhD thesis presented an approximation to LR(1), called LALR(1). Eventually Steve Johnson's yacc, based on LALR(1), highly tuned for use in small memories, and freely available on Unix, became the dominant solution for building LR parsers.

Jacques Cohen wrote an interesting personal history, including his interest in these techniques.

In the meantime, the computer manufacturers have given us gigabytes of memory and nanosecond cycle times. For many languages, Knuth's original LR(1) algorithm, with no bells and whistles, now works just fine. It is simpler to understand and implement than its successors. So xcom uses LR(1) and recursive descent interchangeably. A production compiler would more likely use yacc.