LALR Parser - History

History

in 1965, Donald Knuth invented the LR parser (Left to Right, Rightmost derivation). The LR parser can recognize any deterministic context-free language in linear-bounded time. However, rightmost derivation has very large memory requirements and implementing an LR parser was impractical due to the limited memory of computers at that time. To address this shortcoming, in 1969, Frank DeRemer proposed two simplified versions of the LR parser, namely the Look-Ahead LR (LALR) and the Simple LR parser that had much lower memory requirements at the cost of less language recognition power with the LALR parser being the most powerful alternative. Later, in 1977, memory optimizations for the LR parser were invented but still the LR parser was less memory efficient than the simplified alternatives.

In 1979, Frank DeRemer and Tom Pennello announced a series of optimizations for the LALR parser that would further improve its memory efficiency. The formal presentation of these optimizations was made in 1982.

Read more about this topic:  LALR Parser

Famous quotes containing the word history:

    When the landscape buckles and jerks around, when a dust column of debris rises from the collapse of a block of buildings on bodies that could have been your own, when the staves of history fall awry and the barrel of time bursts apart, some turn to prayer, some to poetry: words in the memory, a stained book carried close to the body, the notebook scribbled by hand—a center of gravity.
    Adrienne Rich (b. 1929)

    Revolutions are the periods of history when individuals count most.
    Norman Mailer (b. 1923)

    The history of every country begins in the heart of a man or a woman.
    Willa Cather (1876–1947)