4、词法分析器实现：手工编写词法分析器（状态机法）或使用生成器（如Flex、Lex、Ragel），处理标识符、关键字、数字、字符串、注释等

词法分析器是编译器的第一个前端阶段，其核心任务是将源代码字符流转换为有意义的词法单元（）序列。无论是手工编写还是借助生成器，词法分析器的本质都是对有限自动机（Finite Automaton）的工程化实现。本章将深入剖析手工状态机法与生成器法的核心原理、实现路径与实战取舍，帮助你在自制编译器项目中做出合理的技术选型，并掌握处理标识符、关键字、数字、字符串、注释等典型词法元素的完整方法。

词法分析器实现路径与状态机结构 手工状态机法 S0 ID NUM STR OP CMT 字母 数字 " 符号 符号 生成器法 (Flex/Ragel) 正则表达式规则文件 .l / .rl 文件 DFA 最小化 + 表驱动 自动生成跳转表 C/Go/Rust 源码输出 yylex() / 自定义接口 优势 • 声明式规则，易维护 • 自动处理最长匹配/回溯 • 支持上下文条件(状态) 流输出 → 语法分析器

4.1 词法分析的核心原理与设计

词法分析器的工作可以抽象为：读入字符流 → 识别词素（Lexeme）→ 归类为 → 输出给语法分析器。通常由类型（Type）和属性值（Attribute）组成，例如对于标识符 count，类型为 ID，属性值为字符串 "count"；对于数字 42，类型为 INT_LIT，属性值为整数值 42。

在自制编译器中，类型的设计直接决定了后续语法分析的复杂度。一个合理的集合应至少包含：关键字（Keyword）、标识符（Identifier）、字面量（Literal：整数、浮点数、字符串、字符）、运算符与分隔符（Operator & Delimiter）、注释（Comment，通常直接丢弃）以及文件结束符（EOF）。关键字与标识符的区分是词法分析的一个经典问题：通常采用“先识别为标识符，再查关键字表”的策略，而不是在状态机中为每个关键字单独设置状态。

设计原则：类型应尽量保持“语法中立”，即词法分析器只负责识别词法类别，不进行语义判断。例如，if 和 while 都归为关键字类型，但具体是哪个关键字由属性值区分。这样设计可以降低词法分析与语法分析的耦合度，便于编译器后续阶段的扩展。

4.2 手工编写词法分析器：状态机法

手工编写词法分析器通常采用确定性有限自动机（DFA）的思想，通过 switch-case 或 if-else 结构模拟状态转移。其核心是定义一组状态，每个状态对应一个字符输入后的转移逻辑。对于初学者，建议从“全局状态变量 + 逐字符扫描”的模式开始。

4.2.1 状态定义与转移表设计

以识别标识符、整数、字符串和注释为例，我们可以定义如下状态：

  • START：初始状态，跳过空白字符。
  • IN_ID：正在读取标识符或关键字。
  • IN_NUM：正在读取整数或浮点数。
  • IN_STR：正在读取字符串字面量。
  • IN_LINE_CMT：正在读取单行注释（//）。
  • IN_BLOCK_CMT：正在读取块注释（/* */）。

状态转移的核心逻辑是：当前状态 + 当前输入字符 → 下一状态 + 动作（记录词素、生成或报错）。例如，在 START 状态遇到字母或下划线，则进入 IN_ID 状态并开始累积字符；在 IN_ID 状态遇到字母、数字或下划线，则继续累积；遇到其他字符，则结束当前词素，生成，并回退该字符（即“不放回”或“放回”策略，取决于实现方式）。

// 伪代码示例：状态机核心循环
 nextToken() {
    State state = START;
    StringBuilder lexeme = new StringBuilder();
    while (true) {
        char c = getNextChar();
        switch (state) {
            case START:
                if (isWhitespace(c)) { continue; }
                if (isLetter(c) || c == '_') { state = IN_ID; lexeme.append(c); }
                else if (isDigit(c)) { state = IN_NUM; lexeme.append(c); }
                else if (c == '"') { state = IN_STR; }
                else if (c == '/' && peekNext() == '/') { state = IN_LINE_CMT; consumeNext(); }
                else if (c == '/' && peekNext() == '*') { state = IN_BLOCK_CMT; consumeNext(); }
                else { return makeToken(OPERATOR, c); }
                break;
            case IN_ID:
                if (isLetterOrDigit(c) || c == '_') { lexeme.append(c); }
                else { rollback(); return makeToken(ID_OR_KEYWORD, lexeme.toString()); }
                break;
            // ... 其他状态处理
        }
    }
}

