词法分析
词法分析程序设计
词法分析程序和语法分析程序的接口方式
词法分析程序完成的是编译第一阶段的工作，可以有以下方法：
- 独立的一遍，把字符流的源程序变成单词序列，输出到一个中间文件，这个文件作为语法分析程序的输入而继续编译过程
- 词法分析程序每得到一次调用，就从源程序文件中读入一些字符，直到识别出一个单词，或者直到下一个单词的第一个字符为止。可以节省中间文件或存储区
![[images/截屏2026-04-08 10.08.57.png]]
词法分析程序输出
当语法分析程序接收到下一个单词的请求时，另词法分析程序从左到右读入源程序的字符流，以识别下一个单词。
在识别出下一个单词同时验证其词法正确性之后，词法分析程序将结果以单词符号的形式发送至语法分析程序以回应其请求；若发现词法错误则返回出错信息
单词分类
- 关键字/保留字
- 标识符
- 常数
- 运算符
- 界符
表达式
使用二元式表示：
$$
(\text{单词种类},\text{单词值})
$$
对于部分单词，除了需要值，还需要其他信息。如对标识符，还需要记录类别、层次以及其他属性，可以将这些属性全部收集在符号表中，设计成：
$$
(\text{标识符},\text{指向标识符在符号表中位置的指针})
$$
工作分离
为什么将分析拆分成词法分析和语法分析：
- 使编译程序的结构更简洁
- 提高编译程序的效率
- 增强编译程序的可移植性
识别单词
识别有意义的单词符号，依赖于程序设计语言的词法规则描述，确保没有歧义性
描述工具
- 状态转换图
- 扩展巴克斯范式（EBNF）
- 有限状态自动机
- 正规表达式
- 正规文法
几乎任何一种有意义的单词种别对应的单词集合都是正规语言
PL/0 词法分析程序设计
对单词的一种 EBNF 描述
<无符号整数> ::= <数字>{<数字>}
<标识符> ::= <字母>{<字母>|<数字>}
<字母> ::= a|b|...|X|Y|Z
<数字> ::= 0|1|...|9
<保留字> ::= const|var|procedure|begin|end|odd|if|then|call|while|do|read|write
<运算符> ::= +|-|*|/|#|<|<=|>|>=|:=
<界符> ::= (|)|,|;|.
保留字、运算符、界符仅包含有限个单词符号，所以将每个单词符号设计为独立的词法单元（即每个单词符号有独立的种别）
enum symbol {
nul, ident, number, plus, minus,
times, slash, oddsym, eql, neq,
lss, leq, gtr, geq, lparen,
rparen, comma, semicolon, period, becomes,
beginsym, endsym, ifsym, thensym, whilesym,
writesym, readsym, dosym, callsym, constsym,
varsym, procsym,
};
nul 表示不能识别的符号
对于
$$
\text{position}:=\text{initial}+\text{rate}*60
$$
扫描生成：
$$
\text{ident}\ \text{becomes}\ \text{ident}\ \text{plus}\ \text{ident}\ \text{times}\ \text{number}\ \text{semicolon}
$$
词法分析程序定义
PL/0 语法分析程序在需要读取下一个单词时，就调用 getsym() 返回下一个单词符号
int getsym()
词法分析器的实现
实现方案
词法分析器（Lexical Analyzer 或 Scanner）的实现有多种方案：
1. 手工编码
- 直接编写代码：根据单词的描述手工编写状态转换逻辑
- 优点：灵活，可以针对性优化，效率高
- 缺点：开发工作量大，易出错，维护困难
- 适用场景：简单的词法规则，对性能要求极高的场景
2. 基于状态转换表
- 预先构造转换表：将状态转换图转换为二维表
- 表驱动的识别程序：通用的表驱动代码 + 特定的转换表
- 优点：结构清晰，易于维护，便于自动生成
- 缺点：表可能很大（状态数 × 字符集大小）
- 适用场景：复杂的词法规则，需要自动化工具生成
3. 自动生成工具
- 词法分析器生成器：如 Lex、Flex、ANTLR
- 输入：正规表达式描述的词法规则
- 输出：C/Java 等语言的词法分析器代码
- 优点：开发效率极高，错误少，易于修改
- 缺点：可能不如手工优化的代码高效
- 适用场景：主流方案，适合绝大多数编译器项目
状态转换表实现
数据结构
状态转换表：二维数组 trans[state][char]
- 行：状态
- 列：输入符号
- 值：下一状态（或错误标记）
#define NUM_STATES 10
#define NUM_CHARS 128 // ASCII 字符集
int trans[NUM_STATES][NUM_CHARS]; // 转换表
bool is_final[NUM_STATES]; // 是否为终止状态
TokenType token_type[NUM_STATES]; // 每个终止状态对应的单词类型
表驱动的识别算法
Token get_next_token(char *input, int *pos) {
int state = START_STATE;
int start_pos = *pos;
int last_final_pos = -1; // 最后一次到达终止状态的位置
TokenType last_token_type = NONE;
while (input[*pos] != '\0') {
char ch = input[*pos];
int next_state = trans[state][ch];
if (next_state == ERROR_STATE) {
// 无法继续，检查是否已识别出单词
if (last_final_pos != -1) {
// 回退到最后一次终止状态
*pos = last_final_pos + 1;
return create_token(last_token_type, start_pos, last_final_pos);
} else {
// 词法错误
return create_error_token(*pos);
}
}
state = next_state;
(*pos)++;
// 记录终止状态
if (is_final[state]) {
last_final_pos = *pos - 1;
last_token_type = token_type[state];
}
}
// 输入结束
if (is_final[state]) {
return create_token(token_type[state], start_pos, *pos - 1);
} else if (last_final_pos != -1) {
*pos = last_final_pos + 1;
return create_token(last_token_type, start_pos, last_final_pos);
} else {
return create_error_token(*pos);
}
}
最长匹配原则
词法分析通常采用最长匹配（Maximal Munch）原则：
- 总是匹配尽可能长的单词
- 例如：
ifx应识别为标识符ifx，而不是关键字if+ 标识符x
实现方法：
- 记录到达终止状态的位置（
last_final_pos） - 继续尝试匹配，直到无法继续
- 回退到最后一次终止状态
优化技术
1. 压缩转换表
状态转换表可能很大（例如 100 个状态 × 128 个字符 = 12.8KB），可以压缩：
方法 1：字符类（Character Classes）
- 将具有相同转换行为的字符归为一类
- 例如：所有字母归为
LETTER类，所有数字归为DIGIT类 - 压缩后：100 个状态 × 20 个字符类 = 2KB
enum CharClass { LETTER, DIGIT, PLUS, MINUS, ..., OTHER };
CharClass char_to_class(char ch) {
if (isalpha(ch)) return LETTER;
if (isdigit(ch)) return DIGIT;
if (ch == '+') return PLUS;
// ...
return OTHER;
}
// 压缩后的转换表
int trans[NUM_STATES][NUM_CHAR_CLASSES];
方法 2：稀疏表表示
- 大部分条目是 ERROR_STATE（非法转换）
- 只存储有效转换：
(state, char) → next_state - 使用哈希表或链表表示
2. 直接编码状态转换
对于小型 DFA，可以将每个状态编码为一个函数或 switch-case 分支：
int state_0(char ch) {
if (isalpha(ch)) return STATE_ID;
if (isdigit(ch)) return STATE_NUM;
if (ch == '+') return STATE_PLUS;
// ...
return ERROR_STATE;
}
int state_id(char ch) {
if (isalnum(ch)) return STATE_ID;
return ERROR_STATE; // 识别完成
}
这种方式：
- 避免了数组查找
- 编译器可以优化（如跳转表）
- 代码可读性较差，但效率最高
3. 缓冲区优化
词法分析需要频繁读入字符，I/O 操作很慢，可以使用双缓冲区技术：
Buffer 1: [已读完] → 正在处理
Buffer 2: [正在加载下一块数据]
当 Buffer 1 读完时，切换到 Buffer 2，同时异步加载新数据到 Buffer 1。
词法分析中的常见问题
1. 关键字与标识符的冲突
问题：关键字（如 if、while）和标识符都满足”字母开头，后跟字母或数字”的模式，如何区分？
解决方案：
- 方法 1：先识别为标识符，再查表判断是否为关键字
Token identify(char *lexeme) { if (strcmp(lexeme, "if") == 0) return TOKEN_IF; if (strcmp(lexeme, "while") == 0) return TOKEN_WHILE; // ... 其他关键字 return TOKEN_ID; // 不是关键字，是标识符 } - 方法 2：在 DFA 中为每个关键字单独设置一条路径
- 优点：识别时直接判定
- 缺点：状态数增加
最佳实践：使用哈希表或完美哈希存储关键字，查找时间 O(1)。
2. 注释的处理
问题：注释不是语法分析需要的单词，应该在词法分析阶段过滤掉。
C 风格注释：/* ... */ 和 // ...
// 处理 // 注释（单行）
if (ch == '/' && next_char() == '/') {
while (ch != '\n' && ch != EOF) {
ch = next_char();
}
continue; // 跳过，不返回 Token
}
// 处理 /* */ 注释（多行）
if (ch == '/' && next_char() == '*') {
while (!(ch == '*' && next_char() == '/') && ch != EOF) {
ch = next_char();
}
next_char(); // 跳过 '/'
continue;
}
嵌套注释（Pascal 风格）：
- 需要计数器记录嵌套层次
- 遇到
(*时level++，遇到*)时level-- level == 0时注释结束
3. 空白符的处理
空白符：空格、制表符、换行符等分隔单词，但本身不是单词。
处理方式：
// 跳过空白符
while (isspace(ch)) {
if (ch == '\n') {
line_number++; // 记录行号，用于错误报告
}
ch = next_char();
}
特殊情况：Python 等语言中，缩进（空白符）有语义意义，需要特殊处理。
4. 向前看（Lookahead）
问题：某些单词的识别需要”向前看”一个或多个字符。
示例：
- C 语言中
++、+=、+的识别 - 读到
+时，需要看下一个字符：- 下一个是
+→++（自增） - 下一个是
=→+=（加赋值） - 下一个是其他 →
+（加法）
- 下一个是
实现：
if (ch == '+') {
ch = next_char();
if (ch == '+') {
return TOKEN_INC; // ++
} else if (ch == '=') {
return TOKEN_PLUS_ASSIGN; // +=
} else {
retract(); // 回退一个字符
return TOKEN_PLUS; // +
}
}
回退（Retract）：
- 记录当前位置
- 读入下一个字符判断
- 如果不匹配，回退到记录位置
5. 错误处理与恢复
词法错误：无法识别的字符或字符序列。
错误处理策略：
- 报告错误位置：行号、列号
- 输出错误信息：如 “非法字符 ‘@’ “
- 尝试恢复：
- 跳过非法字符，继续分析
- 或删除、替换、插入字符以修复错误
if (state == ERROR_STATE) {
fprintf(stderr, "词法错误：行 %d，列 %d，非法字符 '%c'\n",
line, column, ch);
ch = next_char(); // 跳过错误字符，继续分析
}
Lex/Flex 词法分析器生成器
Lex/Flex 简介
Lex（Lexical Analyzer Generator）和 Flex（Fast Lexical Analyzer Generator）是经典的词法分析器生成工具。
- 输入：扩展名为
.l的规则文件 - 输出：C 语言的词法分析器代码（通常是
lex.yy.c） - 用法：
flex scanner.l # 生成 lex.yy.c gcc lex.yy.c -lfl # 编译 ./a.out < input.txt # 运行
Lex 文件的结构
Lex 文件分为三部分，用 %% 分隔：
%{
/* 定义段：C 代码，头文件、全局变量等 */
#include <stdio.h>
int line_num = 1;
%}
/* 辅助定义：正规表达式的缩写 */
digit [0-9]
letter [a-zA-Z]
id {letter}({letter}|{digit})*
%%
/* 规则段：模式-动作对 */
{id} { printf("ID: %s\n", yytext); }
{digit}+ { printf("NUMBER: %s\n", yytext); }
"+" { printf("PLUS\n"); }
"-" { printf("MINUS\n"); }
"*" { printf("TIMES\n"); }
"/" { printf("DIVIDE\n"); }
[ \t]+ { /* 忽略空白符 */ }
\n { line_num++; }
. { printf("ERROR: 非法字符 '%s'\n", yytext); }
%%
/* 辅助函数段：C 代码，main() 等 */
int main() {
yylex(); // 启动词法分析
return 0;
}
int yywrap() {
return 1; // 返回 1 表示输入结束
}
Lex 中的特殊变量和函数
yytext：指向当前识别出的单词（字符串）yyleng：当前单词的长度yylineno：当前行号（需要在定义段添加%option yylineno）yylex()：主词法分析函数，返回 Token 类型yywrap()：输入结束时调用，返回 0 表示继续，返回 1 表示结束
Lex 的正规表达式
Lex 支持扩展的正规表达式语法：
| 语法 | 含义 |
|---|---|
x |
字符 x |
. |
除换行符外的任意字符 |
[xyz] |
字符 x、y 或 z 之一 |
[a-z] |
a 到 z 的任意字符 |
[^a-z] |
除 a 到 z 外的任意字符 |
r* |
0 个或多个 r |
r+ |
1 个或多个 r |
r? |
0 个或 1 个 r（可选） |
r{n} |
恰好 n 个 r |
r{n,m} |
n 到 m 个 r |
rs |
r 后跟 s（连接） |
r|s |
r 或 s（选择） |
(r) |
分组 |
^r |
行首的 r |
r$ |
行尾的 r |
r/s |
r 后跟 s，但只匹配 r（向前看） |
Lex 的冲突解决规则
当多个模式都能匹配当前输入时，Lex 使用以下规则：
- 最长匹配优先（Longest Match）
- 总是选择匹配最长的模式
- 先定义优先（First Match）
- 如果多个模式匹配相同长度，选择在
.l文件中先定义的
- 如果多个模式匹配相同长度，选择在
示例：
if { return IF; }
{id} { return ID; }
输入 if：匹配第一条规则（关键字），不是标识符。
输入 ifx：只能匹配第二条规则（标识符）。
Lex 与 Yacc/Bison 的配合
Lex 通常与语法分析器生成器 Yacc/Bison 配合使用：
scanner.l（词法分析器）：
%{
#include "parser.tab.h" // Yacc 生成的头文件
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
"+" { return PLUS; }
"-" { return MINUS; }
[ \t\n]+ { /* 忽略空白 */ }
%%
parser.y（语法分析器）：
%{
#include <stdio.h>
int yylex();
void yyerror(char *s);
%}
%token NUMBER PLUS MINUS
%%
expr: expr PLUS term { $$ = $1 + $3; }
| term { $$ = $1; }
;
term: NUMBER { $$ = $1; }
;
%%
编译：
flex scanner.l
bison -d parser.y
gcc lex.yy.c parser.tab.c -o calculator
总结与实践建议
词法分析的核心知识
理论基础：
- 正规表达式、正则文法、有限自动机三者等价
- Thompson 构造法（RE → NFA）、子集构造法（NFA → DFA）、最小化算法
实现技术：
- 状态转换表驱动
- 最长匹配原则
- 向前看与回退
实用工具：
- Lex/Flex（C/C++）
- ANTLR（Java/Python/C++/…）
- 手工编写（小项目、特殊需求）
设计词法分析器的步骤
- 定义单词类别：关键字、标识符、常数、运算符、界符
- 描述词法规则：用正规表达式或 EBNF
- 选择实现方案：手工 or Lex/Flex
- 处理特殊情况：注释、空白符、关键字、错误恢复
- 优化：压缩转换表、缓冲区优化、字符类
- 测试：边界情况、错误输入、性能测试
学习建议
动手实践：
- 用 Lex/Flex 为简单语言（如计算器）编写词法分析器
- 手工实现一个小型词法分析器（如识别标识符、数字、运算符）
阅读经典代码：
- GCC、Clang 的词法分析器源码
- 教材配套的 PL/0 编译器源码
理解设计权衡：
- 何时用自动生成工具？何时手工编写？
- 如何在效率和可维护性之间平衡？
与语法分析结合：
- 词法分析只是编译的第一步
- 学习 Yacc/Bison，理解词法与语法的接口
单词的形式化描述工具
正则文法（Regular Grammar）是描述词法单元的重要工具，属于 3 型文法（最严格的文法类型）。
定义
正则文法分为右线性文法和左线性文法：
右线性文法：产生式形如
$$
A\rightarrow aB\ \ 或\ \ A\rightarrow a
$$
其中 $A,B\in V_N$，$a\in V_T$
左线性文法：产生式形如
$$
A\rightarrow Ba\ \ 或\ \ A\rightarrow a
$$
特点
- 只能线性展开，不能嵌套递归
- 右线性文法和左线性文法等价（生成同样的语言）
- 正则文法生成的语言称为正规语言（Regular Language）
示例
描述标识符的右线性文法：
$$
\begin{aligned}
A&\rightarrow aA\ |\ bA\ |\ …\ |\ zA\ |\ AA\ |\ BA\ |\ …\ |\ ZA \
A&\rightarrow a\ |\ b\ |\ …\ |\ z\ |\ A\ |\ B\ |\ …\ |\ Z
\end{aligned}
$$
简写为：
$$
\begin{aligned}
A&\rightarrow \text{letter}\ A\ |\ \text{digit}\ A \
A&\rightarrow \text{letter}\ |\ \text{digit}
\end{aligned}
$$
其中 $\text{letter}$ 表示任意字母，$\text{digit}$ 表示任意数字
正规表达式
正规表达式（Regular Expression，简称正则表达式或 Regex）是描述正规语言的另一种方式，比正则文法更简洁直观。
定义
设 $\Sigma$ 是字母表，$\Sigma$ 上的正规表达式及其表示的正规集合递归定义如下：
基础规则：
- $\varepsilon$ 是正规表达式，表示集合 ${\varepsilon}$
- $\phi$ 是正规表达式，表示空集 ${}$
- 对于 $\forall a\in\Sigma$，$a$ 是正规表达式，表示集合 ${a}$
归纳规则：若 $r$ 和 $s$ 是正规表达式，分别表示集合 $L(r)$ 和 $L(s)$，则：
- 并（选择）：$r|s$ 是正规表达式，表示 $L(r)\cup L(s)$
- 连接：$rs$ 是正规表达式，表示 $L(r)L(s)={xy|x\in L(r), y\in L(s)}$
- 闭包（重复）：$r^$ 是正规表达式，表示 $L(r)^={\varepsilon}\cup L(r)\cup L(r)L(r)\cup…$
运算符优先级
从高到低：闭包 $*$ > 连接 > 并 $|$
例如：$ab^|c$ 等价于 $(a(b^))|c$
常用简写
- $r^+$：表示 $rr^$（至少一次重复），即 $L(r)^+=L(r)L(r)^$
- $r?$：表示 $r|\varepsilon$（可选，出现 0 次或 1 次）
- $[a_1a_2…a_n]$：表示 $a_1|a_2|…|a_n$（字符类）
- $[a-z]$：表示字母 $a$ 到 $z$ 的所有字符
- $[0-9]$：表示数字 $0$ 到 $9$ 的所有字符
- $[^a]$：表示除 $a$ 外的任意字符（补集）
示例
标识符（以字母开头，后跟字母或数字）：
$$
\text{letter}(\text{letter}|\text{digit})^*
$$或简写为：$[a\text{-}zA\text{-}Z][a\text{-}zA\text{-}Z0\text{-}9]^*$
无符号整数：
$$
\text{digit}\ \text{digit}^*\ \ 或\ \ \text{digit}^+
$$简写为：$[0\text{-}9]^+$
实数：
$$
\text{digit}^+.\text{digit}^|\text{digit}^.\text{digit}^+
$$C 语言的注释（
/* ... */）：
$$
/\ast(\text{非}\ast|\ast\text{非}/)^*\ast/
$$
正规表达式与正则文法的等价性
定理：正规表达式和正则文法描述的语言类是相同的，都是正规语言。
这意味着：
- 任何正规表达式都可以转换为等价的正则文法
- 任何正则文法都可以转换为等价的正规表达式
有限自动机
有限自动机（Finite Automaton，FA）是识别正规语言的抽象计算模型，也是实现词法分析器的理论基础。
定义
有限自动机是一个五元组 $M=(Q,\Sigma,\delta,q_0,F)$：
- $Q$：有限的状态集合
- $\Sigma$：有限的输入符号字母表
- $\delta$：状态转换函数
- $q_0\in Q$：初始状态
- $F\subseteq Q$：终止状态集合（也叫接受状态或最终状态）
分类
1. 确定有限自动机（DFA，Deterministic Finite Automaton）
特点：
- 对于任意状态 $q$ 和输入符号 $a$，最多有一个转换 $\delta(q,a)=p$
- 不存在 $\varepsilon$ 转换（空转换）
- 在任何时刻，自动机都处于唯一确定的状态
状态转换函数：$\delta:Q\times\Sigma\rightarrow Q$
工作过程：
- 从初始状态 $q_0$ 开始
- 读入一个输入符号 $a$
- 根据 $\delta(q,a)$ 转到新状态
- 重复步骤 2-3，直到输入串读完
- 如果最终状态 $\in F$，则接受该串；否则拒绝
2. 非确定有限自动机（NFA，Nondeterministic Finite Automaton）
特点：
- 对于某个状态 $q$ 和输入符号 $a$，可能有多个转换
- 可能存在 $\varepsilon$ 转换（不读入任何符号就能转换状态）
- 同一时刻，自动机可能处于多个状态的”叠加”
状态转换函数：$\delta:Q\times(\Sigma\cup{\varepsilon})\rightarrow 2^Q$（返回状态集合）
工作过程：
- 从初始状态集合 ${q_0}$ 开始
- 对于当前状态集合中的每个状态，尝试所有可能的转换
- 如果至少有一条路径能使输入串被读完且最终状态 $\in F$，则接受该串
DFA 示例
识别以 $01$ 结尾的二进制串
状态转换图：
0 1 0
→(q0) → (q1) → ((q2))
↓ ↑
└───────┘
1
- 圆圈表示状态，双圈
((q2))表示终止状态 - 箭头
→表示初始状态
状态转换表：
| 当前状态 | 输入 0 | 输入 1 |
|---|---|---|
| $q_0$ | $q1$ | $q_0$ |
| $q_1$ | $q_1$ | $q_2$ |
| $q_2$ | $q_1$ | $q_0$ |
运行示例：
- 输入串
101：$q_0\xrightarrow{1}q_0\xrightarrow{0}q_1\xrightarrow{1}q_2$ ✓ 接受 - 输入串
100：$q_0\xrightarrow{1}q_0\xrightarrow{0}q_1\xrightarrow{0}q_1$ ✗ 拒绝
NFA 示例
识别包含子串 $01$ 的二进制串
状态转换图：
0,1 0 1
→(q0) ⇒ (q1) → ((q2))
↓ ↑
└────────────────┘
0,1
- 双线箭头
⇒表示可能有多条路径（非确定性）
在状态 $q_0$ 看到 $0$ 时，可以选择：
- 留在 $q_0$（等待子串 $01$ 的出现）
- 转到 $q_1$（认为子串 $01$ 开始了）
这就是”非确定性”：同时探索多条路径，只要有一条成功就接受。
DFA 与 NFA 的关系
定理：对于任何 NFA，都存在一个等价的 DFA（接受相同的语言）。
子集构造法（Subset Construction）：将 NFA 转换为 DFA
- DFA 的每个状态对应 NFA 的一个状态集合
- DFA 的初始状态对应 NFA 初始状态的 $\varepsilon$-闭包
- 转换关系根据 NFA 的所有可能转换计算
实践意义：
- NFA 更容易从正规表达式构造（构造简单）
- DFA 更容易实现（执行效率高）
- 词法分析器的实现：正规表达式 → NFA → DFA → 最小化 DFA → 代码
正规表达式、有限自动机、正则文法的关系
这三种描述工具等价，都能描述正规语言：
正规表达式 ⇄ 有限自动机 ⇄ 正则文法
↘ ↓ ↙
正规语言
转换关系
正规表达式 → NFA（Thompson 构造法）
- 对基本正规表达式构造基本 NFA
- 对复合正规表达式递归构造复合 NFA
NFA → DFA（子集构造法）
- 使用状态集合表示 DFA 的状态
- 计算 $\varepsilon$-闭包
DFA → 最小化 DFA（状态最小化算法）
- 合并等价状态
- 减少状态数量
DFA → 正规表达式（状态消除法）
- 逐步消除中间状态
- 用正规表达式标记转换
正则文法 ⇄ 有限自动机
- 状态对应非终结符
- 转换对应产生式
Thompson 构造法：正规表达式转 NFA
Thompson 构造法是一种系统化的方法，将任何正规表达式转换为等价的 NFA。
基本思想
为每种正规表达式的构造方式提供一个对应的 NFA 模板，然后递归组合。
基本规则
空串 $\varepsilon$：
→(i) ─ε→ ((f))单个符号 $a$：
→(i) ─a→ ((f))
归纳规则
假设 $N(r)$ 和 $N(s)$ 分别是正规表达式 $r$ 和 $s$ 对应的 NFA：
并（选择）$r|s$：
ε ┌─ N(r) ─┐ ε →(i) ──┬───→ └────────┘ ───┬→ ((f)) └─ε→ ┌─ N(s) ─┐ ε──┘ └────────┘- 新的初始状态 $i$ 通过 $\varepsilon$ 转换到 $N(r)$ 和 $N(s)$ 的初始状态
- 两个 NFA 的终止状态通过 $\varepsilon$ 转换到新的终止状态 $f$
连接 $rs$：
→(i) ─ N(r) ─ ε ─ N(s) ─→ ((f))- 将 $N(r)$ 的终止状态和 $N(s)$ 的初始状态合并（或用 $\varepsilon$ 连接）
闭包 $r^*$：
┌────── ε ──────┐ ↓ ↓ →(i) ─┴→ ┌─ N(r) ─┐ ─┴→ ((f)) └────────┘ ↓ ↑ └─ε─→┘- $\varepsilon$ 从 $i$ 直接到 $f$（0 次重复）
- $\varepsilon$ 从 $f$ 回到 $N(r)$ 的初始状态（多次重复）
构造示例
为正规表达式 $(a|b)^*abb$ 构造 NFA
步骤分解：
- $a$ 和 $b$ 的基本 NFA
- $a|b$ 的 NFA（并操作）
- $(a|b)^*$ 的 NFA（闭包操作）
- $abb$ 的 NFA（连接操作）
- $(a|b)^*abb$ 的 NFA（连接操作）
最终 NFA 大约有 10 个状态。
Thompson 构造法的特点
- 优点：
- 构造过程系统化，易于实现
- 生成的 NFA 状态数 $\leq 2\times(\text{正规表达式中运算符和操作数的总数})$
- 缺点：
- 生成的 NFA 包含大量 $\varepsilon$ 转换
- 状态数较多，需要后续优化（转 DFA、最小化）
子集构造法：NFA 转 DFA
子集构造法（Subset Construction，也叫幂集构造法）将 NFA 转换为等价的 DFA。
核心思想
- NFA 的不确定性：在某个状态读入某个符号时，可能转到多个状态
- DFA 的确定性要求：每个状态读入每个符号，最多转到一个状态
- 解决方案：让 DFA 的一个状态对应 NFA 的一个状态集合
关键概念
1. $\varepsilon$-闭包（$\varepsilon$-closure）
状态 $s$ 的 $\varepsilon$-闭包 $\varepsilon\text{-closure}(s)$ 是从 $s$ 出发，只通过 $\varepsilon$ 转换能到达的所有状态的集合（包括 $s$ 本身）。
状态集合 $T$ 的 $\varepsilon$-闭包：
$$
\varepsilon\text{-closure}(T)=\bigcup_{s\in T}\varepsilon\text{-closure}(s)
$$
计算方法（深度优先搜索或广度优先搜索）：
function ε-closure(T):
stack = T
result = T
while stack is not empty:
s = stack.pop()
for each state t with s -ε→ t:
if t not in result:
result.add(t)
stack.push(t)
return result
2. move 操作
$\text{move}(T,a)$ 表示从状态集合 $T$ 中的某个状态出发，通过符号 $a$ 能到达的所有状态的集合（不考虑 $\varepsilon$ 转换）。
$$
\text{move}(T,a)=\bigcup_{s\in T}{t|s\xrightarrow{a}t}
$$
子集构造算法
输入：NFA $N=(Q_N,\Sigma,\delta_N,q_0,F_N)$
输出：DFA $D=(Q_D,\Sigma,\delta_D,q_{0D},F_D)$
算法步骤：
1. 初始化：
q₀_D = ε-closure({q₀}) // DFA 的初始状态
Q_D = {q₀_D} // DFA 的状态集合
WorkList = {q₀_D} // 待处理的状态队列
2. while WorkList 非空:
T = WorkList.pop()
for each 输入符号 a ∈ Σ:
U = ε-closure(move(T, a))
if U 非空:
δ_D(T, a) = U
if U ∉ Q_D:
Q_D.add(U)
WorkList.add(U)
3. F_D = {T | T ∈ Q_D 且 T ∩ F_N ≠ ∅}
// 包含 NFA 终止状态的 DFA 状态集合都是终止状态
子集构造示例
NFA：识别以 $abb$ 结尾的串（假设已从正规表达式 $(a|b)^*abb$ 构造得到）
简化的 NFA（状态编号 0-3）：
状态 0: -a→ {0,1}, -b→ {0}
状态 1: -b→ {2}
状态 2: -b→ {3}
状态 3: 终止状态
构造 DFA：
| DFA 状态 | NFA 状态集合 | 输入 a | 输入 b |
|---|---|---|---|
| A | {0} | B | A |
| B | {0,1} | B | C |
| C | {0,2} | B | D |
| D | {0,3} | B | A |
其中状态 D 是终止状态（包含 NFA 的终止状态 3）。
子集构造法的复杂度
- 最坏情况：DFA 的状态数可达 $2^{|Q_N|}$（NFA 状态集合的幂集）
- 实际情况：通常远少于最坏情况，很多状态集合不可达
DFA 的最小化
即使经过子集构造，得到的 DFA 仍可能包含冗余状态。DFA 最小化算法通过合并等价状态，得到状态数最少的等价 DFA。
等价状态
两个状态 $p$ 和 $q$ 等价，当且仅当：
- 对于任意输入串 $w$，从 $p$ 和 $q$ 出发，要么都到达终止状态，要么都到达非终止状态
如果 $p$ 和 $q$ 等价，可以合并为一个状态。
Hopcroft 最小化算法（基本思想）
核心思想：反向思考——找出可区分的状态对，剩下的就是等价的。
算法步骤（简化版）：
1. 初始划分：将状态分为两组
- 终止状态 F
- 非终止状态 Q \ F
2. 重复以下步骤，直到划分不再改变：
for each 状态组 G:
for each 输入符号 a:
检查 G 中的状态在读入 a 后是否转到同一组
if 不是，将 G 分裂成多个子组
3. 每个最终的状态组合并为一个状态
最小化示例
原 DFA（部分状态可能等价）：
状态: {A, B, C, D, E}
终止状态: {E}
转换:
A -a→ B, A -b→ C
B -a→ B, B -b→ D
C -a→ B, C -b→ C
D -a→ B, D -b→ E
E -a→ B, E -b→ C
初始划分：${A,B,C,D}$ 和 ${E}$
第 1 轮：
- 检查 ${A,B,C,D}$ 对 $a$：都转到 $B$ ✓
- 检查 ${A,B,C,D}$ 对 $b$：$A\rightarrow C, B\rightarrow D, C\rightarrow C, D\rightarrow E$
- $E$ 是终止状态，$C$ 不是，所以 $D$ 和其他状态可区分
- 分裂为 ${A,B,C}$ 和 ${D}$
第 2 轮：继续细分… 最终得到最小 DFA。
最小化的意义
- 减少状态数：更小的状态转换表
- 提高效率：词法分析器运行更快
- 唯一性：对于给定语言，最小 DFA 是唯一的（同构意义下）
状态转换图
状态转换图（State Transition Diagram）是有限自动机的图形化表示，也是实现词法分析器的直观工具。
组成元素
- 状态（圆圈）：表示识别过程中的不同阶段
- 初始状态（带箭头的圆圈）：分析开始的状态
- 终止状态（双圆圈）：识别成功的状态
- 转换（带标记的箭头）：读入某个符号后的状态变化
示例
识别标识符的状态转换图
letter
┌──────────┐
↓ │
→(start) ─letter→ ((id))
↑ │
└────┘
letter|digit
- 状态
start：初始状态 - 状态
id：终止状态（识别出标识符） - 转换条件：
start读入letter转到idid读入letter或digit保持在id- 读入其他字符（如空格、运算符）：停止，识别成功
从状态转换图到代码
状态转换图可以直接翻译为程序代码：
enum State { START, ID };
enum State recognize_identifier(char *input) {
enum State state = START;
int i = 0;
char ch = input[i];
while (ch != '\0') {
switch (state) {
case START:
if (isalpha(ch)) {
state = ID;
i++;
ch = input[i];
} else {
return ERROR; // 不是标识符
}
break;
case ID:
if (isalnum(ch)) {
i++;
ch = input[i];
} else {
return ID; // 识别成功，ch 是后续字符
}
break;
}
}
return state; // 返回最终状态
}
多单词类型的状态转换图
实际的词法分析器需要识别多种单词类型，可以将它们组合在一个状态转换图中：
digit
┌──────┐
↓ │
→(start) ─digit→ ((number))
│
letter
↓
(A) ─letter|digit→ ((id))
↑ │
└───────────────────┘
letter|digit
[其他状态省略：运算符、界符等]
这种统一的状态转换图对应一个完整的词法分析器（Scanner）