企业官网建设流程全解析

简介：这份《自制编程语言》配套资料面向希望从零理解语言设计与实现的学习者，聚焦语法设计、词法语法分析、解释器与编译器构建等核心问题，适合具备一定C语言基础、想打通“设计—实现—运行”链路的开发者与高年级学生。资料以Crowbar和Diksam两个自制语言案例为主线，从计算器示例逐步推进到语言版本迭代，串联yacc/lex、bison/flex、LL解析、make/gmake构建，以及MinGW、Cygwin在Windows与Linux下的环境配置，并涉及垃圾回收等实现细节，可帮助读者理解编译器与解释器的分工及跨平台构建差异。读者还可据此梳理语言设计原则、运行环境与资源管理、代码风格等知识，并对照案例复现完整工具链。包内共1个PDF文件，约2.38MB，便于集中阅读、离线查阅和做笔记。目前已有870人学习，适合用作编译原理课程实践、个人语言项目或入门后的补充材料。

1. 两套能跑起来的实现，比读完一本编译原理更早让人开窍

学编程语言最反直觉的地方在于：读完形式语言与自动机那一套理论，你依然写不出一个带函数调用和垃圾回收的解释器；而照着两个能跑的版本把从字符流到可执行的整条链路走通一遍，很多原本靠背诵的概念会突然落到实处。这套资料给的就是两个可运行的实现：Crowbar 从 ver.0.1 一路演进到 ver.0.4，每个版本只引入一个新机制——变量与表达式、控制流与函数、垃圾回收、类与继承；Diksam 则从 0.1 到 0.4 走另一条路，静态类型加字节码虚拟机。两条路线并排放在一起，你看到的就不是“语言怎么写”，而是同一个语义问题在解释执行和编译执行下各自要付什么代价，以及为什么大部分现实中的语言最终都在这两者之间来回摇摆。

2. 词法与语法分析：.l 和 .y 到底被编译成了什么

很多人第一次跑 flex/bison 时会有一种玄学感：明明写的是正则和文法，怎么就变成 C 文件了。要破除这种感觉，只需要记住一件事——这两个工具做的事，本质上是把你写的声明式规则，翻译成两张可以查的表和一段驱动这两张表的循环代码。

2.1 flex：把正则编译成一台最长匹配的 DFA

flex 读入.l文件，把每条规则左侧的正则先转成 NFA，再用子集构造法确定化成 DFA，最后生成一个yylex()函数。它的匹配策略是固定的两条：最长匹配优先，长度相同时按规则在文件中出现的先后顺序决定。这一条决定了很多语言里关键字和标识符必须分开写规则，也决定了.l文件里规则的排列顺序本身就是语义的一部分。

