History
In 1965 Donald Knuth invented the LR(k) parser (Left to right, Rightmost derivation parser) a type of shift-reduce parser, as a generalization of existing precendence parsers. This parser has the potential of recognizing all deterministic context-free languages and can produce both left and right derivations of grammar rules. Knuth proved that it reaches its maximum language recognition power for k=1 and provided a method for transforming LR(k), k > 1 grammars into a LR(1) grammar.
Unfortunately, the LR(1) parser has the practical disadvantage of having enormous memory requirements for its internal grammar representation. The first attempt to solve this problem were the memory optimizations introduced in 1977 by D. Pager but still the LR parser required significantly more memory than other parsing methods. Earlier, in 1969, Frank DeRemer had suggested two simplified version of the LR Parser called LALR and SLR which greatly reduced memory requirements at the cost of less language recognition power. These two parsers (especially LALR) have since been and still are by far the most common implementations of the LR Parser.
Read more about this topic: Canonical LR Parser
Famous quotes containing the word history:
“The history of American politics is littered with bodies of people who took so pure a position that they had no clout at all.”
—Ben C. Bradlee (b. 1921)
“We may pretend that we’re basically moral people who make mistakes, but the whole of history proves otherwise.”
—Terry Hands (b. 1941)
“Let it suffice that in the light of these two facts, namely, that the mind is One, and that nature is its correlative, history is to be read and written.”
—Ralph Waldo Emerson (1803–1882)