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:
“It’s not the sentiments of men which make history but their actions.”
—Norman Mailer (b. 1923)
“What you don’t understand is that it is possible to be an atheist, it is possible not to know if God exists or why He should, and yet to believe that man does not live in a state of nature but in history, and that history as we know it now began with Christ, it was founded by Him on the Gospels.”
—Boris Pasternak (1890–1960)
“I am ashamed to see what a shallow village tale our so-called History is. How many times must we say Rome, and Paris, and Constantinople! What does Rome know of rat and lizard? What are Olympiads and Consulates to these neighboring systems of being? Nay, what food or experience or succor have they for the Esquimaux seal-hunter, or the Kanaka in his canoe, for the fisherman, the stevedore, the porter?”
—Ralph Waldo Emerson (1803–1882)