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:
“Postmodernism is, almost by definition, a transitional cusp of social, cultural, economic and ideological history when modernism’s high-minded principles and preoccupations have ceased to function, but before they have been replaced with a totally new system of values. It represents a moment of suspension before the batteries are recharged for the new millennium, an acknowledgment that preceding the future is a strange and hybrid interregnum that might be called the last gasp of the past.”
—Gilbert Adair, British author, critic. Sunday Times: Books (London, April 21, 1991)
“When the coherence of the parts of a stone, or even that composition of parts which renders it extended; when these familiar objects, I say, are so inexplicable, and contain circumstances so repugnant and contradictory; with what assurance can we decide concerning the origin of worlds, or trace their history from eternity to eternity?”
—David Hume (1711–1776)
“History is not what you thought. It is what you can remember. All other history defeats itself.
In Beverly Hills ... they don’t throw their garbage away. They make it into television shows.
Idealism is the despot of thought, just as politics is the despot of will.”
—Mikhail Bakunin (1814–1876)