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 1 History 2 Uses 3 Limitations 4 See also 5 References

[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

• Deterministic parsing
• Deterministic pushdown automaton
• LR parser
• LL parser

[edit] References

1. ^ (2001) A Half-Century of Automata Theory. World Scientific Publishing Co. Pte. Ltd. 

Automata theory: formal languages and formal grammars

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.