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)
“There is a constant in the average American imagination and taste, for which the past must be preserved and celebrated in full-scale authentic copy; a philosophy of immortality as duplication. It dominates the relation with the self, with the past, not infrequently with the present, always with History and, even, with the European tradition.”
—Umberto Eco (b. 1932)
“A man will not need to study history to find out what is best for his own culture.”
—Henry David Thoreau (1817–1862)