1.2 乔姆斯基谱系与识别边界：规则需要多少记忆

本课目标

• 准确说出四类文法及对应识别模型；
• 理解各层语言类的包含关系；
• 判断常见编译任务主要落在哪一层；
• 避免把实际正则方言、程序语义和文法层次混为一谈。

1. 四类文法不是四种编程语言

设 $V$ 为非终结符集合，$\mathrm{\Sigma }$ 为终结符集合。谱系从限制最少的 0 型到限制最强的 3 型：

类型	产生式的核心限制	对应模型	典型语言
3 型：正则文法	右线性如 $A\to aB$ 或 $A\to a$；也可统一采用左线性形式	有限自动机	token 的多数字符模式
2 型：上下文无关文法	左侧是单个非终结符 $A\to \gamma$	非确定性下推自动机（NPDA）	括号嵌套、表达式语法
1 型：上下文有关文法	规则通常不缩短字符串，等价定义需处理开始符号生成空串的例外	非确定性线性有界自动机	$\{a^n{b}^n{c}^n\mid n\ge 1\}$
0 型：无限制文法	左侧至少含一个非终结符，除此之外基本不限制	图灵机	图灵可识别语言

表中 3 型还需约定空串产生式，例如允许右线性形式中的 A → ε。1 型采用非收缩文法的定义时，可额外允许 S → ε，但此时开始符号不能出现在任何产生式右侧。下列包含关系采用允许空串的标准约定。

表中的非确定性不能省略：NPDA 识别所有上下文无关语言，而确定性 PDA 只覆盖其中一部分；一般上下文有关语言对应的是非确定性线性有界自动机。

语言类满足严格包含关系：

$$\text{Regular}⊊\text{Context-Free}⊊\text{Context-Sensitive}⊊\text{Recursively Enumerable}.$$

越靠左，表达能力越受限，通常也越容易得到高效且可预测的识别算法；越靠右，不意味着“更适合所有任务”。

2. 有限状态只能记住有限种历史

有限自动机的记忆就是当前状态。状态数量固定，因此它能记住：

• 当前是否见过某个符号；
• 计数对某个固定整数取模的结果；
• 是否匹配了某个有限模式的前缀。

例如“二进制串中 1 的数量为偶数”只需两个状态：偶数与奇数。每读到一个 1 就切换状态，读到 0 保持不变。

但语言

$$L=\{a^n{b}^n\mid n\ge 0\}$$

要求保存任意大的 $n$。有限状态无法为所有 $n$ 保留不同记忆，因此该语言不是正则语言。

3. 泵引理提供反证工具

正则语言泵引理说：若 $L$ 正则，则存在泵长度 $p$，任何长度至少为 $p$ 的 $w\in L$ 都可分成 $w=xyz$，满足：

1. $|xy|\le p$；
2. $|y|>0$；
3. 对所有 $i\ge 0$，$x{y}^{i}z\in L$。

对 $a^p{b}^p$，因为前 $p$ 个字符全是 a，片段 $y$ 只能包含 a。无论怎样选择满足前两条约束的拆分，$y$ 都只含一个或多个 a。把 $y$ 删除，即取 $i=0$，会改变 a 的数量却不改变 b 的数量，结果不再属于 $L$，产生矛盾。

证明时的顺序是：假设任意泵长度 $p$，选择合适的 $w$，然后覆盖所有合法拆分，最后找到使结果出界的 $i$。只挑一个自己喜欢的拆分失败，不能证明非正则。

泵引理是正则语言的必要条件，不是充分条件。无法找到反例，不等于已经证明语言正则；证明正则通常直接构造正则表达式、正则文法或有限自动机。

4. 栈能处理一类嵌套结构

下推自动机比有限自动机多一个栈。读到左括号时压栈，读到右括号时弹栈，就能处理任意有限深度的平衡括号；遇到空栈却要弹出时拒绝，读完输入后栈也必须回到初始状态。

