This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0010609024 Reproduction Date:
In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, 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 in linear time and in fact a parser can be automatically generated from the grammar by a parser 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 are LALR, SLR, and LL.
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.^{[1]}^{[2]}^{[3]} 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.^{[4]} In 1965, Donald Knuth invented the LR(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 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.^{[6]} These two parsers have since been widely used in compilers of many computer languages.
Parsing, Turing machine, Noam Chomsky, Linguistics, Mathematical logic
Computer science, Automata theory, Formal language, String (computer science), Nondeterministic finite automaton
Deterministic pushdown automaton, Nested word, Proper subset, Context-free language, Unambiguous grammar
Computer science, Linguistics, Noam Chomsky, Regular language, Turing machine
Nested word, Ptime, Automata theory, Formal language, Formal grammar
Automata theory, Nested word, Transition monoid, Regular language, Star-free language
Tree-adjoining grammar, Nested word, Context-free grammar, Pushdown automaton, Context-sensitive grammar