Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules

can be applied to a nonterminal symbol regardless of its context.

In particular, in a context-free grammar, each production rule is of the form

A

→

α

{\displaystyle A\ \to \ \alpha }

with

A

{\displaystyle A}

a single nonterminal symbol, and

α

{\displaystyle \alpha }

a string of terminals and/or nonterminals (

α

{\displaystyle \alpha }

can be empty). Regardless of which symbols surround it, the single nonterminal

A

{\displaystyle A}

on the left hand side can always be replaced by

α

{\displaystyle \alpha }

on the right hand side. This distinguishes it from a context-sensitive grammar, which can have production rules in the form

α

A

β

→

α

γ

β

{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }

with

A

{\displaystyle A}

a nonterminal symbol and

α

{\displaystyle \alpha }

,

β

{\displaystyle \beta }

, and

γ

{\displaystyle \gamma }

strings of terminal and/or nonterminal symbols.

A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,

⟨

Stmt

⟩

→

⟨

Id

⟩

=

⟨

Expr

⟩

;

{\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}

replaces

⟨

Stmt

⟩

{\displaystyle \langle {\text{Stmt}}\rangle }

with

⟨

Id

⟩

=

⟨

Expr

⟩

;

{\displaystyle \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}

. There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol").

Nonterminal symbols are used during the derivation process, but do not appear in its final result string.