本章开始进入形式语言与自动机的部分。这里的核心问题是：如何用一组明确的规则描述一个语言，以及这些规则能够生成怎样的字符串集合。

自然语言往往依赖经验和语境，形式语言则把语法规则写成严格的数学对象。语法只负责说明一个串长什么样，语义则通常交给别的计算模型或数学模型来解释。

短语结构文法

短语结构文法记作 $G=(\Sigma,T,S,P)$ ，其中 $\Sigma$ 是符号表，$T$ 是终结符集合，$S$ 是起始符号，$P$ 是产生式集合。

如果记 $N=\Sigma-T$ ，那么 $N$ 中的符号称为非终结符。产生式一般写作

$$ w_1 \rightarrow w_2 $$

其中 $w_1,w_2$ 都是 $\Sigma$ 上的字符串，并且 $w_1$ 中至少要含有一个非终结符。

文法中的一步替换称为直接派生。若 $w_0=lz_0r$ ，$w_1=lz_1r$ ，并且 $z_0\rightarrow z_1$ 是一个产生式，则记作

$$ w_0 \Rightarrow w_1 $$

若经过有限多次直接派生可以从 $w_0$ 得到 $w_n$ ，则记作

$$ w_0 \Rightarrow^* w_n $$

由文法 $G$ 生成的语言就是从起始符号出发，最终能派生出的所有终结符串

$$ L(G)=\lbrace{}w\in T^* \mid S\Rightarrow^* w\rbrace $$

例如课件中给出的文法可以生成形如偶数个 $1$ 后接一个 $0$ 的字符串。证明这类结论时，通常一边说明产生式每用一次会增加什么结构，一边说明反过来任意满足结构的串都能由文法生成。

一种更直接的写法是令终结符为 $0,1$ ，起始符为 $S$ ，产生式为

$$ S\rightarrow 11S,\qquad S\rightarrow 0 $$

这样每递归一次就在前面增加两个 $1$ ，最后用 $S\rightarrow 0$ 结束，得到的正好是 $0,110,11110,\ldots$ 这一类串。

构造文法时要先看目标语言的形状，再决定递归产生式怎么写。比如 $0^n1^n$ 这一类“左右同步增长”的语言，常见写法是让一次递归同时在左侧放一个 $0$ ，在右侧放一个 $1$

$$ S\rightarrow 0S1,\qquad S\rightarrow \lambda $$

Chomsky 层级

Chomsky 层级按照产生式约束把文法分成四类。越往下约束越强，能描述的语言集合也越小。

非收缩文法要求所有产生式 $w_1\rightarrow w_2$ 都满足左端长度不超过右端长度。除了起始符推出空串的特殊情况外，1 型文法可以看作非收缩文法。

派生树

对上下文无关文法来说，派生过程可以画成派生树，也叫语法分析树。树根是起始符，内部节点是非终结符，叶子节点是终结符。按从左到右读叶子节点，就能得到一个句子。

派生树的好处是把“先用哪条产生式”变成了树形结构。对于编程语言语法，后面做语法分析时常常需要类似的树。

巴科斯-诺尔范式

巴科斯-诺尔范式常用于表示 2 型文法，也就是上下文无关文法。它的写法主要是把左端相同的产生式合并，用竖线隔开不同右端，用 ::= 代替箭头，并用尖括号表示非终结符。

例如数字和标识符的一部分规则可以写成：

1
2
3

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | ... | z
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

它本质上只是另一种更适合阅读的记号。比如若一个非终结符有多种产生式，普通文法会写成多行，BNF 则可以把它们合并成一行，从而更接近编程语言手册里的语法定义。