第3章 词法分析

从词法规约、正则表达式、NFA/DFA、子集构造、直接构造、最小化到Lex实现可验证扫描器；用编译流水线、状态轨迹和等价性验证门交付正则—NFA—DFA映射、状态轨迹、token流与冲突案例

学习目标

  • 能说明“第3章 词法分析”如何从词法规约、正则表达式、NFA/DFA、子集构造、直接构造、最小化到Lex实现可验证扫描器，并区分Pearson英文第二版、中文译本、现代工具和本站重写
  • 能先预测“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”会改变哪一个输入、表示、栈/图状态、IR、目标代码或验证结果，再操作三类交互证据
  • 能只注入“提前接受较短规则，破坏最长匹配并吞错输入边界”，定位首个偏离“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第3章 词法分析”围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”建立贯穿任务：让同一输入串经过手写扫描器、NFA模拟和DFA扫描器。先写下哪个输入、表示、栈/图状态、IR、目标代码或验证结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”并交付正则—NFA—DFA映射、状态轨迹、token流与冲突案例，编译成功、分析收敛、目标码长度或基准加速才构成机制证据。

原版书目、556个正式坐标与访问边界

“第3章 词法分析”以Pearson官方书页核对Alfred V. Aho、Monica S. Lam、Ravi Sethi、Jeffrey D. Ullman著 Compilers: Principles, Techniques, and Tools, Second Edition：英文精装ISBN 9780321486813，2006年版；Pearson明确列出12章与两个附录，并说明第10章“指令级并行”、第11章“并行与局部性优化”、第12章“过程间分析”是第二版新增重点。Pearson官方目录继续核对版本与章/附录框架。

“第3章 词法分析”再以中文版完整目录与高校馆藏书目核对赵建华、郑滔、戴新宇译《编译原理（第2版）》，机械工业出版社，2009年，631页，ISBN 9787111251217。正式分母计入12个章标题、2个附录标题、533个数字编号节/小节和附录A的9个编号节，合计556个核心目录层级；章末总结、练习、参考文献和索引不重复计为知识节点。

原书与译本均受版权保护，“第3章 词法分析”不复制、翻译或改写原文、图表、算法伪码和练习，只把官方目录当作范围坐标；中文讲解、状态轨迹、反例、交互、练习与答案均为独立教学重写。本页独立核对 1只用于核对现代IR、工具或实验边界，不反向证明原书采用本站表述。

原版目录层级与可验证机制

第3章 词法分析

正式坐标 1/50。 原版目录键 第3章 词法分析。在“第3章 词法分析”的第1个正式坐标中，「第3章 词法分析」通过声明阶段接口、名字/类型/状态角色和源—目标语义映射推进词法边界、自动机与扫描状态；复核者保存阶段快照、符号表、类型、IR谱系、诊断和源位置，出现阶段边界丢失绑定、类型、控制依赖或源位置就撤回结论。

3·1 词法分析器的作用

正式坐标 2/50。 原版目录键 3.1 词法分析器的作用。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标2把「3·1 词法分析器的作用」落实为声明阶段接口、名字/类型/状态角色和源—目标语义映射；只有阶段快照、符号表、类型、IR谱系、诊断和源位置可重放且反例排除阶段边界丢失绑定、类型、控制依赖或源位置，本节点才算掌握。

3·1·1 词法分析与语法分析

正式坐标 3/50。 原版目录键 3.1.1 词法分析与语法分析。“第3章 词法分析”的目录节点3「3·1·1 词法分析与语法分析」不能停在术语或伪码：它要声明阶段接口、名字/类型/状态角色和源—目标语义映射，交付阶段快照、符号表、类型、IR谱系、诊断和源位置，并把阶段边界丢失绑定、类型、控制依赖或源位置设为单一反事实。

3·1·2 词法单元、模式和词素

正式坐标 4/50。 原版目录键 3.1.2 词法单元、模式和词素。对“第3章 词法分析”而言，「3·1·2 词法单元、模式和词素」在第4次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·1·3 词法单元的属性