/* crowbar 词法分析器结构示意：起始条件用来处理需要配对的结构 */ %option noyywrap %{ #include "crowbar.h" %} %x COMMENT STRING_LITERAL_STATE /* 进入注释/字符串后切到独立状态 */ %% "/*" { BEGIN COMMENT; } /* 切换状态，而不是用正则硬啃 */ <COMMENT>"*/" { BEGIN INITIAL; } /* 回到正常状态 */ <COMMENT>.|\n ; /* 注释内容整体丢弃 */ \" { BEGIN STRING_LITERAL_STATE; } <STRING_LITERAL_STATE>\" { BEGIN INITIAL; return STRING_LITERAL; } [0-9]+ { yylval.int_value = atoi(yytext); return INT_LITERAL; } [ \t\n]+ ; /* 空白不产生 token */ . { yyerror("非法字符"); } %%

这段代码最值得琢磨的不是语法，而是为什么要用起始条件而不是一条/\*.*?\*/的正则。原因是 DFA 没有栈：它能记住“当前走到第几个状态”，但记不住“已经开了几层注释”。注释、字符串、括号这类需要配对的结构，本质上不是正则语言能表达的东西。所以词法层只能靠状态机做粗粒度的切换，真正的嵌套结构必须交给上层的语法分析器用显式栈去管。这就是“为什么词法分析不够、必须有语法分析”的最朴素答案。

顺带说一个细节：yytext指向的是匹配缓冲区里的原始文本，yylval才是把语义值传给语法分析器的通道。yylval在生成的y.tab.h里被声明成一个联合体，具体哪个成员有效，由%token <int_value>这类声明决定。这个联合体是词法层和语法层之间唯一的契约。

2.2 bison：移进-归约与 LALR(1) 表驱动

bison 读入.y文件，构造 LALR(1) 分析表，生成yyparse()。这个函数内部是一个循环：从词法分析器取一个 token，查 action 表决定是移进（把这个 token 压进状态栈）还是归约（按某条产生式把栈顶的 n 个符号弹出，计算语义值，再把左部符号压回去），归约之后查 goto 表决定下一个状态。

/* 表达式文法片段：%left/%right 用来消解二义性，而不是改写文法 */ %token <int_value> INT_LITERAL %type <expression> expression %left '+' '-' %left '*' '/' %right '=' %% expression : expression '+' expression { $$ = create_binary('+', $1, $3); } | expression '-' expression { $$ = create_binary('-', $1, $3); } | expression '*' expression { $$ = create_binary('*', $1, $3); } | INT_LITERAL { $$ = create_int($1); } ; %%

$$和$1、$3是语义值栈上的槽位，归约时从左部对应的位置取出来，算完写回$$。create_binary在归约发生的瞬间就被调用，也就是说语法树是边解析边建的，解析结束时树也就建好了，不存在“先出一棵树再遍历一遍”的中间阶段。

这里有个反直觉的点值得单独说：左侧递归（expression '+' expression这种自己套自己）在自底向上的分析器里不但没问题，反而是推荐写法。因为分析器用的是堆上的显式栈，左递归恰好对应“先把左边归约完，再移进运算符和右边”，栈深度只跟运算符优先级有关，跟输入长度基本无关。但如果换成手写递归下降，同样的左递归会直接把调用栈打穿。同一个文法，两种分析方式对写法方向的要求正好相反。

还有一条会在后面反复出现的因果链：.y文件在生成y.tab.c的同时会生成y.tab.h，里面是所有 token 的编号定义；词法分析器的.l文件里有一行#include "y.tab.h"。这意味着bison 必须先于 gcc 成功执行，否则 gcc 拿到的就是一份缺头文件的 C 代码。第 5 章那些y.tab.h: No such file的报错，根子都在这里。

2.3 手写的 LL 解析器：为什么有人放着生成器不用

资料里另有一份llparser，是纯手写的递归下降实现，不依赖 bison/flex。它的结构是每个非终结符对应一个函数，靠向前看一个 token 决定走哪条分支。代价是文法必须改写：左递归要改成循环，有公共前缀的要提取左因子，否则就得回溯。

# 递归下降的核心手法：用 while 循环表达左递归 def parse_expr(self): value = self.parse_term() # 先吃掉一个 term while self.peek() in ('+', '-'): # 左结合 -> 循环，而不是递归调用自己 op = self.next() rhs = self.parse_term() value = value + rhs if op == '+' else value - rhs return value # 直接求值，不建语法树

parse_term内部再处理*和/，层级本身就编码了优先级，不需要%left那种声明。这种“解析即求值”的单遍结构，是最小形态的树遍历解释器——它连树都没建。好处是错误信息能精确到“这里期望一个表达式，实际拿到)”，而且整个实现只依赖编译器本身；坏处是文法一旦变复杂（比如要支持类型声明、类定义），手写的分支会迅速膨胀成难以维护的一团。

选哪条路，取决于你的目标是“讲清机制”还是“支撑一门完整的语言”。前者用手写，控制流一目了然；后者用生成器，文法改动只需要改几行声明。资料里两套都给了，恰好让人能对照着看同一段文法在两种实现下的形状差异。

3. 从语法树到执行：树遍历和字节码的分岔口

