第3章 词法分析

导读

词法分析是编译过程的第一个阶段，也是编译器与源代码直接接触的环节。它的任务是将源代码的字符流转换为记号流，为后续的语法分析奠定基础。词法分析看似简单——不就是把字符拼成单词吗？但实际上，词法分析涉及了丰富的形式语言理论，特别是正则表达式和有限自动机。

本章将系统地介绍词法分析的理论和实践。我们将从正则表达式开始，学习如何用形式化的方法描述词法规则；然后介绍有限自动机（包括NFA和DFA），学习如何将正则表达式转换为自动机；最后讨论词法分析器的自动生成工具（如Lex/Flex），以及词法分析中的各种实际问题。

通过本章的学习，你将理解为什么 123abc 在某些语言中是合法的（数字后面跟标识符），而在另一些语言中是不合法的；你将理解为什么正则表达式 [a-z]+ 能够匹配所有小写字母组成的字符串；你将理解词法分析器是如何高效地工作的，以及为什么它的效率对编译器的整体性能至关重要。

核心概念详解

3.1 词法分析的基本概念

词法分析器（Lexical Analyzer），也称为扫描器（Scanner）或词法扫描器（Lexical Scanner），是编译器的第一个阶段。它的主要功能包括：

读取源程序的字符流

将字符流组织成有意义的词素（lexeme）

为每个词素产生相应的记号（token）

过滤掉空白字符和注释

将错误信息与源代码行号关联

基本术语定义：

• 记号（Token）：一个分类标签，表示一类词素。如 ID、NUM、IF、PLUS 等。
• 词素（Lexeme）：源程序中匹配某个记号的具体字符序列。如 count、123、if 等。
• 模式（Pattern）：描述记号对应的词素应满足的规则的表达式。如 [a-zA-Z_][a-zA-Z0-9_]* 描述标识符的模式。

以语句 int count = 10; 为例：

3.2 正则表达式

正则表达式（Regular Expression）是描述词法规则的标准工具。它基于字母表上的运算来定义语言（字符串的集合）。

正则表达式的递归定义：

给定字母表 Σ，Σ 上的正则表达式及其定义的语言如下：

基础表达式：

- ε 是正则表达式，表示语言 {ε}（只包含空串）

- ∅ 是正则表达式，表示语言 {}（空集）

- 对于每个 a ∈ Σ，a 是正则表达式，表示语言 {a}

归纳构造：

- 如果 r 和 s 是正则表达式，则以下也是正则表达式：

- r|s（选择/并）：表示语言 L(r) ∪ L(s)

- rs（连接）：表示语言 L(r) · L(s)

- r*（克林闭包）：表示语言 L(r)*

- (r)（分组）：表示语言 L(r)

- r+（正闭包）：表示语言 L(r)+（一个或多个重复）

- r?（可选）：表示语言 L(r) ∪ {ε}

常用正则表达式示例：

标识符:     [a-zA-Z_][a-zA-Z0-9_]*
整数:       [0-9]+
浮点数:     [0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
字符串:     "([^"\\]|\\.)*"
注释:       \/\*([^*]|\*[^/])*\*\/
C风格注释:  \/\/.*
空白:       [ \t\n\r]+

正则表达式的代数定律：

正则表达式满足以下重要的代数定律：

3.3 有限自动机

有限自动机（Finite Automaton）是正则表达式的计算模型。它是一种具有有限个状态的抽象机器，用于识别（接受）正则语言。

确定有限自动机（DFA）：

一个DFA是一个五元组 (Q, Σ, δ, q₀, F)，其中：

• Q 是有限状态集
• Σ 是输入字母表
• δ: Q × Σ → Q 是转移函数
• q₀ ∈ Q 是初始状态
• F ⊆ Q 是接受状态集

DFA的特点：

• 每个状态对每个输入符号恰好有一个转移
• 没有ε转移（不消耗输入的状态转移）
• 对于任何输入串，DFA的运行路径是唯一确定的

非确定有限自动机（NFA）：

一个NFA也是一个五元组 (Q, Σ, δ, q₀, F)，但转移函数不同：

• δ: Q × (Σ ∪ {ε}) → P(Q)（Q的幂集）

NFA的特点：

• 一个状态对同一个输入符号可以有多个转移
• 可以有ε转移
• 对于输入串，NFA可能有多条运行路径，只要有一条到达接受状态就接受

DFA与NFA的等价性：

虽然NFA看起来比DFA更强大，但两者实际上是等价的——它们识别的语言类完全相同，都是正则语言。任何NFA都可以通过子集构造法（Subset Construction）转换为等价的DFA。

子集构造法的核心思想：DFA的每个状态对应NFA的一个状态子集。DFA在读取输入符号a后从状态S转移到状态T，其中T是NFA中从S中任意状态出发经过a（可能先经过ε转移）能到达的所有状态的集合。

