P1 · 调试器：给还没出生的 CPU 装上 GDB

本章目标

读完本章你能回答：

• 为什么 stage 1 不写 CPU，而是写调试器？——可观测性先于可执行性
• p $pc + 4 从按下回车到打印出 0x80000004，中间发生了哪 3 件事？
• 为什么 9 个调试命令里有 5 个”长得一样”？
• 怎么测试一个”自己就是解释器”的程序？

以及你能动手做：

• 写一个表驱动的 regex 词法分析器，处理 20 多种 token
• 写一个递归下降 parser，10 层优先级，支持 C 风格的混合运算
• 写一个监视点系统，复用表达式求值器、嵌入主循环只需 1 行
• 写一个差分模糊测试，用宿主 cc 做 oracle 对拍自己写的求值器

---

1. 为什么此刻不写 CPU

直觉告诉你：”计算机最核心的是 CPU，先写 CPU 再说其他。”

这是新手 stage 1 翻车的头号原因。CPU 的问题不在实现难，而在调试难：

• 寄存器值不对——你打算怎么看？
• PC 跳错了——你打算怎么找？
• 内存被写乱了——你打算怎么对比前后？

没有调试器，你只有一种工具：printf。整个文件塞满 printf("pc=%x\n", pc)，跑一条指令看 50 行日志，改代码再删这些 printf……然后发现漏删了一条 printf 于是测试挂了。

换个视角：先把调试器写好，CPU 一出生就能被看见、被单步、被监视。这不是哲学，是工程节奏：

工程原则：可观测性先于可执行性。能”看见”系统比”让系统跑”更重要。一个跑不起来但能看见的系统，可以修；一个跑得起来但看不见的系统，只能重写。

那么，调试器能不能在 CPU 存在前写出来？ 能。它只需要两样东西：

/* 调试器今天唯一依赖的 CPU 接口，现在是 stub: */
word_t isa_reg_val(const char *name, bool *ok) {
    (void)name;
    *ok = true;
    return 0;
}

word_t paddr_read(paddr_t addr, int len) {
    (void)addr; (void)len;
    return 0;
}

整个本章，所有代码都在这两个函数上方工作。P2 会把 paddr_read 换成真的内存读、P3 会把 isa_reg_val 换成 cpu.gpr[i] 查表——签名不变，调试器一行不改。

这就是 P0 强调”先搭壳”的真意。Stage 0 的壳是 REPL，stage 1 的壳是调试器，CPU 来的时候所有脚手架都到位了。

1.1 GDB 的命令集 vs 我们的 9 个命令

我们要做的不是完整 GDB，而是它的最小可观测性集：

GDB 命令	我们对应的	作用
print	p EXPR	求值表达式
x /N WORDS	x N EXPR	扫描 N 个字从地址 EXPR
info reg	info r	打印寄存器
watch EXPR	w EXPR	监视点
delete N	d N	删监视点
step	si [N]	单步 N 条
continue	c	运行到停止
help	help [cmd]	帮助
quit	q	退出

看这张表你会发现一件有意思的事：9 个命令里，p / x / w / d / info 五个都需要某种”解析参数”的能力。它们的参数不是原生 int，是表达式——p $pc + 4、x 10 $sp - 32、w *0x80001000。

所以本章真正的主角不是”9 个命令”，而是表达式求值器。9 个命令 = 1 个共享基础 + 少量分派逻辑。

---

2. 核心概念：表达式求值是本章的隐藏主角

我们先用最偷懒的方式实现 p，看看能不能蒙混过关。

v1 · strtoul 版 cmd_p：

static int cmd_p(char *args) {
    word_t v = strtoul(args, NULL, 0);  /* base=0 自动识别 0x / 0 前缀 */
    printf("= 0x%08x\n", v);
    return 0;
}

跑一下：

(temu) p 42
= 0x0000002a
(temu) p 0xff
= 0x000000ff

看起来能用。然后你手贱试一下：

(temu) p 1+2
= 0x00000001        ← 期望 3

strtoul 吃到 + 就停了。问题是你真正想要的不是”把字符串转数字”，是”把字符串当C 表达式来算”。

再想想 x 10 EXPR 和 w EXPR——如果只有 strtoul，这俩命令的参数就只能是 42 / 0x80000000 这种字面量。不能写 x 10 $sp - 32，不能写 w *($pc + 8)。调试器的表达力就是表达式求值器的表达力。

2.1 三段式架构

表达式求值器做的事，就是把字符串变成数字：

  "$pc + 4"
      │
      │  ① Lexer  (char → token)
      ▼
  [TK_REG "$pc"]  [+]  [TK_NUM "4"]
      │
      │  ② Parser (递归下降，按优先级层层 recurse)
      ▼
  +(reg("pc"), num(4))
      │
      │  ③ Evaluator  (在 parse 时同步求值，不建 AST)
      ▼
  0x80000004

三段式是编译原理教材的标配。我们做一个简化版本：

• Lexer 用 regex.h 驱动——声明式写规则，比手写状态机好读
• Parser 和 Evaluator 合并——递归下降时直接返回值，不建 AST

核心洞察：调试器的表达式很短（撑死二三十个 token），不需要 AST 做中间表示。”一次遍历出结果”的递归下降求值器，代码量只有建 AST 方案的一半。

2.2 理论视角：为什么 lexer 和 parser 要分开——Chomsky 层级

表达式求值能拆成 lexer + parser 不是偶然，背后有形式语言理论的硬约束。

1956 年 Noam Chomsky 定义了四种语言的层级（Chomsky hierarchy）：

类型	名字	能识别它的机器	例子
Type-3	Regular（正则）	DFA / NFA（有限自动机）	[0-9]+、浮点数字面量
Type-2	Context-Free（上下文无关）	下推自动机（带栈的 FA）	(((...))) 配对括号、C 表达式
Type-1	Context-Sensitive	Linear-bounded automaton	自然语言的一部分
Type-0	Recursively Enumerable	图灵机	任何可计算的事

关键分水岭是 Type-3 和 Type-2：

• 正则语言能用纯状态机识别——没有栈、不能递归、不能匹配配对括号。这就是为什么 regex 不能正确匹配 “任意层嵌套的括号” （虽然现代 PCRE regex 加了递归扩展，但那已经不是数学意义上的”正则”了）
• 上下文无关语言需要栈——因为你要 “记住”入栈了多少个左括号才能验证右括号够不够

Lexer / Parser 分工就是按这条线切的：

"1 + (2 * 3)"
    │
    │  ① Lexer  (正则 / Type-3 级别)
    ▼            ·只认识扁平 token，不管嵌套
