手撸解释器实战：Crowbar/Diksam教学代码库详解

简介本资源是一套面向编程语言学习者与编译原理初学者的《自制编程语言》系统性入门资料聚焦语言设计、实现与工程实践全过程。内容覆盖语法语义设计原则、编译器/解释器开发流程、MinGW环境搭建、bison/flex词法与语法分析器生成以及Crowbar和Diksam两款真实自制语言的完整演进版本v0.1–v0.4源码与配套技术文档含Linux/Windows双平台构建脚本make.sh/make.bat及GCC/MinGW适配说明。资源为单个PDF文件大小2.38MB结构清晰、图文结合便于离线研读与代码对照。目前已有870人学习下载适合高校计算机专业学生、自学者及对编译器开发感兴趣的开发者可直接用于课程设计参考、小型语言原型开发或编译原理实践项目支撑。1. 这不是玩具语言Crowbar/Diksam 资料包是手撸解释器的硬核脚手架专治“学完编译原理仍不会写 parser”的焦虑你翻过《编译原理》龙书背熟了 LL(1)、LR(0)、FIRST/FOLLOW 集甚至能徒手画出语法树——但当你真正想造个能跑print(hello)的小语言时卡在了y.tab.h: No such file or directory你照着教程敲bison -d parser.y终端却报process_begin: CreateProcess failed你把flex和bison装进C:\Program Files\GnuWin32结果m4直接崩溃说cannot open Files……这不是玄学是真实踩坑现场。这份名为《自制编程语言》的资料包本质是一套可编译、可调试、带完整演进版本链的工业级教学代码库它包含 Crowbar0.1→0.4和 Diksam0.1→0.4两个真实运行过的解释器源码配套四版逐层迭代的电子书含中文注释以及覆盖 Linux/macOS/Windows 三端的构建脚本make.sh/make.bat/gmake。它不讲抽象理论只提供你能cd进去、make出来、./crowbar test/test.crb立刻看到输出的实打实二进制。适合两类人一是刚啃完 Dragon Book 想落地验证的在校生二是需要快速搭建 DSL 解析引擎的嵌入式/工具链工程师——它解决的不是“什么是语法分析”而是“为什么我的 lex.yy.c 总找不到 y.tab.h”。2. 从 ZIP 解压到第一个可执行文件Crowbar 构建全流程拆解含 Windows MinGW 与 Linux 原生双路径2.1 解压即得完整项目结构理解crowbar_book_0_X目录的演进逻辑该资料包以多个 ZIP 文件形式存在命名规则为crowbar_book_0_X.zipX1~4和diksam_book_0_X.zipX1~4。每个 ZIP 解压后形成独立目录例如crowbar_book_0_2其核心结构如下crowbar_book_0_2/ ├── crowbar/ # Crowbar 解释器主源码C 语言 │ ├── crowbar.y # Bison 语法定义文件BNF 描述 │ ├── crowbar.l # Flex 词法定义文件正则匹配 token │ ├── main.c # 入口函数调用 parser interpreter │ ├── interface.c # AST 构建与遍历接口 │ ├── execute.c # 字节码执行或直接解释逻辑 │ └── ... # 内存管理、GC、字符串池等模块 ├── test/ # 测试用例集.crb 后缀 │ └── test.crb # 示例print(Hello, Crowbar!); ├── Makefile # GNU Make 构建规则关键 ├── make.sh # Linux/macOS 下一键构建脚本 └── make.bat # Windows 下批处理构建脚本注意crowbar_book_0_1是最简版本仅含基础 parsercrowbar_book_0_4引入了 GC垃圾回收和更健壮的错误处理。不要跳过早期版本——0_1的 Makefile 只有 30 行是你理解整个构建链路的黄金起点而0_4的memory/子目录里藏着gc.c这才是工业级语言的分水岭。2.2 Linux/macOS 原生构建三步走通bisonflexgcc在类 Unix 系统上构建依赖链清晰flex生成词法分析器 →bison生成语法分析器 →gcc编译所有.c文件 → 链接成crowbar可执行文件。执行以下命令# 1. 进入项目根目录以 crowbar_book_0_2 为例 cd crowbar_book_0_2 # 2. 确保已安装 flex/bison/gccUbuntu/Debian sudo apt-get install flex bison build-essential # 3. 执行构建自动调用 make.sh ./make.shmake.sh的核心逻辑是#!/bin/bash # make.sh 内容精简版 flex crowbar.l # 生成 lex.yy.c词法分析器 C 源码 bison -d crowbar.y # 生成 y.tab.c 和 y.tab.h语法分析器 C 源码 头文件 gcc -o crowbar *.c # 编译所有 .c 文件含 lex.yy.c, y.tab.c, main.c...参数说明flex crowbar.l读取crowbar.l中的正则规则输出lex.yy.c其中yytext指向当前匹配的 token 字符串yylval用于传递 token 值如数字字面量。bison -d crowbar.y-d参数强制生成y.tab.h该头文件声明了yyparse()函数和yylval类型定义是lex.yy.c能#include y.tab.h的前提。若省略-dy.tab.h不会生成必然报错。gcc -o crowbar *.c此处*.c包含lex.yy.c、y.tab.c、main.c等顺序无关紧要因 GCC 会自动解析符号依赖。构建成功后./crowbar test/test.crb将输出Hello, Crowbar!。若失败请立即跳转至第 4 章「避坑指南」。2.3 Windows MinGW 构建绕过C:\Program Files路径陷阱的实操方案Windows 下最大的血泪经验是绝对不要把 MinGW 或 Bison 安装到含空格的路径如C:\Program Files\。所有报错m4: cannot open Files或CreateProcess failed均源于此。正确做法是:: 1. 下载并安装 MinGW 到无空格路径推荐 D:\MinGW :: 访问 http://www.mingw.org/ 下载 mingw-get-setup.exe :: 安装时Installation Directory 改为 D:\MinGW非默认 C:\MinGW :: 2. 启动 MinGW Installation Manager勾选 :: - mingw32-base (基础 GCC 工具链) :: - msys-base (提供 bash、make 等 Unix 工具) :: - mingw32-gcc-g (C/C 编译器) :: 3. 将 D:\MinGW\bin 和 D:\MinGW\msys\1.0\bin 加入系统 PATH :: 控制面板 → 系统 → 高级系统设置 → 环境变量 → Path :: 4. 下载 GNUWin32 版 bison/flex非 Cygwin :: 访问 http://gnuwin32.sourceforge.net/packages/bison.htm :: 下载 Complete package, except sources → 解压到 D:\bison :: 同样下载 flex → 解压到 D:\flex :: 将 D:\bison\bin 和 D:\flex\bin 加入 PATH :: 5. 进入项目目录使用 mingw32-make非 Windows 自带 make D: cd \win_sjis\crowbar_book_0_2 D:\MinGW\bin\mingw32-make.exemingw32-make.exe会读取Makefile执行# Makefile 关键片段crowbar_book_0_2 YACC bison LEX flex CC gcc y.tab.c y.tab.h: crowbar.y $(YACC) -d $(YACCFLAGS) $ lex.yy.c: crowbar.l $(LEX) $(LEXFLAGS) $ crowbar: y.tab.c lex.yy.c main.c interface.c ... $(CC) -o $ $^关键点Makefile中YACC bison必须指向你安装的bison.exe在D:\bison\bin而非系统 PATH 中可能存在的旧版本。若bison --version报错说明 PATH 未生效需重启 CMD。3. 从源码读懂解释器骨架Crowbar 的四大核心模块与执行流程图解3.1 词法分析器crowbar.l如何把字符流切分成有意义的 Tokencrowbar.l是 Flex 输入文件定义了 Crowbar 语言的词法规则。其核心结构为%{ #include crowbar.h #include y.tab.h // 必须包含否则 yylval 无法识别 %} %% [0-9] { yylval.int_value atoi(yytext); return INTEGER; } print { return PRINT; } ( { return LPAREN; } ) { return RPAREN; } ; { return SEMICOLON; } [ \t\n] ; /* 忽略空白 */ . { return yytext[0]; } /* 默认返回单字符 */ %% int yywrap() { return 1; }逻辑说明%{ ... %}区域插入 C 头文件y.tab.h提供INTEGER、PRINT等 token 枚举值及yylval结构体定义。%%后是规则区[0-9]匹配整数atoi(yytext)将字符串转为整型存入yylval.int_valueprint返回PRINTtoken。yywrap()是 Flex 必须实现的函数返回1表示输入结束。参数说明yytext是 Flex 自动维护的指针指向当前匹配的字符串yylval是 Bison 定义的联合体union用于在 lexer 和 parser 间传递 token 值如数字、标识符名。3.2 语法分析器crowbar.yBNF 规则如何驱动 AST 构建crowbar.y使用 Bison 语法定义 Crowbar 的语法规则。关键片段如下%{ #include crowbar.h #include interface.h %} %union { int int_value; char *str_value; struct ASTNode *node; } %token int_value INTEGER %token str_value IDENTIFIER %type node program statement print_statement expression %% program: statement { $$ $1; } ; statement: print_statement { $$ $1; } ; print_statement: PRINT LPAREN expression RPAREN SEMICOLON { $$ new_print_node($3); } // 创建 AST 节点 ; expression: INTEGER { $$ new_integer_node($1); } ; %% // new_print_node() 在 interface.c 中实现分配内存并设置 typePRINT_NODE逻辑说明%union定义yylval的联合体类型支持int_value整数、str_value字符串、nodeAST 节点指针。%token和%type声明 token 和非终结符的类型确保$1、$3等引用时类型安全。print_statement规则中{ $$ new_print_node($3); }是动作代码$$是当前产生式的结果即print_statement对应的 AST 节点$3是expression的节点。new_print_node()在interface.c中实现负责 malloc 内存并初始化节点字段。参数说明$$是产生式左部的值$1、$2是右部第 1、2 个符号的值new_print_node()返回struct ASTNode*其type字段设为PRINT_NODEchild字段指向$3表达式节点。3.3 解释器执行器execute.cAST 如何被递归求值execute.c是 Crowbar 的“大脑”它遍历 AST 并执行对应操作。核心函数execute_node()如下void execute_node(struct ASTNode *node) { switch(node-type) { case PRINT_NODE: printf(%d\n, execute_node(node-child)); // 递归求值子表达式 break; case INTEGER_NODE: return node-value; // 直接返回整数值 case ADD_NODE: return execute_node(node-left) execute_node(node-right); default: error(Unknown node type); } }逻辑说明PRINT_NODE节点先递归调用execute_node(node-child)求值其子表达式如INTEGER_NODE再printf输出。INTEGER_NODE节点直接返回node-value在new_integer_node()中设置。ADD_NODE节点递归求值左右子树再相加。参数说明node-child是单子节点如print(12)中12是PRINT_NODE的唯一子节点node-left/node-right是二叉节点如ADD_NODE的左右操作数。3.4 内存管理模块memory/Crowbar 0.4 的 GC 实现原理crowbar_book_0_4新增memory/目录实现标记-清除Mark-SweepGC。关键数据结构// memory/gc.h typedef struct Object { enum ObjectType type; // INTEGER, STRING, ARRAY... struct Object *next; // 链表指针 bool marked; // 标记位true可达 } Object; extern Object *object_list; // 所有分配对象的链表头GC 流程标记阶段从全局变量、栈帧等根集合出发递归遍历所有可达对象置markedtrue。清除阶段遍历object_list释放所有markedfalse的对象内存并重置markedfalse。为什么需要 GCCrowbar 0.1~0.3 中string_pool.c用固定大小数组管理字符串易溢出array.c中数组扩容需手动realloc。0.4 引入 GC 后new_string_object()分配的字符串对象由 GC 统一管理开发者无需关心free()—— 这正是现代语言如 Python、JS的基石。4. 避坑指南Crowbar 构建与运行中 5 个高频翻车现场及根治方案4.1 现象y.tab.h: No such file or directory原因bison -d crowbar.y未执行或执行后y.tab.h生成在错误目录如./src/下但crowbar.l在./下。解决确认bison命令是否成功执行无报错且生成y.tab.c和y.tab.h。检查crowbar.l中#include y.tab.h的路径若y.tab.h在同级目录则正确若在src/下需改为#include src/y.tab.h。终极方案在Makefile中显式指定输出目录y.tab.c y.tab.h: crowbar.y bison -d -o ./y.tab.c crowbar.y # 强制输出到当前目录4.2 现象m4: cannot open FilesWindows原因bison或flex安装在C:\Program Files\路径含空格m4bison 依赖的宏处理器无法解析。解决卸载C:\Program Files\下的 Bison/Flex重新安装到D:\bison、D:\flex。删除系统 PATH 中所有C:\Program Files\相关条目只保留D:\bison\bin、D:\flex\bin、D:\MinGW\bin。验证CMD 中执行where bison输出应为D:\bison\bin\bison.exe。4.3 现象gcc: y.tab.c: No such file or directory原因bison生成了y.tab.c但gcc编译时未包含该文件Makefile中crowbar: *.c未匹配y.tab.c因y.tab.c是隐藏文件。解决修改Makefile显式列出所有源文件SRCS y.tab.c lex.yy.c main.c interface.c execute.c ... crowbar: $(SRCS) $(CC) -o $ $^或使用通配符crowbar: y.tab.c lex.yy.c *.c确保y.tab.c在前。4.4 现象Segmentation fault运行时崩溃Linux/macOS原因crowbar.l中st_line未初始化fgets(st_line, ...)向野指针写入。解决查找crowbar.l中类似代码static char *st_line; // 未分配内存 while (fgets(st_line, LINE_BUF_SIZE, stdin) ! NULL) { ... }修复为static char st_line[1024]; // 栈上分配固定缓冲区 while (fgets(st_line, sizeof(st_line), stdin) ! NULL) { ... }或动态分配char *st_line malloc(LINE_BUF_SIZE);需在main()中free(st_line)。4.5 现象/usr/bin/ld: cannot find -lmsvcp60Linux 下链接错误原因crowbar_book_0_4的Makefile中误加了 Windows 特定链接选项-lmsvcp60Microsoft Visual C 运行库Linux GCC 无法识别。解决编辑crowbar_book_0_4/Makefile搜索-lmsvcp60将其删除。或改为条件编译ifeq ($(OS),Windows_NT) LDFLAGS -lmsvcp60 endif需在 Makefile 开头添加OS : $(shell uname -s)5. 进阶验证用gdb调试 parser 执行流定位语法错误的黄金三步法5.1 编译时加入调试信息让gdb看得见源码行号crowbar_book_0_X的Makefile默认未开启调试符号导致gdb无法显示源码。必须修改CFLAGS# 修改前crowbar_book_0_2/Makefile CFLAGS -g -Wall -Wswitch-enum -ansi -pedantic -DDEBUG # 修改后确保 -g 在最前且无 -O2 等优化干扰 CFLAGS -g -O0 -Wall -Wswitch-enum -ansi -pedantic -DDEBUG为什么-O0关键编译器优化如-O2会内联函数、重排指令导致gdb单步时跳转混乱print命令显示变量值为空。-O0关闭优化保证源码与汇编严格一一对应。5.2 用gdb拦截yyparse()观察语法分析器每一步动作假设测试文件test/error.crb内容为print(1);缺少右操作数我们想看 parser 在哪一行报错# 1. 重新编译确保 -g 生效 make clean make # 2. 启动 gdb 并设置断点 gdb ./crowbar (gdb) break yyparse # 在语法分析器入口打断点 (gdb) run test/error.crb # 运行并触发断点 # 3. 单步执行观察 token 流 (gdb) step # 进入 yyparse() (gdb) step # 下一步通常进入 yylex() (gdb) print yytext # 查看当前 token 字符串如 print (gdb) print yylval.int_value # 查看 token 值如 0技巧当 parser 报错syntax error, unexpected ;, expecting )时在gdb中step到yyparse()内部用info registers查看RIP指令指针附近汇编结合list命令定位crowbar.y中哪条规则匹配失败。5.3 构建最小可复现案例MWE用bison -v生成状态转移报告当语法歧义导致 parser 行为异常如if (a) if (b) x; else y;的悬空 else需分析 Bison 自动生成的状态机# 1. 生成详细报告crowbar.y 状态图 bison -v crowbar.y # 生成 crowbar.output 文件 # 2. 分析 crowbar.output关键段落 State 17: expression: expression . expression (rule 5) expression: expression . - expression (rule 6) shift, and go to state 20 - shift, and go to state 21 [reduce using rule 5 (expression)] - [reduce using rule 6 (expression)] # 3. 识别冲突State 17 中 既可 shift移进又可 reduce规约→ 移进-规约冲突解决方案在crowbar.y顶部添加优先级声明%left - %left * /此声明告诉 Bison当冲突发生时对和-使用左结合并优先 shift解决悬空 else。从那以后我每次遇到syntax error都强制走一遍bison -vgdb断点三连先看crowbar.output确认是否有冲突再用gdb在yyparse()中单步观察 token 流最后检查crowbar.l的正则是否意外吞掉了关键字符如.匹配了不该匹配的符号。这套组合拳让我在三天内 debug 通了 Diksam 的嵌套函数调用希望帮到你。本文还有配套的精品资源点击获取