3. 词法分析：如何将源代码拆分成Token，有限状态机的应用

好，咱们今天聊聊词法分析。说白了，就是编译器怎么把你看得懂的源代码，拆成它自己认识的最小单元——Token。

我记得刚入行那会儿，总觉得这步很简单，不就是按空格切分嘛？后来被现实狠狠教育了一回。你想想看，int a = 0x1F; 这行代码，空格只是辅助，真正决定怎么切分的是语言本身的规则。

3.1 什么是Token？

Token 是编译器能理解的最小语法单元。它不再是字符，而是有明确分类的“词”。

常见的 Token 类型包括：

  • 关键字：int、return、if、while 等
  • 标识符：变量名、函数名，比如 main、counter
  • 常量：数字 42、字符串 "hello"、字符 'A'
  • 运算符：+、-、*、== 等
  • 分隔符：;、{、}、(、) 等

每个 Token 通常用一个结构体表示，包含类型和值。比如：

typedef struct {
    TokenType type;  // 枚举类型：KEYWORD, IDENTIFIER, NUMBER, ...
    char* value;     // 原始字符串
    int line;        // 行号，方便报错
} Token;
我的习惯：在 Token 结构体里一定带上行号和列号。调试时能直接定位到源码位置，省去很多排查时间。

3.2 词法分析的核心：有限状态机

词法分析器怎么知道当前读到的是关键字还是标识符？怎么区分 == 和 =？

答案就是——有限状态机（FSM）。

有限状态机说白了就是一个状态转换图。你每读一个字符，就根据当前状态和这个字符，决定下一步跳到哪个状态。直到某个状态表示“我识别完一个 Token 了”，就输出它。

我画了一张图，帮你理解这个过程：

词法分析有限状态机示例 S0 起始 S1 标识符 S2 数字 S3 运算符 S4 字符串 S5 注释 输出Token 字母/_ 数字 + - * / = " // 字母/数字/_ 数字 遇到非字母/数字 遇到非数字 下一个字符 遇到" 遇到换行

这张图展示了一个简化的词法分析状态机。从起始状态 S0 开始，每读一个字符就决定下一步走向。比如读到字母或下划线，就进入标识符状态 S1，然后一直读直到遇到非字母数字字符，就输出一个标识符 Token。

3.3 实战：手写一个简单的词法分析器

光说不练假把式。咱们直接写一段 C 代码，实现一个能识别整数、标识符和运算符的迷你词法分析器。

#include <stdio.h>
#include <ctype.h>
#include <string.h>

typedef enum {
    TOKEN_NUMBER,
    TOKEN_IDENTIFIER,
    TOKEN_OPERATOR,
    TOKEN_EOF
} TokenType;

typedef struct {
    TokenType type;
    char value[64];
} Token;

// 有限状态机核心函数
Token getNextToken(FILE* fp) {
    Token token;
    int ch;
    int state = 0;  // 0: 起始, 1: 数字, 2: 标识符, 3: 运算符
    int idx = 0;

    // 跳过空白字符
    do {
        ch = fgetc(fp);
    } while (ch != EOF && isspace(ch));

    if (ch == EOF) {
        token.type = TOKEN_EOF;
        strcpy(token.value, "EOF");
        return token;
    }

    // 状态机开始
    while (1) {
        switch (state) {
            case 0:  // 起始状态
                if (isdigit(ch)) {
                    state = 1;
                    token.value[idx++] = ch;
                } else if (isalpha(ch) || ch == '_') {
                    state = 2;
                    token.value[idx++] = ch;
                } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                    state = 3;
                    token.value[idx++] = ch;
                } else {
                    // 无法识别的字符，简单跳过
                    ch = fgetc(fp);
                    continue;
                }
                break;

            case 1:  // 数字状态
                if (isdigit(ch)) {
                    token.value[idx++] = ch;
                } else {
                    // 遇到非数字，回退并输出
                    ungetc(ch, fp);
                    token.value[idx] = '\0';
                    token.type = TOKEN_NUMBER;
                    return token;
                }
                break;

            case 2:  // 标识符状态
                if (isalnum(ch) || ch == '_') {
                    token.value[idx++] = ch;
                } else {
                    ungetc(ch, fp);
                    token.value[idx] = '\0';
                    token.type = TOKEN_IDENTIFIER;
                    return token;
                }
                break;

            case 3:  // 运算符状态
                // 单字符运算符，直接输出
                token.value[idx] = '\0';
                token.type = TOKEN_OPERATOR;
                return token;
        }
        ch = fgetc(fp);
    }
}