[NUM "1"] [+] [(] [NUM "2"] [*] [NUM "3"] [)]
    │
    │  ② Parser (上下文无关 / Type-2 级别)
    ▼            ·递归下降时用 call stack 处理括号嵌套

为什么这样分工？ 两个理由：

1. 计算复杂度：正则引擎 O(n)，CFG 引擎至少 O(n log n)（实用算法如 recursive descent 接近 O(n)，但最坏 O(n³) 如 CYK）。能用正则的部分就别用 CFG 搞
2. 职责分离：lexer 负责”认字符”、parser 负责”认结构”。把”去掉空格”、”识别关键字”这些脏活留给 lexer，parser 只看干净的 token 流——代码量减半

形式对应：token 流是 Type-3 的”输出”，也是 Type-2 的”输入”。Chomsky 层级在软件工程里最常见的落地形式——就是 lexer → parser 的这根箭头。

这也解释了一个新手疑惑：”为什么不用一个大正则就把整个表达式 match 了？”—— 因为 C 表达式不是正则语言。配对括号、嵌套一元算符都需要栈。单层 regex 根本表达不了。

---

3. 设计选择

三个岔路口，每个都有”正确但啰嗦”和”偷懒但足够”的答案：

3.1 Lexer：手写状态机 vs regex.h

维度	手写状态机	regex.h
代码量	规则越多越爆炸	一条规则 = 一行
运行速度	快	慢（解释执行）
可读性	需要读代码才知道规则	规则表一眼看懂
依赖	零	POSIX libc
调试器需要吗	不热	选它

调试器不是热点代码，用户敲一行表达式的成本远大于求值耗时。声明式规则能让你几秒钟看完全部支持的 token。

3.2 Parser：优先级表 vs 递归下降

优先级表 + shunting-yard（Dijkstra 的算法）：

• 优点：紧凑，一个循环搞定所有优先级
• 缺点：算法不直观，调试时难看出”这一层在处理哪个优先级”

递归下降（recursive descent，一层优先级一个函数）：

• 优点：函数调用栈直接映射到 C 语言的优先级表，单步调试时肉眼可见
• 缺点：函数多（10 层优先级 = 10 个函数）

我们选递归下降。每个函数 10 行以下，总代码量和 shunting-yard 相当，但读起来就像在抄 C 参考手册。

3.3 建 AST vs 直接求值

我们不建 AST。parser 递归返回 word_t，parse 完成的那一刻值也算出来了。

代价：失去一些东西，比如真正的短路求值（1 || f() 会把 f() 也求一遍）、常量折叠、好看的语法错误定位。本章都不需要。

3.4 实现哪些优先级？

C 语言有 13 层优先级，TEMU 实现其中 10 层：

优先级（高→低）	运算符	实现？
1	*EXPR ~ ! -（一元）	✅
2	* / %	✅
3	+ -	✅
4	<< >>	✅
5	< <= > >=	✅
6	== !=	✅
7	&	✅
8	^	✅
9	\|	✅
10	&&	✅
11	\|\|	✅
12	?:	❌（YAGNI）
13	, / =	❌（YAGNI）

三目运算符 ?:、逗号 / 赋值——调试器里用不上，20 行代码换不到 1 次使用场景，直接砍。

3.5 理论视角：递归下降在解析算法家族中的位置

我们选递归下降不是因为”简单”，而是因为它是LL(1) parser 的手写版——在解析算法家族里是一个有明确理论定位的选择。

Parsing 算法按”从哪端开始推导”分成两大阵营：

方向	算法族	代表	特点
Top-down（从起始符号推）	LL(k), PEG	递归下降、ANTLR、yacc 的替代	一边读一边猜产生式，call stack = 语法树
Bottom-up（从输入推）	LR(k), LALR(1), SLR	Bison/Yacc 生成的 parser	移进归约，用 table 驱动，认得的文法更广

LL(k) vs LR(k) 的直觉区别：

• LL(k)：Left-to-right scan, Leftmost derivation, k tokens lookahead。每步看前 k 个 token 决定用哪条产生式。递归下降就是 LL(1) 手写版（每步看 1 个 token）。
• LR(k)：Left-to-right scan, Rightmost derivation (reversed), k tokens lookahead。先移进再归约，能处理的文法比 LL(k) 严格更广——但人写不了，要 table 驱动。

LL 能力的限制：左递归

LL parser 看到产生式 A → A op B 时会死循环——第一步就递归调用自己，没推进。所以我们的 EBNF 必须写成：

add    = mul ("+" mul)*        ✅ LL 友好
-- 等价但 LL 处理不了：
add    = add "+" mul | mul     ❌ 左递归

这就是为什么我们所有二元层都用 while 循环 + parse_next_level()——那是 LL 表达左结合的标准等价形式（消除左递归）。

工业选择：

• gcc / clang：手写递归下降（LL 类，但用了大量 backtracking 和 hack）—— 性能好、错误信息可控、可增量
• Bison / Yacc：LALR(1)（LR 的紧凑变种）生成 parser —— 能处理 GCC 早期也用过的复杂文法，但 debug 痛苦
• Python / JavaScript / TypeScript：都用手写 LL 或 PEG —— 现代趋势
• PEG parsers（Parsing Expression Grammar）：有顺序选择 / 和内置 backtrack，理论上更强

为什么教学选递归下降：

/* recursive descent 的 debug 体验 */
parse_expr → parse_logor → parse_logand → parse_bor
                                              │
                                              ↓
                     这里单步调试就能看到"当前正在处理哪个优先级"

call stack = 语法树的深度。调试器单步时你能直接看到解析进度。LR 用 table 驱动，调试时看到的是一堆 state number，人完全读不懂。

结论：递归下降既满足理论要求（LL(1) 手写），又有最好的调试体验——是教学场景的最优解。工业场景嘛……要看你和性能 / 文法复杂度谁更贵。

---

4. 代码实现 · 上篇：Lexer

4.1 Token 类型定义

单字符 token 我们复用 ASCII 值（+ 就是 43），多字符 token 从 256 开始用 enum 定义——绝不和 ASCII 冲突：

enum {
    TK_NOTYPE = 256,
    TK_NUM, TK_HEXNUM, TK_REG,
    TK_EQ, TK_NEQ, TK_LE, TK_GE,
    TK_AND, TK_OR,
    TK_SHL, TK_SHR,
    TK_DEREF, TK_NEG,
};

注意末尾那两个 TK_DEREF / TK_NEG——它们在词法阶段并不存在，是 lex 之后一个 fixup pass 里改出来的。保留悬念，见 §4.4。

