第2章词法分析

从词元、正则、有限自动机和生成器实现Tiger词法分析项目；用C编译流水线、状态轨迹和端到端验证门交付正则—自动机映射、状态轨迹、token流与错误位置

学习目标

能说明“第2章词法分析”如何从词元、正则、有限自动机和生成器实现Tiger词法分析项目，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“字符位置、最长匹配、规则优先级和token属性怎样逐步对应？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“较短规则提前接受，破坏最长匹配并错分Tiger标识符”，定位首个偏离“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第2章词法分析”围绕“字符位置、最长匹配、规则优先级和token属性怎样逐步对应？”建立贯穿任务：在Tiger C实现轨道中复现“第2章词法分析”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付正则—自动机映射、状态轨迹、token流与错误位置，单模块测试、编译成功或性能变化才构成机制证据。

原版书目、296个正式坐标与C轨道边界

“第2章词法分析”以Andrew W. Appel作者官方目录核对 Modern Compiler Implementation 的C、Java、ML三种实现轨道、2部分、21章和Tiger语言附录；以作者C版页面核对Andrew·W·Appel与Maia Ginsburg、Cambridge University Press、C实现轨道、平装ISBN 0-521-60765-5、软件/练习模块与勘误入口，再以Cambridge C版页面核对原版身份。

“第2章词法分析”以中文版修订版完整目录核对赵克佳、黄春、沈志宇译《现代编译原理：C语言描述（修订版）》，人民邮电出版社，2018年，385页，ISBN 9787115476883。“第2章词法分析”的正式分母为2个部分标题、21个章标题、1个附录标题、251个编号节/小节、附录4节和17个正式“程序设计”项目，合计296个核心层级；每章重复的推荐阅读与习题不另计。

作者页面可访问不等于允许复制书稿，“第2章词法分析”不复制、翻译或改写原文、图表、伪码与习题；所有中文讲解、C接口示意、状态轨迹、反例、交互、练习和答案均为独立教学重写。本页独立核对 1只用于核对本页C实现或现代IR边界，不能混入Java/ML轨道或反向证明原书采用本站表述。

原版目录层级与C项目机制

第2章词法分析

正式坐标 1/9。 原版目录键 第2章词法分析。在“第2章词法分析”的第1个正式坐标中，「第2章词法分析」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进Tiger扫描器、自动机与词元边界；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。

2·1 词法单词

正式坐标 2/9。 原版目录键 2.1 词法单词。围绕“字符位置、最长匹配、规则优先级和token属性怎样逐步对应？”，“第2章词法分析”在坐标2把「2·1 词法单词」落实为把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；只有正则—自动机、token流、项目集、分析表、栈轨迹与冲突可重放且反例排除最长匹配、展望符、冲突或恢复状态错误，本节点才算掌握。

2·2 正则表达式

正式坐标 3/9。 原版目录键 2.2 正则表达式。“第2章词法分析”的目录节点3「2·2 正则表达式」不能停在术语或伪码：它要把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，交付正则—自动机、token流、项目集、分析表、栈轨迹与冲突，并把最长匹配、展望符、冲突或恢复状态错误设为单一反事实。

2·3 有限自动机

正式坐标 4/9。 原版目录键 2.3 有限自动机。对“第2章词法分析”而言，「2·3 有限自动机」在第4次检查中改变可观察状态，因为它负责把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；正则—自动机、token流、项目集、分析表、栈轨迹与冲突必须与“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受最长匹配、展望符、冲突或恢复状态错误。

2·4 非确定有限自动机

正式坐标 5/9。 原版目录键 2.4 非确定有限自动机。在“第2章词法分析”的第5个正式坐标中，「2·4 非确定有限自动机」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进Tiger扫描器、自动机与词元边界；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。

2·4·1 将正则表达式转换为NFA

正式坐标 6/9。 原版目录键 2.4.1 将正则表达式转换为NFA。围绕“字符位置、最长匹配、规则优先级和token属性怎样逐步对应？”，“第2章词法分析”在坐标6把「2·4·1 将正则表达式转换为NFA」落实为把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；只有正则—自动机、token流、项目集、分析表、栈轨迹与冲突可重放且反例排除最长匹配、展望符、冲突或恢复状态错误，本节点才算掌握。

2·4·2 将NFA转换为DFA

正式坐标 7/9。 原版目录键 2.4.2 将NFA转换为DFA。“第2章词法分析”的目录节点7「2·4·2 将NFA转换为DFA」不能停在术语或伪码：它要把“将NFA转换为DFA”放进Tiger扫描器、自动机与词元边界的C接口—状态—变换—验证链，交付第2章词法分析的输入角色、中间状态、输出、反例与整合证据，并把只复述“将NFA转换为DFA”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

2·5 Lex：词法分析器的生成器

正式坐标 8/9。 原版目录键 2.5 Lex：词法分析器的生成器。对“第2章词法分析”而言，「2·5 Lex：词法分析器的生成器」在第8次检查中改变可观察状态，因为它负责把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；正则—自动机、token流、项目集、分析表、栈轨迹与冲突必须与“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受最长匹配、展望符、冲突或恢复状态错误。

程序设计：词法分析

正式坐标 9/9。 原版目录键 程序设计：词法分析。在“第2章词法分析”的第9个正式坐标中，「程序设计：词法分析」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进Tiger扫描器、自动机与词元边界；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。

