第2章 词法分析

词法分析（Lexical Analysis / Scanning）将源程序字符流转换为记号（token）流，是编译器前端的第一步。

2.1 扫描处理

记号（Token）

扫描程序生成的逻辑单元，表示源程序中的信息单元。每个记号有一个类型和可选的属性值。

• 关键字：if, while, for 等固定串
• 标识符：用户定义的名字（字母开头，字母数字组成）
• 特殊符号：+, *, >=, <> 等单字符或多字符符号
• 数字常量：整型、浮点型
• 字符串文字

缓冲区与先行

• 使用双缓冲区处理大源程序
• 单符号先行（single symbol lookahead）：一次只生成一个记号
• 最长子串原则：任何时候能构成记号的最长字符串被视为下一个记号
• 遇到分隔符时需回退（backing up）或提前查看（lookahead）

保留字 vs 标识符

• 方法一：先识别为标识符，再查保留字表（TINY 使用此法）
• 方法二：在 DFA 中直接区分
• 保留字查找：线性搜索 → 二分搜索 → 杂凑表 → 最小完美杂凑函数

2.2 正则表达式

正则表达式表示字符串的模式。一个正则表达式完全由它匹配的串的集合定义，该集合称为语言，写作 L(r)。

基本运算

常用正则表达式示例

标识符:    letter (letter | digit)*
数字常量:  digit+ (. digit+)? (E (+|-)? digit+)?
注释:      /* ([^*] | *+[^/])* */

代数定律

• r | s = s | r（交换律）
• r | (s | t) = (r | s) | t（结合律）
• r (s t) = (r s) t（并置结合律）
• r (s | t) = r s | r t（分配律）
• r ε = ε r = r
• r** = r*

扩展表示法

• r+：一个或多个重复
• .：匹配任意字符
• [0-9]、[a-zA-Z]：字符范围
• ~a：不在给定集合中的字符
• r?：可选子表达式

2.3 有穷自动机

DFA（确定的有穷自动机）

每个状态对每个输入符号有唯一确定的转换。

![[编译原理/attachments/figures/ch02_s32_2.3.1 Definite of Deterministic finite a.png]]

图中英文：letter=字母，digit=数字，other=其他，始态→接受态表示标识符识别过程

![[编译原理/attachments/figures/ch02_s36_2.3.1 Definite of Deterministic finite a.png]]

图中英文：start=初始状态，accept=接受状态，a, b=输入字符

![[编译原理/attachments/figures/ch02_s41_Deterministic finite automation (DFA).png]]

图中英文：无特殊术语，为 DFA 状态转换示例

五元组：(S, Σ, δ, s0, F)

• S：状态集合
• Σ：输入字母表
• δ：转移函数 S × Σ → S
• s0：初始状态
• F：接受状态集合

NFA（非确定的有穷自动机）

![[编译原理/attachments/figures/ch02_s51_NFA (Nondeterministic Finite Automaton).png]]

图中英文：NFA=Nondeterministic Finite Automaton（非确定有穷自动机），input=输入，state=状态，ε=空串转移

• 一个状态对同一输入可能有多个转换
• 允许 ε-转换（不消费字符的转移）
• NFA 通常比 DFA 更紧凑

NFA → DFA 转换（子集构造法）

算法要点：
1. NFA 每个状态子集 → DFA 的一个状态
2. ε-闭包(s)：从 s 出发仅通过 ε 转移能到达的所有状态
3. 对于每个子集 T 和每个输入符号 a：
   DFAstate(T, a) = ε-闭包(所有从 T 中状态通过 a 到达的状态)

ε-闭包计算

ε-闭包(T):
   将 T 中所有状态入栈
   栈非空时:
      出栈 → t
      对 t 的每条 ε 转移到达 u:
          若 u 不在闭包中:
              添加 u, u 入栈
   返回闭包集合

DFA 状态最小化（划分法）

1. 初始分两组: 接受状态组 F, 非接受状态组 S-F
2. 重复:
      对每组 G, 若存在字符 a 使组内状态经 a 转移
      到不同的组 → 拆分 G
3. 直到无法继续拆分

2.4 从正则表达式到 DFA

正则表达式 →[Thompson 构造]→ NFA →[子集构造法]→ DFA →[最小化]→ 最小 DFA

Thompson 构造（正则 → NFA）

2.5 TINY 扫描程序的实现

![[编译原理/attachments/figures/ch02_s87_FA of TINY.png]]

图中英文：letter=字母，digit=数字，other=其他，TINY DFA 中标识符和数字的识别路径

• 用 DFA 实现（双重嵌套 case 语句）
• 主过程：getToken() — 根据当前状态和输入字符进行状态转换
• 保留字表：TINY 只有 8 个保留字（if, then, else, end, repeat, until, read, write）
• 使用 ungetNextChar() 处理超前读取后的回退

2.6 Lex 扫描程序生成器

• Lex 输入文件结构：定义部分 %% 规则部分 %% 用户子程序
• 规则格式：模式 { 动作 }
• Lex 用正则表达式描述模式，自动构造 DFA
• 生成的扫描程序输出为 C 代码

考试重点

★★★ 第一梯队（必考）

★★☆ 第二梯队

★☆☆ 第三梯队