语法分析结束，语言实现才走到真正分岔的地方：拿到的那棵树（或者那串指令）怎么变成行为。这一步的选择，几乎决定了后续所有模块的形态——变量怎么存、函数怎么调、垃圾回收要扫哪些根。

3.1 AST 的节点结构：用 tag + union 手写一张虚表

C 里没有虚函数表，多态节点只能自己造。标准做法是一个类型标签加一个联合体，标签决定联合体里哪个成员有效：

typedef enum { INT_EXPRESSION, BINARY_EXPRESSION, ASSIGN_EXPRESSION, FUNCTION_CALL_EXPRESSION } ExpressionType; struct Expression { ExpressionType type; /* 标签，等价于手写的 vtable 指针 */ union { int int_value; struct { /* 二元运算 */ struct Expression *left; ExpressionType operator; struct Expression *right; } binary; struct { /* 赋值 */ char *name; struct Expression *operand; } assign; struct { /* 函数调用 */ char *name; struct Expression *arguments; } func_call; } u; };

这种布局的好处是节点大小固定、可以整块分配、遍历时缓存友好；坏处是每次求值都要做一次 switch 分支，而这个分支的预测成功率完全取决于输入程序的形状。求值函数就是一个递归的 switch：

Value eval_expression(Expression *expr) { switch (expr->type) { case INT_EXPRESSION: return expr->u.int_value; /* 叶子节点，直接返回 */ case BINARY_EXPRESSION: { Value l = eval_expression(expr->u.binary.left); /* 先左后右，顺序写死 */ Value r = eval_expression(expr->u.binary.right); return eval_binary(l, expr->u.binary.operator, r); } /* ... 其余节点类型 ... */ } }

注意求值顺序是后序的：子节点先算完，父节点才算。这个顺序在语言规范里必须明确规定，否则f() + g()里两个函数的副作用先后就不确定了。绝大多数语言规定从左到右，实现上就体现为这两行代码的书写顺序——别小看它，把这两行调换，程序在绝大多数测试用例上照样跑对，只在有副作用的表达式上偶发翻车，属于典型的隐蔽 bug。

3.2 字节码：把树压平成一维指令流

Diksam 走的是另一条路：把语法树线性化成一段 opcode 数组，运行时用一个取指-译码-执行的循环去跑。

typedef enum { OP_PUSH_INT, OP_PUSH_DOUBLE, OP_ADD, OP_MUL, OP_LOAD_LOCAL, OP_STORE_LOCAL, OP_JUMP, OP_JUMP_IF_FALSE, OP_CALL, OP_RETURN } OpCode; /* 编译期： a = b + 1 编译为 LOAD_LOCAL <b 的下标> PUSH_INT 1 ADD STORE_LOCAL <a 的下标> */ /* 运行期：一个循环 + 一个 switch */ while (1) { OpCode op = code[pc++]; /* 取指，pc 单调递增 */ switch (op) { case OP_PUSH_INT: stack[++sp] = code[pc++]; break; case OP_ADD: sp--; stack[sp-1] += stack[sp]; break; case OP_LOAD_LOCAL: stack[++sp] = frame[code[pc++]]; break; case OP_STORE_LOCAL: frame[code[pc++]] = stack[sp--]; break; /* ... */ } }

对比两种模型的代价很清晰。树遍历的问题是：每求一个节点要解引用一个指针再跳一次 switch，节点分散在堆上，缓存局部性差；同一段代码被循环执行一千次，就解释一千次。字节码把结构压平成一维数组，pc 自增就是顺序访存，取指和译码的开销被降到最低。代价是必须多一次编译、多一份中间表示，出错时要把 pc 映射回源码的行列号才能报错——所以字节码实现里那张“指令地址到源码位置”的映射表不是可选项，是必需品。

Diksam 之所以愿意付这个代价，跟它的类型系统有关：静态类型要求类型检查在编译期完成，既然你无论如何都要完整遍历一遍语法树，那顺手产出字节码的边际成本就不高了。这是设计上很典型的一种“既然已经付了这笔钱，就把能一起做的事都做掉”的取舍。

