In
formal grammar
A formal grammar is a set of Terminal and nonterminal symbols, symbols and the Production (computer science), production rules for rewriting some of them into every possible string of a formal language over an Alphabet (formal languages), alphabe ...
theory, the deterministic context-free grammars (DCFGs) are a
proper subset
In mathematics, a set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is 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 language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meanin ...
s. 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
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
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.
History
In the 1960s, theoretical research in computer science on
regular expressions
A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of character (computing), characters that specifies a pattern matching, match pattern in string (computer science), text. Usually ...
and
finite automata
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...
led to the discovery that
context-free grammars are equivalent to nondeterministic
pushdown automata. These grammars were thought to capture the syntax of computer programming languages. The first high-level computer programming languages were under development at the time (see
History of programming languages) and writing
compilers
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
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. In 1965,
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
invented the
LR(k) parser and proved that there exists an LR(k) grammar for every deterministic context-free language. 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.
These two parsers have since been widely used in compilers of many computer languages. Recent research has identified methods by which canonical LR parsers may be implemented with dramatically reduced table requirements over Knuth's table-building algorithm.
[X. Chen]
Measuring and extending LR(1) parsing
University of Hawaii PhD dissertation, 2009.
See also
*
Deterministic parsing
*
LL parser
References
{{Formal languages and grammars
Formal languages