元数据卡

• 前置知识：第1-2章（正则语言与自动机）、基本 C 或 Java 编程
• 预计时间：45 分钟
• 核心难度：入门
• 阅读模式：轻松漫游
• 完成标志：能手写简单的词法分析器，能理解 Lex/flex 的工作方式

你已经爬完了咒术高塔的前四层——那里的数学世界没有程序可以运行。第五层是工程之门。你看到一排排的编译工具链，最小的那个工具在最前面，它的任务非常简单：把源代码的字符流变成有意义的词（token）。这就是词法分析器。

---

你的进度

前面四章给了你理论基石：正则语言对应词法分析，CFG 对应语法分析，TM 对应代码优化和静态分析。这一章你放下纸笔，拿起真工具——写一个能跑的词法分析器。

---

你的任务

从一串字符中分离出 token——关键字、标识符、数字、运算符、分隔符。你会从手写状态机开始（用 C 实现一个简单的词法分析器），然后了解 Lex/flex 这种自动生成工具的工作方式，最后理解词法分析器在编译器中的位置和它与语法分析器的协作方式。

---

破局 · 溯源

你面前有一行 C 代码：

int count = 42;

对你来说，这显然被分成：int（关键字）、count（标识符）、=（赋值运算符）、42（整数常量）、;（语句结束符）。但编译器看到的只有一串 ASCII 字符：i, n, t, 空格, c, o, u, n, t…… 它不认识"关键字"、"标识符"这些概念。你需要把字符流转化为 token 流。

手工构建词法分析器

最朴素的做法是：维护一个状态机，每个字符触发状态转移。下面是一个用 C 实现非常简化的词法分析：

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

typedef enum {
    TOKEN_EOF, TOKEN_NUM, TOKEN_ID, TOKEN_IF,
    TOKEN_ASSIGN, TOKEN_SEMI, TOKEN_UNKNOWN
} TokenType;

typedef struct {
    TokenType type;
    char lexeme[256];
} Token;

Token next_token(FILE *fp) {
    Token tok;
    int c = fgetc(fp);

    // 跳过空白
    while (c == ' ' || c == '\t' || c == '\n')
        c = fgetc(fp);

    if (c == EOF) {
        tok.type = TOKEN_EOF;
        return tok;
    }

    // 数字
    if (isdigit(c)) {
        int i = 0;
        do {
            tok.lexeme[i++] = c;
            c = fgetc(fp);
        } while (isdigit(c));
        tok.lexeme[i] = '\0';
        tok.type = TOKEN_NUM;
        ungetc(c, fp);  // 多读的字符还回去
        return tok;
    }

    // 标识符或关键字
    if (isalpha(c) || c == '_') {
        int i = 0;
        do {
            tok.lexeme[i++] = c;
            c = fgetc(fp);
        } while (isalnum(c) || c == '_');
        tok.lexeme[i] = '\0';
        ungetc(c, fp);
        if (strcmp(tok.lexeme, "if") == 0)
            tok.type = TOKEN_IF;
        else
            tok.type = TOKEN_ID;
        return tok;
    }

    // 运算符
    if (c == '=') {
        tok.lexeme[0] = '=';
        tok.lexeme[1] = '\0';
        tok.type = TOKEN_ASSIGN;
        return tok;
    }

    // 分号
    if (c == ';') {
        tok.lexeme[0] = ';';
        tok.lexeme[1] = '\0';
        tok.type = TOKEN_SEMI;
        return tok;
    }

    tok.lexeme[0] = c;
    tok.lexeme[1] = '\0';
    tok.type = TOKEN_UNKNOWN;
    return tok;
}

这个函数是一个简化版的状态机。你注意到模式：逐个字符读入，每读到一个字符就决定下一步去哪里。当某个模式结束时（比如读到非数字字符后，数字结束），要把多读的那个字符放回去（ungetc）——这是词法分析器中极其常见的"最长匹配"工程策略。

最长匹配与回退

前面提到过这个规则：词法分析器总是尽可能多地读入字符，直到不能再追加为止。比如输入 ifx，如果词法分析器已经读入 if 就停下，会把它当作关键字 if 而不是标识符 ifx。正确的策略是继续读——读完 ifx 后发现不能继续（后面是空格），检查接受状态：如果 ifx 本身不是完整的 token，但 if 是——回退到 if 的位置。在 DFA 实现中，你总是维护"最近的一个接受状态位置"作为回退点。

Lex/flex 词法分析器生成器

