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:
“American time has stretched around the world. It has become the dominant tempo of modern history, especially of the history of Europe.”
—Harold Rosenberg (1906–1978)
“When the history of guilt is written, parents who refuse their children money will be right up there in the Top Ten.”
—Erma Brombeck (20th century)
“To history therefore I must refer for answer, in which it would be an unhappy passage indeed, which should shew by what fatal indulgence of subordinate views and passions, a contest for an atom had defeated well founded prospects of giving liberty to half the globe.”
—Thomas Jefferson (1743–1826)