#compilers #词法分析
本页目录

词法器设计

从 token 表示到缓冲区管理到 Unicode 处理——一个工程化的词法器要考虑的远不止自动机理论,位置追踪和错误恢复的质量直接决定编译器报错的用户体验。

概述

正则与自动机讲了词法分析的数学基础——正则→NFA→DFA→最小化。这篇讲工程:一个真实的词法器怎么设计 token 种类、怎么处理关键字和标识符的消歧、怎么追踪源码位置、怎么做错误恢复、以及手写 vs 生成器的选择。这些不是"锦上添花"——位置追踪和错误恢复的质量直接决定后续编译错误的用户体验,而这两样在课本里常被略过。

Token 的种类设计

一条 token 至少需要三个字段:

Token {
    kind: TokenKind,       ← 枚举: Number, Plus, Identifier, If, ...
    text: &str,            ← 源码中的实际文本 (如 "42", "+", "my_var")
    span: Span,            ← 源码中的位置 (起始行/列 → 结束行/列)
}

kind 和 text 分开是一个关键设计:kind 用于语法分析(parser 根据 token 种类做决策,如看到 If 进入 if 语句解析);text 用于语义分析和错误报告(如 42 的数值是 42,报错时高亮源码 "my_var" 这一串)。

Token 种类设计遵循两个互相牵制的原则:parser 需要的粒度⁠(运算符要每种一个 kind,+ / - / * 各一个,否则 parser 没法决策)和lexer 识别的一致性⁠(能在一个 DFA 状态下确认该 token 的类型)。

关键字不单独走 lexer 的 DFA 分支——lexer 只识别"一个标识符"(字母开头 + 数字/下划线后续),然后查关键字表:

识别到标识符 "if" → lookup_keyword("if") → TokenKind::If
识别到标识符 "myvar" → lookup_keyword("myvar") → 不在表中 → TokenKind::Identifier

关键字表通常是编译时构造的完美哈希或 trie,lookup O(1) 或 O(len)。这比在 DFA 里为每个关键字建单独终结状态干净——DFA 的状态爆炸是真实风险(所有关键字的不同前缀都变成不同状态)。

位置追踪:行的世界

源码是一维的字节流,报错时要转回人类可读的行:列⁠。词法器必须追踪两个量:

当前 offset:    从文件头到当前字符的字节偏移 (span 的起点/终点用 offset 存)
当前 line:      1-based
当前 column:    1-based (或 0-based, 取决于编辑器约定)

每次遇到换行符 \n(或 \r\n):line += 1, column = 1, offset += 换行符长度。

Span 存 offset 而非 line/col——offset 可以直接用于"从文件中切出这段源码"(substring),且不需要知道换行位置。line/col 只在报错时才从 offset + 行首偏移表(line table)反推:

line_table: Vec<offset>   ← 每行首字符在文件中的 offset

span_to_linecol(span):
    line = line_table.binary_search(span.start).unwrap() + 1
    col = span.start - line_table[line - 1] + 1

为什么反推而不是直接存?因为同一个源码位置会在 diagnostics 中被追问多次(如多个 pass 都报同一行的错),存 offset 是稳定的(不随文件编辑而变,在 IDE 增量重解析中重要),line/col 是可以从 offset + line table 重新推导的。

peek / consume / unget:词法器的控制界面

词法器暴露给语法分析器的界面只有几个操作:

  • peek():返回当前 token 但不消费(读 token 不前进)。parser 用它做分支决策——"如果下一个是 + 走这条路,如果 * 走那条路"。
  • consume():返回当前 token 并前进到下一个。
  • consume(kind):断言当前 token 必须是 kind,否则报错——用于 parser 已知语法结构时的读取(如"consumed ("之后必然有 )")。

peek 是最频繁的 parser 操作(每次决策都调),必须是 O(1)——意味着词法器在 peek 之前必须已经完成了下一次 token 的扫描。实现上,lexer 总"提前扫描一个 token"缓存下来,peek 直接返回缓存,consume 返回缓存并触发下一次扫描。

注意⁠: consume(kind) 这个 API 在不同实现中有不同分工。有些词法器直接在 lexer 层提供 consume(kind) 做断言消费;更多情况下,这是 parser 的职责——parser 先调用 peek() 拿到 token,比较 token.kind == expected,再决定是否调用 consume()。无论哪种方式,语义是一致的。

缓冲区管理:大文件与流式输入

