Context-free Grammar

:V → ''w''
where V is a Non-terminal Symbol and ''w'' is a string consisting of terminals and/or non-terminals. The term "context-free" comes from the fact that the non-terminal V can always be replaced by ''w'', regardless of the context in which it occurs. A Formal Language is Context-free if there is a context-free grammar that generates it.

Context-free grammars are powerful enough to describe the Syntax of most Programming Language s; in fact, the syntax of most programming languages are specified using context-free grammars. On the other hand, context-free grammars are simple enough to allow the construction of efficient Parsing Algorithm s which, for a given string, determine whether and how it can be generated from the grammar. An Earley Parser is an example of such an algorithm, while LR and LL Parser s only deal with more restrictive subsets of context-free grammars.

BNF ( Backus-Naur Form ) is the most common notation used to express context-free grammars.

Not all formal languages are context-free — a well-known Counterexample is

\{ a^n b^n c^n : n \ge 0 \}

, the set of strings containing some number of a's, followed by the same number of b's and the same number of c's.
This particular language can be generated by a Parsing Expression Grammar , which is a relatively new Formalism that is particularly well-suited to programming languages.

FORMAL DEFINITION

Just as any Formal Grammar , a context-free grammar G can be defined as a 4-tuple:

G = (V_t, V_n, P, S)

where

$V_t$ is a finite set of terminals

$V_n$ is a finite set of non-terminals

$P$ is a finite set of production rules

$S$ is an element of $V_n$ , the distinguished starting non-terminal.

elements of $P$ are of the form

EXAMPLES

Example 1

A simple context-free grammar is

Information About

Context-free Grammar