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:

    In all history no class has been enfranchised without some selfish motive underlying. If to-day we could prove to Republicans or Democrats that every woman would vote for their party, we should be enfranchised.
    Carrie Chapman Catt (1859–1947)

    The greatest honor history can bestow is that of peacemaker.
    Richard M. Nixon (1913–1995)

    It takes a great deal of history to produce a little literature.
    Henry James (1843–1916)