Sherfiter's wiki for fun

第 2 章 · 词法分析:正则与 DFA

词法分析器的任务听起来卑微:把字符流切成 token。但支撑它的是整门课第一个漂亮的自动化理论:正则表达式描述「单词长什么样」,有限自动机(DFA)高效地「认出」它们,而且两者能力完全等价(Kleene 定理),还有现成的机械转换。学完这章,你不仅会写 tokenizer,还能看懂 grep 的正则引擎为什么快、为什么正则不能匹配括号配对。

2.1 token:语言的单词

词法分析器(lexer/scanner)读字符流,输出 token 流:

输入:  int main() { return 42; }
输出:  KW(int) IDENT(main) LPAREN RPAREN LBRACE KW(return) NUM(42) SEMI RBRACE

每类 token 由一条**模式(pattern)**定义,模式用正则表达式写:

IDENT   : [a-zA-Z_][a-zA-Z0-9_]*      ← 字母或下划线开头,后接字母数字下划线
NUM     : [0-9]+                       ← 数字串
KW      : int | return | if | ...      ← 关键字(先按 IDENT 切,再查表判关键词)
WS      : [ \t\n]+                     ← 空白:跳过(或用来报语法错误)

工程细节:关键字和标识符的冲突用「先统一当标识符切,再查关键字表」解决,别在正则里枚举关键字(能写但丑)。最长匹配原则也在这层:>= 要切成一个 token 而不是 > 和 =,这是 DFA 自带的贪心性质。

2.2 正则 → NFA → DFA:理论发动机

正则表达式的三种基本运算:连接 ab、选择 a|b、闭包 a*(重复零次以上),加上括号,表达所有「正则语言」。

Thompson 构造:把每条正则机械地变成一个 NFA(非确定有限自动机,一个状态可以在同输入下走向多个状态)。比如 a|b 变成两个并行分支:

      a ─▶┐
  →(s0)   (s3)
      b ─▶┘

子集构造:把 NFA 确定化成 DFA(每个 DFA 状态 = NFA 状态的集合),消除歧义。

DFA 模拟:O(1) 每字符,识别一个 n 字符的 token 只走 n 步,这就是 grep 快的原因。

一条正则从「人写的模式」到「机器高效执行」的全自动流水线:Thompson → 子集构造 → 最小化(Hopcroft 算法,去掉等价状态)。考试重点是最小 DFA 的构造(合并「行为完全一致」的状态);工程现实是你大概率用 lex/flex/正则库,但面试和 debug 都需要你脑子里有这台自动机。

2.3 正则的能力边界:为什么配不了括号

正则(指经典理论正则,不是 Perl 的各种扩展)有个铁限制:记不住配对。识别「任意配对的括号」需要一个计数器(数开括号减闭括号是否为负),而 DFA 只有有限个状态,数到多少都有溢出的那一刻。形式化说法:语言 { aⁿbⁿ } 不是正则的,泵引理可以证明。

这个「不能」在第 3 章被上下文无关文法接住。语言的分层:正则语言 ⊊ 上下文无关语言 ⊊ 更高。每层上移,表达能力增强,分析成本也上升。记住这条线,你在选工具时就有依据:token 层面用正则(够用且快),嵌套结构(表达式、语句块)必须上 CFG。

2.4 动手:手写一个 tokenizer

用手写状态机实现(不用生成器,理解原理最快):

// 极简 tokenizer:支持标识符、数字、+、*、(、)
typedef enum { T_NUM, T_ID, T_PLUS, T_MUL, T_LP, T_RP, T_EOF } TokType;

TokType next_token(const char **p, char *buf) {
    while (**p == ' ' || **p == '\t') (*p)++;       // 跳空白
    char c = **p;
    if (c == '\0') return T_EOF;
    if (c == '+') { (*p)++; return T_PLUS; }
    if (c == '*') { (*p)++; return T_MUL; }
    if (c == '(') { (*p)++; return T_LP; }
    if (c == ')') { (*p)++; return T_RP; }
    if (c >= '0' && c <= '9') {                     // 数字串
        int i = 0;
        while (**p >= '0' && **p <= '9') buf[i++] = *(*p)++;
        buf[i] = 0; return T_NUM;
    }
    if (isalpha(c) || c == '_') {                   // 标识符
        int i = 0;
        while (isalnum(**p) || **p == '_') buf[i++] = *(*p)++;
        buf[i] = 0; return T_ID;
    }
    return T_EOF;   // 真实实现:报「非法字符」错误并带行号
}

这个手写过程里藏着 DFA 的影子:每个 if 分支就是一个状态转移,「读到数字后继续吃数字」就是 NUM: [0-9]+ 的 * 闭包循环。flex 生成的代码把这一切变成一张跳转表,原理相同。

2.5 错误处理:词法层的礼貌

词法错误(非法字符、非法数字字面量如 123abc)的恢复策略通常很粗暴:跳过当前字符,继续。因为词法错误的修复价值极低,而报告位置的价值极高(「line 12: illegal character '@'」)。编译器前端的错误信息质量(带行号、带上下文)是工程的重要分,第 6 章语义分析还会升级这条标准。

常见错误

  • 忘了最长匹配。手写时用 if 顺序判断,遇到 >= 切成两个 token;DFA 天然贪心,手写要显式「多看一个字符」。
  • 关键字当标识符。if 被切成 IDENT 后忘了查表降级。
  • 忽略注释与字符串。// 后面全是垃圾、字符串里的 + 不能当运算符;词法器要有「字符串字面量」和「注释」的状态(它们也是 DFA 状态)。
  • 行号没跟踪。报错不带行号的编译器会被用户骂,在读到 \n 时维护 line counter。

练习

  1. 动手:给 2.4 的 tokenizer 加上:-、/、// 注释、字符串字面量(支持 \" 转义)。写测试输入跑通。
  2. 手算:对正则 (a|b)*abb 手工构造 NFA(Thompson),再用子集构造法得到 DFA,标出接受状态。这是考试送分题原型。
  3. 动手:用 flex 写同一份 tokenizer(写 .l 文件,跑 flex + gcc),对比手写代码量;打开 flex 生成的 lex.yy.c,找到那张 DFA 跳转表(yy_ec/yy_accept 数组)。
  4. 思考:为什么 JSON 的解析器不能用纯正则一步到位?结合 2.3 的「括号配对」论证,再想想「正则切词 + 递归下降」的两段式为什么就够用(这正是第 3 章的事)。
豫ICP备2026027944号