正式坐标 5/50。 原版目录键 3.1.3 词法单元的属性。在“第3章 词法分析”的第5个正式坐标中，「3·1·3 词法单元的属性」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·1·4 词法错误

正式坐标 6/50。 原版目录键 3.1.4 词法错误。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标6把「3·1·4 词法错误」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·2 输入缓冲

正式坐标 7/50。 原版目录键 3.2 输入缓冲。“第3章 词法分析”的目录节点7「3·2 输入缓冲」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·2·1 缓冲区对

正式坐标 8/50。 原版目录键 3.2.1 缓冲区对。对“第3章 词法分析”而言，「3·2·1 缓冲区对」在第8次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·2·2 哨兵标记

正式坐标 9/50。 原版目录键 3.2.2 哨兵标记。在“第3章 词法分析”的第9个正式坐标中，「3·2·2 哨兵标记」通过追踪栈帧、非局部绑定、根集、堆对象和收集阶段推进词法边界、自动机与扫描状态；复核者保存活动记录、访问链、根集、对象图、写屏障与暂停统计，出现生命周期、根集或屏障错误导致悬垂引用、泄漏或误回收就撤回结论。

3·3 词法单元的规约

正式坐标 10/50。 原版目录键 3.3 词法单元的规约。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标10把「3·3 词法单元的规约」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·3·1 串和语言

正式坐标 11/50。 原版目录键 3.3.1 串和语言。“第3章 词法分析”的目录节点11「3·3·1 串和语言」不能停在术语或伪码：它要把“串和语言”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，交付第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据，并把只复述“串和语言”名称而没有可观察状态、单故障和恢复验证设为单一反事实。

3·3·2 语言上的运算

正式坐标 12/50。 原版目录键 3.3.2 语言上的运算。对“第3章 词法分析”而言，「3·3·2 语言上的运算」在第12次检查中改变可观察状态，因为它负责把“语言上的运算”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链；第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受只复述“语言上的运算”名称而没有可观察状态、单故障和恢复验证。

3·3·3 正则表达式

正式坐标 13/50。 原版目录键 3.3.3 正则表达式。在“第3章 词法分析”的第13个正式坐标中，「3·3·3 正则表达式」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·3·4 正则定义

正式坐标 14/50。 原版目录键 3.3.4 正则定义。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标14把「3·3·4 正则定义」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·3·5 正则表达式的扩展

正式坐标 15/50。 原版目录键 3.3.5 正则表达式的扩展。“第3章 词法分析”的目录节点15「3·3·5 正则表达式的扩展」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·4 词法单元的识别

正式坐标 16/50。 原版目录键 3.4 词法单元的识别。对“第3章 词法分析”而言，「3·4 词法单元的识别」在第16次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·4·1 状态转换图

正式坐标 17/50。 原版目录键 3.4.1 状态转换图。在“第3章 词法分析”的第17个正式坐标中，「3·4·1 状态转换图」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·4·2 保留字和标识符的识别

正式坐标 18/50。 原版目录键 3.4.2 保留字和标识符的识别。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标18把「3·4·2 保留字和标识符的识别」落实为把“保留字和标识符的识别”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链；只有第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据可重放且反例排除只复述“保留字和标识符的识别”名称而没有可观察状态、单故障和恢复验证，本节点才算掌握。

3·4·3 完成运行示例

正式坐标 19/50。 原版目录键 3.4.3 完成运行示例。“第3章 词法分析”的目录节点19「3·4·3 完成运行示例」不能停在术语或伪码：它要把“完成运行示例”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，交付第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据，并把只复述“完成运行示例”名称而没有可观察状态、单故障和恢复验证设为单一反事实。

3·4·4 基于状态转换图的词法分析器体系结构

正式坐标 20/50。 原版目录键 3.4.4 基于状态转换图的词法分析器体系结构。对“第3章 词法分析”而言，「3·4·4 基于状态转换图的词法分析器体系结构」在第20次检查中改变可观察状态，因为它负责声明阶段接口、名字/类型/状态角色和源—目标语义映射；阶段快照、符号表、类型、IR谱系、诊断和源位置必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受阶段边界丢失绑定、类型、控制依赖或源位置。

