12.2.1 Formal definition of context-free grammar

We conclude this section by way of summary with a quick formal description of a context-free grammar and the language it generates. A context-free grammar $G$ is defined by four parameters $N$, $\Sigma$, $P$, $S$ (technically “is a 4-tuple”):

N a set of non-terminal symbols (or variables)

$ \Sigma $ a set of terminal symbols (disjoint from N)

$ R $ a set of rules or productions, each of the form $ A \to \beta $, where $ A $ is a non-terminal, $ \beta $ is a string of symbols from the infinite set of strings $ (\Sigma \cup N)^* $

S a designated start symbol

For the remainder of the book we'll adhere to the following conventions when discussing the formal properties (as opposed to explaining particular facts about English or other languages) of context-free grammars.

| Capital letters like A, B, and S | Non-terminals |

| --- | --- |

| S | The start symbol |

| Lower-case Greek letters like $ \alpha $, $ \beta $, and $ \gamma $ | Strings drawn from $ (\Sigma\cupN) $* |

| Lower-case Roman letters like u, v, and w | Strings of terminals |

A language is defined via the concept of derivation. One string derives another one if it can be rewritten as the second one via some series of rule applications. More formally, following Hopcroft and Ullman (1979),

if $A \to \beta$ is a production of $P$ and $\alpha$ and $\gamma$ are any strings in the set $(\Sigma \cup N)*$, then we say that $\alpha A\gamma$ directly derives $\alpha\beta\gamma$, or $\alpha A\gamma \Rightarrow \alpha\beta\gamma$.

Derivation is then a generalization of direct derivation:

Let $ \alpha_1, \alpha_2, \ldots, \alpha_m $ be strings in $ (\Sigma \cup N)^* $, $ m \geq 1 $, such that

$$ \alpha_{1}\Rightarrow\alpha_{2},\alpha_{2}\Rightarrow\alpha_{3},\ldots,\alpha_{m-1}\Rightarrow\alpha_{m} $$

We say that $ \alpha_1 $ derives $ \alpha_m $, or $ \alpha_1 \overset{*}{\to} \alpha_m $.

We can then formally define the language $ \mathcal{L}_{G} $ generated by a grammar $ G $ as the set of strings composed of terminal symbols which can be derived from the designated start symbol $ S $.

$$ \mathcal{L}_{G}=\{w|w\mathrm{i s i n}\Sigma*\mathrm{a n d}S{\stackrel{*}{\Rightarrow}}w\} $$

The problem of mapping from a string of words to its parse tree is called parsing; we will define algorithms for parsing in Ch. 13 and in Ch. 14.

12.3 SOME GRAMMAR RULES FOR ENGLISH

In this section we introduce a few more aspects of the phrase structure of English; for consistency we will continue to focus on sentences from the ATIS domain. Because of space limitations, our discussion will necessarily be limited to highlights. Readers are strongly advised to consult a good reference grammar of English, such as Huddleston and Pullum (2002).