不能把整个文件读进一个 String 再做词法分析——大文件内存会爆。词法器用环形缓冲区或双缓冲⁠:

环形缓冲 (ring buffer):
  维护一个固定大小的窗口 (如 4KB), 指向当前扫描位置
  消费过的数据被丢弃
  接近窗口末尾时, 从文件读入下一块到缓冲的开头部分

  但 token 不能跨缓冲断点 → lexer 保证在不需要回看时推进缓冲

双缓冲(两个交替填充的 buffer)是 flex 的经典做法——YY_BUFFER_SIZE 默认 16KB,当前缓冲消费完后切换到另一个已填充的缓冲,IO 和扫描并行。

现代场景里,内存普遍充裕,很多实现直接 mmap 整个文件到虚拟地址空间——OS 按需加载页,编译器不需要自己的缓冲区逻辑。但词法分析器仍需追踪 offset 以支持 span 的构造。

Unicode:词的字母表再不是 128 个 ASCII

C 时代词法器只处理 ASCII——128 个字符,每个是 1 字节。现代语言(Rust、Go、Swift)在源码层面支持 Unicode:

  • 标识符可以含 Unicode 字母(的、蛇、é、α)。
  • 字符类 \w 不再等价于 [a-zA-Z0-9_]——Rust 的标识符字符类是 XID_Start + XID_Continue(Unicode 标准定义的"编程语言标识符安全字符")。

词法器处理 Unicode 的策略是保持 tokenizer 工作在字节层面,按 UTF-8 规则识别 multi-byte 序列⁠:

识别标识符时:
  逐个字节扫描
  如果是 ASCII 字母/数字/下划线 → 消费 1 字节, 继续
  如果是 UTF-8 多字节首字节(通过 bit 模式快速判断: 110xxxxx=2字节, 1110xxxx=3字节, 11110xxx=4字节)
    → 按规则消费完整序列, 解码码位
  查 Unicode 表确认该码位是否在 XID_Start/XID_Continue 里
  否则: 标识符结束

不需要预解码整个文件为 Vec<char>——只在扫描到 multi-byte 序列时解码当前字符,可保持内存效率。

错误恢复:词法器不能崩

词法器遇到非法字符(@ 在 C 里、未闭合的字符串字面量),不能崩溃。它必须:

  1. 报告错误⁠(在哪行哪列,非法字符是什么)。
  2. 跳过该字符继续扫描⁠——不打断 parser 后续工作(让用户一次编译看到所有词法错误,而非修一个报一个)。

字符串未闭合是最常见的词法错误:

"hello world          ← 缺少闭合引号

处理:当 " 后扫描到行末或 EOF 仍未闭合 → 报告 "unterminated string literal, expected closing "",⁠假装在当前位置闭合⁠(或跳过整行),继续扫描。

手写 vs 生成器:工业界的真实选择

手写 lexer生成器 (flex, re2c, lex)
实例Clang, Rustc, V8, CPythonBash, awk, 各 DSL
方式手动管理状态 + DFA 表或直接写正则输入 → 自动生成 DFA/表
优点错误信息极好, 可定制, 内联积极, 无生成器依赖正则直接对应 token, 改 token 容易
缺点token 多时状态管理繁重, 新人要学代码生成的代码可读性差, 错误信息难调

工业界编译器绝大多数手写⁠——因为编译错误信息的质量是产品的脸面,生成器在这一点上无法和手写竞争。生成器最大的价值在"正则到 DFA"的自动转换(不需要手算子集构造),但生成的 DFA 和手写的错误恢复混在一起时可维护性差。

Clang 的 lexer 是手写的典范:每个 token 种类的消费逻辑清晰可读,对每种字符类或 token 开头做分支,错误恢复策略内嵌在每种 token 的处理逻辑中。

参考

  • flex 手册⁠: The Fast Lexical Analyzer — 生成器的完整使用、缓冲区管理、YY_CURRENT_BUFFER
  • re2c: http://re2c.org — 另一生成器路线,产出嵌入代码而不是全量 DFA 表
  • Clang: lib/Lex/Lexer.cpp — 手写 lexer 的工业标杆, 行号/缓冲/错误恢复

Keywords: lexer design, token kind, span, line/column tracking, line table, peek, consume, unget, ring buffer, double buffer, mmap, Unicode, XID_Start, XID_Continue, UTF-8, identifier, keyword table, error recovery, invalid character, unterminated string, hand-written lexer, lexer generator, flex, re2c

相关页面

© 2026 liz's doc