3·5 词法分析器生成工具Lex

正式坐标 21/50。 原版目录键 3.5 词法分析器生成工具Lex。在“第3章 词法分析”的第21个正式坐标中，「3·5 词法分析器生成工具Lex」通过声明阶段接口、名字/类型/状态角色和源—目标语义映射推进词法边界、自动机与扫描状态；复核者保存阶段快照、符号表、类型、IR谱系、诊断和源位置，出现阶段边界丢失绑定、类型、控制依赖或源位置就撤回结论。

3·5·1 Lex的使用

正式坐标 22/50。 原版目录键 3.5.1 Lex的使用。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标22把「3·5·1 Lex的使用」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·5·2 Lex程序的结构

正式坐标 23/50。 原版目录键 3.5.2 Lex程序的结构。“第3章 词法分析”的目录节点23「3·5·2 Lex程序的结构」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·5·3 Lex中的冲突解决

正式坐标 24/50。 原版目录键 3.5.3 Lex中的冲突解决。对“第3章 词法分析”而言，「3·5·3 Lex中的冲突解决」在第24次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·5·4 向前看运算符

正式坐标 25/50。 原版目录键 3.5.4 向前看运算符。在“第3章 词法分析”的第25个正式坐标中，「3·5·4 向前看运算符」通过把“向前看运算符”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链推进词法边界、自动机与扫描状态；复核者保存第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据，出现只复述“向前看运算符”名称而没有可观察状态、单故障和恢复验证就撤回结论。

3·6 有穷自动机

正式坐标 26/50。 原版目录键 3.6 有穷自动机。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标26把「3·6 有穷自动机」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·6·1 不确定有穷自动机

正式坐标 27/50。 原版目录键 3.6.1 不确定有穷自动机。“第3章 词法分析”的目录节点27「3·6·1 不确定有穷自动机」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·6·2 转换表

正式坐标 28/50。 原版目录键 3.6.2 转换表。对“第3章 词法分析”而言，「3·6·2 转换表」在第28次检查中改变可观察状态，因为它负责把“转换表”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链；第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受只复述“转换表”名称而没有可观察状态、单故障和恢复验证。

3·6·3 自动机对输入串的接受

正式坐标 29/50。 原版目录键 3.6.3 自动机对输入串的接受。在“第3章 词法分析”的第29个正式坐标中，「3·6·3 自动机对输入串的接受」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·6·4 确定有穷自动机

正式坐标 30/50。 原版目录键 3.6.4 确定有穷自动机。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标30把「3·6·4 确定有穷自动机」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·7 从正则表达式到自动机

正式坐标 31/50。 原版目录键 3.7 从正则表达式到自动机。“第3章 词法分析”的目录节点31「3·7 从正则表达式到自动机」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·7·1 从NFA到DFA的转换

正式坐标 32/50。 原版目录键 3.7.1 从NFA到DFA的转换。对“第3章 词法分析”而言，「3·7·1 从NFA到DFA的转换」在第32次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·7·2 NFA的模拟

正式坐标 33/50。 原版目录键 3.7.2 NFA的模拟。在“第3章 词法分析”的第33个正式坐标中，「3·7·2 NFA的模拟」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·7·3 NFA模拟的效率

正式坐标 34/50。 原版目录键 3.7.3 NFA模拟的效率。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标34把「3·7·3 NFA模拟的效率」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·7·4 从正则表达式构造NFA

正式坐标 35/50。 原版目录键 3.7.4 从正则表达式构造NFA。“第3章 词法分析”的目录节点35「3·7·4 从正则表达式构造NFA」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·7·5 字符串处理算法的效率

正式坐标 36/50。 原版目录键 3.7.5 字符串处理算法的效率。对“第3章 词法分析”而言，「3·7·5 字符串处理算法的效率」在第36次检查中改变可观察状态，因为它负责把“字符串处理算法的效率”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链；第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受只复述“字符串处理算法的效率”名称而没有可观察状态、单故障和恢复验证。

3·8 词法分析器生成工具的设计