4.2 规则表：顺序是一切

static struct rule {
    const char *re;
    int         type;
} rules[] = {
    { "[ \t]+",                    TK_NOTYPE },
    { "0[xX][0-9a-fA-F]+",         TK_HEXNUM },   /* must precede NUM  */
    { "[0-9]+",                    TK_NUM    },
    { "\\$[a-zA-Z_][a-zA-Z_0-9]*", TK_REG    },

    { "==", TK_EQ  }, { "!=", TK_NEQ },           /* must precede '!'  */
    { "<=", TK_LE  }, { ">=", TK_GE  },           /* must precede <,>  */
    { "&&", TK_AND }, { "\\|\\|", TK_OR },
    { "<<", TK_SHL }, { ">>", TK_SHR },           /* must precede <,>  */

    { "\\+", '+' }, { "-", '-' },
    { "\\*", '*' }, { "/", '/' }, { "%", '%' },
    { "<",  '<' }, { ">",  '>' },
    { "&",  '&' }, { "\\|", '|' }, { "\\^", '^' },
    { "~",  '~' }, { "!",  '!' },
    { "\\(", '(' }, { "\\)", ')' },
};

为什么 == 必须排在 != 之后？其实不需要。但 == / != / <= / >= 都必须排在单字符 < > 的前面，否则遇到 <= 时引擎先匹配 <，余下的 = 变成未识别字符。

同理 0x 必须在 [0-9] 前：否则 0x80 会先被切成 TK_NUM "0" + 剩下的 x80 无法识别。

核心洞察：POSIX regex 引擎是按表顺序第一个匹配，不是最长匹配。这意味着规则顺序就是语义。把多字符 token 放前面是一条不能违反的规矩。

4.3 编译 + 匹配

regcomp 把字符串规则编译成 DFA，贵；regexec 匹配，便宜。所以只编译一次：

static regex_t re_compiled[NR_RULES];

static void init_regex(void) {
    static bool done = false;
    if (done) return;
    for (int i = 0; i < NR_RULES; i++) {
        int ret = regcomp(&re_compiled[i], rules[i].re, REG_EXTENDED);
        if (ret != 0) {
            char buf[128];
            regerror(ret, &re_compiled[i], buf, sizeof buf);
            panic("expr: cannot compile regex '%s': %s", rules[i].re, buf);
        }
    }
    done = true;
}

static bool done 加上 early return 是函数级幂等性的惯用法——多次调用没事。

4.4 make_tokens v1（有缺陷版）

static bool make_tokens_v1(const char *s) {
    nr_token = 0;
    int pos = 0;
    while (s[pos] != '\0') {
        bool matched = false;
        for (int i = 0; i < NR_RULES; i++) {
            regmatch_t m;
            /* rm_so == 0 保证是"在当前位置开头"匹配，不是"在字符串中间找到" */
            if (regexec(&re_compiled[i], s + pos, 1, &m, 0) == 0 &&
                m.rm_so == 0) {
                int len = (int)m.rm_eo;
                int type = rules[i].type;
                if (type != TK_NOTYPE) {
                    tokens[nr_token].type = type;
                    memcpy(tokens[nr_token].str, s + pos, len);
                    tokens[nr_token].str[len] = '\0';
                    nr_token++;
                }
                pos += len;
                matched = true;
                break;
            }
        }
        if (!matched) {
            Log("unexpected character at: '%s'", s + pos);
            return false;
        }
    }
    return true;
}

喂它 "1 + 2"，得到：

[TK_NUM "1"]  [+]  [TK_NUM "2"]

漂亮。喂它 "-5"：

[-]  [TK_NUM "5"]

……parser 看到开头是 - 该怎么办？它不知道这是”一元取负”还是”二元减号的左操作数缺失”。歧义问题就地出现。

类似地，*0x80001000 的 * 是解引用还是”乘法”？取决于前面有没有操作数。

4.5 Unary fixup：5 行代码解决四种歧义

关键观察：一元算符只会出现在”上一个 token 不是操作数”的位置。

/* 什么算"操作数"？常数、寄存器、右括号 —— 这之后的 - / * 一定是二元。 */
static bool is_operand_tok(int t) {
    return t == TK_NUM || t == TK_HEXNUM || t == TK_REG || t == ')';
}

然后在 make_tokens 末尾加一个后处理 pass：

/* Disambiguate unary operators: if '*' or '-' does not follow an
 * operand token, treat it as dereference / negation. */
for (int i = 0; i < nr_token; i++) {
    bool prev_is_operand =
        (i > 0) && is_operand_tok(tokens[i - 1].type);
    if (tokens[i].type == '*' && !prev_is_operand) tokens[i].type = TK_DEREF;
    if (tokens[i].type == '-' && !prev_is_operand) tokens[i].type = TK_NEG;
}

5 行代码，同时解决四种歧义：

输入	token 流（fixup 前）	token 流（fixup 后）
-5	[-] [5]	[NEG] [5]
a - b	[a] [-] [b]	[a] [-] [b]（不变）
*0x1000	[*] [0x1000]	[DEREF] [0x1000]
a * -b	[a] [*] [-] [b]	[a] [*] [NEG] [b]

工程原则：词法分析器和 parser 的分界处会出现一些”不是严格词法也不是严格语法”的工作（比如一元歧义、缩进语法）。一个独立的后处理 pass 几乎总是比让 parser look-ahead 优雅。

---

5. 代码实现 · 中篇：Parser（递归下降）

5.1 EBNF 骨架

按优先级从低到高写：

logor    = logand ("||" logand)*
logand   = bor    ("&&" bor)*
bor      = bxor   ("|"  bxor)*
bxor     = band   ("^"  band)*
band     = eq     ("&"  eq)*
eq       = rel    (("==" | "!=") rel)*
rel      = shift  (("<" | "<=" | ">" | ">=") shift)*
shift    = add    (("<<" | ">>") add)*
add      = mul    (("+"  | "-")  mul)*
mul      = unary  (("*"  | "/" | "%") unary)*
unary    = ("-" | "!" | "~" | "*") unary | primary
primary  = NUM | HEXNUM | REG | "(" logor ")"

每一条产生式对应一个 C 函数——10 条 = 10 个函数。所有二元运算层的函数都是同一个模式：

v = next_level();
while (peek is my-op) { consume; r = next_level(); v = combine(v, op, r); }
return v;

5.2 Parser 状态 + helpers

static int  p_pos;   /* 当前 token 下标 */
static bool p_err;   /* 出错标志，报错就置 true，不 abort */

