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:
“For a transitory enchanted moment man must have held his breath in the presence of this continent, compelled into an aesthetic contemplation he neither understood nor desired, face to face for the last time in history with something commensurate to his capacity for wonder.”
—F. Scott Fitzgerald (18961940)
“In every election in American history both parties have their clichés. The party that has the clichés that ring true wins.”
—Newt Gingrich (b. 1943)
“No one is ahead of his time, it is only that the particular variety of creating his time is the one that his contemporaries who are also creating their own time refuse to accept.... For a very long time everybody refuses and then almost without a pause almost everybody accepts. In the history of the refused in the arts and literature the rapidity of the change is always startling.”
—Gertrude Stein (18741946)