int main() {
    FILE* fp = fopen("test.c", "r");
    if (!fp) return 1;

    Token t;
    do {
        t = getNextToken(fp);
        printf("Token: type=%d, value=%s\n", t.type, t.value);
    } while (t.type != TOKEN_EOF);

    fclose(fp);
    return 0;
}

核心要点：这个状态机只有 4 个状态，但已经能处理大部分基础 Token 了。实际编译器里的词法分析器可能有几十个状态，但原理一模一样。

3.4 避坑指南：我踩过的那些坑

我曾经在写一个嵌入式 C 的交叉编译器时，遇到过一个极其隐蔽的 bug。代码里有个宏定义：

#define MAX(a,b) ((a)>(b)?(a):(b))

词法分析器把 MAX 当成了普通标识符，结果预处理器展开时完全乱了套。后来我才意识到，词法分析阶段必须区分关键字和标识符。我的做法是：在识别出标识符后，查一下关键字哈希表，如果匹配就改成关键字类型。

另一个常见坑是 最大匹配原则。比如 >>= 这个序列，应该被识别成 >>=（右移赋值）还是 >、>=？C 标准规定：总是取最长的合法 Token。所以 >>= 会被识别成一个 Token，而不是三个。

注意：如果你自己写词法分析器，一定要实现“回退”机制。当状态机发现当前路径走不通时，要能回退到上一个安全状态，并输出已识别的 Token。上面的代码里用 ungetc 就是干这个的。

3.5 有限状态机的实现方式

实际工程中，实现词法分析器有几种主流方式：

方式 优点 缺点 适用场景
手写状态机 灵活、可控、性能高 代码量大、容易出错 小型语言、教学
Lex / Flex 自动生成、规则清晰 生成的代码可读性差 工业级编译器
正则表达式 + 自动机 表达能力强 性能不如手写 脚本语言、解释器

我个人习惯是：原型阶段用 Flex 快速生成，生产环境再手写优化。Flex 生成的代码虽然丑，但正确性有保障，能帮你快速验证语法规则。

3.6 词法分析中的几个关键细节

有些细节，面试常考，实际开发也容易翻车：

  • 字符串字面量：遇到 " 进入字符串状态，直到遇到下一个 " 结束。但要注意转义字符 \" 不能算结束。
  • 注释处理：// 单行注释直接读到换行；/* */ 多行注释要记录状态，跨行处理。
  • 浮点数：3.14 和 .5 都是合法浮点数，状态机要能处理小数点前后缺数字的情况。
  • 宽字符：L"hello" 这种前缀，需要额外状态处理。

一个小技巧：调试词法分析器时，可以先把所有 Token 打印出来，看看是否符合预期。我经常用 printf("Token: %s\n", token.value) 来验证，比看汇编输出直观多了。

3.7 总结

词法分析是整个编译过程的“入口”。它把源代码从字符流变成 Token 流，为后续的语法分析铺平道路。有限状态机是它的核心武器，理解了这个，你就掌握了编译器最基础的一环。

嗯，这里要注意：不要小看词法分析。虽然它看起来简单，但很多编译器的性能瓶颈就出在这里。一个高效的词法分析器，能节省整个编译时间的 10%-20%。

下次你写代码时，可以想想编译器是怎么“看”你的代码的。它看到的不是漂亮的缩进和注释，而是一个个冷冰冰的 Token。这就是编译器的世界观。

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