编译原理第二章：词法分析

2.0 总览

2.0.1 词法分析的位置

词法分析不是孤立的，它属于整个编译前端的一环。

• 编译过程（Compiling Process）为了把一种语言翻译成另一种语言
• 编译器先要拆开并理解程序，再重新组织输出
• 前端做 analysis（分析），
• Lexical analysis：把输入分成 token
  • 词法分析只负责“切词”
  • 不负责理解完整语法
  • 更不负责程序语义
• Syntax analysis：分析语法结构
• Semantic analysis：分析程序意义
• IR（中间表示）把前端和后端隔开
• 后端做 synthesis（综合）

这一章的核心问题其实只有一个：

如何把“字符流”变成“单词流（token 流）”？

也就是：源码明明只是一个个字符，编译器为什么能知道：

• if 是关键字
• match0 是标识符
• 0.0 是实数
• ( 是左括号
• 空格和注释该忽略

这一章的路线是：

1. 先理解 token 是什么
2. 再用 正则表达式（RE） 描述 token
3. 再用 有限自动机（FA） 实现这些规则
4. 然后引入 NFA
5. 再把 NFA 变成 DFA
6. 再把 DFA 最小化
7. 最后说明为什么现实里常用 Lex/flex 自动生成词法分析器

自然语言描述 → 正则表达式 → 自动机 → 词法分析器实现。

2.0.2. 词法分析器的任务：

• 输入：字符流
• 输出：token 流
• 会识别：
• 名字（identifier）
• 关键字（keyword）
• 标点符号（punctuation）
• 会丢弃：
• 空白符
• 注释

课件给了一个例子：

 float match0(char *s) /* find a zero */
 { 
     if (!strncmp(s, "0.0", 3))
    return 0.; 
} 

这段 C 程序会被拆成

FLOAT  ID(match0)  LPAREN  CHAR STAR ID(s) RPAREN 
LBRACE  
    IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN  RPAREN
    RETURN REAL(0.0) SEMI 
RBRACE
EOF 

2.0.3. 接口

词法分析器的接口通常像一个函数，例如：

• getToken()
• 或 yylex()

每调用一次，就返回下一个 token。

为什么要用形式化工具来研究词法分析：

• 因为后面语法分析也会用类似形式化方法
• 而且这些工具不只在编译里有用，例如日志解析

2.1 Lexical Token

2.1.1. 定义 lexical token

• token 是一段字符序列
• 它是编程语言语法中的一个单位
• token 类型是有限集合

例子：

Token	例子
ID	foo n14 last
NUM	73 0 00 515 082
REAL	66.1 .5 10. 1e67 5.5e-10
IF	if
COMMA	,
NOTEQ	!=
LPAREN	(
RPAREN	)

2.1.2. 词法分析器的输出

2.1.2.1. 输出包含什么

这里用具体程序演示 token 化结果，还是这个例子：

 float match0(char *s) /* find a zero */
 { 
     if (!strncmp(s, "0.0", 3))
    return 0.; 
} 

这段 C 程序会被拆成

FLOAT  ID(match0)  LPAREN  CHAR STAR ID(s) RPAREN 
LBRACE  
    IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN  RPAREN
    RETURN REAL(0.0) SEMI 
RBRACE
EOF 

这里可见：

• 词法分析器不仅返回 token 的类型
• 有些 token 还带语义值（semantic value）

例如：

• ID(match0)：类型是 ID，值是 match0
• NUM(3)：类型是 NUM，值是 3
• REAL(0.0)：类型是 REAL，值是 0.0

也就是说：

token 不只是标签，还可能带“附加信息”。

2.1.2.2. 输出不包含什么？

• 源码里有的东西，不一定都变成 token

• 一部分内容会被直接忽略或提前处理掉。

• 预处理器会先处理某些内容

• 词法分析器面对的是预处理后的字符流

• 保留字不能当标识符，比如IF、VOID、RETURN

• 什么东西不是 token：注释、预处理指令、宏、空格、tab、换行

2.2. 正则表达式

2.2.0. 词法分析器的实现&为什么需要正则表达式

已经知道输入和输出了，那词法分析器怎么实现？

答案是：先要描述语言的词法规则。

2.2.0.1. 如何描述词法规则

这里用 C/Java 的标识符规则举例，说明“自然语言版词法规则”：

1. 标识符由字母和数字组成
2. 第一个字符必须是字母
3. _ 算字母
4. 大小写不同
5. 下一个 token 要取尽可能长的字符串
6. 最长匹配（longest match）：能多吃就多吃。
7. 空白和注释一般忽略，但有时空白用于分隔相邻 token

2.2.0.2. 如何实现词法分析器

1. ad hoc lexer：手写任何编程语言来实现
2. 这样十分繁琐
3. 更简单的方法
4. regular expressions：用正则描述 token
   • 易懂，但直接实现麻烦
5. deterministic finite automata：用 DFA 实现 lexer
   • 容易实现，但手工从规则构造不方便
6. 数学把两者连接起来

2.2.0.3. “从规则到程序”的总路线

1. 自然语言描述 lexical tokens

2. 将自然语言转成 regular expression

3. regular expression 转成 deterministic finite automata

4. 最后按照 DFA 实现 lexer

2.2 Regular Expression

2.2.1 基础概念：

• language：字符串集合
• string：符号的有限序列

• symbol：来自有限字母表的元素

• 这里先不讨论字符串意义

• 只讨论“它属不属于这个集合”

比如：

• C 语言关键字集合是一个语言
• 所有合法标识符也是一个语言

定义正则表达式的作用：

• 正则表达式可以用有限描述表示某些可能无限的语言
• 每个正则表达式 r 表示一个正规语言 L(r)

2.2.2. 正则表达式的定义

2.2.2.1. 定义

定义两种最基本的正则：

• 普通符号 a

• 表示只含字符串 "a" 的语言

• ε

• 表示只含空串 "" 的语言

定义两个组合操作：

• Alternation（并/选择）：M | N
• 属于 L(M) 或 L(N) 的字符串都算

• a|b 表示 {a, b}

• Concatenation（连接）：M · N

• 先来自 M，后来自 N
• (a|b)·a 表示 {aa, ba}

定义 Kleene closure（Kleene 星号）：

• M* 表示 M 中字符串重复 0 次或多次

• ((a|b)·a)*可以表示 {"", "aa", "ba", "aaaa", "baaa", "aaba", "baba", "aaaaaa", …}

它可以表示无限多个字符串，因为重复次数不受限。

例题：

• (0|1)*·0 表示二进制中所有能被 2 整除的数

• b*(abb*)*(a|ε)：由 a 和 b 构成且没有连续两个 a

• (a|b)*aa(a|b)*：所有包含连续 aa 的由 a,b 构成的字符串

.：任意单个字符（通常不含换行）

"<一个字符串>"：引用，表示字符串自身

2.2.2.2. 规则

讲正则简写规则和优先级：

• * 绑定最紧

• 连接比 | 更紧

• ab|c 其实是 (a·b)|c

• (a|) 其实是 (a|ε)

2.2.2.3. 缩写

缩写不增加表达能力

• [abcd] 等价于 (a|b|c|d)
• [b-g] 是区间等价于 [bcdefg]
• [b-gM-Qkr] 等价于 [bcdefgMNOPQkr]
• M? 等价于 (M|ε)
• M+ 等价于 M·M*

2.2.3. 用正则描述 token

2.2.3.1. 示例

正则表达式	行为
遇到if	做{return IF;}
遇到[a-z][a-z0-9]*	做{return ID;}
[0-9]+ | {return NUM;}
([0-9]+"."[0-9]*)|([0-9]*"."[0-9]+)	实数规则
注释和空白的规则	匹配后“不做事”
非法字符	报错

2.2.3.2. 词法规则必须完整

• 就是任何输入字符都应该被某条规则处理到。
• 所以最后要放一个“兜底规则”：
• 任何单字符都能匹配到
• 如果不是合法字符，就报错

2.2.3.3. 正则规则会有歧义：

• if8 应该识别为 IF + 8，还是一个 ID？
• if 89 开头的 if 应该识别成保留字还是标识符？

2.2.3.3.1. 消歧规则：

1. Longest match（最长匹配）

2. 取能匹配任一正则的最长前缀。

3. Rule priority（规则优先级）

4. 如果同一个最长前缀可被多条规则匹配，则取最先写的规则。

于是：

• if8 按最长匹配，应识别为 ID
• if 本身同时符合 IF 和 ID，按规则顺序，识别为 IF

2.3. Finite Automata

正则适合描述 token，但真正计算机程序实现时，更适合用有限自动机

2.3.1. 有限自动机形式定义：

一个自动机包含：

• 有限的状态集合 S
• 字母表 Σ
• 转移函数 move
• 初始状态 s0
• 终态集合 F

自动机图的画法：

• 圆圈表示状态
• 双圆表示终态
• 从外面指向某状态的箭头表示初态
• 一条边标多个字符是多条平行边的简写

2.3.1. DFA（确定有限自动机）：

2.3.1.1. 定义

• 同一状态出发，不能有两条相同字符标记的边

DFA 如何接受字符串：

1. 从初态出发
2. 对每个输入字符走唯一一条边
3. 所有字符读完后若停在终态，则接受
4. 否则拒绝

每一步都没有歧义，只有一个下一步。

2.3.1.2. 合并

现在有 6 个分开的自动机，怎么合成一个真正的词法分析器？

真正 lexer 不能每种 token 单独一台机器，而要合成成一台总机器。

每个终态标记它识别的 token 类型

解释组合后的状态 I：

• 它同时像 IF 自动机里的I
• 也像 ID 自动机里的I
• 因为后者是终态，所以合并后也必须是终态

这说明合并自动机时，一个状态可能同时继承多个“角色”。

2.3.1.3. 如何把自动机编码成程序：

• 用一个转移矩阵 trans[state][char]，表示在 state 状态的时候遇到字符 char 的时候应该如何转移。

• 没有边时用 dead state（死状态）0

• 死状态对所有字符都回到自己

• 再用一个 finality array 记录哪些终止状态对应什么动作

2.3.1.4. 自动机运行

维护两个变量：

• Last-Final
• Input-Position-at-Last-Final

每进入一个终态就更新这两个变量。 当走到死状态时，就知道：

• 最近一次成功匹配是什么 token
• 它在什么位置结束

例如：

• 识别出 IF
• 遇到空白时跳过并继续
• 某些非法字符（如 - 在不合法位置）会报错然后继续

• 说明自动机并不是只识别一个 token，而是不断：

  1. 从当前位置开始

  2. 找最长匹配

  3. 输出一个 token 或执行忽略动作

  4. 从下一个位置继续

2.4. NFA

• NFA
• Thompson 构造
• 子集构造
• DFA 最小化

2.4.1.定义NFA（非确定有限自动机）

• 同一状态在同一输入符号下，可以去多个不同状态
• 还允许 ε-边
• ε-边不消耗输入字符

这是 NFA 和 DFA 的本质区别。

• 有 ε-边时，即使当前有正常字符边，也可以先走 ε-边
• ε-边不消耗字符

这让 NFA 更灵活，也更容易构造。

定义 NFA 如何接受字符串：

只要存在某一条可能路径最终到达终态，NFA 就接受。

和 DFA 的区别是：

• DFA：唯一运行路径
• NFA：只要有一条成功路径就行

2.4.2. Thompson 构造

2.4.2.1. 意义

RE 到 NFA 很容易，这就是 Thompson 构造的价值

如果我们知道：

1. 基本正则如何转成基本 NFA

2. 正则的三种构造操作如何在 NFA 上模拟

那么任意正则都能转成 NFA。

2.4.2.2. 流程

每个正则 M 都会对应一个带 tail（起始边） head（终止状态）的 NFA 片段。

这是最关键的 Thompson 构造规则图。它给出：

• a 如何转 NFA
• ε 如何转 NFA
• M|N 如何转 NFA
• M·N 如何转 NFA
• M* 如何转 NFA
• M+ 视作 M·M*
• M? 视作 M|ε
• [abc]

• "abc"

• 并：新建开始和结束，用 ε 分叉/汇合

• 连接：把前一个的尾和后一个的头接起来
• 闭包：允许回环和跳过

2.4.3. 子集构造，NFA 转 DFA

2.4.3.1. 运算定义

ε-closure： - 对一个状态集合 S - closure(S) 是只走 ε-边、不消耗输入所能到达的全部状态集合

并定义：

• edge(s,c)：从状态 s 走一条标记为 c 的边能到达的状态集合

DFAedge： - \(DFAedge(d,c)=closure\left(\bigcup_{s\in d} edge(s,c)\right)\)

1. 从 d 中每个状态出发
2. 走一条 c 边
3. 把所有结果合并
4. 再把这些状态的 ε-closure 全部补齐

2.4.3.2. 子集构造

DFA 的一个状态，其实可以看成 NFA 状态集合。

例子中：

• 先算 closure({1}) = {1,4,9,14}
• 读入 i 后得到新的状态集合
• 再读 n 后得到新的状态集合

• 最终接受

• 从 d1 = closure({s1}) 开始

• 对每个状态集合 d 和每个输入符号 c
• 计算 d' = DFAedge(d,c)（经过边 c 可以到达的所有状态集合）
• 不断重复，直到没有新状态集合出现

这就是子集构造的核心过程。这样构造出的机器就是 DFA： - 状态：所有可达的 NFA 状态集合 - 转移：DFAedge(d,c) - 字母表不变 - 初态：d1 - 终态：包含某个 NFA 终态的那些集合

若 NFA 有 n 个状态，理论上最多会有 2^n 个集合状态，因为状态集合只能变大，NFA 状态总数有限，迭代计算 closure(S)一定终止。

2.4.4. DFA 最小化

子集构造得到的是“能用的 DFA”，不一定是“最省的 DFA”。

2.4.4.1. 等价状态：

两个状态 s1 和 s2 等价，当且仅当：

• 从 s1 出发接受某串 σ
• 当且仅当从 s2 出发也接受 σ

它们可合并。

这是最小化的本质：找出“行为完全一样”的状态，合并它们。

2.4.4.2. 算法思想

一个“看起来合理但不充分”的判定条件： - 同时都是终态或同时都不是终态 - 且每个输入字符转移到的目标一样

这个条件不够一般： - 某些状态虽然目标状态名字不同 - 但这些目标状态本身是等价的 - 所以原状态仍可能等价

判断等价不能只看一步，要看“未来所有行为”。

---

2.4.4.2.1. distinguishable states（可区分状态）：

若存在字符串 x，使得：

• 从 s 出发读 x 后到终态
• 从 t 出发读 x 后不到终态

或反过来，

那 x 就区分了 s 和 t。

所以：

• 能被某个串区分开的状态，不等价
• 不能被任何串区分开的状态，才等价

这是最小化的逻辑基础。

2.4.4.2.2. 最小化算法的思想：

• 先把显然不同的状态分开
• 再不断细分分组
• 直到不能再分

具体思想：

1. 终态和非终态先分开
2. 若两个状态经过某输入后会落入不同组，它们也应分开
3. 最后每组中的状态互相等价

2.4.4.2.3. 正式算法：

1. 初始划分 Π = {S-F, F}
2. 对 Π 中每个组 G：
3. 若组内状态在某些输入字符下转移到不同组
4. 就把 G 再细分
5. 如果新划分和旧划分一样，结束；否则继续

这是最小化的标准 partition-refinement 算法。

划分结束后如何重建最小 DFA：

• 每个最终分组挑一个代表状态
• 最小 DFA 的状态就是这些代表
• 原初态所属组的代表成为新初态
• 含终态的组代表成为新终态
• 转移按“代表的目标组代表”来连

词法分析中特别重要的修正：

普通 DFA 最小化里，所有终态可以先放在一个组里。 但词法分析器里不行，因为不同终态可能对应不同 token 类型。

例如：

• 一个终态表示 IF
• 另一个终态表示 ID

它们即使“结构上像”，也不能合并。

所以词法分析器的初始划分不是：

• {S-F, F}

而应是：

• {S-F, F1, F2, ..., Fk}

其中 Fi 是识别同一种 token 的终态集合。

2.5 Lex: A Lexical Analyzer Generator：

现在要落到词法分析的工具：Lex

为什么会有 Lex：

• DFA 构造是机械劳动
• 适合让计算机自动完成
• 所以有 lexical-analyzer generator
• Lex 能把正则规格说明自动翻译成 DFA，并生成 C 程序

Lex 生成的结果：

• 会产生一个 C 函数 yylex
• 它就像 getToken
• 本质是一个表驱动的 DFA 实现
• 最流行版本是 flex

Lex 输入文件 a.l 的三段结构：

{ definitions }
%%
{ rules }
%%
{ auxiliary routines }

• %{ ... %} 放 C 代码
• digit [0-9]
• number {digit}+
• 规则中把十进制转成十六进制输出
• main() 调用 yylex()

这一页很关键，因为它把“理论规则”变成了“工具输入格式”。

---

2.5.1. 第一部分 definitions：

• 在第一个 %% 之前
• %{...%} 中可写 C 头文件、全局变量等
• 后面可写正则缩写、状态声明

例如：

%{ 
#include <stdlib.h>
#include <stdio.h>
int count = 0;
%}
digit [0-9]
number {digit}+

2.5.2. 第二部分 rules：

• 每条规则由：
• 一个正则表达式
• 一个动作（C 代码片段）
• 当正则匹配时执行对应动作
• yytext：当前匹配到的字符串
• yyleng：匹配长度

例如：

{ number } { int n = atoi (yytext);
            printf(“%x”, n);
            if (n > 9) count ++; }

2.5.3. 第三部分 auxiliary routines：

• 放辅助函数
• 比如 main()
• 或规则里调用但别处没定义的函数

也就是说，这是普通 C 代码补充区。

main( )
 { yylex ( );
 fprintf(stdeer, “number of replacements = %d”, count);
 return 0;
 }