4.2.2 关键字与标识符的区分

在 IN_ID 状态结束时，我们拿到一个完整的标识符字符串。此时，通过查哈希表或二分查找，判断该字符串是否为保留关键字。如果是，则返回对应的关键字；否则返回标识符。这种“先识别后查表”的方法比在状态机中为每个关键字单独设置状态要简洁得多，且易于扩展新关键字。

4.2.3 数字字面量的处理

数字识别需要区分整数、浮点数和科学计数法。状态机可以设计为：IN_NUM → 遇到小数点进入 IN_FLOAT → 遇到 e/E 进入 IN_EXP。同时要注意边界情况：123abc 应识别为整数 123 后，将 abc 作为下一个的起始字符（需要回退）。此外，十六进制（0xFF）、八进制（0755）等格式需要额外的状态分支。

常见陷阱：数字后直接跟字母（如 123abc）是非法词法单元。状态机必须在数字状态结束时检查下一个字符，如果是字母或下划线，应报错“无效的数字字面量”，而不是将 123 和 abc 拆分为两个。这需要“超前查看一个字符”的能力。

4.3 使用生成器：Flex与Ragel实战

生成器法将词法规则用正则表达式声明式地描述，工具自动生成确定性有限自动机（DFA）的驱动代码。Flex（Lex的GNU实现）是C/C++生态的经典选择，而Ragel则支持更复杂的“状态机动作”和多种语言输出（C、Go、Ruby等）。

4.3.1 Flex规则文件结构

一个典型的Flex文件（.l）由三部分组成，用 %% 分隔：

%{
// 定义区：C代码头文件、宏、全局变量
#include ".h"
#define YYSTYPE char*
%}

%%
// 规则区：正则表达式 + 动作代码
"if"        { return _IF; }
"else"      { return _ELSE; }
[a-zA-Z_][a-zA-Z0-9_]*  { yylval = strdup(yytext); return _ID; }
[0-9]+      { yylval = strdup(yytext); return _INT; }
\"[^\"\n]*\" { yylval = strdup(yytext); return _STR; }
"//"[^\n]*  { /* 跳过单行注释 */ }
"/*"([^*]|\*+[^*/])*\*+"/" { /* 跳过块注释 */ }
[ \t\n]+    { /* 跳过空白 */ }
.           { return yytext[0]; }  // 运算符等单字符

%%
// 用户代码区：辅助函数
int yywrap() { return 1; }

Flex的核心优势在于自动处理最长匹配（Longest Match）和正则表达式的优先级。例如，if 规则放在标识符规则之前，确保 if 被识别为关键字而非标识符。Flex生成的DFA经过最小化，运行效率极高。

4.3.2 Ragel的状态机描述

Ragel采用更接近状态机的语法，适合需要精细控制状态转移的场景。例如，识别一个带转义字符的字符串：