正式坐标 37/50。 原版目录键 3.8 词法分析器生成工具的设计。在“第3章 词法分析”的第37个正式坐标中，「3·8 词法分析器生成工具的设计」通过声明阶段接口、名字/类型/状态角色和源—目标语义映射推进词法边界、自动机与扫描状态；复核者保存阶段快照、符号表、类型、IR谱系、诊断和源位置，出现阶段边界丢失绑定、类型、控制依赖或源位置就撤回结论。

3·8·1 生成的词法分析器的结构

正式坐标 38/50。 原版目录键 3.8.1 生成的词法分析器的结构。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标38把「3·8·1 生成的词法分析器的结构」落实为声明阶段接口、名字/类型/状态角色和源—目标语义映射；只有阶段快照、符号表、类型、IR谱系、诊断和源位置可重放且反例排除阶段边界丢失绑定、类型、控制依赖或源位置，本节点才算掌握。

3·8·2 基于NFA的模式匹配

正式坐标 39/50。 原版目录键 3.8.2 基于NFA的模式匹配。“第3章 词法分析”的目录节点39「3·8·2 基于NFA的模式匹配」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·8·3 词法分析器使用的DFA

正式坐标 40/50。 原版目录键 3.8.3 词法分析器使用的DFA。对“第3章 词法分析”而言，「3·8·3 词法分析器使用的DFA」在第40次检查中改变可观察状态，因为它负责声明阶段接口、名字/类型/状态角色和源—目标语义映射；阶段快照、符号表、类型、IR谱系、诊断和源位置必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受阶段边界丢失绑定、类型、控制依赖或源位置。

3·8·4 实现向前看运算符

正式坐标 41/50。 原版目录键 3.8.4 实现向前看运算符。在“第3章 词法分析”的第41个正式坐标中，「3·8·4 实现向前看运算符」通过把“实现向前看运算符”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链推进词法边界、自动机与扫描状态；复核者保存第3章 词法分析的输入角色、中间状态、输出、反例与等价性证据，出现只复述“实现向前看运算符”名称而没有可观察状态、单故障和恢复验证就撤回结论。

3·9 基于DFA的模式匹配器的优化

正式坐标 42/50。 原版目录键 3.9 基于DFA的模式匹配器的优化。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标42把「3·9 基于DFA的模式匹配器的优化」落实为声明阶段接口、名字/类型/状态角色和源—目标语义映射；只有阶段快照、符号表、类型、IR谱系、诊断和源位置可重放且反例排除阶段边界丢失绑定、类型、控制依赖或源位置，本节点才算掌握。

3·9·1 NFA的重要状态

正式坐标 43/50。 原版目录键 3.9.1 NFA的重要状态。“第3章 词法分析”的目录节点43「3·9·1 NFA的重要状态」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·9·2 从语法树计算得到的函数

正式坐标 44/50。 原版目录键 3.9.2 从语法树计算得到的函数。对“第3章 词法分析”而言，「3·9·2 从语法树计算得到的函数」在第44次检查中改变可观察状态，因为它负责让产生式、推导、分析选择、语义动作和树/IR状态逐步对应；文法版本、分析栈、输入指针、树、属性和动作日志必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受分析选择或语义动作时点与文法依赖不一致。

3·9·3 计算nullable、firstpos和lastpos

正式坐标 45/50。 原版目录键 3.9.3 计算nullable、firstpos和lastpos。在“第3章 词法分析”的第45个正式坐标中，「3·9·3 计算nullable、firstpos和lastpos」通过把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来推进词法边界、自动机与扫描状态；复核者保存正则—NFA—DFA映射、状态轨迹、接受/回退与token流，出现规则优先级、最长匹配、预读或输入边界错误就撤回结论。

3·9·4 计算followpos

正式坐标 46/50。 原版目录键 3.9.4 计算followpos。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标46把「3·9·4 计算followpos」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

3·9·5 从正则表达式直接构造DFA

正式坐标 47/50。 原版目录键 3.9.5 从正则表达式直接构造DFA。“第3章 词法分析”的目录节点47「3·9·5 从正则表达式直接构造DFA」不能停在术语或伪码：它要把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，交付正则—NFA—DFA映射、状态轨迹、接受/回退与token流，并把规则优先级、最长匹配、预读或输入边界错误设为单一反事实。

