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:
“All things are moral. That soul, which within us is a sentiment, outside of us is a law. We feel its inspiration; out there in history we can see its fatal strength.”
—Ralph Waldo Emerson (1803–1882)
“We are told that men protect us; that they are generous, even chivalric in their protection. Gentlemen, if your protectors were women, and they took all your property and your children, and paid you half as much for your work, though as well or better done than your own, would you think much of the chivalry which permitted you to sit in street-cars and picked up your pocket- handkerchief?”
—Mary B. Clay, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 3, by Susan B. Anthony and Ida Husted Harper (1902)
“It gives me the greatest pleasure to say, as I do from the bottom of my heart, that never in the history of the country, in any crisis and under any conditions, have our Jewish fellow citizens failed to live up to the highest standards of citizenship and patriotism.”
—William Howard Taft (1857–1930)