简介：编译原理是理解编程语言底层机制的核心知识体系，而词法分析、语法分析是构建语言前端的第一道门槛。在实际工程中，开发者既可以借助yacc/lex生成LALR解析表，也可以手写递归下降解析器，两者在错误处理、优先级控制与代码可读性上各有取舍。理解这些原理不仅能解释IDE的智能提示、代码高亮等功能的实现方式，也为设计领域特定语言、解析DSL或结构化日志提供了直接的技术支撑。更进一步，解释器与字节码虚拟机分别是“边说边做”和“先编译后执行”两种执行模型，前者便于快速原型验证，后者贴近Python、Java虚拟机的真实架构。本文基于一套从零开始自制编程语言的完整实战记录，覆盖token识别、语法树求值、垃圾回收、正则库集成以及构建工具链的避坑经验，并附crowbar和Diksam两套语言的逐版本源码，适合想深入理解编译原理的开发者作为实践参考。

1. 自制编程语言：为什么最难的部分从来不是语法

很多人以为自制编程语言最难的坎是语法设计，实际动手才发现，语法两天就能捣鼓出个雏形，真正让人崩溃的是工具链：bison 在 Windows 上跑不起来、y.tab.h 神秘失踪、make 报出一串乱码路径。这份资料的价值正在于它把「从零写一个解释器」的全过程完整摊开——词法分析、语法分析、语法树求值、GC、正则库集成，再到把解释器改造成编译器，并且附带了 crowbar 和 Diksam 两套语言从 0.1 到 0.4 的逐版本演进源码。跟着版本号走一遍，等于亲眼看着一个语言是怎么从能跑、到能处理字符串、到管得住内存、再到拥有正则能力的过程。搞懂这套链路，编译原理里那些黑匣子概念——token、LALR、语义分析——就全都有了具体的落点。

2. 语法分析的两种引擎：yacc/lex 生成器与手写 LL 解析器

2.1 词法分析：从正则到自动机，flex 如何把源码切成 token

写编程语言的第一道工序是把源码字符串拆成有意义的词法单元，即 token。这份资料里的 mycalc 用的是 yacc/lex 组合，其中 lex 负责词法：它读取一个 .l 文件，文件里写的是一堆正则规则，例如标识符长什么样、数字长什么样、运算符长什么样。lex 的原理是先把每条规则编译成 NFA，再合并成 DFA，最后生成一张状态转移表，输出成一个叫 lex.yy.c 的 C 文件。这个文件里有一个 yylex() 函数，每次被调用就从输入缓冲区里啃出一个 token。

这里有个常被忽略的设计点：DFA 的状态合并方式决定了匹配优先级。lex 的默认策略是「最长匹配优先，等长时先出现的规则优先」。比如关键词 if 和标识符 identifier 的正则理论上都匹配 "if" 字符串，但因为 if 规则写在前面，lex 会优先返回 IF 这个 token 而非 IDENTIFIER。crowbar 的 .l 文件里能把==和=区分开，靠的也是这条最长匹配规则。如果你把规则的顺序写反了，就会出现if被当作普通变量解析出去的诡异现象。

实际的 .l 规则段大概是这样的结构：

