In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form
where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty).
Thus, the difference with arbitrary grammars is that the left hand side of a production rule is always a single nonterminal symbol rather than a string of terminal and/or nonterminal symbols. The term "context-free" expresses ...
more
In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form
where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty).
Thus, the difference with arbitrary grammars is that the left hand side of a production rule is always a single nonterminal symbol rather than a string of terminal and/or nonterminal symbols. The term "context-free" expresses the fact that nonterminals are rewritten without regard to the context in which they occur.
A formal language is context-free if some context-free grammar generates it. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.
Context-free grammars play a central role in the description and design of programming languages and compilers. They are also used for analyzing the syntax of natural languages.
Since the time of Pāṇini, at least, linguists have described the grammars of languages in...
less