static Token *peek(void) {
    return (p_pos < nr_token) ? &tokens[p_pos] : NULL;
}
static Token *consume(void) {
    Token *t = peek();
    if (t) p_pos++;
    return t;
}
static bool eat(int type) {
    Token *t = peek();
    if (t && t->type == type) { p_pos++; return true; }
    return false;
}
static int peek_type(void) {
    Token *t = peek();
    return t ? t->type : 0;
}

策略选择：出错不立刻 return 逃出所有层（那样要到处 check return），而是置一个全局 p_err，继续返回 0 给上层。外层 expr() 入口统一判断。代码简单，代价是报错时会多走几步”无效求值”。

5.3 parse_primary：最内层

static word_t parse_primary(void) {
    Token *t = consume();
    if (!t) { Log("unexpected end of expression"); p_err = true; return 0; }
    switch (t->type) {
        case TK_NUM:
            return (word_t)strtoul(t->str, NULL, 10);
        case TK_HEXNUM:
            return (word_t)strtoul(t->str, NULL, 16);
        case TK_REG: {
            bool ok = false;
            word_t v = isa_reg_val(t->str + 1, &ok);   /* 跳过 '$' */
            if (!ok) { Log("unknown register '%s'", t->str); p_err = true; }
            return v;
        }
        case '(': {
            word_t v = parse_expr();
            if (!eat(')')) { Log("expected ')'"); p_err = true; }
            return v;
        }
        default:
            Log("unexpected token '%s'", t->str);
            p_err = true;
            return 0;
    }
}

