简介编译原理是理解编程语言底层机制的核心知识体系而词法分析、语法分析是构建语言前端的第一道门槛。在实际工程中开发者既可以借助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.htoken 的编号不是 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_primaryparse_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 最终选择了追踪式 GCmark-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 下解析脚本报 0x0dCRLF 行尾符怎么会混进源码现象在 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.exeCygwin 提供的是 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 虚拟机的架构全貌但难点分布也完全不同。作为一份教学资料先解释器后编译器的顺序是刻意的先用最简单直接的方式建立一个能跑的完整语言再让学习者亲眼看到同样一套语义用编译方式重写一遍。我一般会这么理解这个取舍——树遍历解释器是「说到做到」字节码虚拟机是「先想再做」。前者的设计目标是让每一步都可见可调后者的设计目标是让执行更贴近机器。一个更现实的教训是动手造语言时不要一开始就冲字节码虚拟机。先在树遍历解释器上把语法、语义、数据结构的边界摸清再考虑编译优化。这种「先能用再变快」的顺序和资料里逐版本演进的做法完全一致。从那以后我每回看一个语言项目的源码都会强制自己先找出它最快的求值入口——是递归函数还是指令循环——再决定从哪开始读这个习惯帮我避开了不知道多少阅读死胡同。希望帮到你。本文还有配套的精品资源点击获取