简介《自制编程语言》相关资料1是一份面向编程语言学习者与实现爱好者的专题PDF适合希望从语法设计、编译器/解释器实现到实际编码规范建立整体认识的读者也可作为课程设计或小型语言项目的参考。压缩包内仅含1个PDF文件约2.38MB体量轻便便于集中阅读与检索。内容围绕语言设计原则、词法/语法分析工具、运行时环境与资源管理等主题展开并借Crowbar、Diksam等示例串联版本演进、make构建以及Linux与Windows下的开发差异涉及MinGW、bison/flex等工具的使用背景。已有870人学习说明其在同类资料中具有一定参考价值。读者可从中获得语言实现流程的整体框架、工具链配置思路与示例项目拆解线索用于理解编译器与解释器的分工、梳理自制语言的学习路径并对照自身项目查漏补缺。1. 从 0.1 到 0.4一门自制编程语言为什么要按「版本切片」交付把 crowbar_book_0_1 到 0_4、diksam_book_0_1 到 0_4 这八个目录并排打开第一反应通常是「同一份代码的八个快照」。但真把它们 diff 一遍会发现每个版本增加的不是功能数量而是一层机制0.1 只有表达式和变量0.2 补上控制流和函数调用0.3 引入 GC0.4 才谈得上对象与错误处理。这种切片方式的用意恰好也是所有编程语言实现里最容易被忽略的一点——语言不是一次性设计出来的而是一层层语义叠加出来的每一层的边界必须卡在「刚好能支撑下一个机制跑起来」的位置。这也是为什么这批资料里除了两门语言还塞了 calc、mycalc、llparser 三个前置 Demo它们是把「词法→语法→执行」这条链拆开单独压测的脚手架。搞懂这条链上每一层为什么这么切比读懂任何一段语法定义都更有迁移价值。2. 词法分析flex 生成的 DFA 究竟替你消除了哪些判断手写一个词法器并不难难的是它在遇到注释、字符串、行号统计、非法字符这四件事同时发生时还能保持正确。flex 的价值不在于「帮你写 if-else」而在于它把「此刻处于什么语境」从隐式的代码路径变成了显式的自动机状态。2.1 最长匹配与规则顺序两条规则谁赢在生成期就定死了flex 把所有规则的正则并成一台 DFA运行时反复执行两个动作从当前位置出发跑到无法继续为止取这一趟走过的最长前缀作为匹配结果长度相同时取在 .l 文件里出现更早的那条规则。这条规则看着像细节实际决定了关键字和标识符的写法顺序%option noyywrap %x COMMENT STRING_LITERAL_STATE %% if { return IF; } /* 必须写在标识符规则之前 */ else { return ELSE; } while { return WHILE; } [ \t\n] { } /* 空白直接吞掉 */ [0-9] { sscanf(yytext, %d, yylval.int_value); return INT_LITERAL; } [A-Za-z_][A-Za-z0-9_]* { yylval.identifier st_insert_string(yytext); /* 驻留 */ return IDENTIFIER; } . { error_lexical(...); } /* 兜底的非法字符 */[A-Za-z_][A-Za-z0-9_]*这条规则同样能匹配if但因为if写在前面等长匹配时它优先胜出。把这两条顺序对调if就会变成普通标识符语法分析器随后会报一个和真正原因完全无关的错——这是新手最常踩的一次坑而且报错位置离病根很远。代码里有两点需要单独说明。yylval是词法器与语法器之间传递语义值的约定结构体由 bison 生成类型在 .y 里用%union声明词法器只负责填字段具体怎么用是语法器的事。st_insert_string做的是字符串驻留——同样的标识符文本只保留一份后面比较标识符相等时比的是指针而不是strcmp这是把「名称」压成整数 ID 的常用做法也为后面变量槽按索引定位铺路。2.2 排他状态注释和字符串为什么不能只靠一条正则注释完全可以写成一条正则/*([^*]|\*[^*/])*\*/。能跑但代价有三。第一注释里出现未闭合的/*时这条正则匹配失败兜底规则只会报「非法字符/」读者根本不知道是第几行开始的注释没闭合。第二行号统计要靠在动作里数\n可一旦注释被单条正则整体吞掉里面的换行就数不到了后续所有报错行号整体偏移。第三字符串字面量里的转义、跨行禁止、错误恢复单条正则表达起来非常别扭。排他状态%x把这些隐式信息变成显式变量/* { BEGIN COMMENT; comment_start_line yylineno; } COMMENT*/ { BEGIN INITIAL; } COMMENT\n { yylineno; } /* 注释内也数行 */ COMMENT. { } COMMENTEOF { error_at_line(comment_start_line, 注释未闭合); } \ { BEGIN STRING_LITERAL_STATE; init_string_buffer(); } STRING_LITERAL_STATE\\n { append_char(\n); } /* 转义在这里收敛 */ STRING_LITERAL_STATE\ { BEGIN INITIAL; yylval.string ...; return STRING_LITERAL; } STRING_LITERAL_STATE. { append_char(yytext[0]); }进入COMMENT状态后只有带COMMENT前缀的规则参与匹配主规则区全部失效——这就是「排他」的含义。于是「注释未闭合」可以在 EOF 处用当初记下的起始行号精确报出来而不是让读者自己去找。字符串同理转义序列在这里统一收敛成一个字符语法器和后面的执行引擎完全不需要知道\n在源码里写成了两个字符。提示COMMENTEOF这条规则很容易漏。漏了之后未闭合注释会以「非法字符」的形式报到文件末尾排查成本陡增。2.3 词法器与语法器的契约y.tab.h 里那几个数字bison 会把所有 token 编号写进 y.tab.h形如#define IF 258。flex 生成的 lex.yy.c 必须在编译时看到这份头文件否则return IF;里的IF就是未定义标识符。这条依赖关系看起来只是构建问题本质是两者之间的接口契约词法器产出整数 token 加一个语义值语法器按整数做分支决策谁都不认识对方的内部结构。理解了这层契约很多「玄学」现象就有了解释。比如改了 .y 里的 token 顺序、重新生成 y.tab.h 之后没有重新编译 lex.yy.c运行时语法器会莫名其妙地走错分支——因为两边对同一个数字的理解不一致了。这也是为什么后面的绕坑章节里y.tab.h: No such file这类报错属于「依赖倒挂」而不是「环境坏了」。3. 语法分析bison 的移进-归约决策和你手写 LL 的差别在哪词法器把字符流压成 token 流之后语法器要做的事只有一件判断当前这串 token 能不能由文法推导出来并且顺手把结构建出来。bison 用自底向上的 LALR(1)llparser 用手写的自顶向下递归下降两条路线在「决策依据」「报错质量」「维护成本」上完全不同。3.1 LALR(1) 状态机为什么表达式文法必须写 %leftbison 生成的解析器维护一个状态栈每读一个 token 就查表决定「移进把 token 压栈进新状态」还是「归约把栈顶若干个符号按某条产生式折叠成一个非终结符」。表是在生成期算好的运行时只做查表和跳转所以速度很快。问题出在歧义文法上。E - E E这种写法遇到1 2 3时读到第二个既可以归约前两个也可以继续移进这叫移进-归约冲突。bison 默认的策略是「移进优先」不会报错但语义可能不是你想要的。显式写优先级是把这份决策从「默认行为」变成「声明式约定」%token int_value INT_LITERAL %token identifier IDENTIFIER %type expression expression primary_expression %left - %left * / %right /* 赋值右结合 */ %% expression : expression expression { $$ create_binary(, $1, $3); } | expression - expression { $$ create_binary(-, $1, $3); } | expression * expression { $$ create_binary(*, $1, $3); } | expression / expression { $$ create_binary(/, $1, $3); } | primary_expression { $$ $1; } ;%left -告诉 bison同一优先级遇到冲突时归约左结合并且* /声明在后面所以优先级更高。%right 是右结合a b c会解析成a (b c)。这些声明不改变文法本身只改变冲突的裁决方向——所以 bison 仍然会生成同一张分析表只是填充方式变了。代价是错误信息只能给出「在某个 token 处 Unexpected」。LALR 在发现错误时栈里已经压了一堆中间状态要做到「期望什么」这种提示需要额外的错误恢复规则error产生式配合写起来相当费劲。3.2 y.tab.c 与 y.tab.h依赖倒挂是构建失败的头号原因bison 一次生成两个文件y.tab.c 里是分析表和yyparse()y.tab.h 里是 token 编号和语义值联合体。flex 生成的 lex.yy.c 依赖后者。于是正确的构建顺序被固定死了# 正确顺序先语法后词法最后链接 bison --yacc -dv crowbar.y # 产出 y.tab.c / y.tab.h / crowbar.output flex crowbar.l # 产出 lex.yy.c里面 include y.tab.h gcc -c lex.yy.c y.tab.c main.c execute.c eval.c ... gcc -o crowbar *.o-d是生成头文件-v是额外产出crowbar.output——这份文件记录了完整的状态机、每条冲突的移进/归约明细是排查语法问题唯一靠谱的入口。很多人只写文件名不写-d然后困惑于 y.tab.h 为什么不存在其实 bison 从来没被要求生成它。资源里的 mycalc 就是这个顺序的最小复现先跑 bison 再跑 gcc。一旦 Makefile 里没写lex.yy.c: y.tab.h这条依赖或者用并行模式构建gcc 就会先被调度去编译 lex.yy.c报出mycalc.l:3:19: error: y.tab.h: No such file or directory。这条报错指向的是 .l 文件的第 3 行但病根在 Makefile 的依赖图属于典型的「错误位置与病因分离」。3.3 手写 LLllparser 为什么能绕开 yacc代价落在哪llparser 走的是另一条路为每个非终结符写一个函数靠前瞻一个 token 决定进哪个分支匹配成功就返回失败就报错。这种递归下降的写法有三个好处报错位置可以精确到「这里期望的是)但读到的是,」可以在解析过程中顺手做类型检查和常量折叠不必等语法树建完不依赖任何生成工具改文法就是改函数。代价也很直接。文法必须先做两件事消除左递归E - E T要改写成E - T E、E - T E | ε提取左公因式否则前瞻一个 token 不够用。改写之后语法树的形状会和原始文法对不上需要在构造节点时手工「扶正」代码量比 .y 文件大得多/* LL(1) 版本expression - term ( term)*加法在循环里累积 */ Expression *parse_expression(void) { Expression *left parse_term(); while (is_add_op(current_token)) { Token op current_token; advance(); /* 吃掉运算符 */ Expression *right parse_term(); left create_binary(op.kind, left, right); /* 左结合靠循环顺序保证 */ } return left; }这段代码里没有优先级表左结合性由while的累积顺序天然保证优先级由函数调用层次expression 调 termterm 调 factor保证。可读性其实比 .y 更好但每加一条文法规则都要同步改函数、改前瞻判断、改错误提示规模和一致性全靠人工维持。两相对照选择就很清楚了语法稳定、以表达式为主的场景生成工具省事需要精细报错、要在解析期做语义动作的场景手写更可控。资源里同时提供 mycalcyacc/lex 版和 llparser手写版恰好就是让人把这两条路的成本放在一起比。4. 执行模型从栈式字节码循环到带类型检查的编译执行语法树建好之后怎么「跑」它是这个资源里跨度最大的一处设计演进。crowbar 走的是「编译成字节码 栈式虚拟机解释」diksam 在此基础上加了编译与执行分离、类与接口、异常处理目录也相应拆成了 compiler 与 main 两套构建。4.1 栈机循环execute.c 里那个 switch 就是解释器的心脏栈式虚拟机的思路极简所有操作数放在一个值栈上指令只负责「压栈、出栈、运算、把结果压回去」控制流靠跳转指令改 pc。整个解释器就是一个死循环加一个大 switchvoid execute_bytecode(Bytecode *code) { int pc 0; for (;;) { Opcode op code-instructions[pc]; switch (op) { case OP_PUSH_INT: stack[sp].int_value code-instructions[pc].int_value; break; case OP_PUSH_DOUBLE: stack[sp].double_value code-instructions[pc].double_value; break; case OP_ADD: /* 类型在编译期已确定这里直接按 double 运算不再判断类型 */ sp--; stack[sp - 1].double_value stack[sp].double_value; break; case OP_JUMP: pc code-instructions[pc].int_value; /* 绝对跳转 */ break; case OP_JUMP_IF_FALSE: if (!stack[--sp].int_value) pc code-instructions[pc].int_value; else pc; break; } } }关键点在OP_ADD那几行注释如果语言是静态类型的加法的类型在编译期就已经确定运行时堆栈上的两个值必然同类型不需要每次运算再查一遍类型标签。这一步省下来的是解释器热路径上最贵的分支。反过来动态类型语言的字节码通常要带类型标签并做运行时派发指令循环就会臃肿得多。注意sp与栈边界必须在编译期算好最大深度并在运行时校验。栈溢出是解释器最容易出现的内存越界来源尤其是递归调用密集的脚本。4.2 变量槽与作用域静态类型为什么能算出一个整数偏移树遍历解释器里「变量」通常是一个从名字到值的哈希表。字节码解释器不这么干——因为名字在编译期就已知可以在编译期把每个局部变量分配到一个固定槽位运行时只用一个整数下标访问typedef struct LocalVariable { char *name; /* 仅用于错误消息与调试运行时查找不走它 */ int index; /* 相对于当前帧基址的偏移 */ TypeSpec *type; } LocalVariable;访问一个局部变量被编译成「帧基址 偏移」的一次寻址而不是一次字符串哈希。全局变量则放进一个独立的全局变量数组编译期分配全局下标。这个设计之所以成立前提是语言有静态作用域和显式声明——名字解析在编译期完成运行时不再有「这个名字到底指哪个变量」的歧义。函数调用时压入新帧帧里保存返回地址、旧帧基址和本次调用的局部变量槽返回时恢复。这套机制和真实 CPU 的调用约定同构理解了它再去看为什么栈式 VM 的指令集里要专门有OP_CALL、OP_RETURN、OP_PUSH_STACK_FRAME这几条就顺理成章了。4.3 标记-清除 GC那三行标记代码为什么不能省0.3 版本引入 GC是这批资料里含金量最高的一段。此前的版本用固定大小的对象数组或简单的引用计数一旦语言支持了对象引用和循环引用引用计数就漏了标记-清除则是「从根出发能到达的都留下剩下的全清掉」天然不怕环。对象统一挂在一个链表上每个对象头里带一个标记位typedef struct HeapHeader { struct HeapHeader *next; /* 所有堆对象的单向链表 */ uint8_t mark; /* 0 未标记1 可达 */ } HeapHeader; /* 标记阶段从根集出发递归着色 */ void gc_mark_object(Object *obj) { if (obj NULL || obj-header.mark) return; /* 已标记就直接返回防环 */ obj-header.mark 1; switch (obj-type) { case OBJ_STRING: break; /* 字符串无子引用 */ case OBJ_ARRAY: /* 数组要递归标记每个元素 */ for (int i 0; i obj-u.array.size; i) gc_mark_object(obj-u.array.elements[i]); break; case OBJ_CLOSURE: /* 闭包要标记它捕获的环境 */ gc_mark_object((Object *)obj-u.closure.env); break; } }两个细节决定了它能不能真正工作。第一obj-header.mark的提前返回是防环的唯一手段——没有它两个互相引用的对象会让递归无限下去直接栈溢出。第二「根集」必须精确且完整全局变量数组、当前执行栈上所有活跃的值、当前帧的局部变量槽、以及编译期常量池里持有的对象一个都不能漏。漏掉任何一个那个对象在标记阶段就是「不可达」的扫描阶段会被回收程序随后在某个毫不相关的地方崩掉——这类 bug 的定位难度极高因为崩溃点与出错点相隔很远。扫描阶段反而简单遍历对象链表标记为 0 的从链表摘掉、释放内存标记为 1 的把标记位清零等下一轮再用。触发时机一般是「分配新对象时发现已用内存超过阈值」阈值调大能减少 GC 次数但会抬高内存峰值调小则相反这是解释器里少数需要实际压测才能定的参数。从 0.3 到 0.4GC 的改动主要是补上了错误处理路径上的根集登记——抛出错误、展开栈帧的过程中栈上的临时对象不能被误回收。这类「异常路径上的 GC 正确性」在教科书里经常一笔带过实际写起来却最容易翻车。5. 排查make、bison 和路径空格怎么把编译链拆掉这批资料里最真实的部分其实是那些报错记录——同一个问题会在不同环境反复出现。下面五条是按出现频率排的每条都按「现象 → 原因 → 解决」走一遍。第一条mycalc.l:3:19: error: y.tab.h: No such file or directory。现象是编译 lex.yy.c 时找不到头文件但明明 bison 已经跑过了。原因是构建顺序错乱Makefile 里没声明lex.yy.c依赖y.tab.h直接gcc lex.yy.c就会先于 bison 执行并行构建时更明显。解决办法是在 Makefile 里把依赖写死——lex.yy.c: y.tab.hy.tab.h: mycalc.y让 make 自己去推顺序而不是靠人手敲命令的先后。第二条m4: cannot open Files: No such file or directory后面还跟着半截(x86)\GnuWin32\Bison/share/bison。现象是 bison 一启动就报一堆 m4 找不到文件的错。原因是 bison 的安装路径里带空格典型的Program Files (x86)它把自身 share 目录拼进 m4 的命令行时没加引号空格把路径切成了几段m4 于是去找一个叫Files的文件。解决办法只有两个装到无空格路径比如根目录下的短目录或者换一个不带空格的安装包布局。改环境变量、改 PATH 都没用因为切开路径的是 bison 自己。第三条process_begin: CreateProcess(NULL, bison --yacc -dv crowbar.y, ...) failed后面跟着一串乱码。现象是 make 能跑起来但一调用 bison 就失败错误信息还是乱码。原因是 bison 的可执行文件不在 PATH 里make 用 CreateProcess 直接调bison找不到乱码则是控制台代码页与编译器输出的编码不一致造成的跟真正的错误无关。解决办法是把 bison、flex 的 bin 目录加进 PATH 并重开终端至于乱码可以先chcp切代码页或者干脆把输出重定向到文件再按对应编码看——追乱码本身没意义看懂前一行英文才是重点。第四条gmake: *** No targets specified and no makefile found.现象是 make 找不到 Makefile。原因通常是当前目录不对——资源里 crowbar 和 diksam 各自有独立的 Makefilediksam 从 0.3 起还拆成了 compiler 和 main 两处进错一层就什么也找不到。另一个原因是工具名MinGW 下的 make 叫mingw32-make.exe很多资料里让重命名成gmake.exe如果只敲make而 PATH 里没有同名程序也可能落到别的实现上。解决办法是先pwd确认目录再确认用的是哪一份 make。第五条/usr/bin/ld: cannot find -lmsvcp60。现象是链接阶段失败提示找不到某个 Windows 运行库。原因是 Makefile 里写死了只在某个平台存在的库名换到另一个平台就没有对应文件。解决办法是改 Makefile 里的链接参数或者为该平台准备一份单独的构建配置——这也是为什么资源里同时给了 make.sh 和 make.bat 两份脚本而不是指望一份 Makefile 通吃。还有一类不算构建错误但很常见的脚本在某个环境里跑得好好的换到另一个环境就报「无法识别的字符(0x0d)」。原因是源文件在另一个系统上编辑保存时被写成了 CRLF 行尾而词法分析器的空白规则只认\n\r成了非法字符。解决办法是统一行尾或者在词法规则里显式把\r也当空白吞掉——后者更稳因为它把「环境差异」收敛进了语言实现内部。6. 设计取舍语义检查越早错误信息就越难写回头看这八个版本会发现一条清晰的主线crowbar 从「能算表达式」一路走到「有 GC 和错误恢复」diksam 则从「有类与接口」走到「编译与执行分离、目录拆成 compiler 和 main」。每一次能力扩张代价都落在同一个地方——错误信息。静态类型让运行时省掉了类型判断但也意味着所有类型错误必须在编译期被发现而编译期的类型检查需要完整的类型推导与上下文信息。字节码让执行变快但栈展开时的根集登记、异常路径上的对象生命周期都比树遍历复杂得多。GC 让内存管理透明但「精确根集」这个要求把编译器、执行引擎和错误处理三处的耦合拉满了任何一处漏登记都会变成难以复现的崩溃。最容易的判断标准是一个新特性如果只在正常路径上正确在错误路径上会引入不确定性那它就不该在这一版加进来。取舍点偏解释执行早期版本偏编译执行后期版本类型检查运行时分派实现简单编译期确定热路径更短变量访问名字哈希查找帧基址加整数偏移内存回收引用计数或固定数组标记-清除需精确根集错误信息位置粗实现省事位置精确需贯穿整条编译链如果只想验证这套实现能不能跑通最省事的入口是 test 目录下的脚本拿一份现成的 .crb 喂给编译出来的解释器看它能不能正确求值、能不能在语法错误时报出准确行列。然后改一处文法、重新生成、重跑同一份脚本——这一步能同时验证词法、语法、执行三段是否一致。我自己的习惯是每次动 .y 或 .l 之后先把 bison 的-v输出扫一眼冲突数量再看一眼 y.tab.h 的 token 编号有没有变最后才去跑测试。吃过一次「改了文法忘了重新生成、运行时行为诡异」的亏之后这套动作就成了肌肉记忆。资源里从 calc 到 mycalc 到 llparser 到 crowbar、diksam 的版本序列实际上就是把这条验证路径按难度铺好了顺着走一遍比直接啃最终的完整实现要扎实得多。希望帮到你。本文还有配套的精品资源点击获取