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:
“Literary works cannot be taken over like factories, or literary forms of expression like industrial methods. Realist writing, of which history offers many widely varying examples, is likewise conditioned by the question of how, when and for what class it is made use of.”
—Bertolt Brecht (1898–1956)
“To history therefore I must refer for answer, in which it would be an unhappy passage indeed, which should shew by what fatal indulgence of subordinate views and passions, a contest for an atom had defeated well founded prospects of giving liberty to half the globe.”
—Thomas Jefferson (1743–1826)
“It takes a great deal of history to produce a little literature.”
—Henry James (1843–1916)