2 Lexical Analysis
职责
词法分析器(Scanner / Lexer)是编译器的第一个阶段,做三件事:
- 切分:把连续的字符流切成有意义的单元
- 归类:给每个单元打上类别
- 过滤:丢掉空白、换行、注释
输出是一串 Token,每个 Token 形如 <类别, 属性值>:
源码: if (x <= 10) count++;
Token: [IF, -] [LPAREN, -] [ID, "x"] [LE, -] [NUM, 10]
[RPAREN, -] [ID, "count"] [INC, -] [SEMI, -]属性值(lexical value)只对标识符和常量有意义——关键字、运算符的类别本身就足够,值可以为空。
为什么"切分"不是简单的事
直觉上 split() 就够了,但真实语言有几处坑:
最长匹配:<= 必须识别成一个 LE,而不是 < 加 =。同理 ==、>=、!=、++、->、::。
回退:匹配 <= 时要先看到 < 再试探 =。如果后面不是 =,要回退一个字符再重新走。这就是"最长匹配 + 回退"机制。
关键字还是标识符:if 是关键字,iffy 是标识符。必须先按标识符的规则扫完整个单词,再查保留字表判断。
上下文相关:C++ 的 >> 在模板嵌套里要当两个 >;C 的 typedef 会让后续标识符变成类型名。这类问题严格说词法层解决不了,业界做法是词法分析器和语法分析器互相打信号(lexer hack / symbol table feedback)。
正则定义
形式化地描述 Token 的模式。正则比文法弱,但恰好够用——因为词法结构不需要记忆嵌套。
给定字母表,正则定义:
| 符号 | 含义 |
|---|---|
| 空串 | |
| 单个字符 | |
| 选择(或) | |
| 连接 | |
| 闭包(零次或多次) | |
| 正闭包(一次或多次) | |
| 可选 |
常见 Token 的正则:
letter = [A-Za-z_]
digit = [0-9]
id = letter (letter | digit)*
int = digit+
float = digit+ '.' digit* ( [eE] [+-]? digit+ )?
| '.' digit+ ( [eE] [+-]? digit+ )?
ws = (' ' | '\t' | '\n' | '\r')+
comment = '//' [^\n]* | '/*' ([^*] | '*'+ [^*/])* '*'+ '/'注意 float 的定义里,1.、.5、1e10 都得覆盖,还要防止 1..2 被误吃。写浮点正则时最容易漏的就是指数部分。
有限自动机
正则只是声明,自动机才是执行。
DFA vs NFA
| DFA(确定) | NFA(不确定) | |
|---|---|---|
| 同一状态同一输入 | 唯一后继 | 可有多个后继 |
| 转移 | 不允许 | 允许 |
| 匹配复杂度 | 回溯时可能指数级 | |
| 构造难度 | 难(直接从正则构造) | 易 |
| 状态数 | 可能指数级膨胀 | 与正则规模线性 |
结论:用 NFA 便于构造,转成 DFA 便于执行。
Thompson 构造:正则 → NFA
递归地把正则翻译成带 转移的 NFA 片段:
ε: ──►(s)──ε──►(f)
a: ──►(s)──a──►(f)
r|s: ┌──ε─►[NFA r]─ε─┐
──►(s)─┤ ├─►(f)
└──ε─►[NFA s]─ε─┘
rs: ──►[NFA r]──►[NFA s]──►
r*: ┌────────ε────────┐
│ ▼
──►(s)──ε──►[NFA r]──ε──►(f)
└───────ε───────►每个构造只增加常数个状态,所以总状态数是。
子集构造:NFA → DFA
核心思想:DFA 的一个状态 = NFA 的一个状态集合。
算法(省略 ε-closure 细节):
Dstates = { ε-closure(nfa_start) } 未标记
while 存在未标记的 DFA 状态 T:
标记 T
for 每个输入符号 a:
U = ε-closure(move(T, a))
if U 非空 且 U ∉ Dstates:
Dstates.add(U) 未标记
Dtrans[T, a] = Uε-closure(S):从 S 中状态出发,只走 边能到达的所有状态。 move(T, a):T 中状态经符号 a 能直接到达的状态集合。
最坏情况状态数指数爆炸,但实际的词法规则很少触发——因为真实 Token 的模式都很简单。
最小化:Hopcroft 算法
把 DFA 的状态按"行为是否等价"合并。步骤:
- 初始划分:接受态 / 非接受态(再按对应 Token 类型细分)
- 反复细分:若状态 同组,但 与 不同组,则拆分
- 到划分不再变化为止
最小化后的 DFA 是同语言下状态数最少的(唯一,同构意义下)。
从自动机到词法分析器
教科书路线:正则 → NFA → DFA → 最小化 DFA → 表驱动扫描器。
正则规则集
│ Thompson 构造
▼
NFA
│ 子集构造
▼
DFA
│ Hopcroft 最小化
▼
最小 DFA ──► 转移表(二维数组)
│
▼
表驱动扫描器工业界(flex、re2c、Go 的 lexer)确实走这条路,因为转移表可以预先算好,运行时是纯粹的数组查表,快且可预测。
但手写 lexer 通常更直接——用 switch + 手写状态机,因为可读性更好、调试更容易、还能处理上面那些"词法层解决不了"的边界情况。LLVM/Clang、V8、Lua 的 lexer 都是手写的。
最长匹配与优先级
两条规则同时匹配时:
- 最长匹配优先:能匹配多长就匹配多长
- 同等长度时,先声明的规则优先
第二条决定了关键字必须写在标识符前面(或单独查表):
"if" { return IF; } /* 声明在前,同等长度优先命中 */
[a-z]+ { return ID; }如果把 [a-z]+ 写在前面,if 就永远被当标识符了。
手写词法分析器:一个能跑的实现
// 一个够用的 C 子集 lexer
#include <string>
#include <vector>
#include <cctype>
enum class Tok {
End, If, Else, While, Return, Int,
Id, Num,
Assign, Eq, Ne, Le, Lt, Ge, Gt,
Plus, Minus, Star, Slash,
LParen, RParen, LBrace, RBrace, Semi, Comma
};
struct Token {
Tok kind;
std::string text; // lexeme
long long value; // Num 的字面值
};
class Lexer {
const std::string& src;
size_t pos = 0;
static const std::vector<std::pair<const char*, Tok>>& keywords() {
static const std::vector<std::pair<const char*, Tok>> kw = {
{"if", Tok::If}, {"else", Tok::Else}, {"while", Tok::While},
{"return", Tok::Return}, {"int", Tok::Int},
};
return kw;
}
char peek(size_t off = 0) const {
return pos + off < src.size() ? src[pos + off] : '\0';
}
void skipSpaceAndComments() {
for (;;) {
while (std::isspace((unsigned char)peek())) ++pos;
if (peek() == '/' && peek(1) == '/') { // 行注释
while (peek() && peek() != '\n') ++pos;
} else if (peek() == '/' && peek(1) == '*') { // 块注释
pos += 2;
while (peek() && !(peek() == '*' && peek(1) == '/')) ++pos;
pos += 2;
} else break;
}
}
public:
explicit Lexer(const std::string& s) : src(s) {}
Token next() {
skipSpaceAndComments();
size_t start = pos;
char c = peek();
if (!c) return {Tok::End, "", 0};
// 标识符 / 关键字
if (std::isalpha((unsigned char)c) || c == '_') {
while (std::isalnum((unsigned char)peek()) || peek() == '_') ++pos;
std::string text = src.substr(start, pos - start);
for (auto& [kw, k] : keywords())
if (text == kw) return {k, text, 0};
return {Tok::Id, text, 0};
}
// 数字
if (std::isdigit((unsigned char)c)) {
long long v = 0;
while (std::isdigit((unsigned char)peek()))
v = v * 10 + (peek() - '0'), ++pos;
return {Tok::Num, src.substr(start, pos - start), v};
}
// 运算符:先试探两字符,再回退到单字符
auto two = [&](char b, Tok t) {
if (peek(1) == b) { pos += 2; return Token{t, src.substr(start, 2), 0}; }
return Token{Tok::End, "", 0};
};
switch (c) {
case '=': { auto t = two('=', Tok::Eq); return t.kind == Tok::End ? (++pos, Token{Tok::Assign, "=", 0}) : t; }
case '!': { auto t = two('=', Tok::Ne); return t.kind == Tok::End ? (++pos, Token{Tok::End, "!", 0}) : t; }
case '<': { auto t = two('=', Tok::Le); return t.kind == Tok::End ? (++pos, Token{Tok::Lt, "<", 0}) : t; }
case '>': { auto t = two('=', Tok::Ge); return t.kind == Tok::End ? (++pos, Token{Tok::Gt, ">", 0}) : t; }
case '+': ++pos; return {Tok::Plus, "+", 0};
case '-': ++pos; return {Tok::Minus, "-", 0};
case '*': ++pos; return {Tok::Star, "*", 0};
case '/': ++pos; return {Tok::Slash, "/", 0};
case '(': ++pos; return {Tok::LParen, "(", 0};
case ')': ++pos; return {Tok::RParen, ")", 0};
case '{': ++pos; return {Tok::LBrace, "{", 0};
case '}': ++pos; return {Tok::RBrace, "}", 0};
case ';': ++pos; return {Tok::Semi, ";", 0};
case ',': ++pos; return {Tok::Comma, ",", 0};
default: ++pos; return {Tok::End, std::string(1, c), 0}; // 非法字符
}
}
};要点:
peek(off)做前瞻,配合"试探两字符再回退"实现最长匹配- 关键字用查表而非写进状态机,规则集变化时不用改自动机
- 非法字符不直接终止,而是返回一个特殊 Token 并继续——这样一次能报多个错
- 常量在词法阶段就把字符串转成数值,后面不用再解析
缓冲:为什么需要双缓冲区
扫描器要频繁前瞻再回退,如果直接读文件会大量 seek。经典解法是双缓冲区(double buffering):
[ 前半 1024B ][ 后半 1024B ]
▲ ▲
lexemeBegin forwardforward 前瞻时可能跨到后半;当 forward 到达某半末尾,立刻读下一块填进另一半;若整个缓冲区都不够装一个 Token(超长字符串),则扩容。这样绝大部分前瞻都在内存里完成。
现代实现没这么讲究——直接把整个源文件读进内存就行,几 MB 的源码现代机器毫无压力。双缓冲区是内存按 KB 计时代的产物,但思想(批量读 + 指针扫描)还在。
错误处理
词法层能发现的错误有限但必须优雅处理:
| 错误 | 处理 |
|---|---|
非法字符(@、$ 在非允许位置) | 报错,跳过该字符继续 |
| 字符串/注释未闭合 | 报错,标记文件结束 |
| 数字溢出 | 报错,取截断值或标记 |
策略是 "绝不终止编译",尽量多报。报错信息要带行列号,所以扫描时需要维护 line 计数(遇到 \n 自增,行首记录 colBase)。
常见坑
- 忘记最长匹配,把
<=切成<和=,语法阶段报一堆莫名其妙的错 - 关键字表顺序,或者干脆忘了关键字也要走最长匹配(
ifx不能切成if+x) - 浮点数正则漏掉指数,
1e10被切成1和e10 - 注释嵌套:C 的
/* */不嵌套,但/* // */里的//不是注释开始——必须先处理块注释 - 预处理在词法之前:C/C++ 里
#define、#include由预处理器处理,严格来说在词法分析之前(现代编译器把二者融合了) - Unicode:标识符允许中文/emoji 时,
isalpha要换成 UTF-8 解码,不能按字节扫
参考
- flex / re2c:自动生成词法分析器
- Crafting Interpreters - Scanning
- re2c 的 DFA 生成思路:NFA → DFA → 最小化 → 直接生成 C
goto代码(比转移表更快)