Context-Free Grammar

A Context-Free Grammar (CFG) is a notation for describing languages. It is more powerful than regular languages, but still cannot describe all languages. For example, a CFG can describe the language of balanced parentheses, but cannot describe the language of palindromes.

The basic idea of a CFG is to describe a language by using sets of denotations, which are called nonterminal symbols. These nonterminal symbols are combined using production rules to generate strings of terminal symbols. The terminal symbols are the actual symbols of the language. Context-free means that the production rules are applied regardless of the context in which the nonterminal symbols appear.

For example, the language of $\{0^n{1}^n\mid n\ge 0\}$ can be described by the CFG:

$$\begin{array}{rl}S& \to 0S1\mid \epsilon \end{array}$$

Here, $S$ is a nonterminal symbol, and the production rules say that $S$ can be replaced by $0S1$ or by the empty string $\epsilon$. This CFG generates strings like $0011$, $000111$, $00001111$, etc.

conventions

• Nonterminal symbols are usually written as uppercase letters, such as $S$.
• Terminal symbols are usually written as lowercase letters, such as $a$.

Formal Definition

A CFG is defined by a 4-tuple $(V,\mathrm{\Sigma },R,S)$, where:

• $V$ is a finite set of nonterminal symbols.
• $\mathrm{\Sigma }$ is a finite set of terminal symbols.
• $R$ is a finite set of production rules, each of the form $A\to \alpha$, where $A\in V$ and $\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }$.
• $S$ is the start symbol, which is a nonterminal symbol.

Sentential Forms

A sentential form is a string of terminal and nonterminal symbols. The start symbol $S$ is the initial sentential form. The CFG generates strings by applying production rules to replace nonterminal symbols with other symbols. The set of all possible sentential forms is called the language of the CFG.

A context-free language is the set of all strings that can be generated by a CFG. As we mentioned earlier, not all languages can be described by a CFG. There is a intuitive idea: context-free languages can count only two things at a time, not three.

BNF Notation

Grammars for programming languages are often written in BNF. In BNF, we write variables in angle brackets, and use ::= to denote a production rule. Terminals are often multi-character strings indicated by boldface or underlining.

Kleene Star

The Kleene star in BNF can be translated to a CFG by using a new nonterminal symbol. For example, the BNF rule:

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <digit> <integer>

can be translated to the CFG:

$$\begin{array}{rl}\text{digit}& \to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9\\ \text{integer}& \to \text{digit}\mid \text{digit integer}\end{array}$$

Optional Elements

Optional elements in BNF can be translated to a CFG by using a new nonterminal symbol. For example, the BNF rule:

<if-statement> ::= if <expression> then <statement> [else <statement>]

can be translated to the CFG:

$$\begin{array}{rl}\text{I}& \to \text{if E then S else S}\\ & \mid \text{if E then S}\end{array}$$

Leftmost and Rightmost Derivation

A leftmost derivation is a sequence of sentential forms where the leftmost nonterminal symbol is always the one that is replaced, which is denoted by ${\Rightarrow }_{lm}$. For example, $wA\beta {\Rightarrow }_{lm}w\alpha \beta$, where $A\to \alpha$ is a production rule and $w$ is a string of terminal symbols.

A rightmost derivation is similar, but the rightmost nonterminal symbol is always the one that is replaced, which is denoted by ${\Rightarrow }_{rm}$. For example, $\beta Aw{\Rightarrow }_{rm}\beta \alpha w$, where $A\to \alpha$ is a production rule and $w$ is a string of terminal symbols.