Deterministic Context-free Grammar Information
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 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 |
History
In the 1960s, 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]
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.
Limitations
Since DCFGs are a proper subset of CFGs, they are of less descriptive power than some CFGs.
See also
References
- ^ A Salomaa & D Wood & S Yu, ed (2001). A Half-Century of Automata Theory. World Scientific Publishing Co. Pte. Ltd. pp. 38–39.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Categories: Formal languages
|