3·9·6 最小化DFA的状态数

正式坐标 48/50。 原版目录键 3.9.6 最小化DFA的状态数。对“第3章 词法分析”而言，「3·9·6 最小化DFA的状态数」在第48次检查中改变可观察状态，因为它负责把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；正则—NFA—DFA映射、状态轨迹、接受/回退与token流必须与“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”对齐，不能接受规则优先级、最长匹配、预读或输入边界错误。

3·9·7 词法分析器中的状态最小化

正式坐标 49/50。 原版目录键 3.9.7 词法分析器中的状态最小化。在“第3章 词法分析”的第49个正式坐标中，「3·9·7 词法分析器中的状态最小化」通过声明阶段接口、名字/类型/状态角色和源—目标语义映射推进词法边界、自动机与扫描状态；复核者保存阶段快照、符号表、类型、IR谱系、诊断和源位置，出现阶段边界丢失绑定、类型、控制依赖或源位置就撤回结论。

3·9·8 DFA模拟中的时间和空间权衡

正式坐标 50/50。 原版目录键 3.9.8 DFA模拟中的时间和空间权衡。围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”，“第3章 词法分析”在坐标50把「3·9·8 DFA模拟中的时间和空间权衡」落实为把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来；只有正则—NFA—DFA映射、状态轨迹、接受/回退与token流可重放且反例排除规则优先级、最长匹配、预读或输入边界错误，本节点才算掌握。

先预测，再操作三个章专属实验

分步1 / 3

1. 输入、表示与翻译流水线

为“第3章 词法分析”选择正式目录坐标，在参考流水线与单一故障间切换，逐阶段核对输入、变换、输出和不变量。

输入—表示—翻译流水线

第3章 词法分析

选择正式目录坐标，再比较参考编译合同与单一故障的首个状态分岔。

阶段 1/4

第3章 词法分析 · 输入与表示

输入
让同一输入串经过手写扫描器、NFA模拟和DFA扫描器
变换
冻结词法边界、自动机与扫描状态所需的源程序、文法/IR/机器版本、shape和符号角色
输出证据
第3章 词法分析的输入合同、版本表与基线快照
不变量检查
第3章 词法分析的源位置、名字、类型、控制/数据依赖和可见性没有越界

第3章 词法分析的可重放协议

阶段允许动作必留证据拒绝条件
第3章 词法分析 · 输入与表示冻结词法边界、自动机与扫描状态所需的源程序、文法/IR/机器版本、shape和符号角色第3章 词法分析的输入合同、版本表与基线快照未满足“第3章 词法分析的源位置、名字、类型、控制/数据依赖和可见性没有越界”
第3章 词法分析 · 状态变换执行从词法规约、正则表达式、NFA/DFA、子集构造、直接构造、最小化到Lex实现可验证扫描器的最小算法并保存每一步状态第3章 词法分析的参考轨迹、故障轨迹与首个状态分岔未满足“第3章 词法分析每一步可由同一输入、规则、版本和顺序复算”
第3章 词法分析 · 输出与代价比较变换前后IR/目标状态、诊断、资源或分析精度第3章 词法分析的前后差、语义映射、代价和恢复路径未满足“第3章 词法分析没有把编译成功、分析收敛或单一基准加速当作完整正确性”
第3章 词法分析 · 独立验证重放预测、单故障、恢复和不适用边界第3章 词法分析的接受、回退或拒绝理由未满足“第3章 词法分析满足“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致””
unit: "dbc-unit-03"
question: "最长匹配、规则优先级、预读和自动机状态怎样共同决定token？"
scenario: "让同一输入串经过手写扫描器、NFA模拟和DFA扫描器"
invariant: "字符位置、词素边界、规则顺序、接受状态、回退与token属性一致"
fault: "提前接受较短规则，破坏最长匹配并吞错输入边界"
evidence: "正则—NFA—DFA映射、状态轨迹、token流与冲突案例"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

