In formal grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

 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

Deterministic pushdown automaton

In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack....

 can recognize. A DCFG is the finite set of rules defining the set of well-formed expressions in some deterministic context-free language

Deterministic context-free language

A deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton.The set of deterministic...

.

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

History of programming languages

This article discusses the major developments in the history of programming languages. For a detailed timeline of events, see the timeline of programming languages.- Before 1940 :The first programming languages predate the modern computer...

) 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.

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

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

performs.

Limitations

Since DCFGs are a proper subset of CFGs, they are of less descriptive power than some CFGs.