Deterministic context-free grammar
From Wikipedia, the free encyclopedia
In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. The deterministic context-free grammars are those which a deterministic pushdown automaton can recognize. A DCFG is the finite set of rules defining the set of well-formed expressions in some deterministic context-free language.
Contents |
[edit] History
In the 1960's, theoretic research in computer science on regular expressions and finite automata led to the discovery that context-free grammars are equivalent to 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, which was a requirement due to computer memory constraints. [1]
[edit] Uses
LALR parsers, which use a subset of DCFGs, have practical value as program code validators. Given the formal rules of a DCFG, these parsers efficiently ensure a program can be generated from those rules. In fact, this syntax validation is one of the operations a compiler performs.
[edit] Limitations
- Some grammars cannot be recognized by a deterministic pushdown automaton, so DFCGs lack the full power of context-free grammars.
[edit] See also
[edit] References
- ^ (2001) A Half-Century of Automata Theory. World Scientific Publishing Co. Pte. Ltd.
Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
---|---|---|---|
Type-0 | Unrestricted | Recursively enumerable | Turing machine |
n/a | (no common name) | Recursive | Decider |
Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
n/a | Indexed | Indexed | Nested stack |
n/a | Tree-adjoining etc. | (Mildly context-sensitive) | Embedded pushdown |
Type-2 | Context-free | Context-free | Nondeterministic pushdown |
n/a | Deterministic context-free | Deterministic context-free | Deterministic pushdown |
Type-3 | Regular | Regular | Finite |
n/a | Star-free | Counter-Free | |
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it. |