形式文法

在计算机科学中, 形式文法是一种通过规则描述语言的方法. 例如, 2 进制自然数可以用如下规则描述:

$S D ::= D S ∣ D ::= 0 ∣ 1$

在不加特殊说明的情况下, 第一条规则是开始的规则, 例如上面的规则中便是 $S$ , 紧接着是关于 “ $S$ 规则能匹配哪些符号” 的说明, 竖线表示 “或者”, $D S$ 表示 “先使用 $D$ 匹配些什么, 再接着用 $S$ 匹配”.

例如字符串 $010$ 可以通过如下方式匹配:

$S \to D S \to 0 S \to 0 D S \to 01 S \to 01 D \to 010$

首先, 将 $S$ 展开为 $D S$ 以便进一步展开 $D$ 并匹配第一个 $0$ , 然后继续展开 $S$ , 以此类推.

最常见的形式文法是语境无关文法.

1定义

定义 1.1 (语言). 令 $V$ 为有限集, 称为字母表, 里面的元素叫做终结符号. 一个语言就是 $V$ 上的自由幺半群 $V^{*}$ 的子集.

定义 1.2 (规则). 对于字母表 $V$ 和一组表示变量名的集合 $X$ (里面的元素称为非终结符号), 规则包含如下信息:

•	它本身的名字, 使用变量名 $S \in X$ 表示,

•	它的内容, 为该规则某种可能的展开方式. 每一种展开方式就是一组终结或非终结符号, 因此这个整体就是 $(X + V)^{*}$ 中的元素, 其中 $X + V$ 是两集合的并集.

给定两种符号的集合, 它们能写出的所有规则的集合为 $X \times (X + V)^{*}$ .

终结符号之所以终结是因为它们不像非终结符号一样可以使用规则进一步展开, 它们直接匹配字符.

注 1.3. 同一个变量名可以对应多个规则, 在描述时使用 $∣$ 合并. 例如, $S ::= α β ψ ∣ δ εφ$ 就对应了两条规则:

•	$S$ 可以展开为 $α β ψ$ ,
•	$S$ 可以展开为 $δ εφ$ .

定义 1.4 (语境无关文法). 语境无关文法为四元组 $(V, X, R, s)$ , 其中:

•	$V$ 和 $X$ 分别是字母表和变量名的集合,

•	$s \in X$ 是开始的规则名,

•	$R \subset X \times (X + V)^{*}$ 是规则.

语境无关文法对应的语言 $L (V, X, R, s)$ 构造如下:

首先定义重写关系 $(\to_{R}) \subseteq (X + V)^{*} \times (X + V)^{*}$ : 令 $α, β \in (X + V)^{*}$ 且 $(s, w) \in R$ , 那么有 $(α s β) \to_{R} (α wβ)$ 成立.

取由该关系构成的重写系统的自反传递闭包 $\to_{R}^{*}$ , 这便是按规则所有可能的展开方式.

最后定义语言为: $L (V, X, R, s) := {w_{1} w_{2} \dots w_{k} \in V^{*} ∣ s \to_{R}^{*} w_{1} w_{2} \dots w_{k}}$

下推自动机可以执行语境无关文法的匹配.

定义 1.5. 对于字母表 $V$ 和一组表示变量名的集合 $X$ (里面的元素称为非终结符号), 规则表示一种重写关系.

一组终结或非终结符号可以看作 $(X + V)^{*}$ 中的元素, 其中 $X + V$ 是两集合的并集. 重写关系便是这样的元素上的关系.

给定两种符号的集合, 它们能写出的所有规则的集合为 $(X + V)^{+} \times (X + V)^{*}$ , 其中 $(X + V)^{+}$ 是 $(X + V)^{*}$ 的非空子集.

定义 1.6 (无限制文法). 无限制文法将语境无关文法中的规则改为 1.5 中的规则, 其余内容不变.

Turing 机可以执行语境无关文法的匹配.

•	类型论的句法一般使用语境无关文法描述, 例如简单类型 $λ$ 演算、Martin-Löf 类型论.

术语翻译

形式文法 • 英文 formal grammar

终结符 • 英文 terminal symbol

语境无关文法 • 英文 context free grammar (CFG)

无限制文法 • 英文 unrestricted grammar