( 分支是递归的入口：整个 parser 的”回到最外层”就是靠 parse_primary 里 ( 的递归调用 parse_expr。这是递归下降的核心”咬尾”。

5.4 parse_unary：右递归

static word_t parse_unary(void) {
    int t = peek_type();
    if (t == TK_NEG)   { consume(); return (word_t)(-(sword_t)parse_unary()); }
    if (t == '!')      { consume(); return parse_unary() ? 0 : 1; }
    if (t == '~')      { consume(); return ~parse_unary(); }
    if (t == TK_DEREF) { consume(); return paddr_read(parse_unary(), 4); }
    return parse_primary();
}

一元算符右结合：! ~ -5 = !(~(-5))。用”递归调用自己”而非 while 循环来自然实现右结合——每多一个一元，就多一层递归。

TK_DEREF 直接调 paddr_read。现在 stub 返回 0；P2 的时候换成真内存读，这一行不动。

5.5 二元算符层：一个模板套十次

static word_t parse_mul(void) {
    word_t v = parse_unary();
    while (1) {
        int op = peek_type();
        if (op != '*' && op != '/' && op != '%') break;
        consume();
        word_t r = parse_unary();
        if ((op == '/' || op == '%') && r == 0) {
            Log("division by zero");
            p_err = true;
            return 0;
        }
        if      (op == '*') v = v * r;
        else if (op == '/') v = v / r;
        else                v = v % r;
    }
    return v;
}

static word_t parse_add(void) {
    word_t v = parse_mul();
    while (1) {
        int op = peek_type();
        if (op != '+' && op != '-') break;
        consume();
        word_t r = parse_mul();
        v = (op == '+') ? v + r : v - r;
    }
    return v;
}

注意两件事：

1. 除零检查：我们宁可返回错误也不让宿主进程吃 SIGFPE。guest 的 bug 不能崩溃 host。
2. 左结合：while 循环 + v = f(v, r) 就是左结合的标准模式。a - b - c 算成 (a - b) - c。

移位层还有一个要点：

static word_t parse_shift(void) {
    word_t v = parse_add();
    while (1) {
        int op = peek_type();
        if (op != TK_SHL && op != TK_SHR) break;
        consume();
        word_t r = parse_add();
        /* shift by >=32 是 C 的 UB；RV32 硬件定义为用低 5 位，所以 mask 31 */
        v = (op == TK_SHL) ? (v << (r & 31)) : (v >> (r & 31));
    }
    return v;
}

注释里有隐藏考点：宿主 C 里 x << 32 是 undefined behavior——可能返回 0，可能返回 x，可能返回垃圾。但 RV32I 硬件规定”移位量取低 5 位”。我们的调试器是给 guest 用的，语义要跟 guest 硬件对齐，不是跟 host C 对齐。

5.5.1 理论视角：结合性在文法里的形式化

上面 parse_add 用 while 循环而非递归，这个选择是在编码左结合。右结合用另一种形式。两者都可以形式化到 EBNF 层面。

左结合文法的自然写法（但 LL 不能直接用）：

add    = add "+" mul | mul

这是左递归——add 的第一个符号可能是它自己。LL parser 调用 parse_add() 第一步再调 parse_add()，无限循环。

消除左递归的改写（Ullman & Aho 教的标准技巧）：

add    = mul add'
add'   = "+" mul add' | ε

add' 是辅助符号，它要么”吃一个 + mul 然后继续 add’“，要么空。这能跑但语法树形状变了——它变成右递归了！1 + 2 + 3 被解析成 (1 + (2 + 3)) 而不是 ((1 + 2) + 3)。对 + / * 这种数学上满足结合律的算符，结果无差；但 - / / 会出问题：10 - 5 - 3 应该是 2（左结合），右结合会变成 8。

所以我们用 while 循环——它是”消除左递归 + 显式用迭代保持左结合求值顺序”的产物：

word_t parse_add(void) {
    word_t v = parse_mul();            /* 先吃一个 mul */
    while (peek is + or -) {           /* 后面每吃一个 */
        consume;
        word_t r = parse_mul();
        v = combine(v, r);             /* 立刻左向合并 */
    }
    return v;
}

这对应 EBNF：

add    = mul (("+" | "-") mul)*

星号下的迭代做两件事：消除左递归（文法变 LL 友好）+ 保持左结合求值（在循环里立刻 combine 而非递归返回后合并）。

右结合文法（unary 层走这条）：

unary  = ("-" | "!" | "~" | "*") unary | primary

天然不左递归（第一个符号是终结符算符），所以可以直接右递归。我们的 parse_unary 正是这么写：

if (t == TK_NEG) { consume(); return -parse_unary(); }

递归自己 = 右结合。! ~ -5 推导成 !(~(-5))，正确。

总结一张表：

结合性	自然文法	LL 友好的改写	代码模式
左结合 a - b - c = (a-b)-c	左递归 A = A op B \| B	迭代形式 A = B (op B)*	v = next(); while(op) v = combine(v, next());
右结合 ! ~ -5 = !(~(-5))	右递归 A = op A \| B	不用改	return op(parse_self());

“为什么左右结合会是文法性质？” 因为文法决定语法树的形状，树的形状决定求值顺序。结合性不是一个独立的”语义规则”，它是 parser 构造过程的副作用。想明白这点你就真的理解了文法和语言的关系。

5.6 剩下的 6 层：一口气写完

下面这 6 个函数结构完全相同，只是换了算符和下一层：

static word_t parse_rel(void) {
    word_t v = parse_shift();
    while (1) {
        int op = peek_type();
        if (op != '<' && op != '>' && op != TK_LE && op != TK_GE) break;
        consume();
        word_t r = parse_shift();
        switch (op) {
            case '<':   v = (v <  r) ? 1 : 0; break;
            case '>':   v = (v >  r) ? 1 : 0; break;
            case TK_LE: v = (v <= r) ? 1 : 0; break;
            case TK_GE: v = (v >= r) ? 1 : 0; break;
        }
    }
    return v;
}
static word_t parse_eq(void) {
    word_t v = parse_rel();
    while (1) {
        int op = peek_type();
        if (op != TK_EQ && op != TK_NEQ) break;
        consume();
        word_t r = parse_rel();
        v = (op == TK_EQ) ? (v == r) : (v != r);
    }
    return v;
}
static word_t parse_band(void) {
    word_t v = parse_eq();
    while (peek_type() == '&') { consume(); v &= parse_eq(); }
    return v;
}
static word_t parse_bxor(void) {
    word_t v = parse_band();
    while (peek_type() == '^') { consume(); v ^= parse_band(); }
    return v;
}
static word_t parse_bor(void) {
    word_t v = parse_bxor();
    while (peek_type() == '|') { consume(); v |= parse_bxor(); }
    return v;
}
static word_t parse_logand(void) {
    word_t v = parse_bor();
    while (peek_type() == TK_AND) {
        consume();
        word_t r = parse_bor();
        v = (v && r) ? 1 : 0;
    }
    return v;
}
static word_t parse_logor(void) {
    word_t v = parse_logand();
    while (peek_type() == TK_OR) {
        consume();
        word_t r = parse_logand();
        v = (v || r) ? 1 : 0;
    }
    return v;
}
static word_t parse_expr(void) { return parse_logor(); }

一眼看下来你会发现——这不是复制粘贴，这是同一个算法实例化 10 次。递归下降的威力就是这么直接：C 优先级表上增加一层算符，就加一个同构函数。

5.7 入口：expr()

word_t expr(const char *s, bool *success) {
    init_regex();
    if (!make_tokens(s)) { *success = false; return 0; }
    if (nr_token == 0)   { *success = false; return 0; }

    p_pos = 0;
    p_err = false;
    word_t v = parse_expr();

    if (p_err) {
        *success = false;
        return 0;
    }
    /* 如果没把所有 token 消费完，说明输入有尾巴 */
    if (p_pos != nr_token) {
        Log("trailing garbage starting at token #%d ('%s')",
            p_pos, tokens[p_pos].str);
        *success = false;
        return 0;
    }
    *success = true;
    return v;
}

最后那个 p_pos != nr_token 检查是教材里常漏的：没有它，p 1 2 会静静返回 1，因为 parse_expr 吃完 1 就 return 了，剩下的 2 没人管。成功的 parser 必须把输入吃干净。

---

6. 代码实现 · 下篇：Watchpoint

监视点 w EXPR 的语义：每执行一条指令，重新算一次 EXPR，值变了就停下来报告。

关键观察：watchpoint 就是表达式求值器的定时重放。核心逻辑只有”存一下 expr 字符串、存一下上一次的值、每步调一次 expr()“。

6.1 数据结构

#define WP_EXPR_MAX 64

typedef struct WP {
    int        no;                 /* 1-based, stable across deletes */
    char       expr_str[WP_EXPR_MAX];
    word_t     last_value;
    struct WP *next;
} WP;

static WP  *head     = NULL;
static int  next_no  = 1;

两个设计决策：

1. expr_str 拷进结构体而不是存指针。用户输入的 REPL 行在 char line[256] buffer 里，下次读入就被覆盖，指针立刻失效
2. next_no++ 永不回退：GDB 里你 d 3 然后再 w，新 watchpoint 是 #4 不是 #3——编号稳定，不因为删除重排

6.2 增：wp_add

void wp_add(const char *e) {
    if (strlen(e) >= WP_EXPR_MAX) {
        printf("w: expression too long (max %d chars)\n", WP_EXPR_MAX - 1);
        return;
    }
    bool ok = false;
    word_t v = expr(e, &ok);
    if (!ok) {
        printf("w: cannot evaluate '%s'\n", e);
        return;
    }

    WP *w = malloc(sizeof(WP));
    Assert(w != NULL, "malloc WP failed");
    w->no         = next_no++;
    w->last_value = v;
    w->next       = NULL;
    strncpy(w->expr_str, e, WP_EXPR_MAX - 1);
    w->expr_str[WP_EXPR_MAX - 1] = '\0';   /* strncpy 不保证终止 */

    /* Append to tail so display order matches creation order. */
    if (head == NULL) {
        head = w;
    } else {
        WP *cur = head;
        while (cur->next) cur = cur->next;
        cur->next = w;
    }
    printf("watchpoint #%d: %s = 0x%08" PRIx32 "\n", w->no, w->expr_str, v);
}

注意 strncpy 的坑：如果 strlen(e) >= N，它不会在 dst[N-1] 补 \0，后续 printf 会读过界。手工补一个是惯例。

6.3 删：wp_del 的双指针技巧

初学者写链表删除节点容易翻车：

/* 初学者写法（有 bug） */
bool wp_del_naive(int no) {
    WP *cur = head;
    WP *prev = NULL;
    while (cur) {
        if (cur->no == no) {
            if (prev == NULL) head = cur->next;    /* 特判头 */
            else              prev->next = cur->next;
            free(cur);
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

问题不是 bug，是丑——要特判 prev == NULL。改用双指针 WP **cur：

bool wp_del(int no) {
    WP **cur = &head;          /* 指向"那个指向下一个节点的指针" */
    while (*cur) {
        if ((*cur)->no == no) {
            WP *dead = *cur;
            *cur = dead->next;
            free(dead);
            return true;
        }
        cur = &(*cur)->next;
    }
    return false;
}

cur 一开始指向 head，之后指向前一个节点的 next 字段——指针变量的地址。这样”修改链”只需要 *cur = dead->next，不需要区分是改 head 还是改某个 prev->next。

编程技巧：凡是链表删除要写”特判头”，都可以用双指针消掉。Linus 以此为经典面试题。

6.4 显示：wp_display

void wp_display(void) {
    if (head == NULL) {
        printf("(no watchpoints)\n");
        return;
    }
    printf("%-4s %-40s %s\n", "Num", "Expression", "Value");
    for (WP *w = head; w; w = w->next) {
        printf("%-4d %-40s 0x%08" PRIx32 "\n",
               w->no, w->expr_str, w->last_value);
    }
}

GDB 风格的三列表格：编号 / 表达式 / 上次值。

6.5 核心：wp_check

bool wp_check(void) {
    bool any = false;
    for (WP *w = head; w; w = w->next) {
        bool ok = false;
        word_t v = expr(w->expr_str, &ok);
        if (!ok) continue;              /* silently skip broken expressions */
        if (v != w->last_value) {
            printf("watchpoint #%d (%s) changed: 0x%08" PRIx32
                   " -> 0x%08" PRIx32 "\n",
                   w->no, w->expr_str, w->last_value, v);
            w->last_value = v;
            any = true;
        }
    }
    return any;
}

全部逻辑 15 行。**整个 watchpoint 的”智能”就是 for + expr() + 比较"**——我们"免费"得到了"监视寄存器运算结果"、"监视内存地址"、"监视复合条件" 等等能力，因为 expr()` 已经足够通用。

求值失败时静默跳过，不删除 watchpoint——这是优雅降级：表达式现在算不出（比如监视的是 *$sp - 4 而 $sp 当前是非法地址）不代表永远算不出，下一步可能就对了。

6.6 挂进主循环：1 行的接入点

P0 的 cmd_c 现在可以补上 wp hook：

for (uint64_t i = 0; i < n; i++) {
    exec_once();                                   /* 今天是 stub */
    if (g.state != TEMU_RUNNING) break;
    if (wp_check()) { g.state = TEMU_STOP; break; }
}

exec_once() 今天什么也不做（stage 1 没有 CPU）。P3 给它填真实内容后，watchpoint 立刻就能工作——一行不改。

这就是”先写调试器”的最大红利：当 CPU 终于出生时，它一诞生就能被监视、被单步、被读寄存器。不用你再回头加调试支持。

---

7. 测试：怎么测一个”自己是解释器”的程序

表达式求值器最棘手的测试问题是——“标准答案从哪来？”

你手写 3 1+2、7 1+2*3，一共能写几百条？对 parser 的角落 case（比如 1 << 31、~(~0u + 1)、3 | 5 ^ 2 & 1）你确定手算对了吗？

答案：找一个你信任的 oracle。宿主的 cc（C 编译器）就在你手边。

7.1 三层测试

层	做什么	目的
Smoke	printf 'p 1+2\nq\n' \| ./temu + grep	REPL 分派没崩
Golden	手写 期望值<tab>表达式 文件，跑 ./temu -t FILE	precedence / 边界 case 可控覆盖
Fuzz	生成随机表达式 → 宿主 C 编 + 跑 = expected → 喂 TEMU 对比	广度覆盖 + 差分检查

7.2 Golden 文件格式

# TEMU expression evaluator — basic test cases
# Format: <expected>  <expression>
# <expected> 用 strtoul(base=0)，所以 0x / 0 前缀都接受

# --- arithmetic ---
3           1 + 2
11          1 + 2 * 5
10          2 * (3 + 2)
8           5 - -3
2           100 % 7

# --- unary ---
0xfffffffb  -5
0xffffffff  ~0
1           !0
1           !!5

# --- precedence ---
7           1 + 2 * 3
6           1 + 2 + 3
2           10 - 5 - 3

7.3 -t FILE 的实现

main.c 加一个分支：

static int run_expr_tests(const char *path) {
    FILE *fp = fopen(path, "r");
    if (fp == NULL) {
        fprintf(stderr, "cannot open test file '%s'\n", path);
        return 2;
    }

    char line[8192];
    int  pass = 0, fail = 0, lineno = 0;

    while (fgets(line, sizeof line, fp)) {
        lineno++;

        char *hash = strchr(line, '#');
        if (hash) *hash = '\0';                    /* # 注释 */
        char *nl = strchr(line, '\n');
        if (nl) *nl = '\0';

        char *p = line;
        while (*p == ' ' || *p == '\t') p++;
        if (*p == '\0') continue;                  /* 空行 */

        char *end;
        word_t expected = (word_t)strtoul(p, &end, 0);
        if (end == p) { fail++; continue; }

        while (*end == ' ' || *end == '\t') end++;

        bool ok = false;
        word_t got = expr(end, &ok);
        if (!ok)             { fail++; continue; }
        if (got != expected) { fail++; continue; }
        pass++;
    }
    fclose(fp);
    printf("expr tests: %d passed, %d failed\n", pass, fail);
    return fail == 0 ? 0 : 1;
}

strtoul(p, &end, 0) 里的 base=0 是 libc 的魔法参数：它会自动识别 0x / 0 / 十进制前缀。golden 文件里 0xfffffffb 和 11 都能直接用。

7.4 差分模糊测试（fuzz）

真正的考验。核心想法：

gen-expr 生成 N 条随机表达式
  ↓
每条：包成 C main()、用 cc 编译、跑得到 expected
  ↓
把 (expected, 表达式) 写到 test 文件
  ↓
喂给 ./temu -t，它对每条算一次，比较

7.5 生成器 gen-expr：两个关键 trick

static void gen_expr(void) {
    if (depth >= MAX_DEPTH || rand() % 4 == 0) {
        emit("(0u + "); emit_num(); emit_char(')');       /* 叶子 */
        return;
    }
    depth++;
    emit("(0u + ");                                        /* 整体包一层 */
    int r = rand() % 10;
    if      (r < 1) emit_num();
    else if (r < 3) gen_unop_expr();
    else if (r < 4) gen_shift();
    else            gen_binop_expr();
    emit_char(')');
    depth--;
}

这里有两处不自然的写法，都是踩过坑的：

Trick 1：(0u + X) wrap 每一层

宿主 C 的隐式类型提升是个雷。~0 在 C 里是 int(-1)，和 uint32_t 做位运算时结果意外。所以生成器给每层都裹一层 (0u + …)——强制整个表达式链走 unsigned int。TEMU 侧是 word_t = uint32_t，天然就是这个类型。

Trick 2：移位量强制 [0, 31]

static void emit_shift_amount(void) {
    char tmp[16];
    snprintf(tmp, sizeof tmp, "%uu", (unsigned)(rand() % 32));
    emit(tmp);
}

如果生成器吐 1 << 64，宿主 C 是 UB，行为不确定，对拍会间歇性失败。TEMU 是 & 31 稳定行为。解决两边分歧最简单的方式：生成器只生成两边都定义良好的情况。

7.6 fuzz.sh 骨架

#!/usr/bin/env bash
set -u
N=${1:-200}

TMPDIR=$(mktemp -d)
trap 'rm -rf "$TMPDIR"' EXIT
EXPRS=$TMPDIR/exprs.txt
TESTFILE=$TMPDIR/tests.txt

./build/tools/gen-expr/gen-expr "$N" > "$EXPRS"

while IFS= read -r EXPR; do
    # 包成 C main() 编译运行
    {
        echo '#include <stdio.h>'
        echo '#include <stdint.h>'
        echo 'int main(void) {'
        printf '    uint32_t r = (uint32_t)(%s);\n' "$EXPR"
        echo '    printf("%u\n", r); return 0; }'
    } > "$TMPDIR/probe.c"

    cc -w -O0 -o "$TMPDIR/probe" "$TMPDIR/probe.c" 2>/dev/null || continue
    expected=$("$TMPDIR/probe" 2>/dev/null) || continue

    # 把 'u' 后缀去掉再喂 TEMU —— 我们的运算符集里没有 'u' 字符，全局替换安全
    TEMU_EXPR=${EXPR//u/}
    printf '%s\t%s\n' "$expected" "$TEMU_EXPR" >> "$TESTFILE"
done < "$EXPRS"

./build/temu -t "$TESTFILE"

最后一步 ${EXPR//u/} 是 bash 的全局替换语法——把所有 u 去掉。因为 TEMU 不认 5u 这种后缀，但我们运算符里没有 u（==、||、<< 都不含），全局删除安全。

跑 bash tests/expr/fuzz.sh 500 得到：

fuzz: generated=500  verified=486  skipped=14
expr tests: 486 passed, 0 failed ✓

没有一个手写的测试能达到这个覆盖密度。差分测试的本质是：让一个已经正确的程序（host cc）监督你这个新程序。

核心洞察：测试一个解释器最优雅的方式，不是证明它”对”，而是证明它和另一个你信任的解释器一致。这把测试问题从”怎么算期望值”降级成”怎么跟别人比”——后者容易得多。

7.7 理论视角：Oracle 问题与差分测试的学术谱系

“测试一个解释器”其实是软件测试领域一个经典难题的特例。

Oracle problem（测试预言问题）—— Pezzè & Young 在《Software Testing and Analysis》里的经典定义：

给定输入 $x$，你怎么知道程序输出 $f(x)$ 是”正确”的？你需要一个 oracle——能独立计算 $f(x)$ 的权威参考。

大多数软件测试的 oracle 是人（”这个按钮点击后应该跳转到登录页”）。但“程序的正确输出”本身就是复杂计算结果的场景里——编译器、解释器、JIT、浏览器渲染引擎——人类 oracle 不够用，你需要另一个程序。

学术脉络（时间顺序）：

年	作者 / 文献	贡献
1982	Weyuker：On Testing Non-Testable Programs	首次提出 pseudo-oracle 概念：用”独立实现”当参考
1998	McKeeman：Differential Testing for Software	正式命名 differential testing，应用到 C 编译器
2000	Claessen & Hughes：QuickCheck（Haskell 论文）	Property-based testing：让用户声明属性，工具生成随机输入验证
2011	Yang, Chen, Eide, Regehr：Finding and Understanding Bugs in C Compilers	CSmith——用差分测试找到 GCC / Clang 数百个 bug，该论文证明工业编译器远没”绝对正确”那么稳
2015+	AFL, libFuzzer, Jazzer	Coverage-guided fuzzing 普及到几乎所有语言的 runtime 和解析器

差分测试 vs 其他：

方法	Oracle 来源	覆盖度	成本
手写 golden tests	人	低	人工 × 用例数
Property-based testing	性质断言	高	写 property 不易
Differential testing	另一个程序	极高	几乎零
Coverage-guided fuzzing	崩溃 / assert	高（覆盖路径）	工具成本

差分测试的魅力：完全免费的 oracle。我们的 cc 是几千人调试了 30 年的程序，信任它不亏。

差分测试的死穴：Correlated failures

差分测试假设两边独立实现。现实里”独立”是相对的：

• 两个程序可能基于同一份错误规范（比如 RISC-V spec v1 有 bug，Spike 和 TEMU 都按它写）
• 两个程序可能共享同一段错误思路（1 << 32 在 C 里是 UB，我和 host cc 可能都错误地假设它是 0）

真实例子：CSmith 团队在 2011 年报告，LLVM 和 GCC 有一批共享 bug——两者都错误处理某些极端表达式，差分测试抓不到。他们不得不再引入第三方 oracle（商业编译器）做三方对拍。

对我们的启发：

1. TEMU 的 reference CPU (第二实现) 在 P4 会出现——但两边都是我写的，共享失败风险高
2. 补救：tests/isa/ 的手工用例（golden oracle）+ Spike（权威第三方）的组合
3. 最安全的 oracle 是规范本身——直接对照 RISC-V 规范写测试向量，规避”两个实现共享错误假设”

科研传统：McKeeman 的论文引用至今超过 400 次；CSmith 论文超过 1500 次。差分测试是系统软件测试的事实标准——你在本章实现的 fuzz 框架，是这个传统在调试器级别的落地。

---

8. 踩坑清单

前面散落的坑汇总，新手盖书时这一页必留：

8.1 Regex 规则顺序

多字符 token 永远排在其前缀的单字符 token 之前：== 前于 =，<= 前于 <，0x[0-9a-f]+ 前于 [0-9]+。搞反了会出诡异的 “unexpected character at” 错误。

8.2 rm_so == 0 是”锚定”

if (regexec(&re, s + pos, 1, &m, 0) == 0 && m.rm_so == 0) { ... }

POSIX regex 默认会”在字符串中间找到”——你要的是”在当前位置开头匹配”。没有 rm_so == 0 检查，abc + 1 的 + 可能在错误位置被识别。

8.3 一元歧义只能在 lex 之后修

* 和 - 在词法阶段不可能知道自己是一元还是二元——需要前文。所以 fixup pass 必须存在。让 parser 做这件事（look-ahead 两格看左邻居）会让所有 parse 层的代码都脏。

8.4 Shift 的 C UB

x << n 当 n >= 32 时 C 不定义行为。三件事要做对：

1. TEMU 实现 mask 低 5 位（r & 31）
2. Fuzz 生成器的 shift amount 限在 [0, 31]
3. 心里清楚：这是个语义分界——guest 硬件行为 vs host C 行为

8.5 除零不能传给宿主

if ((op == '/' || op == '%') && r == 0) { p_err = true; return 0; }

少了这一行，p 1/0 会让整个 TEMU 进程被 kernel kill（SIGFPE）。guest 的错误决不能升级为 host 的崩溃。

8.6 strtok 的全局状态

strtok 有藏在 libc 里的静态指针。两处调用链嵌套（sdb 分派命令 + 表达式 lexer）会互相污染。本章的 lexer 没用 strtok——用了 regex——就是这个原因之一。

8.7 strncpy 不补 \0

C 标准库最反直觉的函数：strncpy(d, s, n) 在 strlen(s) >= n 时不会在末尾放 \0。惯用法是紧接着 d[n-1] = '\0'。

8.8 parse 完要检查 token 吃干净

if (p_pos != nr_token) { /* trailing garbage */ }

这行检查常漏。没它，p 1 2 静静返回 1，bug 无声。

8.9 差分测试的类型陷阱

宿主 C 的 int vs TEMU 的 uint32_t 对齐——~0 在两边类型不同。(0u + X) wrap 每一层是你的好朋友。

8.10 Stub 不是 bug

isa_reg_val 返回 0 不是”错误”，是”未初始化”。读者看见 p $pc = 0 会以为哪里写错了——其实是 stage 1 的正确行为。P3 才开始返回真值。

---

9. 动手练习

Easy 1 · 支持八进制 0o777

在 rules[] 加一行 { "0[oO][0-7]+", TK_OCTNUM }（记得 TK_OCTNUM 加到 enum），parse_primary 里分支调 strtoul(s + 2, NULL, 8)。

学到：规则表驱动的扩展成本——两处改动，零侵入。新规则加在哪一行有讲究：必须在 TK_NUM 之前，否则 0777 会被 [0-9]+ 抢先。

Easy 2 · p/x 和 p/d 格式化

让 p 支持 p/x EXPR 按 hex 打印、p/d EXPR 按 decimal（模仿 GDB）。strtok(args, " ") 先检查第一段是否以 / 开头。

学到：CLI 子语法的扩展；命令参数从”纯表达式”升级为”格式指示 + 表达式”，这是调试器 UX 的第一步进化。

Medium 1 · 短路求值

当前 parse_logand 无论左值是 0 都会算右值。让它真正短路——左 0 时右不求值。

提示：不求值意味着 token stream 要跳过右表达式而不是”算完丢弃”。你会发现——在递归下降 + on-the-fly 求值架构里做这件事很难。需要”pre-parse 右表达式但不求值”的能力，或者干脆上 AST（见 Hard 1）。

学到：AST 不是学院派装饰，它是某些优化（短路、常量折叠）的前提。

Medium 2 · 一次性 watchpoint

watch EXPR 默认一直有效；加 watch-once EXPR，触发一次后自动 disable（不删除，info w 能看见）。

学到：有状态的调试对象；GDB 有 enable / disable / delete 三种操作的原因——”停用”和”删除”不是一回事。

Hard 1 · 引入 AST

把 parser 改成返回 ExprNode *，加 eval(ExprNode *) 和 free_ast(ExprNode *)。

学到：

• AST 的成本（代码量 +50%、内存管理）
• 收益：短路、常量折叠、带列号的错误定位、pretty-printing
• 这才是”工业级”编译器的架构。你写完这道题就理解为什么 clang / gcc 不用 on-the-fly 求值

Hard 2 · 差分 fuzz 覆盖 / %

目前 gen-expr 故意排除除法因为”宿主 C 除零会 SIGFPE”。让 fuzz 覆盖 / 和 %。

两条路可选：

1. 生成器侧回避：构造 a / (b + 1) 保证除数非零——简单但降低覆盖度
2. fuzz 侧隔离：用 fork + waitpid，子进程跑宿主 C 程序，WTERMSIG(status) == SIGFPE 就认定”宿主侧除零”并跳过这一条

学到：差分测试里”oracle 行为 ≠ target 行为” 的两种工程对策——规范层对齐（限制输入）vs 运行时隔离（子进程 + 信号）。

---

10. 本章小结

你应该能做到：

• 用一句话解释”可观测性先于可执行性”，并能举 TEMU 里的具体例子
• 画出 expr("$pc + 4") 的 lex → parse → eval 三步变换
• 写一个带顺序敏感规则表的 regex 词法分析器
• 写递归下降 parser，10 层优先级，正确处理左结合 / 右结合
• 用 5 行 fixup pass 解决一元算符歧义
• 写一个稳定编号的单向链表（双指针删除）
• 把 watchpoint 用 1 行 hook 接入 cpu_exec 主循环

你应该能解释：

• 为什么 == 规则必须在 ! 之前
• 为什么我们的移位算符 mask 低 5 位（不是简单的 x << n）
• 为什么差分测试里要 (0u + X) wrap 每一层
• 为什么除零在 TEMU 里要显式 check 而不能交给 CPU
• 为什么 expr() 末尾要验证 p_pos == nr_token
• 为什么链表删除用双指针比”prev 指针”优雅

---

11. 延伸阅读

• Aho / Sethi / Ullman · Compilers: Principles, Techniques, and Tools（龙书） 第 2、4 章：lexer 和 parser 的教科书级处理
• Bob Nystrom · Crafting Interpreters（craftinginterpreters.com） 第 6-10 章：从递归下降到 AST 到字节码的自然进化，正好是本章的续章
• GDB User Manual · “Expressions” 节：GDB 的表达式语言是什么样，对比我们做了多大的简化
• man 3 regex / regcomp(3) / regexec(3)：POSIX regex 的完整 flag 语义
• Niklaus Wirth · Compiler Construction：一本 120 页的 Pascal 编译器完整实现，递归下降的模范

---

与后续章节的连接

下一章做什么	本章埋下的伏笔
P2 物理内存	paddr_read stub 换成真读；x N EXPR、*EXPR 零改动升级
P3 RV32I CPU	isa_reg_val stub 换成 cpu.gpr[i]；exec_once 填实；watchpoint 主循环 hook 立刻生效
P3 RV32I CPU	si、c 从”没意义”变成真·单步 / 连续执行
P6a 异常中断	info 会扩 info c 打印 CSR；$mstatus、$mepc 通过 csr_lookup 复用本章的表达式入口
全章节	expr() 是 TEMU 里最稳定的 API——从 P1 写下起到 P6a 不改一个字符

本章代码从今天起服役到 stage 6a 结束。你会发现每个新 stage 添加功能时，调试器一行不用动——它已经准备好看见所有未来的状态。

下一站：P2——给这个有调试器的空壳装上 128 MB 物理内存。