History
In the 1960s, theoretical research in computer science on regular expressions and finite automata led to the discovery that context-free grammars are equivalent to nondeterministic pushdown automata. These grammars were thought to capture the syntax of computer programming languages. The first computer programming languages were under development at the time (see History of programming languages) and writing compilers was difficult. But using context-free grammars to help automate the parsing part of the compiler simplified the task. Deterministic context-free grammars were particularly useful because they could be parsed sequentially by a deterministic pushdown automaton, which was a requirement due to computer memory constraints. In 1965, Donald Knuth invented the LR(k) parser and proved that there exists an LR(k) grammar for every deterministic context-free language. This parser still required a lot of memory. In 1969 Frank DeRemer invented the LALR and Simple LR parsers, both based on the LR parser and having greatly reduced memory requirements at the cost of less language recognition power. The LALR parser was the stronger alternative. These two parsers have since been widely used in compilers of many computer languages.
Read more about this topic: Deterministic Context-free Grammar
Famous quotes containing the word history:
“... in a history of spiritual rupture, a social compact built on fantasy and collective secrets, poetry becomes more necessary than ever: it keeps the underground aquifers flowing; it is the liquid voice that can wear through stone.”
—Adrienne Rich (b. 1929)
“The principal office of history I take to be this: to prevent virtuous actions from being forgotten, and that evil words and deeds should fear an infamous reputation with posterity.”
—Tacitus (c. 55–c. 120)
“All history attests that man has subjected woman to his will, used her as a means to promote his selfish gratification, to minister to his sensual pleasures, to be instrumental in promoting his comfort; but never has he desired to elevate her to that rank she was created to fill. He has done all he could to debase and enslave her mind; and now he looks triumphantly on the ruin he has wrought, and say, the being he has thus deeply injured is his inferior.”
—Sarah M. Grimke (1792–1873)