自动机理论 • 下推自动机

上下文无关文法

正则语言做不到的事

对于如下文法：

A → 0A1
A → B
B → #

你是写不出一个正则表达式（或者构造出一个有限自动机）来识别这个文法的语言的。

这个文法是一个不能退化成正则文法的上下文无关文法。

上下文无关文法的形式化定义

上下文无关文法由如下四元组 $(V, T, R, S)$ 定义，其中：

• V 是变量集合
• T 是终结符集合
• R 是文法的规则 (A → 0A1 之类的)
• S 是开始变量，表示整个语言

下推自动机

和有限状态机能识别正则文法类似，上下文无关文法也能由一类状态机来识别。

我们观察上面的文法，可以发现生成的语言就是“在#左右两边有等量的0和1”的语言。

我们可以在“看到”0时向一个栈中压入一个0，在看到1时弹出，如果栈最终能弹空，则这个串符合这个文法。

下推自动机的形式化定义

下推自动机由如下 6 元组 $(Q, \Sigma, S, \delta, q_0, F)$ 定义，其中：

• Q 是状态集合
• $\Sigma$ 是输入符号集合
• S 是栈字母表集合
• $\delta$ 是状态转换函数，其参数为一个状态，一个输入符号和一个栈顶符号（可以为空），输出一个新状态和一个新栈顶符号，表现了状态机在某状态，栈顶符号为某个符号，接收到某输入时，进入的新状态和对栈的操作，一个 (状态, 输入符号, 栈顶符号) 可能对应多组输出
• $q_0$ 是开始状态
• F 为 终止或者接受状态的集合

构造识别某上下文无关文法的下推自动机

最简单的方法是，我们忽略状态这件事，只留下一个状态 $q_0$，所有的转换都在栈上进行。

• 对于所有的变量 A 和从这个变量出来的推导式 A → X，无论 X 是非终结符（变量），终结符还是任意公式，我们都添加一个代表 X 的栈字母，然后定义 $\delta$ 在 A 点上的值： $\delta(q, ε, A) := (q, X)$¹。
• 对于所有终结符 b，我们定义 $\delta$ 在 b 点上的值：$\delta(q, ε, b) := (q, ε)$。

所得到的自动机如果能弹空栈，则说明能接受这个语言。

确定性下推自动机和确定性上下文无关文法

存在一部分下推自动机，其状态转换函数中，一个 (状态, 输入符号, 栈顶符号) 只对应单组输出，这种下推自动机就是确定性下推自动机，能被这种自动机识别的文法就是确定性上下文无关文法。

这类下推自动机只要扫一遍输入串就能确定这个串能否被接受，说明这样的文法 parse 的复杂度是线性的，因此这类文法（尤其是其中几个子集）在构造各种 parser 的工程实践中是非常重要的。

判断文法是否是确定性的

判断方法称为 DK-test，我们在学习 LR(0) 分析时，学到了构造 LR(0) 状态机的方法，这个 LR(0) 状态机其实应该被称为 DK 状态机。

如果这个 DK 状态机中，原本文法中接受状态对应的状态：

• 有且只有只有一条代表匹配完成（即 ⋅ 在产生式最后的）产生式
• 其中所有产生式不形如 $B → X ⋅ a Y$，其中 a 是一个终结符