%%{
    machine lexer;
    action emit_str { /* 处理字符串 */ }
    str = '"' ( [^"\\] | '\\' . )* '"' %emit_str;
    main := |*
        str => { return _STR; };
        [a-zA-Z_][a-zA-Z0-9_]* => { return _ID; };
        [0-9]+ => { return _INT; };
        space;
    *|;
}%%

Ragel的优势在于支持条件动作（Conditional Actions）和嵌入代码，可以在状态转移的任意位置插入C代码，非常适合处理上下文相关的词法规则（如不同语言模式下的字符串定界符）。

对比维度手工状态机Flex/LexRagel
学习曲线中等，需理解DFA低，正则表达式即可较高，需理解状态机语法
代码可读性逻辑清晰但冗长声明式，简洁声明式，但语法复杂
性能高（手动优化）高（自动DFA最小化）高（可精细控制）
调试难度中等，可加日志较低，规则直观较高，需理解生成代码
适用场景教学、嵌入式、自定义语言通用编译器前端协议解析、复杂词法

4.4 实战案例：为自制语言“TinyC”编写词法分析器

假设我们要为教学语言 TinyC 编写词法分析器，该语言支持：int、return、if 等关键字，标识符，十进制整数，单行注释（//）和块注释（/* */），以及运算符 + - * / = == != < > 和括号 ( ) { } ;。

4.4.1 初始现象与目标

我们选择手工状态机法实现，目标是在不依赖外部工具的情况下，生成一个可嵌入C语言项目的词法分析器，并输出序列到控制台。初始代码约200行，要求支持错误恢复（遇到非法字符时跳过并报错）。

4.4.2 关键输入与设计决策

输入示例代码：

int main() {
    // 计算两数之和
    int a = 10;
    int b = 20;
    return a + b; /* 返回结果 */
}

我们定义枚举：_INT、_ID、_KEYWORD、_OP、_LPAREN、_RPAREN、_LBRACE、_RBRACE、_SEMI、_EOF。状态机设计为：START、IN_ID、IN_NUM、IN_LINE_CMT、IN_BLOCK_CMT。对于 == 和 != 这类双字符运算符，需要额外的“等待第二个字符”状态。

4.4.3 实现步骤与结果

  1. 初始化：定义全局变量 currentChar 和 peekChar，实现 advance() 和 peek() 函数。
  2. 主循环：在 getNextToken() 中，根据当前状态和输入字符执行转移。
  3. 关键字表：使用静态哈希表存储 int、return、if 等，在 IN_ID 结束时查表。
  4. 注释处理：在 START 状态检测到 / 后，查看下一个字符：若是 / 则进入行注释状态，直到换行；若是 * 则进入块注释状态，直到 */。
  5. 错误处理：遇到 @、# 等非法字符，打印错误信息并跳过该字符，继续扫描。

测试结果：对上述输入，程序正确输出了约20个，包括 _KEYWORD(int)、_ID(main)、_LPAREN 等。注释被完全跳过，没有产生。性能方面，处理10万行代码耗时约15ms，满足教学需求。

复盘经验：手工状态机的最大挑战是回退（Rollback）管理。例如，识别完 int 后，下一个字符是空格，此时需要将空格“放回”输入流，以便下一次扫描从空格开始。建议使用“缓冲区 + 指针”的方式，而不是依赖 ungetc()，这样更可控。

4.5 常见误区与性能优化

无论是手工还是生成器，词法分析器都有一些共通的“坑”：

  • 误区1：忽略字符回退。在识别完一个后，多读了一个字符，必须回退，否则会丢失字符。
  • 误区2：关键字与标识符混淆。如果先匹配标识符规则，再匹配关键字规则，会导致 if 被识别为标识符。正确做法是“最长匹配 + 规则优先级”。
  • 误区3：字符串中的转义字符。处理 "a\"b" 时，不能遇到 " 就结束字符串，必须处理 \" 转义序列。
  • 误区4：注释嵌套。C语言注释不嵌套，但某些语言（如Pascal）允许嵌套。状态机需要额外计数器。

性能优化方面，手工状态机可以采用查表法：将状态转移逻辑预计算为二维数组 state[当前状态][字符类别]，避免大量的 if-else 分支。字符类别可以粗分为：字母、数字、空白、运算符、其他，共5类，从而将状态表缩小到 状态数 × 5 的规模。对于生成器，Flex生成的DFA已经是最优的，但可以通过 -Cf 选项生成更快的表驱动代码。

风险提示：在自制编译器中，词法分析器的错误恢复策略会影响后续语法分析的稳定性。建议在词法层只做“跳过非法字符并报错”，不要尝试“猜测”用户意图。例如，遇到 123abc 时，报错后可以跳过 123，但将 abc 作为标识符继续扫描，这样语法分析器能获得更多有效信息。

最后，无论选择哪种实现方式，建议为词法分析器编写单元测试，覆盖边界情况：空文件、只有注释、连续运算符、超长标识符、数字边界（如 2147483648 溢出）等。测试驱动开发（TDD）能显著减少编译器后续阶段的调试成本。

← 上一章 📖 返回目录 下一章 →