Informal grammar theory, thedeterministic context-free grammars (DCFGs) are aproper subset of thecontext-free grammars. They are the subset of context-free grammars that can be derived fromdeterministic pushdown automata, and they generate thedeterministic context-free languages. DCFGs are alwaysunambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.
DCFGs are of great practical interest, as they can be parsed inlinear time and in fact a parser can be automatically generated from the grammar by aparser generator. They are thus widely used throughout computer science. Various restricted forms of DCFGs can be parsed by simpler, less resource-intensive parsers, and thus are often used. These grammar classes are referred to by the type of parser that parses them, and important examples areLALR,SLR, andLL.
In the 1960s, theoretical research in computer science onregular expressions andfinite automata led to the discovery thatcontext-free grammars are equivalent to nondeterministicpushdown automata.[1][2][3] These grammars were thought to capture the syntax of computer programming languages. The first high-level computer programming languages were under development at the time (seeHistory of programming languages) and writingcompilers was difficult. But usingcontext-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 adeterministic pushdown automaton, which was a requirement due to computer memory constraints.[4] In 1965,Donald Knuth invented theLR(k) parser and proved that there exists an LR(k) grammar for every deterministic context-free language.[5] This parser still required a lot of memory. In 1969Frank DeRemer invented theLALR andSimple 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.[6] These two parsers have since been widely used in compilers of many computer languages. Recent research has identified methods by which canonical LR parsers may be implemented with dramatically reduced table requirements over Knuth's table-building algorithm.[7]