手写状态机维护起来很累。Lex 和它的 GNU 版本 flex 是自动生成词法分析器的工具。你只需要写一套规则模板，flex 会生成 C 代码。

一个 flex 示例：

%{
/* 这里可以放 C 头文件和辅助函数 */
#include "tokens.h"
%}

%%
"if"          { return IF; }
[a-zA-Z][a-zA-Z0-9]*  { return IDENTIFIER; }
[0-9]+        { return NUMBER; }
"="           { return ASSIGN; }
";"           { return SEMI; }
[ \t\n]       { /* 跳过空白 */ }
.             { return UNKNOWN; }
%%

每一行由三部分组成：正则表达式 + 花括号内的动作代码。flex 内部做的事情正是第2章描述的过程——将正则表达式转化为 NFA，合并所有 NFA，转化为 DFA，生成跳转表。这个 DFA 在 flex 运行时是一个大的 switch 语句或跳转表。

词法分析器与语法分析器的协作

你通常不会单独运行词法分析器——它被语法分析器"拉"着跑：语法分析器每次需要下一个 token 时，调用 next_token()。这种协作方式叫"单遍扫描"：不需要把全部 token 读入内存再解析，而是边分词边解析。

语法分析器 ←调用→ 词法分析器 ←读取← 源代码文件
          (token)           (字符)

---

第一层：够用——写一个能工作的简单词法分析器

上面的 C 代码已经可以工作了——你可以把它和一个主函数拼起来，从标准输入读取代码，输出 token 流。试试看：

int main(int argc, char *argv[]) {
    Token t;
    do {
        t = next_token(stdin);
        printf("Token: type=%d, lexeme=%s\n", t.type, t.lexeme);
    } while (t.type != TOKEN_EOF);
    return 0;
}

编译运行：

$ echo "int x = 42;" | ./lexer
Token: type=4, lexeme=int
Token: type=3, lexeme=x
Token: type=5, lexeme==
Token: type=2, lexeme=42
Token: type=6, lexeme=;
Token: type=1, lexeme=

第二层：深入——为什么 Lex/flex 比手写快

Flex 生成的 DFA 对每个字符最多做一次查表+跳转。而手写的词法分析器用 if-else 链或 switch 语句，每个字符可能经过多次条件判断。Flex 的 DFA 表是预编译的，对每个字符的决策时间是 O(1)。在现代硬件上，flex 生成的词法分析器可以每秒处理数 MB 的源代码——比等量的 if-else 快一两个数量级。

---

常见陷阱

陷阱1：忘记跳过注释。 在经典 C 词法分析中，/* ... */ 注释是多行结构——词法分析器需要进入"注释模式"，直到遇见 */ 才退出。这个状态需要词法分析器单独处理，然后继续输出不包含注释的 token 流。

陷阱2：字符串字面量中的转义序列。 在处理 "hello\nworld" 时，\n 是一个字符，不是反斜杠+字母 n。词法分析器在字符串模式中需要识别转义序列。这通常通过增加一个"字符串内部"状态来解决。

陷阱3：预处理指令。 C 的 #include、#define 等预处理指令在词法分析之前由预处理器处理，它们不属于 token 流的一部分。如果你在写完整编译器的词法分析器，注意不要把 #include 当成标识符。

---

通关挑战

• 热身（5分钟）： 在上面的词法分析器中加入对 == 和 != 两个运算符的支持。注意：当前遇到 = 时，还要看下一个字符是不是 =——这需要"超前读取"。

• 挑战（30分钟）： 用 flex 写一个完整的词法分析器，支持 C 语言的小子集：关键字（int, if, else, while, return）、数字、标识符、运算符（+ - * / = == != < > <= >=）、分隔符（; { } ( )）。验证输入 int gcd(int a, int b) { if (b == 0) return a; } 的输出是否正确。

• 观察： 下载一个开源编译器（如 TinyCC 或 8cc）的源码，找到它的词法分析器（通常叫 lexer.c 或 next_token 函数），看看它有多少状态。猜测它用了多少"最长匹配 + 回退"的策略。

---

旅人笔记

词法分析器将字符流转化为 token 流，核心武器是正则语言（DFA）；flex 自动完成"正则-> NFA -> DFA"的全过程，让你只写规则，不写状态机。

---

下一站预告

词法分析器把代码变成了 token 序列，但这串 token 有什么结构？下一章，你拿这些 token 来重建代码的树形结构——抽象语法树。