%{ #include "mycalc.h" #include "y.tab.h" %} %% [0-9]+ { return INT_LITERAL; } "+" { return PLUS; } "*" { return MUL; } [a-zA-Z_][a-zA-Z0-9_]* { return IDENTIFIER; } [ \t\n] { /* skip whitespace */ } . { fprintf(stderr, "unknown char: %c\n", *yytext); } %%

这段规则里最关键的细节是#include "y.tab.h"：token 的编号不是 lex 决定的，而是 yacc 在生成 y.tab.h 时给每个 %token 分配的宏常量。lex 生成的词法分析器要返回这些编号给 yacc 的语法分析器用，所以 .l 文件必须依赖 .y 文件先编译出 y.tab.h。这就是后面避坑章里一堆「y.tab.h: No such file」报错的根源——生成顺序错了，整个构建就断在第一步。

2.2 语法分析：LALR 查表与递归下降，两条路各买什么账

拿到 token 流之后，语法分析要判断这些 token 组成的序列是否符合文法规则。yacc（以及 GNU 的 bison）走的是 LALR(1) 路线：把文法规则编译成一张巨大的解析表，yyparse() 里有一个状态栈，每读入一个 token，查表决定是移进（shift）还是归约（reduce）。移进就是把 token 压栈，归约则是用一条产生式把栈顶的几个符号替换成等价的非终结符。crowbar.y 里会有类似这样的产生式：

expression : expression ADD expression | expression SUB expression | INT_LITERAL | IDENTIFIER | LPAREN expression RPAREN ;

bison 会为这套产生式生成动作表与跳转表，执行时通过查表完成整个推导过程，不用手动写回溯逻辑。代价是表本身是个黑匣子：如果你写出二义性文法，bison 汇报冲突时的报错信息对初学者极不友好，什么 shift/reduce conflict、reduce/reduce conflict，不看表根本不知道是哪里撞了车。

与生成器相对的路子是手写解析器，资料里的 llparser 就是其中代表。手写版用的是递归下降：每个非终结符对应一个 C 函数，函数里按文法顺序调用下一个 token 的匹配函数，层层嵌套完成分析。这里没有查表，代码即文法，出错时可以精确控制错误信息。

llparser 的代码布局大致是这样：

static Token *next_token; static Node *parse_expression(void) { Node *left = parse_primary(); /* 先解析操作数 */ while (next_token->kind == TOKEN_PLUS || next_token->kind == TOKEN_MUL) { Token *op = next_token; next_token = lex_get_token(); Node *right = parse_primary(); /* 再解析右操作数 */ left = new_binary_node(op, left, right); } return left; }

这段代码的价值在于它把「递归下降」的递归二字展示得特别直白：parse_expression 调 parse_primary，parse_primary 里如果遇到括号又回调 parse_expression，形成相互递归。手写路线的坑也随之暴露——运算符优先级完全靠你手动安排函数调用顺序来实现，写到最后很容易绕晕；而 LALR 生成器把优先级写在 %left、%right 声明里，两行就解决了。

2.3 依赖链陷阱：为什么生成器的输出文件会被编译器抢先吞噬

mycalc 和 mycalc_ex 的构建脚本展示了 yacc/lex 项目最经典的一个依赖链：先用 bison 处理 .y 文件产出 y.tab.c 和 y.tab.h，再用 flex 处理 .l 文件产出 lex.yy.c，最后 gcc 把这两个生成的 C 文件和入口 main.c 一起编译链接。任何一个环节的文件没生成成功，后续环节全炸。素材里真实的报错场景是这样的：

$ gcc -c lex.yy.c mycalc.l:3:19: error: y.tab.h: No such file or directory #include "y.tab.h"

原因就是 bison 因为路径问题（后文详述）压根没跑成功，y.tab.h 根本没落盘，而 make 又不知道 lex.yy.c 依赖 y.tab.h 这层关系，直接拿一个残缺的 .l 去编译。这也是为什么 Makefile 里往往要把 y.tab.h 写成 lex.yy.c 的显式前置依赖。

同样的依赖链问题出现在手写解析器上时，翻车姿势不同但同样隐蔽。资料里记录的 lexicalanalyzer.c 有个经典 BUG，代码是这样：

static char *st_line; static int st_line_pos; static void parse_line(void) { while (fgets(st_line, LINE_BUF_SIZE, stdin) != NULL) { /* 处理一行的 token */ } }

st_line 只是个声明为 char * 的指针，从来没有分配过内存，fgets 直接往里写。这个 BUG 不立刻崩溃是因为 st_line 恰好指向了一段可写的全局内存，但只要编译器的内存布局一变就段错误。这正是手写解析器的血泪教训：生成器帮你管好了缓冲区，手写版每一项都得自己负责。

3. 解释器的骨架：crowbar 从 0.1 到 0.4 到底加了什么

3.1 树遍历解释器：语法树上的递归求值回路

crowbar 系列是这套资料最核心的教学语言，它的整体设计遵循教科书式的「前端 + 求值器」模型。词法、语法分析之后得到的不是可执行代码，而是一棵语法树；求值阶段遍历这棵树，边遍历边计算结果。这种设计叫 tree-walk interpreter，代表性地呈现了解释器最朴素的执行模型。crowbar 里的 eval.c 承担了全部求值工作，核心是 evaluate() 这个递归函数，其结构可看作：

static Value evaluate(Node *node) { switch (node->type) { case INT_EXPRESSION: return create_int_value(node->u.int_value); case ADD_EXPRESSION: { Value left = evaluate(node->u.binary.left); Value right = evaluate(node->u.binary.right); return create_int_value(left.int_value + right.int_value); } case IF_EXPRESSION: { Value cond = evaluate(node->u.if_.condition); if (cond.boolean_value) return evaluate(node->u.if_.then_block); else return evaluate(node->u.if_.else_block); } /* ... 其他节点类型 */ } }

这种递归求值的美妙在于：语法的递归结构被直接映射成求值的递归结构，一个 if 表达式在语法树里是分支节点，在求值器里就是先算条件再决定往哪条子树走。不需要额外的指令指针，也不需要栈帧管理——C 语言的调用栈天然就是求值器的运行时栈。代价是每访问一个节点都要经过一次函数调用和结构体分支分发，性能上不去，这也成了后来 Diksam 转向编译路线的最直接动机。

3.2 多状态词法：为什么字符串和注释不能塞进单一规则

crowbar 0.2 的升级点藏在 .l 文件头部的一个细节里：%start COMMENT STRING_LITERAL_STATE。这是 flex 的起始状态条件（start condition）语法，它暴露了一个单靠正则表达式很难处理的经典问题——词法分析的状态不是一成不变的。

考虑一个双引号字符串："hello \"world\""。里头的反斜杠转义括号该怎么处理？如果用一个普通的正则去匹配字符串字面量，你会陷入「引号、反斜杠、再引号」的组合爆炸；更麻烦的是字符串字面量之后紧跟的换行、空格等空白字符，在字符串结束前都不该被当作普通空白跳过。注释同理，/* ... */内部出现的任何关键字、字符串片段都不应被识别为有效 token。

灵活的状态切换是解法：%start 声明了两个新的起始状态，规则里显式声明哪些规则只在该状态激活。

%start COMMENT STRING_LITERAL_STATE %% "/*" { BEGIN COMMENT; } <COMMENT>"*/" { BEGIN INITIAL; } <COMMENT>. { /* 吞掉注释内容 */ } "\"" { BEGIN STRING_LITERAL_STATE; } <STRING_LITERAL_STATE>"\"" { BEGIN INITIAL; } <STRING_LITERAL_STATE>\\\"" { /* 转义引号，不作为结束符 */ } <STRING_LITERAL_STATE>. { /* 字符串内容 */ } %%

BEGIN指令可以在词法分析中途切换状态，把词法阶段从一个线性匹配器升级成一台小型状态机。这就是为什么 0.2 版能正确处理带引号的字符串，而 0.1 版遇到字符串字面量时会直接懵掉。从设计角度讲，这个改动是任何脚本语言从「玩具」走向「能实际用」的分水岭。

3.3 内存管理：crowbar 0.3 里自己动手写 GC 的动机

crowbar 0.3 引入 GC 是最能体现解释器设计取舍的一步。一个 C 语言编写的解释器，每执行一次表达式都可能创建一个新的 Value 结构体，为字符串拼接分配新的缓冲区。如果不回收，执行一个循环一万次的字符串拼接就能吃光内存。常见的教学语言会选择引用计数——结构体里记一个 ref_count，归零就释放。但 crowbar 最终选择了追踪式 GC（mark-sweep 路径），理由很实际：字符串和对象之间会有循环引用，引用计数对这种结构的管理是结构性的失效。

实现上，GC 环节被拆成几个边界清晰的模块：分配时登记、标记时从根集合出发遍历、清除时回收无主对象。大致结构如：

typedef struct Value_tag { enum { INT_VALUE, STRING_VALUE, ARRAY_VALUE, ... } type; int ref_count; int marked; union { int int_value; char *string_value; /* ... */ } u; } Value; static void gc_mark(Value *v) { if (v == NULL || v->marked) return; v->marked = 1; /* 先标记，再递归标记子对象 */ if (v->type == ARRAY_VALUE) { /* 遍历数组成员，逐个 gc_mark */ } } static void gc_sweep(void) { /* 遍历所有已登记对象，marked == 0 的释放 */ }

为什么教学解释器值得自己写一遍 GC 而不直接挂一个现成库？因为 GC 的触发时机直接暴露了解释器对内存所有权模型的理解：哪些对象从根集合可达，哪些对象在表达式求值中途变成了孤儿，这些一旦理清，后面写原生函数扩展时就不会把 C 指针和语言值的生命周期搞混。0.3 版把这种现象级的概念压缩成几百行代码，是整份资料里信息密度最高的部分之一。

3.4 正则库集成：oniguruma 如何把模式匹配变成原生能力

crowbar 0.4 的卖点是植入正则表达式能力，素材里给出的构建步骤显示它依赖一个外部库 oniguruma，而这个库在 Windows 和 Linux 下编译方式截然不同。这里隐藏着解释器设计的一个通用问题：脚本语言的正则支持，底层到底是谁在做？

答案是把正则库作为原生函数桥接进去。crowbar 源码里通过 native 函数注册机制，把 C 层的Oniguruma正则匹配结果暴露给语言层，脚本里写/pattern/ ~= input这样一条普通语句时，解释器执行的其实是 C 层正则库的编译 + 匹配流程。正则表达式字符串会在首次匹配前被编译成内部字节码，之后每次匹配直接在内置状态机上跑，不再重复解析表达式本身。

这一步对语言的实用价值不用多说：没有正则的语言处理文本就是干瞪眼。更值得关注的是它对解释器架构的考验——区分原生函数和普通函数。原生函数的参数是 C 数据类型，普通函数的参数是语言层的 Value，桥接层必须做一次类型转换和错误处理。crowbar 的 native.c 就负责这件事。

4. 从解释到编译：Diksam 的虚拟机路线

4.1 字节码与虚拟机：Diksam 执行模型的分层结构

crowbar 是纯树遍历解释器，Diksam 则走得更远：先编译后执行。Diksam 编译器的前端仍然是词法、语法、语义分析，但在那之后，语法树不是直接进入求值器，而是被转换为字节码，由一台取指执行的虚拟机来跑。这套结构和 JVM、Python 字节码执行的本质一模一样，只是实现规模小得多。

Diksam 源码里能看到两个核心数据结构：指令集描述和虚拟机的执行循环。指令集的常见形态是操作码 + 操作数，比如：

#define PUSH_INT 1 /* 把一个整型常量压栈 */ #define PUSH_VAR 2 /* 把局部变量压栈 */ #define ADD_INT 3 /* 弹出两个值，相加后压栈 */ #define JUMP 4 /* 无条件跳转 */ #define JUMP_IF_FALSE 5 /* 弹出布尔值，为假则跳转 */ typedef struct { unsigned char opcode; int operand; } Instruction;

虚拟机的执行循环则是对指令数组的逐条分发：

void run(Instruction *code, int code_size) { int pc = 0; /* 程序计数器 */ Value stack[STACK_SIZE]; int sp = 0; /* 栈指针 */ while (pc < code_size) { switch (code[pc].opcode) { case PUSH_INT: stack[sp++] = create_int_value(code[pc].operand); pc++; break; case ADD_INT: { Value right = stack[--sp]; Value left = stack[--sp]; stack[sp++] = create_int_value(left.int_value + right.int_value); pc++; break; } case JUMP_IF_FALSE: if (!stack[--sp].boolean_value) pc = code[pc].operand; else pc++; break; /* ... */ } } }

把表达式翻译成这段字节码的编译器逻辑，通常在 syntax tree 到 instruction array 之间有一层转换。表达式树的后序遍历天然对应压栈顺序：先压左操作数、再压右操作数、最后发一条运算指令。这个设计解释了为什么编译器教科书画指令生成时会用「栈式机器」这个模型——运算对象都得先落地到一个显式的操作数栈上，指令本身只描述做什么和跳到哪。

4.2 语义分析的边疆：类型检查与符号表在编译期的工作

从树求值到字节码编译，最大的分水岭在于语义分析出现在编译期而不是运行期。crowbar 在运行期才找变量、才判断类型是否匹配；Diksam 在编译期就要做符号表解析，把「每一个标识符引用绑定到它对应的定义」这件事提前坐实。所以 Diksam 的编译工具链里有专门一层的 AST 遍历，负责收集所有变量的作用域信息，并据此生成带偏移量的变量访问指令，运行期就不需要动态查名字了。

这一层曾经是初学者最容易误判为「可跳过」的部分，但它恰恰是语言从解释器进化到编译器的价值所在：同样的语义，从「每次执行时查字典」升级为「编译时查一次，运行时查表号」。

4.3 构建结构变化：为什么 0.2 到 0.3 的 Makefile 拆分方式变了

素材里有一个细节非常说明问题：Diksam 0.1 和 0.2 的源码包要在 compiler 目录下执行 make，而 0.3 和 0.4 改成了在 main 目录下执行 make，并且 0.3/0.4 的目录下才有明确的 main 入口。这不是随便挪了挪位置，而是模块化重构的痕迹。

0.1/0.2 时代，编译器主体和运行时揉在一个目录里，入口不明显；0.3 开始把编译器作为库、虚拟机作为另一个模块、main 只做启动装配。运行make时由顶层 Makefile 按依赖顺序进入子目录构建。

这种结构调整的背后逻辑是：当语言的功能越来越多，编译器、虚拟机、原生函数、调试模块都会膨胀，若不拆开，任何一处的改动都会引发全量重编。Makefile 的分层正对应了 Diksam 的模块化分层——compiler 目录放前端和语义分析，main 目录放入口和运行时装配。

5. 环境搭建排查：MinGW、Cygwin 与 bison 的路径陷阱

5.1 bison 编译失败：m4 与 Program Files 的路径空格噩梦

现象：Windows 下运行 bison 生成语法分析器时，报出m4: cannot open 'Files': No such file or directory以及m4: cannot open '(x86)\GnuWin32\Bison/share/bison': No such file or directory。

原因：GnuWin32 的 bison 不是原生实现，内部要调用 m4 宏处理器来展开语法模板。而 bison 安装路径如果带了空格，比如D:\Program Files\GnuWin32，它传给 m4 的文件路径会被按空格拆成两截，「Files」就被当成一个待打开的文件。

解决：把 GnuWin32 装到不含空格的纯英文路径下，比如D:\gnu32；或者干脆放弃 GnuWin32，改用 Cygwin 里的 bison。素材里多位开发者在 2013 年底记录过这个报错，几乎都是路径空格惹的祸。

5.2 y.tab.h 神秘失踪：生成顺序一错，全部功亏一篑

现象：执行 make 后，编译 lex.yy.c 时直接报mycalc.l:3:19: error: y.tab.h: No such file or directory，随后一长串 C 文件报同样的缺失头文件错误。

原因：yacc/lex 项目有固定的生成顺序。Makefile 里如果只声明了目标文件的依赖，而不显式声明 y.tab.c、y.tab.h 对 lex.yy.c 的先决关系，并行执行时 gcc 就会抢在 bison 生成头文件之前去编译 lex.yy.c。

解决：先手动执行bison --yacc -dv crowbar.y确认 y.tab.c 和 y.tab.h 都生成成功，再执行 flex 和 gcc。写 Makefile 时把 y.tab.h 明确加进 lex.yy.c 的依赖列表，让生成器先跑完。从做法上讲，这属于「显式声明跨目标依赖」的范畴。

5.3 Linux 下解析脚本报 0x0d：CRLF 行尾符怎么会混进源码

现象：在 Linux 下直接运行./crowbar test/test.crb，解析脚本文件时报错说第 5 行有一个非法字符(0x0d)，而这个脚本在 Windows 下运行是正常的。

原因：ZIP 包里的文本文件按 Windows 习惯以 CRLF（\r\n）存储行尾，Linux 读文件时把 \r 当成了普通字符。lex 的规则里没有把这个回车符加入空白符号的集合，词法分析器看到 \r 就当成无法识别的字符了。

解决：对 .crb 脚本做格式转换，dos2unix test/test.crb，或用sed -i 's/\r$//'。从这个案例能看出，解释器的容错并不包括对不同操作系统的行尾约定做透明化处理，跨平台移植时文件格式本身就是一种显式约定。

5.4 Linux 下链接失败：找不到 libmsvcp60

现象：在 Linux 上编译 crowbar 0.4 的源码，链接阶段报/usr/bin/ld: cannot find -lmsvcp60。

原因：部分源码包把 Windows 下的链接选项直接写进了 Makefile 的默认配置中，而 libmsvcp60 是微软标准 C++ 运行时库，Linux 的链接器当然找不到这个库。

解决：改用源码包附带的 Linux 构建脚本，或把 Makefile 里的-lmsvcp60删掉，重新 make clean 后再 build。这说明跨平台源码包的 Makefile 往往不是一份通吃文件，必须留意平台分支。

5.5 MinGW 找不到 make：命令名不一致才是常态

现象：在 Windows 命令行进入 crowbar_book_0_1 目录执行 make，提示make: No targets specified and no makefile found，或者干脆'make' 不是内部或外部命令。

原因：MinGW 默认提供的是 mingw32-make.exe，Cygwin 提供的是 make.exe。资料里的 make.bat 有时直接调用 gmake.exe，这个名字在别处又对应 GNU make 的不同发行版。命令名不一致，导致不少人卡在执行环境这一关。

解决：先用where mingw32-make确认工具实际存在，再在 Makefile 所在目录以完整路径执行C:\MinGW\bin\mingw32-make.exe；或者拷贝一份 mingw32-make.exe 并改名 make.exe 放进 PATH。素材里还提到一种做法：把 gmake.exe 复制到 MinGW 的 bin 目录下。这种事看着琐碎，却是跨平台 C 项目构建最常踩的第一块砖。

6. 设计取舍的终点：树遍历解释器与字节码虚拟机谁更适合教人写语言

把 crowbar 和 Diksam 两条路线摆在一起，最值得玩味的不是哪个实现更快，而是作者为什么先做树遍历解释器，又义无反顾地转向字节码虚拟机。tree-walk 的优点是快写快改，试探语言特性时改一发规则重新编译就是新语法，调试期几乎不受编译器中间表示的限制；缺点也明显，每次求值都重新遍历语法树，字符串拼接和循环变量读取都要走一层层节点分发，性能放不进生产环境。

Diksam 的字节码路线把这些开销大半移到了编译期：语法树只遍历一次生成指令数组，运行时只做指令分发和栈操作。代价是多了语义分析和指令生成两个大组件，代码量至少翻倍。对教学而言，字节码路线能展示更接近真实语言（比如 Python 和 Java 虚拟机）的架构全貌，但难点分布也完全不同。

作为一份教学资料，先解释器后编译器的顺序是刻意的：先用最简单直接的方式建立一个能跑的完整语言，再让学习者亲眼看到同样一套语义用编译方式重写一遍。我一般会这么理解这个取舍——树遍历解释器是「说到做到」，字节码虚拟机是「先想再做」。前者的设计目标是让每一步都可见可调，后者的设计目标是让执行更贴近机器。

一个更现实的教训是：动手造语言时不要一开始就冲字节码虚拟机。先在树遍历解释器上把语法、语义、数据结构的边界摸清，再考虑编译优化。这种「先能用，再变快」的顺序，和资料里逐版本演进的做法完全一致。从那以后我每回看一个语言项目的源码，都会强制自己先找出它最快的求值入口——是递归函数还是指令循环——再决定从哪开始读，这个习惯帮我避开了不知道多少阅读死胡同。希望帮到你。

本文还有配套的精品资源，点击获取