3.4 从正则表达式到词法分析器

构建词法分析器的标准流程：

正则表达式 → NFA → DFA → 最小化DFA → 词法分析器代码

步骤1：正则表达式转NFA（Thompson构造法）

Thompson构造法为每个正则表达式子表达式构建一个NFA片段，然后组合：

正则表达式 ε:    (0) --ε--> ((1))

正则表达式 a:    (0) --a--> ((1))

正则表达式 rs:   NFA(r) --ε--> NFA(s)

正则表达式 r|s:  (start) --ε--> NFA(r) --ε--> (accept)
                         --ε--> NFA(s) --ε--> (accept)

正则表达式 r*:   (start) --ε--> NFA(r) --ε--> (accept)
                 (start) --ε--> (accept)
                 (accept) --ε--> NFA(r)

步骤2：NFA转DFA（子集构造法）

算法: NFA到DFA的转换
输入: NFA N
输出: DFA D

Dstart = ε-closure(Nstart)
Dstates = {Dstart}
标记 Dstart 为未处理

while Dstates 中存在未标记状态 T:
    标记 T
    for 每个输入符号 a:
        U = ε-closure(move(T, a))
        if U 不在 Dstates 中:
            将 U 加入 Dstates，标记为未处理
        Dtran[T, a] = U

for 每个状态 T:
    if T 包含 NFA 的接受状态:
        标记 T 为 DFA 的接受状态

步骤3：DFA最小化

DFA最小化的目标是找到状态数最少的等价DFA。算法基于划分细化（Partition Refinement）：

初始划分：将状态分为接受状态组和非接受状态组

细化：对于每个组G和每个输入符号a，如果G中的状态在a上的转移到达不同的组，则拆分G

重复步骤2直到没有组可以被拆分

每个最终组对应最小化DFA的一个状态

3.5 词法分析器的实现

将最小化DFA转换为词法分析器代码有两种主要方式：

方式1：表驱动实现

将DFA表示为转移表，使用通用的解释循环：

int lex_analyzer() {
    int state = 0;  // 初始状态
    char c = next_char();

    while (c != EOF) {
        int next_state = transition_table[state][c];
        if (next_state == ERROR) {
            // 回溯到最后一个接受状态
            return last_accepted_token;
        }
        state = next_state;
        if (is_accepting[state]) {
            last_token = accepting_token[state];
            last_pos = current_pos;
        }
        c = next_char();
    }
    return last_token;
}

方式2：直接编码实现

将DFA直接编码为程序代码，每个状态对应一段代码：

int lex_analyzer() {
state_0:
    c = next_char();
    if (c >= 'a' && c <= 'z') goto state_1;
    if (c >= '0' && c <= '9') goto state_2;
    if (c == '+') return PLUS;
    // ...
    return ERROR;

state_1:  // 标识符
    c = next_char();
    if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) goto state_1;
    // 检查是否为关键字
    return lookup_keyword(buffer);

state_2:  // 数字
    c = next_char();
    if (c >= '0' && c <= '9') goto state_2;
    if (c == '.') goto state_3;
    return NUM;
    // ...
}

直接编码的方式通常比表驱动方式更快（因为没有查表开销），但代码量更大，且不易维护。

重要知识点

3.6 输入缓冲与词法分析的效率

词法分析器需要频繁地读取输入字符，因此I/O效率至关重要。为了减少I/O开销，通常使用双缓冲区技术：

缓冲区布局:
┌──────────────────────────────────────────────────────┐
│  缓冲区1 (N个字符)  │  缓冲区2 (N个字符)  │
└──────────────────────────────────────────────────────┘
  ↑lexemeBegin              ↑forward

• 两个大小相等的缓冲区（通常每个为4096字节）交替使用
• lexemeBegin 指向当前词素的起始位置
• forward 向前扫描，直到发现词素结束
• 当一个缓冲区耗尽时，加载下一个缓冲区的内容
• 特殊标记 EOF 用于标识缓冲区边界

3.7 关键字的识别

关键字（如 if、while、return）的识别有两种策略：

策略1：在词法分析阶段识别

• 为每个关键字建立单独的DFA状态
• 优点：速度快
• 缺点：关键字多时DFA状态爆炸

策略2：在语法分析阶段识别

• 所有标识符统一识别为 ID
• 在符号表中查找，如果匹配关键字则返回对应记号
• 优点：DFA简单
• 缺点：需要额外的查表操作

大多数现代编译器采用策略2，因为它更灵活且易于维护。

3.8 词法分析中的错误处理

词法分析器可能遇到的错误包括：

非法字符：源程序中出现了字母表中不存在的字符

