词法分析基础：正则表达式、有限自动机与词法单元

词法分析是编译器的第一个阶段，它负责将源代码的字符序列转换为有意义的词法单元（）流。如果把编译器比作一个翻译官，那么词法分析器就是那个最先阅读原文、把单词和标点切分出来的速记员。本章将深入剖析词法分析的理论基石——正则表达式与有限自动机，并详细阐述的定义与分类。我们将从数学定义出发，逐步过渡到工程实现，帮助你建立从理论到代码的完整桥梁。理解本章内容，是后续手写词法分析器或使用Lex/Flex等工具的基础，也是构建自制编译器不可逾越的第一步。

上图清晰地展示了词法分析在编译器前端中的位置以及本章的核心知识框架。源代码作为字符流输入，词法分析器依据正则表达式定义的规则，通过有限自动机的状态转移进行模式匹配，最终输出结构化的流。下面，我们将逐一拆解这些概念。

3.1 词法单元（）的定义与分类

3.1.1 核心原理：的三元组结构

词法单元（）是词法分析器输出的最小语义单位。它不是一个简单的字符串，而是一个包含丰富信息的数据结构。通常，一个由以下三个核心部分组成：

• 类型（Type）：标识该的语法类别，如关键字（KEYWORD）、标识符（IDENTIFIER）、整数常量（INT_CONST）、运算符（OP）等。类型是语法分析器进行推导的主要依据。
• 属性值（Attribute Value）：存储的具体文本内容或指向符号表条目的指针。例如，对于标识符，属性值就是变量名；对于整数常量，属性值就是其数值。
• 位置信息（Location）：记录该在源文件中的行号、列号，甚至文件路径。这对于编译器报告精确的错误信息至关重要。

3.1.2 判断方法：的分类标准

如何确定一个字符序列属于哪种类型？这需要依据语言的词法规范。通常，我们可以将分为以下几大类：

3.1.3 案例拆解：一个简单的赋值语句

假设我们有源代码片段：int total = 42;。词法分析器会将其分解为以下流：

1. <KEYWORD, "int", 1:1>
2. <IDENTIFIER, "total", 1:5>
3. <OP, "=", 1:11>
4. <INT_CONST, 42, 1:13>
5. <DELIMITER, ";", 1:15>

注意，这里int被识别为关键字而非标识符，因为关键字规则优先级更高。同时，42被解析为整数常量，其属性值存储为整数42，而非字符串"42"。

3.2 正则表达式：词法规则的描述语言

3.2.1 核心原理：从字符集到模式

正则表达式（Regular Expression, RE）是一种形式化的语言，用于描述字符串的集合。在词法分析中，我们用它来精确地定义每种的构成规则。正则表达式基于三种基本运算：

• 连接（Concatenation）：表示字符依次出现。例如，ab匹配字符串"ab"。
• 并（Union）：表示选择。例如，a|b匹配"a"或"b"。
• 闭包（Kleene Star）：表示零次或多次重复。例如，a*匹配空串、 "a"、 "aa"等。

基于这三种运算，我们可以定义更复杂的语法糖，如[0-9]（数字字符集）、+（一次或多次）、?（零次或一次）等。

3.2.2 操作流程：为编写正则表达式

为编写正则表达式需要遵循以下步骤：

1. 分析词法规范：阅读语言规范，明确每种的字符组成规则。
2. 定义字符集：使用[ ]定义字符集合，如[a-zA-Z]表示所有字母。
3. 构建基本模式：使用连接、并、闭包组合字符集。
4. 处理边界情况：考虑空串、转义字符、Unicode字符等。
5. 测试与验证：使用正则表达式测试工具验证匹配结果。

例如，定义一个C语言风格标识符的正则表达式：[a-zA-Z_][a-zA-Z0-9_]*。这个表达式首先匹配一个字母或下划线，然后匹配零个或多个字母、数字或下划线。

3.2.3 实战场景：正则表达式的歧义与解决

在实际语言中，正则表达式之间可能存在歧义。例如，关键字if也符合标识符的规则。解决方法是采用优先级策略：在构建词法分析器时，将关键字的规则排在标识符规则之前。当输入流中出现"if"时，优先匹配关键字规则。

