Deterministic context-free grammar
- Deterministic context-free grammar
-
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.
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.
| v · d · eAutomata theory: formal languages and formal grammars |
|
|
|
| Grammars |
|
|
|
|
|
(no common name)
|
|
|
|
|
|
|
|
|
Linear context-free rewriting systems etc.
|
|
|
|
|
|
|
|
|
Deterministic context-free
|
|
|
|
|
|
|
|
|
—
|
|
|
|
|
|
Each category of languages is a proper subset of the category directly above it. - Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.
|
|
Wikimedia Foundation.
2010.
Look at other dictionaries:
Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… … Wikipedia
Context-free grammar generation algorithms — are algorithms which generate a context free grammar or grammars from given symbol sequence or sequences.Applications for such algorithms include lossless data compression and data mining. A list of algorithms * Sequitur * Lempel Ziv Welch… … Wikipedia
Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… … Wikipedia
Stochastic context-free grammar — A stochastic context free grammar (SCFG; also probabilistic context free grammar, PCFG) is a context free grammar in which each production is augmented with a probability. The probability of a derivation (parse) is then the product of the… … Wikipedia
Context free — may refer to: Concepts context free grammar deterministic context free grammar stochastic context free grammar weighted context free grammar context free language Software Context Free, a computer language for context free grammars … Wikipedia
Context-sensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… … Wikipedia
Context-free language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… … Wikipedia
Deterministic parsing — In natural language processing, deterministic parsing refers to parsing algorithms that do not back up. LR parsers are an example. (This meaning of the words deterministic and non deterministic differs from that used to describe nondeterministic… … Wikipedia
Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… … Wikipedia
Context-sensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… … Wikipedia