先预测，再操作三个C轨道实验

分步1 / 3

1. C模块、输入与翻译流水线

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

输入—表示—翻译流水线

第2章词法分析

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

正式目录坐标

阶段 1/4

第2章词法分析 · C模块与输入

输入: 在Tiger C实现轨道中复现“第2章词法分析”的输入、状态、变换与验证
变换: 冻结Tiger扫描器、自动机与词元边界所需的C接口、源程序、规则、数据结构和版本
输出证据: 第2章词法分析的模块合同、输入快照与所有权表
不变量检查: 第2章词法分析的类型、所有权、源位置、名字和接口布局没有错位

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

阶段	允许动作	必留证据	拒绝条件
第2章词法分析 · C模块与输入	冻结Tiger扫描器、自动机与词元边界所需的C接口、源程序、规则、数据结构和版本	第2章词法分析的模块合同、输入快照与所有权表	未满足“第2章词法分析的类型、所有权、源位置、名字和接口布局没有错位”
第2章词法分析 · 算法与状态	执行从词元、正则、有限自动机和生成器实现Tiger词法分析项目的最小算法并保存每一步状态	第2章词法分析的参考轨迹、故障轨迹与首个状态分岔	未满足“第2章词法分析每一步可由同一C接口、输入、规则和执行顺序复算”
第2章词法分析 · 输出与整合	比较变换前后AST/IR/汇编/运行时状态和跨模块传递	第2章词法分析的前后差、接口谱系与恢复路径	未满足“第2章词法分析没有把单模块通过或单一样例正确当作端到端正确性”
第2章词法分析 · 独立验证	重放预测、单故障、恢复和不适用边界	第2章词法分析的接受、回退或拒绝理由	未满足“第2章词法分析满足“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致””

unit: "tbc-unit-02"
question: "字符位置、最长匹配、规则优先级和token属性怎样逐步对应？"
scenario: "在Tiger C实现轨道中复现“第2章 词法分析”的输入、状态、变换与验证"
invariant: "第2章 词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "较短规则提前接受，破坏最长匹配并错分Tiger标识符"
evidence: "正则—自动机映射、状态轨迹、token流与错误位置"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

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

本页回顾

掌握“第2章词法分析”不是背术语、表格或伪码，而是围绕“字符位置、最长匹配、规则优先级和token属性怎样逐步对应？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“较短规则提前接受，破坏最长匹配并错分Tiger标识符”。最终交付为正则—自动机映射、状态轨迹、token流与错误位置。

练习与答案

练习

问题 1：C实现合同。 “第2章词法分析”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第2章词法分析”的正式目录坐标已经进入机制、交互和程序设计项目？

“第2章词法分析”的目录项「第2章词法分析」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·1 词法单词」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·2 正则表达式」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·3 有限自动机」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·4 非确定有限自动机」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·4·1 将正则表达式转换为NFA」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「2·4·2 将NFA转换为DFA」：以“把“将NFA转换为DFA”放进Tiger扫描器、自动机与词元边界的C接口—状态—变换—验证链”解释作用，用“第2章词法分析的输入角色、中间状态、输出、反例与整合证据”提供复核。 8. “第2章词法分析”的目录项「2·5 Lex：词法分析器的生成器」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第2章词法分析”的目录项「程序设计：词法分析」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。

问题 3：故障恢复。 怎样证明“较短规则提前接受，破坏最长匹配并错分Tiger标识符”已经被修正？

为“第2章词法分析”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和正则—自动机映射、状态轨迹、token流与错误位置重新满足“第2章词法分析的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

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

词法分析: 检索键 tbc-A 对应正式目录坐标「第2章词法分析」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
词法单词: 检索键 tbc-B 对应正式目录坐标「2·1 词法单词」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
正则表达式: 检索键 tbc-C 对应正式目录坐标「2·2 正则表达式」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
有限自动机: 检索键 tbc-D 对应正式目录坐标「2·3 有限自动机」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
非确定有限自动机: 检索键 tbc-E 对应正式目录坐标「2·4 非确定有限自动机」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
将正则表达式转换为NFA: 检索键 tbc-F 对应正式目录坐标「2·4·1 将正则表达式转换为NFA」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
将NFA转换为DFA: 检索键 tbc-G 对应正式目录坐标「2·4·2 将NFA转换为DFA」；在“第2章词法分析”中用于把“将NFA转换为DFA”放进Tiger扫描器、自动机与词元边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
Lex: 检索键 tbc-H 对应正式目录坐标「2·5 Lex：词法分析器的生成器」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
词法分析: 检索键 tbc-I 对应正式目录坐标「程序设计：词法分析」；在“第2章词法分析”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第2章 词法分析

学习目标

为什么从这个问题开始

原版书目、296个正式坐标与C轨道边界

原版目录层级与C项目机制

第2章 词法分析

2·1 词法单词

2·2 正则表达式

2·3 有限自动机

2·4 非确定有限自动机

2·4·1 将正则表达式转换为NFA

2·4·2 将NFA转换为DFA

2·5 Lex：词法分析器的生成器

程序设计：词法分析

先预测，再操作三个C轨道实验

1. C模块、输入与翻译流水线

第2章 词法分析

第2章 词法分析 · C模块与输入

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

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第2章词法分析

第2章词法分析

第2章词法分析

第2章词法分析 · C模块与输入

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