“第3章 词法分析”要求从同一源程序、文法/IR/机器版本、规则、预算和执行顺序重放参考、故障与恢复路径。重置后若目录选择、模式、阶段、轨迹步骤、案例、证据门或交付包没有回到基线，本次比较已经混入状态泄漏。

本页回顾

掌握“第3章 词法分析”不是背术语、表格或伪码，而是围绕“最长匹配、规则优先级、预读和自动机状态怎样共同决定token？”重建输入、表示、状态变换、输出、代价和独立验证，并用“字符位置、词素边界、规则顺序、接受状态、回退与token属性一致”拒绝“提前接受较短规则，破坏最长匹配并吞错输入边界”。最终交付为正则—NFA—DFA映射、状态轨迹、token流与冲突案例。

练习与答案

练习

  1. 问题 1：编译合同。 “第3章 词法分析”为什么必须先冻结源程序、文法/IR/机器版本、规则、预算和验证口径？
  1. 问题 2：目录逐项覆盖。 怎样证明“第3章 词法分析”的正式目录坐标已经进入机制、交互和练习？
  1. 问题 3：故障恢复。 怎样证明“提前接受较短规则，破坏最长匹配并吞错输入边界”已经被修正？

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

词法分析

检索键 dbc-A 对应正式目录坐标「第3章 词法分析」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析器的作用

检索键 dbc-B 对应正式目录坐标「3·1 词法分析器的作用」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析与语法分析

检索键 dbc-C 对应正式目录坐标「3·1·1 词法分析与语法分析」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法单元、模式和词素

检索键 dbc-D 对应正式目录坐标「3·1·2 词法单元、模式和词素」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法单元的属性

检索键 dbc-E 对应正式目录坐标「3·1·3 词法单元的属性」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法错误

检索键 dbc-F 对应正式目录坐标「3·1·4 词法错误」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

输入缓冲

检索键 dbc-G 对应正式目录坐标「3·2 输入缓冲」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

缓冲区对

检索键 dbc-H 对应正式目录坐标「3·2·1 缓冲区对」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

哨兵标记

检索键 dbc-I 对应正式目录坐标「3·2·2 哨兵标记」；在“第3章 词法分析”中用于追踪栈帧、非局部绑定、根集、堆对象和收集阶段，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法单元的规约

检索键 dbc-J 对应正式目录坐标「3·3 词法单元的规约」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

串和语言

检索键 dbc-K 对应正式目录坐标「3·3·1 串和语言」；在“第3章 词法分析”中用于把“串和语言”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

语言上的运算

检索键 dbc-L 对应正式目录坐标「3·3·2 语言上的运算」；在“第3章 词法分析”中用于把“语言上的运算”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

正则表达式

检索键 dbc-M 对应正式目录坐标「3·3·3 正则表达式」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

正则定义

检索键 dbc-N 对应正式目录坐标「3·3·4 正则定义」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

正则表达式的扩展

检索键 dbc-O 对应正式目录坐标「3·3·5 正则表达式的扩展」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法单元的识别

检索键 dbc-P 对应正式目录坐标「3·4 词法单元的识别」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

状态转换图

检索键 dbc-Q 对应正式目录坐标「3·4·1 状态转换图」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

保留字和标识符的识别

检索键 dbc-R 对应正式目录坐标「3·4·2 保留字和标识符的识别」；在“第3章 词法分析”中用于把“保留字和标识符的识别”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

完成运行示例

检索键 dbc-S 对应正式目录坐标「3·4·3 完成运行示例」；在“第3章 词法分析”中用于把“完成运行示例”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

基于状态转换图的词法分析器体系结构

检索键 dbc-T 对应正式目录坐标「3·4·4 基于状态转换图的词法分析器体系结构」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析器生成工具Lex

检索键 dbc-U 对应正式目录坐标「3·5 词法分析器生成工具Lex」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

Lex的使用

检索键 dbc-V 对应正式目录坐标「3·5·1 Lex的使用」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

Lex程序的结构

检索键 dbc-W 对应正式目录坐标「3·5·2 Lex程序的结构」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

Lex中的冲突解决

检索键 dbc-X 对应正式目录坐标「3·5·3 Lex中的冲突解决」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

