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 the race, from infancy through its stages of barbarism, heathenism, civilization, and Christianity, is a process of suffering, as the lower principles of humanity are gradually subjected to the higher.”
—Catherine E. Beecher (18001878)
“A man will not need to study history to find out what is best for his own culture.”
—Henry David Thoreau (18171862)
“Anything in history or nature that can be described as changing steadily can be seen as heading toward catastrophe.”
—Susan Sontag (b. 1933)