Context Free Grammar (CFG)

In formal language theory, a context-free grammar (CFG) is a 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 (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.

[Reference :: wikipedia]