“栈能计数”只是直觉。一个栈的访问受后进先出限制，并不能处理所有涉及多个计数器的语言。例如 $a^n{b}^n{c}^n$ 不是上下文无关语言；单个 PDA 无法同时保持三段数量相等所需的关系。

上下文无关文法适合描述程序的递归语法结构，但名称解析、类型一致性和“变量先声明后使用”等约束通常需要符号表、属性文法或专门的语义算法。

5. 编译器阶段不等于谱系逐级升级

旧式概括常写成：

词法分析 → 正则语言
语法分析 → 上下文无关语言
语义分析 → 上下文有关语言
代码生成 → 图灵机

前两项是有用近似，后两项容易误导。语义分析确实包含上下文依赖，但现代类型系统、名称解析和控制流检查并不是简单地运行一个 1 型文法识别器。代码生成也不是因为“属于 0 型文法”，而是一个保持程序语义的转换过程。

更准确的工程分层是：

阶段	主要输入	常用模型或结构
词法分析	字符	正则模式、有限自动机、手写扫描器
语法分析	token	上下文无关文法（CFG）、LL/LR、PEG、AST
语义分析	AST 与环境	符号表、类型规则、数据流分析
中间表示与优化	IR	控制流图（也缩写为 CFG）、SSA、格与不动点算法
代码生成	IR 与目标信息	指令选择、调度、寄存器分配

理论谱系帮助我们理解表达能力边界，但不能替代具体编译阶段的算法设计。

6. “正则表达式”未必只表达正则语言

经典正则表达式由连接、选择和 Kleene 星等操作构成，恰好描述正则语言。实际工具常加入额外功能：

• 反向引用可能超出正则语言；
• 环视改变匹配条件与实现方式，但由正则子模式构成的常规环视本身不必超出正则语言；
• 递归模式能表达某些嵌套结构；
• 回溯引擎可能出现指数级运行时间。

因此“用了 regex”不足以推出“由 DFA 线性时间执行”。要看具体方言、引擎和模式。词法分析器生成器通常限制规则，以换取确定的最长匹配、优先级和执行性能。

7. 识别、判定与生成

• 识别：属于语言时最终接受；不属于时可能拒绝，也可能永不停止。
• 判定：对所有输入都在有限时间内停止，并正确回答属于或不属于。
• 生成：通过规则或过程枚举语言中的串。

有限自动机和常用 CFG 解析器会对有限输入停机，因此对应的是判定过程。这里的“常用 CFG 解析器”指保证停机的算法；朴素递归下降若不处理左递归，也可能在合法文法上无限递归。图灵机级别则必须区分“可识别”和“可判定”；第 4 章会用停机问题展示这条边界。

常见误区

• 层级越高越高级：受限模型往往更容易分析、验证和高效执行。
• 上下文无关文法能表达整门编程语言的全部规则：它主要覆盖语法骨架，不覆盖全部静态与动态语义。
• 所有正则表达式都能编译为 DFA：只对表达正则语言的功能成立。
• 泵引理可以证明一个语言正则：它主要用于证明某些语言不正则。

练习

1. 为“1 的数量对 3 取模等于 0”设计三个有限状态。
2. 解释为什么有限最大嵌套深度的括号语言可以是正则语言，而任意深度版本不是。
3. 分别给词法、语法和语义约束举一个例子，并选择合适的处理阶段。
4. 查阅你使用的正则引擎，确认它是否支持反向引用，以及是否保证线性时间。

小结

谱系衡量识别规则需要的计算能力。给一个标识符检查器配上图灵机当然能做事，但不必为了查门票先建整座机场。有限状态处理固定记忆，栈处理一类递归嵌套，线性有界存储和图灵机继续扩大能力。工程上应选满足需求的最弱模型，因为能力越受限，行为通常越容易预测。

下一章进入正则语言内部：先把一条规则画成可靠的 DFA，再讨论 NFA 为什么方便构造，以及二者如何转换。