Appearance
词法分析
概念
词法分析（lexical analysis，也叫扫描 scanning）是编译器的第一站：把一长串字符切成一个个有意义的记号（token）。
输出不是一个"词"，而是记号 = 类别 + 词素：
int x = 3 + 42;切出来是 7 个记号：KW int、ID x、OP =、NUM 3、OP +、NUM 42、PUNC ;。
| 记号类别 | 例子 | 说明 |
|---|---|---|
| 关键字 KW | int、if、while | 语言保留，数量固定 |
| 标识符 ID | x、count、_tmp | 用户起的名字，数量不限 |
| 常量 NUM | 3、42、3.14 | 数值、字符、字符串字面量 |
| 运算符 OP | +、=、== | 参与运算 |
| 界符 PUNC | ;、,、(、) | 只负责分界 |
为什么要单独设这一层：语法分析只需要知道"这是一个标识符"，不需要知道它由哪几个字母拼成。把字符层的琐碎工作（跳空格、跳注释、认数字）挡在外面，语法分析器就能干净一点。这正是 lang/20-steps.md 里编译器六小步的第 ① 步。
原理
一、词素的规则用正则描述
每一类记号都能写成一个正则表达式：
| 记号类别 | 正则 |
|---|---|
| 标识符 | letter (letter ∣ digit)* |
| 无符号整数 | digit digit* |
| 带小数的数 | digit+ . digit+ |
| 单字符运算符 | + - * / ( ) ; |
| 空白（要丢掉） | (空格 ∣ 制表 ∣ 换行)+ |
注意这里的竖线写成了 ∣（U+2223）——它在表格里必须换写法，因为 GFM 表格把竖线当列分隔符，写 | 会把整行切开（详见 md/somerules.md 专项纪律）。
二、正则 → NFA → DFA
正则便于人写，不好让机器执行。所以走三步：
正则表达式 --Thompson 构造--> NFA --子集构造--> DFA --最小化--> 最小 DFA
（人写） （机器不直接跑） （机器跑这个） （可选，省状态）- NFA（非确定有限自动机）：一个状态读同一个字符可以走向多个状态，还能不读字符就"凭空"跳（ε 转移）。它的"非确定"是给构造用的，不是给执行用的。
- DFA（确定有限自动机）：一个状态读一个字符，去向唯一。执行时只需要一张转移表，每读一个字符查一次表，没有回溯，一共 O(n) 步。
- 子集构造：把 NFA 的"状态集合"当成 DFA 的"一个状态"。NFA 有
为什么执行要 DFA 而不是 NFA：NFA 执行要同时跟踪一队可能状态（或反复回溯），而词法是每一个字符都要过的热点代码，必须做到"读一个字符、跳一次"。
三、扫描器的两条硬规则
- 最长匹配（贪婪）：能凑出更长的记号，就绝不多切。
a+++b要切成a+++b，而不是a+++b。 - 关键字优先：先查关键字表，命中就不再当标识符。
int是关键字，intx和iff是标识符——关键字表是一个小哈希表，在识别出完整单词之后再查。
四、怎么把扫得快做到极致
- 双缓冲：一次读一大块到内存，指针滑到缓冲区末尾才补下一块，把"读文件"的开销摊薄。
- 哨兵：在缓冲区末尾放一个永不匹配任何字符的哨兵字符，循环里就不用每次都写"还没到末尾"的判断。
- 查表代替分支：
if (isalpha(c)) ... else if (isdigit(c)) ...换成一张字符类别表，一次数组访问。
五、词法错误怎么处理
词法分析很少单独"报错退出"：遇到既不是字母、数字，也不在运算符表里的字符，就吃掉它、记一条日志，继续往下扫。原因是词法层没有全局视角，为一个坏字符中断整个编译，对用户毫无帮助。
示例
例 1：手写一个扫描器（C）
#include <stdio.h>
#include <ctype.h>
#include <string.h>
static const char *KW[] = {"int", "if", "else", "while", "return"};
static int is_kw(const char *s) {
for (int i = 0; i < 5; i++)
if (strcmp(s, KW[i]) == 0) return 1;
return 0;
}
int main(void) {
const char *src = "int x = 3 + 42;";
int i = 0;
while (src[i]) {
unsigned char c = src[i];
if (isspace(c)) { i++; continue; } /* 空白直接丢 */
if (isalpha(c) || c == '_') { /* 字母开头 -> 标识符或关键字 */
char buf[64]; int n = 0;
while (isalnum((unsigned char)src[i]) || src[i] == '_')
buf[n++] = src[i++];
buf[n] = '\0';
printf("%-6s %s\n", is_kw(buf) ? "KW" : "ID", buf);
} else if (isdigit(c)) { /* 数字开头 -> 常量 */
char buf[64]; int n = 0;
while (isdigit((unsigned char)src[i])) buf[n++] = src[i++];
buf[n] = '\0';
printf("%-6s %s\n", "NUM", buf);
} else { /* 剩下的是运算符或界符 */
printf("%-6s %c\n", strchr(";,", c) ? "PUNC" : "OP", c);
i++;
}
}
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
KW int
ID x
OP =
NUM 3
OP +
NUM 42
PUNC ;例 2：子集构造与关键结论（Python 对照）
def pad(s, w):
"""按显示宽度补空格：中文算 2 列"""
return s + " " * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))
# ---- ① NFA：正则 (a|b)*abb，4 个状态 ----
NFA = {
0: {"a": {0, 1}, "b": {0}},
1: {"b": {2}},
2: {"b": {3}},
3: {},
}
print("=== NFA 转移表（4 个状态，起始 0，接受 3） ===")
print(" " + pad("状态", 8) + pad("a", 10) + "b")
for s in sorted(NFA):
a = ",".join(str(x) for x in sorted(NFA[s].get("a", []))) or "-"
b = ",".join(str(x) for x in sorted(NFA[s].get("b", []))) or "-"
print(" " + pad(str(s), 8) + pad(a, 10) + b)
# ---- ② 子集构造：NFA -> DFA ----
order, seen = [], set()
start = frozenset([0])
work, seen = [start], {start}
DFA = {}
while work:
cur = work.pop(0)
order.append(cur)
row = {}
for ch in "ab":
nxt = set()
for s in cur:
nxt |= NFA[s].get(ch, set())
if nxt:
key = frozenset(nxt)
row[ch] = key
if key not in seen:
seen.add(key)
work.append(key)
DFA[cur] = row
name = {st: "S%d" % i for i, st in enumerate(order)}
print()
print("=== 子集构造得到的 DFA ===")
print(" " + pad("状态", 8) + pad("含 NFA 状态", 20) + pad("a", 8) + pad("b", 8) + "接受?")
for st in order:
inner = "{" + ",".join(str(x) for x in sorted(st)) + "}"
a = name[DFA[st]["a"]] if "a" in DFA[st] else "-"
b = name[DFA[st]["b"]] if "b" in DFA[st] else "-"
print(" " + pad(name[st], 8) + pad(inner, 20) + pad(a, 8) + pad(b, 8)
+ ("是" if 3 in st else "否"))
print(" -> NFA 4 个状态 -> DFA %d 个状态" % len(order))
# ---- ③ 用 DFA 扫一遍 ababb ----
print()
print("=== 用 DFA 扫描 ababb ===")
print(" " + pad("已读入", 10) + pad("落在状态", 12) + "是否命中 abb")
cur = start
for ch in "ababb":
inner = "{" + ",".join(str(x) for x in sorted(cur)) + "}"
cur = DFA[cur][ch]
acc = "是" if 3 in cur else "否"
print(" " + pad(inner, 10) + pad(name[cur], 12) + acc)
# ---- ④ 手写扫描器：字符流 -> 记号流 ----
KEYWORDS = {"int", "if", "else", "while", "return"}
SRC = "int x = 3 + 42;"
i, toks = 0, []
while i < len(SRC):
c = SRC[i]
if c.isspace():
i += 1
continue
if c.isalpha() or c == "_":
j = i
while j < len(SRC) and (SRC[j].isalnum() or SRC[j] == "_"):
j += 1
w = SRC[i:j]
toks.append(("KW" if w in KEYWORDS else "ID", w))
i = j
elif c.isdigit():
j = i
while j < len(SRC) and SRC[j].isdigit():
j += 1
toks.append(("NUM", SRC[i:j]))
i = j
else:
toks.append(("PUNC" if c in ";," else "OP", c))
i += 1
print()
print("=== 扫描 " + SRC + " ===")
print(" " + pad("序号", 6) + pad("类别", 8) + "词素")
for k, (t, v) in enumerate(toks, 1):
print(" " + pad(str(k), 6) + pad(t, 8) + v)
print(" -> 共 %d 个记号" % len(toks))
# ---- ⑤ 最长匹配 ----
print()
print("=== 最长匹配：a+++b 怎么切 ===")
S2 = "a+++b"
i, out = 0, []
while i < len(S2):
if S2[i:i + 2] == "++":
out.append("++")
i += 2
else:
out.append(S2[i])
i += 1
print(" " + S2 + " -> " + " ".join(out))
print(" 规则：能凑出更长的记号就绝不多切（贪婪扫描）")
# ---- ⑥ 关键字优先于标识符 ----
print()
print("=== 关键字表先查，命中就不再当标识符 ===")
for w in ["int", "intx", "iff"]:
print(" " + pad(w, 8) + ("关键字" if w in KEYWORDS else "标识符"))
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
=== NFA 转移表（4 个状态，起始 0，接受 3） ===
状态 a b
0 0,1 0
1 - 2
2 - 3
3 - -
=== 子集构造得到的 DFA ===
状态 含 NFA 状态 a b 接受?
S0 {0} S1 S0 否
S1 {0,1} S1 S2 否
S2 {0,2} S1 S3 否
S3 {0,3} S1 S0 是
-> NFA 4 个状态 -> DFA 4 个状态
=== 用 DFA 扫描 ababb ===
已读入 落在状态 是否命中 abb
{0} S1 否
{0,1} S2 否
{0,2} S1 否
{0,1} S2 否
{0,2} S3 是
=== 扫描 int x = 3 + 42; ===
序号 类别 词素
1 KW int
2 ID x
3 OP =
4 NUM 3
5 OP +
6 NUM 42
7 PUNC ;
-> 共 7 个记号
=== 最长匹配：a+++b 怎么切 ===
a+++b -> a ++ + b
规则：能凑出更长的记号就绝不多切（贪婪扫描）
=== 关键字表先查，命中就不再当标识符 ===
int 关键字
intx 标识符
iff 标识符三条结论：
- 本例里 NFA 4 个状态、DFA 也是 4 个状态，纯属巧合；子集构造的上界是
- DFA 扫描没有分支、没有回溯：读
ababb五次，状态一路S0 → S1 → S2 → S1 → S2 → S3，最后一次落在接受态，说明整个串以abb结尾。 - 投影式的"落在状态"列里
{0,1}这类写法就是"DFA 状态 = NFA 状态集合"的字面体现——子集构造的名字即由此而来。
考点
考点
1. 三步各自的产物（必背）
- 正则 → NFA 用 Thompson 构造：每个基本正则对应一小块结构，再拼起来。
- NFA → DFA 用 子集构造：DFA 的一个状态 = NFA 的一个状态集合；上限
- DFA 化简 用最小化（Hopcroft 的分裂法）：把等价状态合并，最小 DFA 在"忽略状态名"的意义下唯一。
2. NFA 与 DFA 的分工
| 项 | NFA | DFA |
|---|---|---|
| 同一字符的去向 | 可以有多个 | 唯一 |
| ε 转移 | 允许 | 不允许 |
| 执行效率 | 要同时跟踪多个状态或回溯 | 每字符一次查表，O(n) |
| 构造难度 | 从正则直接拼，容易 | 要跑子集构造 |
| 用途 | 给构造用 | 给执行用 |
一句话："正则好写、NFA 好造、DFA 好跑"，所以三者都要有。
3. 两条扫描规则
- 最长匹配：
a+++b→a+++b；a<=b→a<=b，绝不是a<=. - 关键字优先：
int是关键字，intx、iff是标识符。所以必须先扫出完整的单词，再查关键字表，不能边扫边比。
4. 高频陷阱
- 词法错误 ≠ 语法错误：
3x会被切成NUM 3和ID x，词法分析不报错，是语法分析发现两个相邻记号接不上才报错。反过来@这种字符才真的是词法错误。 - 空白、注释、行号这类"没有语义但影响报错位置"的东西，都由词法层处理——所以报错时能给出"第几行第几列"。
- 不要在 NFA 上直接跑：NFA 的执行要么回溯要么多状态并行，都不是词法分析该付出的代价。
- 关键字不是靠正则识别的：
int与intx的正则都能匹配int那一段，光靠正则分不开，必须配一张关键字表。
小结
- 词法分析 = 字符流 → 记号流，输出的是"类别 + 词素"，不是原样的字符串。
- 规则用正则写、机器用DFA跑，中间靠 Thompson 构造与子集构造衔接。
- 扫描器的两条铁律是最长匹配与关键字优先。
- 这一层的错误很少单独终止编译：能在词法层继续，就不要在词法层报错。
回到主线：lang/20-steps.md 把"从 C 源文件到可执行文件"拆成预处理、编译、汇编、链接四步，编译器内部再分六小步。本篇就是把那六小步里的第 ① 步单独摊开看——上一次你只知道"词法分析把字符切成记号"，现在你知道记号长什么样、自动机怎么造、扫描器怎么写得快。
下一篇：语法分析
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。