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:
“You treat world history as a mathematician does mathematics, in which nothing but laws and formulas exist, no reality, no good and evil, no time, no yesterday, no tomorrow, nothing but an eternal, shallow, mathematical present.”
—Hermann Hesse (1877–1962)
“In the history of the United States, there is no continuity at all. You can cut through it anywhere and nothing on this side of the cut has anything to do with anything on the other side.”
—Henry Brooks Adams (1838–1918)
“What is most interesting and valuable in it, however, is not the materials for the history of Pontiac, or Braddock, or the Northwest, which it furnishes; not the annals of the country, but the natural facts, or perennials, which are ever without date. When out of history the truth shall be extracted, it will have shed its dates like withered leaves.”
—Henry David Thoreau (1817–1862)