3.3 名字解析：从运行时查表到编译期定下标

变量访问的实现，是两套代码差距最明显的地方。早期版本里，局部变量存在一个数组里，读取一个变量要拿名字去数组里做strcmp线性查找。变量一多、循环一深，这个查找就成了热路径上的主要开销。

后来演化出的做法是：编译期就把每个局部变量编号，运行时直接按下标访问。

typedef struct { int *return_address; /* 回到调用者的哪条指令 */ Value *locals; /* 大小在编译期确定，下标访问 */ int local_count; Value *stack; /* 这个函数的求值栈基址 */ } Frame;

这一改动的本质，是把“名字”和“位置”彻底分开：名字只在编译期有意义，运行期只剩偏移量。几乎所有真实实现都走这条路，区别只在于偏移量是相对栈帧还是相对某个对象头。理解了这个转变，你再看闭包、再看this的传递、再看栈上分配和堆上分配的边界，很多设计就不再是凭空的规则，而是“名字必须在编译期解决掉”这条约束推出来的结果。

4. 垃圾回收：为什么这个机制要到 ver.0.3 才出现

语言实现里最容易被低估的一件事是：GC 不是高级特性，它是语言表达力提升之后被迫做出的补偿。早期版本里只有立即数和一堆字符串常量，字符串全部放进一个只增不减的驻留池，相同字面量只存一份，生命周期跟进程一样长——既然从不释放，当然就不需要回收。等到字符串拼接、数组、对象进来，堆对象变成运行期动态产生、生命周期不确定，不回收就是持续泄漏，要回收就必须回答“谁还活着”。这个问题的答案，决定了整个运行时数据结构的形状。

4.1 标记-清除：从根集出发的可达性分析

标记-清除的核心只有两句话：从根集出发把所有能走到的对象打上标记，然后扫一遍整个堆，没被标记的整块丢掉。

/* 标记阶段：沿对象图深度优先遍历 */ static void mark_object(Obj *obj) { if (obj == NULL || obj->marked) return; /* 已标记直接返回，顺便防住循环引用死循环 */ obj->marked = 1; switch (obj->type) { case OBJ_STRING: /* 字符串没有子引用，到此为止 */ break; case OBJ_ARRAY: for (int i = 0; i < obj->u.array.len; i++) mark_object(obj->u.array.items[i]); /* 递归标记每个元素 */ break; case OBJ_CLOSURE: mark_object(obj->u.closure.env); /* 闭包捕获的环境也是引用 */ break; } } /* 清除阶段：扫堆，回收未标记对象，并复位标记位 */ static void sweep(void) { Obj **p = &heap_head; while (*p) { if (!(*p)->marked) { Obj *dead = *p; *p = dead->next; /* 从链表上摘掉 */ free_obj(dead); /* 归还内存 */ } else { (*p)->marked = 0; /* 关键：复位，否则下一轮全是“活”的 */ p = &(*p)->next; } } }

这里有几个必须说清的机制点。根集包含哪些东西：全局变量表、当前调用栈上所有活跃栈帧的局部变量、求值栈上还没弹掉的临时值。根集漏掉任何一处，活对象就会被当垃圾收走，症状是数据莫名其妙被覆盖或者随机崩溃，而且往往要等到下一次 GC 才炸——这就是最难查的那类问题，现象和原因隔了几百条指令。

marked标志的双重作用：它既是标记，也是终止递归的条件。如果对象图里有环（A 引用 B、B 引用 A），没有这个判断，mark_object会无限递归直到栈溢出。这正好引出标记-清除相对引用计数的根本优势。

递归标记的隐患：对象图很深时（比如一条长链表），递归会打穿调用栈。常见的实现思路是显式维护一个标记栈，或者用指针反转（Deutsch-Schorr-Waite）把遍历路径临时编码进对象自身的引用字段里，代价是遍历期间必须停止其他所有操作。

4.2 引用计数与标记-清除：一个能处理环，一个不能