无法匹配的串：字符序列不匹配任何记号的模式

词素过长：标识符或数字串超过限制

错误恢复策略：

• 恐慌模式：跳过非法字符，继续扫描
• 删除字符：删除当前字符，尝试继续匹配
• 插入字符：假设缺少某个字符，插入后继续
• 替换字符：将当前字符替换为最接近的合法字符

3.9 Lex/Flex 词法分析器生成器

Lex（及其增强版Flex）是经典的词法分析器生成工具。用户用正则表达式描述记号模式，Lex自动生成C语言的词法分析器代码。

Lex程序的结构：

定义部分
%%
规则部分
%%
用户代码部分

一个简单的Lex程序示例：

%{
#include <stdio.h>
#include "y.tab.h"
%}

DIGIT    [0-9]
ID       [a-z][a-z0-9]*

%%

{DIGIT}+    {
                yylval = atoi(yytext);
                return NUM;
            }

{ID}        {
                yylval = install_id(yytext);
                return ID;
            }

[ \t\n]+    ;   /* 跳过空白 */

"/*"([^*]|\*[^/])*\*/   ;   /* 跳过注释 */

.           {
                printf("非法字符: %s\n", yytext);
            }

%%

int yywrap() { return 1; }

Lex的工作流程：

将正则表达式转换为NFA

将NFA合并为一个大的NFA

将合并后的NFA转换为DFA

最小化DFA

生成C代码实现该DFA

3.10 词法分析器的优化

词法分析器的性能优化技术包括：

前缀压缩：共享公共前缀的DFA状态可以合并

默认转移：大多数状态的大多数输入都转移到同一个"默认"状态，可以用默认值减少表的大小

稀疏表表示：使用链表或哈希表存储非默认转移

行偏移表：将二维转移表压缩为一维数组

状态合并：将行为相似的状态合并

常见误区

误区一：正则表达式能描述所有词法规则

正则表达式不能描述所有词法规则。有些词法规则超出了正则语言的范畴，例如：

• 嵌套的注释（/* ... /* ... */ ... */）
• 缩进敏感的语言（如Python的缩进规则）
• 需要计数的模式（如平衡的括号）

这些情况需要更强大的工具（如上下文无关文法）来处理。

误区二：DFA状态数一定比NFA少

恰恰相反，NFA转DFA时状态数可能指数级增长。一个n状态的NFA可能产生2^n个状态的DFA。这就是为什么DFA最小化如此重要。

误区三：词法分析器越快越好

虽然词法分析器的效率很重要，但过度优化可能带来问题：

• 代码可读性下降
• 维护成本增加
• 调试困难

在实践中，表驱动的DFA实现已经足够快，通常不需要进一步的手动优化。

误区四：词法分析可以处理任意复杂的模式

词法分析应该保持简单。复杂的模式匹配应该交给语法分析器处理。一个好的经验法则是：如果正则表达式变得难以理解和维护，就应该考虑将其移到语法分析阶段。

实践应用

3.11 实际应用中的词法分析

编程语言编译器：

• GCC的C/C++词法分析器使用手工编码的DFA
• Clang/LLVM使用手工编码的词法分析器
• Rust编译器（rustc）使用手工编码的词法分析器

文本处理工具：

• grep/egrep：基于正则表达式的文本搜索工具
• sed：流编辑器，使用正则表达式进行文本替换
• awk：文本处理语言，模式匹配基于正则表达式

网络协议解析：

• HTTP请求解析
• URL解析
• 电子邮件地址验证

配置文件解析：

• INI文件解析
• 环境变量解析
• 命令行参数解析

3.12 词法分析器的测试与调试

测试词法分析器的方法：

单元测试：为每种记号类型编写测试用例

边界测试：测试空输入、超长输入、特殊字符

错误测试：测试非法输入的错误处理

性能测试：测试大文件处理的性能

调试技巧：

• 打印每个识别出的记号及其位置
• 记录状态转移过程
• 使用可视化工具查看DFA状态图

本章小结

本章系统地介绍了词法分析的理论和实践。核心内容包括：

正则表达式：描述词法规则的形式化工具，支持选择、连接、克林闭包等操作。

有限自动机：正则表达式的计算模型，包括DFA和NFA。两者等价，但DFA更适合实现。

构造流程：正则表达式 → NFA（Thompson构造法）→ DFA（子集构造法）→ 最小化DFA → 词法分析器代码。

实现方式：表驱动和直接编码两种实现方式，各有优劣。

Lex/Flex工具：自动化的词法分析器生成工具，简化了词法分析器的开发。

实际考虑：输入缓冲、关键字识别、错误处理、性能优化等实际问题。

词法分析是编译的基础，理解其原理对于后续的语法分析和整个编译过程的学习至关重要。