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:
“A poet’s object is not to tell what actually happened but what could or would happen either probably or inevitably.... For this reason poetry is something more scientific and serious than history, because poetry tends to give general truths while history gives particular facts.”
—Aristotle (384–323 B.C.)
“In the history of the human mind, these glowing and ruddy fables precede the noonday thoughts of men, as Aurora the sun’s rays. The matutine intellect of the poet, keeping in advance of the glare of philosophy, always dwells in this auroral atmosphere.”
—Henry David Thoreau (1817–1862)
“Most events recorded in history are more remarkable than important, like eclipses of the sun and moon, by which all are attracted, but whose effects no one takes the trouble to calculate.”
—Henry David Thoreau (1817–1862)