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

石门的第一条规则只要求检查首尾字符，有限状态已经够用。第二道门要求任意深度的括号配对，守卫必须带一只栈。再往上，规则可能需要改写任意位置的工作带。乔姆斯基谱系把这种“需要多少计算能力”组织成四个层次。

本课目标

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

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

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

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

不同教材会给出等价但细节略有差异的 1 型定义，尤其是 $\varepsilon$ 规则。使用某一定理前，应确认采用的是哪套定义和例外条件。

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

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

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

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

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

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

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

但语言

$$ L={a^nb^n\mid n\ge0} $$

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

3. 泵引理提供反证工具

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

1. $|xy|\le p$；
2. $|y|>0$；
3. 对所有 $i\ge0$，$xy^iz\in L$。

对 $a^pb^p$，因为前 $p$ 个字符全是 a，片段 $y$ 只能包含 a。把 $y$ 重复或删除，会改变 a 的数量却不改变 b 的数量，结果不再属于 $L$，产生矛盾。

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

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

下推自动机比有限自动机多一个栈。读到左括号时压栈，读到右括号时弹栈，就能处理任意有限深度的平衡括号。

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

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

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

旧式概括常写成：

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

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

更准确的工程分层是：

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

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

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

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

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

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

7. 识别、判定与生成

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

有限自动机和常用 CFG 解析器会对有限输入停机，因此对应的是判定过程。图灵机级别则必须区分“可识别”和“可判定”；第 4 章会用停机问题展示这条边界。

常见误区

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

练习

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

小结

谱系衡量规则需要的计算能力，不是给工具贴高低等级。有限状态处理固定记忆，栈处理一类递归嵌套，线性有界存储和图灵机继续扩大能力。工程上应选满足需求的最弱模型，因为能力越受限，行为通常越容易预测。

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