两种方案经常被拿来对比，但真正的分水岭只有一条。

循环引用这一条基本决定了早期脚本语言解释器的选择：只要语言里有对象和闭包，用户写出环就是迟早的事，而这个环在引用计数下就是一块永远漏掉的内存。标记-清除从根集算可达性，环不影响结果，代价是要能准确枚举根集。

4.3 压缩与分代：为什么 GC 最终会和类型系统合流

标记-清除不移动对象，堆上会留下大小不一的空洞。小对象还能填进去，大对象（比如长字符串、大数组）就容易分配失败，明明总空闲内存够用。常见的实现思路是标记-压缩：标记完成后把存活对象往堆的一端挪，用一个 forwarding 指针记录“旧地址 → 新地址”的映射，再扫一遍根集和所有存活对象内部，把引用字段改写成新地址。

这一步有个硬前提：你必须能精确知道某个对象的哪个字段是引用、哪个字段是普通数值。如果是保守式的（比如把栈上任何看起来像指针的值都当引用），压缩就做不了，因为你没法安全地改写一个你不确定是不是指针的值。要精确，就得有类型信息。于是这条因果链就成立了：静态类型系统 → 精确的对象布局描述 → 可以做压缩 → 内存碎片可控 → 长时间运行不退化。GC 和类型系统看着是两个模块，实际上是同一个决策的两个侧面。

5. 跨平台构建排查：bison、Cygwin、MinGW 混用时那些报错在说什么

这套资料的编译过程，几乎是把 Windows 上搭建类 Unix 工具链的所有经典坑踩了一遍。这些报错看着五花八门，但归层之后只有三类：工具没找到、产物没生成、工具链不同源。排查的第一步永远是看输出的第一行错误，而不是最后一行的Error 1——最后一行只是前一个失败的被动结果。

5.1 先归层：No such file到底是谁在抱怨

gcc: y.tab.c: No such file or directory报错的是 gcc，但问题几乎不在 gcc。它是下游，上游的 bison 没跑成功、或者跑成功了但产物落在别的目录，gcc 只是照着 Makefile 里的规则去拿文件却拿不到。同理，mycalc.l:3:19: error: y.tab.h: No such file报的是词法文件找不到头文件，实际原因是 bison 根本没执行。养成一个习惯：抓 make 输出里第一个非零退出的命令，那才是根因所在。

5.2 五条踩坑记录

第一条：mingw32-make: *** No targets specified and no makefile found现象是敲了make或者gmake，直接说找不到目标。原因有两层：一是当前目录不对，cd到了父目录或者源码根而不是具体某个版本目录；二是 Windows 上 MinGW 提供的那份可执行文件名字叫mingw32-make.exe，make这个词根本不认识，而某些终端里gmake也不是自带命令。解决办法是把目录切到含Makefile的那一层，并显式用mingw32-make -f Makefile；如果嫌麻烦，就把mingw32-make.exe复制一份改名成make.exe，但要清楚这是你自己造的别名，不是工具的行为。

第二条：process_begin: CreateProcess(NULL, bison --yacc -dv crowbar.y, ...) failed，紧跟y.tab.h failed现象是 make 直接报创建进程失败，然后由于依赖断链，y.tab.h永远不出现。原因是bison不在 PATH 里。MinGW 本身不带 bison 和 flex，得另外装一套 GnuWin32 版本，然后把它的bin目录加进 PATH。注意 PATH 的生效范围取决于你从哪个终端启动——在系统属性里改完不重启终端是不生效的。验证办法很直接：先单独在命令行敲bison --version，能出版本号再回去 make。

第三条：m4: cannot open 'Files': No such file or directory这条报错最有迷惑性，因为它连“文件”都不像。真实原因是 bison 内部会调用 m4，而拼出来的 m4 搜索路径里有空格：如果装在C:\Program Files (x86)\GnuWin32\...，那个空格会把一整条路径拆成多个参数，于是 m4 收到了Program、Files、(x86)\GnuWin32\...三个不存在的文件名。报错里反复出现的Files和(x86)就是铁证。解决办法只有一个方向：把工具装到无空格的路径下，比如D:\GnuWin32，重新装一遍比修环境变量省事得多。