3.3 有限自动机：从正则到识别器

3.3.1 核心原理：NFA与DFA的数学定义

有限自动机（Finite Automaton, FA）是正则表达式的等价计算模型。它分为两类：

• 非确定有限自动机（NFA）：允许一个状态在输入一个字符后转移到多个状态，且允许ε-转移（不消耗输入字符的转移）。NFA更接近正则表达式的结构，易于从RE直接转换，但识别效率较低。
• 确定有限自动机（DFA）：每个状态在输入一个字符后，有且仅有一个转移目标。DFA识别效率高，但状态数可能多于NFA。

从正则表达式构造NFA可以使用Thompson构造法，而从NFA转换为DFA则使用子集构造法。

3.3.2 判断方法：NFA与DFA的对比

3.3.3 案例拆解：识别"if"和"id"的DFA构建

假设我们只需要识别两个：关键字"if"和标识符（以字母开头的字母数字串）。我们可以构建如下DFA：

状态0: 起始状态
  - 输入'i' → 状态1
  - 输入[a-hj-zA-Z_] → 状态2 (标识符)
状态1: 
  - 输入'f' → 状态3 (接受，关键字"if")
  - 输入字母或数字 → 状态2 (标识符)
状态2: (标识符)
  - 输入字母或数字 → 状态2
  - 其他 → 接受 (标识符)
状态3: (关键字"if")
  - 输入字母或数字 → 状态2 (标识符，如"ifx")
  - 其他 → 接受 (关键字"if")

这个DFA清晰地展示了如何处理最长匹配和优先级。当输入"ifx"时，状态机会从0→1→3，但在状态3遇到'x'时，会转移到状态2，最终接受为标识符。

3.4 从正则到代码：词法分析器的实现策略

3.4.1 核心原理：手写与生成器的权衡

实现词法分析器有两条主流路径：手写词法分析器和使用生成器（如Flex）。手写方式灵活，易于调试和优化，但需要手动处理状态转移逻辑。生成器方式自动化程度高，但生成的代码可读性差，且依赖工具链。

3.4.2 操作流程：手写词法分析器的步骤

1. 定义类型枚举。
2. 实现输入缓冲区管理：支持预读（lookahead）和回退（retract）。
3. 编写核心扫描循环：根据当前字符，使用switch或状态表进行转移。
4. 实现最长匹配逻辑：记录最后一次接受的状态和位置。
5. 返回：填充结构体并返回。

以下是一个简化的C语言风格词法分析器核心循环伪代码：

 nextToken() {
    skipWhitespace();
    int startLine = currentLine;
    int startCol = currentCol;
    char c = getChar();
    switch (c) {
        case '+': return makeToken(OP_PLUS, startLine, startCol);
        case '=': 
            if (peekChar() == '=') {
                getChar(); // 消费第二个'='
                return makeToken(OP_EQ, startLine, startCol);
            } else {
                return makeToken(OP_ASSIGN, startLine, startCol);
            }
        case '0': case '1': ... case '9':
            return parseNumber(startLine, startCol);
        default:
            if (isAlpha(c) || c == '_') {
                return parseIdentifier(startLine, startCol);
            } else {
                reportError("Unexpected character", startLine, startCol);
            }
    }
}

3.4.3 实战场景：处理注释与空白

注释和空白虽然不产生，但必须被词法分析器正确处理。通常，词法分析器会跳过它们。对于块注释（如/* ... */），需要维护一个状态，直到遇到*/。对于行注释（如// ...），则跳过直到行尾。

3.4.4 总结复盘：词法分析器的常见误区

• 误区一：忽略最长匹配。例如，将==误识别为两个=。必须始终尝试匹配最长的可能。
• 误区二：关键字与标识符冲突。未设置优先级，导致关键字被识别为标识符。
• 误区三：错误处理不完善。遇到非法字符时，应报告准确的行列号，并尝试恢复（如跳过该字符），而不是直接终止编译。
• 误区四：缓冲区管理不当。在读取字符时，未考虑文件末尾（EOF）的处理，导致死循环或越界访问。