向前看运算符

检索键 dbc-Y 对应正式目录坐标「3·5·4 向前看运算符」；在“第3章 词法分析”中用于把“向前看运算符”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

有穷自动机

检索键 dbc-Z 对应正式目录坐标「3·6 有穷自动机」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

不确定有穷自动机

检索键 dbc-AA 对应正式目录坐标「3·6·1 不确定有穷自动机」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

转换表

检索键 dbc-AB 对应正式目录坐标「3·6·2 转换表」；在“第3章 词法分析”中用于把“转换表”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

自动机对输入串的接受

检索键 dbc-AC 对应正式目录坐标「3·6·3 自动机对输入串的接受」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

确定有穷自动机

检索键 dbc-AD 对应正式目录坐标「3·6·4 确定有穷自动机」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

从正则表达式到自动机

检索键 dbc-AE 对应正式目录坐标「3·7 从正则表达式到自动机」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

从NFA到DFA的转换

检索键 dbc-AF 对应正式目录坐标「3·7·1 从NFA到DFA的转换」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

NFA的模拟

检索键 dbc-AG 对应正式目录坐标「3·7·2 NFA的模拟」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

NFA模拟的效率

检索键 dbc-AH 对应正式目录坐标「3·7·3 NFA模拟的效率」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

从正则表达式构造NFA

检索键 dbc-AI 对应正式目录坐标「3·7·4 从正则表达式构造NFA」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

字符串处理算法的效率

检索键 dbc-AJ 对应正式目录坐标「3·7·5 字符串处理算法的效率」；在“第3章 词法分析”中用于把“字符串处理算法的效率”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析器生成工具的设计

检索键 dbc-AK 对应正式目录坐标「3·8 词法分析器生成工具的设计」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

生成的词法分析器的结构

检索键 dbc-AL 对应正式目录坐标「3·8·1 生成的词法分析器的结构」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

基于NFA的模式匹配

检索键 dbc-AM 对应正式目录坐标「3·8·2 基于NFA的模式匹配」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析器使用的DFA

检索键 dbc-AN 对应正式目录坐标「3·8·3 词法分析器使用的DFA」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

实现向前看运算符

检索键 dbc-AO 对应正式目录坐标「3·8·4 实现向前看运算符」；在“第3章 词法分析”中用于把“实现向前看运算符”放进词法边界、自动机与扫描状态的输入—状态—变换—验证链，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

基于DFA的模式匹配器的优化

检索键 dbc-AP 对应正式目录坐标「3·9 基于DFA的模式匹配器的优化」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

NFA的重要状态

检索键 dbc-AQ 对应正式目录坐标「3·9·1 NFA的重要状态」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

从语法树计算得到的函数

检索键 dbc-AR 对应正式目录坐标「3·9·2 从语法树计算得到的函数」；在“第3章 词法分析”中用于让产生式、推导、分析选择、语义动作和树/IR状态逐步对应，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

计算nullable、firstpos和lastpos

检索键 dbc-AS 对应正式目录坐标「3·9·3 计算nullable、firstpos和lastpos」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

计算followpos

检索键 dbc-AT 对应正式目录坐标「3·9·4 计算followpos」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

从正则表达式直接构造DFA

检索键 dbc-AU 对应正式目录坐标「3·9·5 从正则表达式直接构造DFA」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

最小化DFA的状态数

检索键 dbc-AV 对应正式目录坐标「3·9·6 最小化DFA的状态数」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

词法分析器中的状态最小化

检索键 dbc-AW 对应正式目录坐标「3·9·7 词法分析器中的状态最小化」；在“第3章 词法分析”中用于声明阶段接口、名字/类型/状态角色和源—目标语义映射，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

DFA模拟中的时间和空间权衡

检索键 dbc-AX 对应正式目录坐标「3·9·8 DFA模拟中的时间和空间权衡」；在“第3章 词法分析”中用于把字符位置、正则规则、自动机状态、最长匹配和token属性连接起来，需要连接原版范围、状态轨迹、等价性证据和不适用边界。

复习本章（6 题）

讨论

评论区加载中…