第四条：Cygwin 和 MinGW 混用导致的链接与路径错误现象是ranlib.exe: '/usr/local/lib/libonig.a': No such file，或者cannot find -lmsvcp60。原因是两套环境的路径语义不同：Cygwin 用/usr/local、/cygdrive/c这一套挂载点，MinGW 的可执行文件完全不认；而-lmsvcp60是 Windows 运行库的名字，在 Linux 上根本不存在，说明有人把 Windows 侧的 Makefile 直接拿到 Linux 跑了。原则很简单：一条构建链上的工具必须同源。要么全部用 Cygwin 的 gcc + configure + make（产物会依赖 cygwin1.dll），要么全部用 MinGW，而且第三方库也必须用 MinGW 重新编译一遍——用 Cygwin 编出来的.a拿到 MinGW 下链接，符号和 ABI 都对不上。另外 32 位和 64 位也不能混，混了会直接报无法识别的文件格式。

第五条：换行符和源码编码现象是在 Linux 下跑测试脚本，解析器报“非法字符(0x0d)”；或者源码里含非 ASCII 字符时，明明内容没问题却编译报错、运行时输出乱码。原因是文件保存成了 CRLF 换行，而词法分析器只把\n当空白，\r就成了无法识别的字符；编码问题同理，编辑器用一种编码存，编译器按另一种读。解决办法：先用dos2unix把测试文件统一转成 LF，源码编码统一到 UTF-8，确实需要别的编码时用编译选项显式告源文件的字符集。

5.3 把环境固定下来的验收清单

排查完之后，最好把“能跑起来的那个状态”固化成几条可复现的检查，下次换机器直接对一遍：

• 单敲bison --version、flex --version、mingw32-make --version，三个都要有输出，缺一个就先解决 PATH。
• 所有工具的安装路径不含空格、不含中文。
• 构建目录里先只跑mingw32-make y.tab.h这类最上游目标，确认 bison 能单独成功，再把整条链跑完。
• 单独跑config类脚本时，看它打印的编译器绝对路径是不是你期望的那一套，不是就立刻停手，别继续 make。
• 第一次跑通之后，把 Makefile 里所有隐式依赖的工具名改成显式路径，避免以后 PATH 变化导致“昨天能编今天不能编”的玄学。

6. 设计取舍：增量版本为什么比一次性写完更有价值

这套资料真正稀缺的地方，不是“给了两个能跑的语言实现”，而是把每个机制单独拎出来变成一个版本：0.1 只有表达式和变量，0.2 加控制流和函数，0.3 加 GC，0.4 加类。每个版本都是一次只动一个维度，出了问题范围可控。如果一次性写完，一旦崩了，你要同时怀疑语法分析、作用域、栈帧、GC 四个模块互相耦合出的错误，排查成本是版本化方式的几倍。这套资料里的实现就是这个思路的产物。

验证一个语言实现是否真的理解了机制，我一般用三个动作：第一，把测试目录的脚本全跑一遍，别只看能不能编译；第二，在两个相邻版本之间做 diff，看新增的那几百行到底改了哪几处数据结构，形状一变，后面所有模块都得跟着变；第三，故意往 GC 里加一行日志，统计每轮回收了多少对象、堆峰值多少，如果峰值随循环次数单调增长，说明根集漏标或者某个引用没被遍历到。

这套资料适合放在手边反复翻，不适合从头读到尾。真正的收获往往发生在你改了一行 opcode、程序输出变了，然后回头去看那个 switch 的时候。我自己吃过一次亏：为了省事把求值顺序里两行调了个位置，所有测试用例全绿，直到某个带副作用的表达式在线上偶发错乱才被发现。从那以后，凡是涉及求值顺序、标记位复位、根集枚举这三处，我都强制自己写一条能暴露顺序的测试用例再往下走。希望帮到你。

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