简介面向编译原理课程的全套实验资料围绕中国海洋大学实验一至实验八覆盖词法分析、语法分析、语义分析、代码生成与优化等核心阶段适合计算机专业学生及自学者。包内共248个文件压缩包446.47MB包括12个c、7个h编译器源码6个y和4个l的lex/yacc定义7个docx及5个doc实验报告另有txt笔记、makefile脚本、可执行exe及大量xz/zst/bz2/zip工具链。已有491人浏览学习。实验从记号拆分、抽象语法树到递归下降解析器、类型系统与中间代码优化再到实验八综合编译器项目形成完整链条预览中的lex.yy.c、cal.tab.c等关键源码体现典型实现配套文档与模板便于快速上手可作为课程设计或实验报告的参考。1. 这套实验到底在做什么——课程脉络与整体思路编译原理这门课很多人一听就觉得是“四大名补”之首仿佛只有大佬才能驾驭。但真当你把实验一到八完整走下来会发现它其实是一条非常清晰的线索从字符流到Token流从Token流到语法树从语法树到中间表示最后落到目标代码。没有哪一步是凭空出现的每一步都是在给下一步铺路。这套实验的经典之处就在于它完全覆盖了前端核心流程。实验一通常是词法分析要求你手写一个扫描器把源代码拆成Token实验二往往是语法分析用递归下降或LR方法建立语法树实验三和四开始进入语义分析涉及符号表、作用域和类型检查实验五到六是中间代码生成通常以四元式或逆波兰形式输出实验七和八则进入代码生成与优化虽然不同学校的划分略有差异但整体脉络基本一致。说白了这套实验就是让你亲手实现一个“小号编译器”。不需要你造出GCC或LLVM级别的产物但你必须理解编译器在拿到一段代码后究竟是怎么一步一步把它变成可执行形式的。很多人在做实验一的时候觉得简单写个状态机就完事了做到实验四开始崩溃符号表管理、作用域嵌套、类型推导全部涌上来再往后到中间代码生成又开始头疼怎么处理控制流和控制栈上变量的生命周期。我的建议是做这套实验千万别当成八个独立的小作业去应付而应该当成一个连续的工程项目。实验一的Token设计会影响实验二语法分析器的写法实验二的AST节点结构会直接影响实验三语义检查的复杂度实验三的符号表实现更是实验四类型检查的根基。很多同学的痛苦根源就是每个实验都从零开始结果前面的设计缺陷在后面全部爆雷。以我个人的实操经验来说这套实验最合理的整体设计路线是语言子集选小一点比如支持整型、浮点、布尔、if/else、while、函数声明和调用但每个阶段的实现要完整宁可功能少也不要东拼西凑。选一个足够小的子集才能让你有时间把每个阶段做扎实。2. 核心实验拆解从词法到语法再到语义2.1 词法分析手写状态机还是用Flex实验一通常是最“轻松”的因为需求非常明确输入一段源代码字符串输出Token序列。比如输入int a 10 20;你要识别出int是关键字、a是标识符、是赋值运算符、10和20是整型字面量、是加法运算符、分号是语句结束符。手写状态机是最常见的做法。核心逻辑就是维护一个“当前状态”然后逐个字符读入根据当前状态和读入字符决定状态转移。比如识别数字时状态可能依次经过“开始数字”“数字中”“小数点后”等状态。写状态机最关键的一点是**前瞻字符lookahead**的处理也就是当你发现当前字符不属于这个Token时得把它“吐回去”作为下一个Token的开头。很多同学在这里踩坑经常出现漏字符或重复读字符的问题。用Flex生成器也可以但我的建议是第一遍先手写一遍哪怕写得粗粝一些也要自己过一遍。原因很简单手写能让你真正理解“最长匹配”和“最大吞食原则”——编译器在扫描的时候永远尽可能多地匹配字符比如a只会被识别成标识符a和自增运算符绝不会拆成a、、。另外实验二甚至更后面的实验你大概率还是要手写语法分析器到时候你的语义动作可能要和手写词法器紧密配合。2.2 语法分析递归下降与LR的取舍语法分析是整个编译原理的“分水岭”。实验二和实验三往往就是卡住最多人的地方。递归下降分析是最符合人类直觉的方法为每个非终结符写一个函数函数内部根据下一个Token的类型决定走哪条产生式。好处是代码直观、调试容易、报错信息好控制坏处是文法必须满足LL(1)条件也就是不能有左递归且FIRST集不能有冲突。我在做实验二的时候踩过一个经典坑表达式文法没消除左递归。比如expr - expr term这种写法如果直接翻译成代码就是死循环因为expr()函数第一步就会调用自己。正确做法是把文法改写成右递归形式expr - term expr_tail expr_tail - term expr_tail | ε term - factor term_tail term_tail - * factor term_tail | ε factor - ( expr ) | NUMBER代码实现上就是每个非终结符对应一个函数每个函数里根据当前Token决定走哪条分支遇到终结符就匹配并消费Token遇到非终结符就调用对应函数。整个过程非常像“猜谜”你根据当前看到的一个符号决定后续整个句子的走向。LR分析方法比如用Yacc或Bison更适合处理复杂的算子优先级和结合性但调试起来比较痛苦一个state冲突的报错信息可能要查很久才能找到原因。我的建议是如果你是刚开始做整套实验优先选递归下降因为它能让你在后续语义分析阶段更容易维护。这里补充一个关键细节在递归下降里处理运算符优先级不用像文法书里那样把所有层次都写出来可以直接在expr_tail里维护一个precedence变量做运算符优先级比较用“Pratt Parser”的思路实现。这种方式的代码量更少而且后续扩展一元运算、比较运算、逻辑运算都非常方便。2.3 语义分析与符号表你未来的第二个女朋友实验三到实验四基本就是符号表大展身手的阶段。符号表要管的事情很杂每个标识符的类型是什么、作用域从哪开始到哪结束、同名变量在不同作用域里怎么区分、函数参数的类型列表是什么。常见的实现方式是用“作用域链”结构一个栈每进入一个作用域就压入一层表哈希表退出作用域时弹出。查找标识符时从栈顶往下逐层找保证内层能“看见”外层但外层看不到内层。这个模型理解起来不复杂但实现中有很多细节。我在符号表上做过最值得说的一件事是用value字段同时存类型和运行时值。实验一里词法分析返回的Token就带有一个literal字段语法分析时这个字面量会被塞进AST的叶子节点而在语义分析阶段符号表会把变量名映射到类型和值信息。这样后面做中间代码生成时需要的所有信息都已经就位了。还有一个很多人忽略的点类型检查的错误恢复。如果检测到int x hello;这种类型不匹配你不能直接报错然后终止编译而应该打印错误信息后把x的类型设成目标类型比如int这样后续代码还能继续编译下去一次运行能暴露更多错误。这在做实验四的时候能帮你省很多事——你不用每次修完一个错误重新跑一遍全流程。2.4 中间代码生成与目标代码生成实验五到六核心是生成中间表示。很多课程会要求生成四元式或三元式格式类似result arg1 op arg2。这一段实验的关键是临时变量管理。比如表达式a b * c乘法优先级更高需要先生成临时变量存乘积再做加法t1 b * c t2 a t1如果你用递归下降的方式做语法分析生成中间代码可以完全镶嵌在语法分析过程中每解析完一个子表达式就生成对应的四元式并返回一个“结果变量名”可能是一个字符串如t1或是一个数字ID如%3。这样生成的代码是对应的后序遍历顺序天然满足运算优先级。实验七到八进入代码生成常见目标形态是栈式虚拟机指令集。这种指令集的好处是执行模型非常简单每个指令在栈上弹出操作数、计算、压回结果。比如a b可能翻译成PUSH a; PUSH b; ADD; STORE c。我在做实验七的时候发现只要中间表示生成得够规范翻译成栈式指令几乎就是机械翻译每个四元式对应一到三条指令。很多人做到这里会感叹“原来编译原理学的那些理论真的能拼出一个能跑的程序来。”这话不假。但前提是你前面几步没有把数据结构设计歪。3. 实操过程与关键细节一个算术表达式的完整旅程3.1 从源码到Token词法规则的写法拿一个最简单的例子来做全套流程展示输入int a 10 20;。第一步词法分析规则概括成一张表Token类型匹配模式示例KEYWORDint、float、if、while、returnintIDENTIFIER字母或下划线开头后续字母数字下划线aNUMBER数字序列可选小数点10、20OPERATOR、-、*、/、、、!、、SEPARATOR;、,、(、)、{、};手写扫描的时候我习惯用一个全局的cursor指针或索引指向当前读到的位置。每轮循环先跳过空白字符然后根据当前字符类型进入不同分支。识别数字的分支是只要后续还是数字或小数点就继续吞并。识别标识符的分支则是先判断是否命中关键字命中就返回KEYWORD类型否则返回IDENTIFIER。这里要特别留意一个细节关键字和标识符的区分。int在语言里是关键字但intx却是合法标识符。你必须在识别完整个单词之后再查表不能读到i就以为遇到关键字。我先做完整单词识别再查关键字表这样就完全没问题。3.2 递归下降解析从Token列表到AST拿到Token序列后进入语法分析。以上面的Token为例语法分析的预期结果是一棵这样的ASTVariableDecl ├── type: int ├── name: a └── init: BinaryOp ├── op: ├── left: Literal(10) └── right: Literal(20)递归下降的代码长这样// expr - term (( | -) term)* ASTNode* expr() { ASTNode* node term(); while (current_token.type TOK_PLUS || current_token.type TOK_MINUS) { Token op current_token; advance(); ASTNode* right term(); node create_binary_op(op, node, right); } return node; }注意这个循环写法就是最典型的“EBNF消除左递归”后的代码形态。它表达的意思是expr是先解析一个term然后只要看到或-就继续解析下一个term并组装成左结合left-associative的二叉树。这里还需要处理一个问题如果用传统的“优先级递降法”每个优先级的函数内部都要写这种while循环。如果表达式再包含比较运算符、逻辑运算符就会多出好几层函数嵌套。我建议用“Pratt解析器”的思路简化给每个运算符设置left_binding_power左绑定力然后循环比较下一个运算符的绑定力。这样做代码量会明显减少后续添加新的二元运算符只需要一行配置而不是再套一层函数。3.3 语义检查与四元式生成AST构建完成之后进入语义检查阶段。遍历AST对每个节点检查二元运算的两个操作数类型是否兼容。整数加减法没问题浮点和整型混合时如果要严格模式就报错宽松模式就进行隐式转换。变量是否声明过。如果在符号表里找不到某个标识符报“未声明变量”。分支条件是否为布尔类型。if语句的条件必须是布尔值如果是if (a)而a是整型有些语言允许非零即真有些语言直接报类型错误。类型检查通过后生成四元式。对于表达式节点输出格式如下语句编号 | 结果变量 | 左操作数 | 运算符 | 右操作数 1 | t1 | 10 | | 20然后添加赋值指令2 | a | t1 | : | (空)四元式可以用一个结构体数组存储每个字段是字符串或空指针符号表里的变量可能直接映射成“栈索引”或“内存地址”这样后续代码生成会简单很多。3.4 目标代码生成栈式虚拟机的指令四元式转栈式指令每一行对照翻译即可四元式栈式指令t1 b * cPUSH b; PUSH c; MUL; POP t1t2 a t1PUSH a; PUSH t1; ADD; POP t2a t2PUSH t2; POP a但要留意真正的编译器不会真的把每个临时变量都存回内存再取出来那样会浪费大量内存和指令。实做时可以偷个懒只要临时变量只被使用一次就让它一直待在栈上不执行POP和PUSH直接用栈顶数据参与运算。我第一次做代码生成时没做这种优化生成的指令数量多了将近一倍后面加上“临时变量引计数”机制后才优化下来。做完这一步一个简单程序就能完整跑通源码输入 - Token序列 - AST - 类型检查 - 四元式 - 栈式指令 - 在虚拟机上执行。我第一次把整个流程跑通时输出结果和手算一致那种成就感是其他课程给不了的。4. 常见问题与排查技巧实录4.1 语法分析死循环左递归还没消除症状程序运行后卡死或者用不了几步就栈溢出。原因文法里存在左递归比如expr - expr term这种产生式被直接翻译成函数调用导致无限递归。排查方法先检查产生式看是否存在“某个非终结符的第一个符号就是它自己”的情况。把文法改写为右递归或EBNF循环形式代码里用while循环代替函数递归。4.2 符号表作用域错乱变量越权访问症状另一个作用域的变量被错误地解析到了或者声明在函数里的变量被函数外访问。原因符号表作用域链没有正确“压栈”和“弹栈”。进入函数体时忘了压入一层新作用域退出时忘了弹出。排查方法在每次进入复合语句块花括号内时明确执行scope_enter()离开时执行scope_exit()。可以在调试模式下打印当前作用域栈的深度对照代码的缩进层次检查是否匹配。4.3 Token丢失或重复前瞻字符没处理好症状词法分析结果少了一个Token或者多出了一个意想不到的Token。原因读取到一个Token结束字符时直接把它消费掉了没有作为下一个Token的起始字符。排查方法写一个统一的next_char()和peek_char()接口。peek_char()不移动索引next_char()才移动。状态机里判断“当前Token结束”之后先peek_char()确认下一个字符属于后续Token再通过unread逻辑回退或者直接把索引指向上一个字符的位置。4.4 类型检查误报布尔和整型的经典混淆症状if (1)被报类型错误但你的语言设计允许非零即真或者while (x)中的x是整型却被要求必须是布尔型。原因语义分析阶段把条件表达式的类型检查写得太严格。排查方法先确认你的语言规格。如果你参考的语言是C那if (1)合法编译器只需要检查条件表达式类型是算术类型即可如果你的语言是严格类型语言类似Java或Rust那么必须要求布尔类型。实验文档通常会写明允许哪些隐式转换照着文档做就不会错。4.5 中间代码顺序错乱控制流语句的标签管理混乱症状if语句的两个分支会同时执行或while循环只执行一次。原因跳转指令的目标标签生成不唯一或者条件跳转的方向反了。常见于多个if语句嵌套时标签名重复。排查方法用全局计数器生成标签每生产一个新标签就label_id。条件跳转指令要仔细检查语义JMP_IF_FALSE L1表示条件为假时跳转到L1JMP_IF_TRUE L1表示条件为真时跳转。调试时可以把生成的指令和标签打印出来人工模拟执行一两条路径对照预期看跳转是否对得上。5. 从实验一到八我的工程经验沉淀整套实验做完收获最大的不是“我知道编译器怎么回事了”而是“我知道一个规模不大的编译系统应该怎么组织它的代码”。说实话这套实验锻炼的设计能力比算法能力更多。比如你要决定AST节点结构用统一结构体一个类型字段加一个union还是每个节点类型单独定义结构体、用继承或组合方式管理你要决定符号表是集中式全局管理还是分布在各节点中你要决定中间表示用数组还是链表存储。这些设计决策没有绝对的对错但每个选择都会在下个阶段的代码量上给你反馈。再分享一个实用技巧每个实验开始前先用一晚上把所有阶段的接口定义好。比如预先定义好Token结构、ASTNode结构、Symbol结构、Quadruple结构并约定它们的创建和销毁函数。这样你做实验一的时候已经把实验三要用的数据结构模板搭好了。后面每个实验只是往既定骨架里填充逻辑就不会返工。只要你愿意静下心来按“词法 - 语法 - 语义 - 中间代码 - 代码生成”这条主线走一遍并在每个阶段留下干净的接口和足够的调试输出到实验五之后你会觉得越来越顺甚至开始想给自己的小语言加加法器、字符串、数组这些扩展功能。这其实就是编译原理实验想带给你最核心的东西把一个看似玄乎的“魔法”拆成一个一个可以落地、可以调试、可以扩展的工程问题。本文还有配套的精品资源点击获取 手写一个迷你编译器：编译原理实验从词法到代码生成详解
简介面向编译原理课程的全套实验资料围绕中国海洋大学实验一至实验八覆盖词法分析、语法分析、语义分析、代码生成与优化等核心阶段适合计算机专业学生及自学者。包内共248个文件压缩包446.47MB包括12个c、7个h编译器源码6个y和4个l的lex/yacc定义7个docx及5个doc实验报告另有txt笔记、makefile脚本、可执行exe及大量xz/zst/bz2/zip工具链。已有491人浏览学习。实验从记号拆分、抽象语法树到递归下降解析器、类型系统与中间代码优化再到实验八综合编译器项目形成完整链条预览中的lex.yy.c、cal.tab.c等关键源码体现典型实现配套文档与模板便于快速上手可作为课程设计或实验报告的参考。1. 这套实验到底在做什么——课程脉络与整体思路编译原理这门课很多人一听就觉得是“四大名补”之首仿佛只有大佬才能驾驭。但真当你把实验一到八完整走下来会发现它其实是一条非常清晰的线索从字符流到Token流从Token流到语法树从语法树到中间表示最后落到目标代码。没有哪一步是凭空出现的每一步都是在给下一步铺路。这套实验的经典之处就在于它完全覆盖了前端核心流程。实验一通常是词法分析要求你手写一个扫描器把源代码拆成Token实验二往往是语法分析用递归下降或LR方法建立语法树实验三和四开始进入语义分析涉及符号表、作用域和类型检查实验五到六是中间代码生成通常以四元式或逆波兰形式输出实验七和八则进入代码生成与优化虽然不同学校的划分略有差异但整体脉络基本一致。说白了这套实验就是让你亲手实现一个“小号编译器”。不需要你造出GCC或LLVM级别的产物但你必须理解编译器在拿到一段代码后究竟是怎么一步一步把它变成可执行形式的。很多人在做实验一的时候觉得简单写个状态机就完事了做到实验四开始崩溃符号表管理、作用域嵌套、类型推导全部涌上来再往后到中间代码生成又开始头疼怎么处理控制流和控制栈上变量的生命周期。我的建议是做这套实验千万别当成八个独立的小作业去应付而应该当成一个连续的工程项目。实验一的Token设计会影响实验二语法分析器的写法实验二的AST节点结构会直接影响实验三语义检查的复杂度实验三的符号表实现更是实验四类型检查的根基。很多同学的痛苦根源就是每个实验都从零开始结果前面的设计缺陷在后面全部爆雷。以我个人的实操经验来说这套实验最合理的整体设计路线是语言子集选小一点比如支持整型、浮点、布尔、if/else、while、函数声明和调用但每个阶段的实现要完整宁可功能少也不要东拼西凑。选一个足够小的子集才能让你有时间把每个阶段做扎实。2. 核心实验拆解从词法到语法再到语义2.1 词法分析手写状态机还是用Flex实验一通常是最“轻松”的因为需求非常明确输入一段源代码字符串输出Token序列。比如输入int a 10 20;你要识别出int是关键字、a是标识符、是赋值运算符、10和20是整型字面量、是加法运算符、分号是语句结束符。手写状态机是最常见的做法。核心逻辑就是维护一个“当前状态”然后逐个字符读入根据当前状态和读入字符决定状态转移。比如识别数字时状态可能依次经过“开始数字”“数字中”“小数点后”等状态。写状态机最关键的一点是**前瞻字符lookahead**的处理也就是当你发现当前字符不属于这个Token时得把它“吐回去”作为下一个Token的开头。很多同学在这里踩坑经常出现漏字符或重复读字符的问题。用Flex生成器也可以但我的建议是第一遍先手写一遍哪怕写得粗粝一些也要自己过一遍。原因很简单手写能让你真正理解“最长匹配”和“最大吞食原则”——编译器在扫描的时候永远尽可能多地匹配字符比如a只会被识别成标识符a和自增运算符绝不会拆成a、、。另外实验二甚至更后面的实验你大概率还是要手写语法分析器到时候你的语义动作可能要和手写词法器紧密配合。2.2 语法分析递归下降与LR的取舍语法分析是整个编译原理的“分水岭”。实验二和实验三往往就是卡住最多人的地方。递归下降分析是最符合人类直觉的方法为每个非终结符写一个函数函数内部根据下一个Token的类型决定走哪条产生式。好处是代码直观、调试容易、报错信息好控制坏处是文法必须满足LL(1)条件也就是不能有左递归且FIRST集不能有冲突。我在做实验二的时候踩过一个经典坑表达式文法没消除左递归。比如expr - expr term这种写法如果直接翻译成代码就是死循环因为expr()函数第一步就会调用自己。正确做法是把文法改写成右递归形式expr - term expr_tail expr_tail - term expr_tail | ε term - factor term_tail term_tail - * factor term_tail | ε factor - ( expr ) | NUMBER代码实现上就是每个非终结符对应一个函数每个函数里根据当前Token决定走哪条分支遇到终结符就匹配并消费Token遇到非终结符就调用对应函数。整个过程非常像“猜谜”你根据当前看到的一个符号决定后续整个句子的走向。LR分析方法比如用Yacc或Bison更适合处理复杂的算子优先级和结合性但调试起来比较痛苦一个state冲突的报错信息可能要查很久才能找到原因。我的建议是如果你是刚开始做整套实验优先选递归下降因为它能让你在后续语义分析阶段更容易维护。这里补充一个关键细节在递归下降里处理运算符优先级不用像文法书里那样把所有层次都写出来可以直接在expr_tail里维护一个precedence变量做运算符优先级比较用“Pratt Parser”的思路实现。这种方式的代码量更少而且后续扩展一元运算、比较运算、逻辑运算都非常方便。2.3 语义分析与符号表你未来的第二个女朋友实验三到实验四基本就是符号表大展身手的阶段。符号表要管的事情很杂每个标识符的类型是什么、作用域从哪开始到哪结束、同名变量在不同作用域里怎么区分、函数参数的类型列表是什么。常见的实现方式是用“作用域链”结构一个栈每进入一个作用域就压入一层表哈希表退出作用域时弹出。查找标识符时从栈顶往下逐层找保证内层能“看见”外层但外层看不到内层。这个模型理解起来不复杂但实现中有很多细节。我在符号表上做过最值得说的一件事是用value字段同时存类型和运行时值。实验一里词法分析返回的Token就带有一个literal字段语法分析时这个字面量会被塞进AST的叶子节点而在语义分析阶段符号表会把变量名映射到类型和值信息。这样后面做中间代码生成时需要的所有信息都已经就位了。还有一个很多人忽略的点类型检查的错误恢复。如果检测到int x hello;这种类型不匹配你不能直接报错然后终止编译而应该打印错误信息后把x的类型设成目标类型比如int这样后续代码还能继续编译下去一次运行能暴露更多错误。这在做实验四的时候能帮你省很多事——你不用每次修完一个错误重新跑一遍全流程。2.4 中间代码生成与目标代码生成实验五到六核心是生成中间表示。很多课程会要求生成四元式或三元式格式类似result arg1 op arg2。这一段实验的关键是临时变量管理。比如表达式a b * c乘法优先级更高需要先生成临时变量存乘积再做加法t1 b * c t2 a t1如果你用递归下降的方式做语法分析生成中间代码可以完全镶嵌在语法分析过程中每解析完一个子表达式就生成对应的四元式并返回一个“结果变量名”可能是一个字符串如t1或是一个数字ID如%3。这样生成的代码是对应的后序遍历顺序天然满足运算优先级。实验七到八进入代码生成常见目标形态是栈式虚拟机指令集。这种指令集的好处是执行模型非常简单每个指令在栈上弹出操作数、计算、压回结果。比如a b可能翻译成PUSH a; PUSH b; ADD; STORE c。我在做实验七的时候发现只要中间表示生成得够规范翻译成栈式指令几乎就是机械翻译每个四元式对应一到三条指令。很多人做到这里会感叹“原来编译原理学的那些理论真的能拼出一个能跑的程序来。”这话不假。但前提是你前面几步没有把数据结构设计歪。3. 实操过程与关键细节一个算术表达式的完整旅程3.1 从源码到Token词法规则的写法拿一个最简单的例子来做全套流程展示输入int a 10 20;。第一步词法分析规则概括成一张表Token类型匹配模式示例KEYWORDint、float、if、while、returnintIDENTIFIER字母或下划线开头后续字母数字下划线aNUMBER数字序列可选小数点10、20OPERATOR、-、*、/、、、!、、SEPARATOR;、,、(、)、{、};手写扫描的时候我习惯用一个全局的cursor指针或索引指向当前读到的位置。每轮循环先跳过空白字符然后根据当前字符类型进入不同分支。识别数字的分支是只要后续还是数字或小数点就继续吞并。识别标识符的分支则是先判断是否命中关键字命中就返回KEYWORD类型否则返回IDENTIFIER。这里要特别留意一个细节关键字和标识符的区分。int在语言里是关键字但intx却是合法标识符。你必须在识别完整个单词之后再查表不能读到i就以为遇到关键字。我先做完整单词识别再查关键字表这样就完全没问题。3.2 递归下降解析从Token列表到AST拿到Token序列后进入语法分析。以上面的Token为例语法分析的预期结果是一棵这样的ASTVariableDecl ├── type: int ├── name: a └── init: BinaryOp ├── op: ├── left: Literal(10) └── right: Literal(20)递归下降的代码长这样// expr - term (( | -) term)* ASTNode* expr() { ASTNode* node term(); while (current_token.type TOK_PLUS || current_token.type TOK_MINUS) { Token op current_token; advance(); ASTNode* right term(); node create_binary_op(op, node, right); } return node; }注意这个循环写法就是最典型的“EBNF消除左递归”后的代码形态。它表达的意思是expr是先解析一个term然后只要看到或-就继续解析下一个term并组装成左结合left-associative的二叉树。这里还需要处理一个问题如果用传统的“优先级递降法”每个优先级的函数内部都要写这种while循环。如果表达式再包含比较运算符、逻辑运算符就会多出好几层函数嵌套。我建议用“Pratt解析器”的思路简化给每个运算符设置left_binding_power左绑定力然后循环比较下一个运算符的绑定力。这样做代码量会明显减少后续添加新的二元运算符只需要一行配置而不是再套一层函数。3.3 语义检查与四元式生成AST构建完成之后进入语义检查阶段。遍历AST对每个节点检查二元运算的两个操作数类型是否兼容。整数加减法没问题浮点和整型混合时如果要严格模式就报错宽松模式就进行隐式转换。变量是否声明过。如果在符号表里找不到某个标识符报“未声明变量”。分支条件是否为布尔类型。if语句的条件必须是布尔值如果是if (a)而a是整型有些语言允许非零即真有些语言直接报类型错误。类型检查通过后生成四元式。对于表达式节点输出格式如下语句编号 | 结果变量 | 左操作数 | 运算符 | 右操作数 1 | t1 | 10 | | 20然后添加赋值指令2 | a | t1 | : | (空)四元式可以用一个结构体数组存储每个字段是字符串或空指针符号表里的变量可能直接映射成“栈索引”或“内存地址”这样后续代码生成会简单很多。3.4 目标代码生成栈式虚拟机的指令四元式转栈式指令每一行对照翻译即可四元式栈式指令t1 b * cPUSH b; PUSH c; MUL; POP t1t2 a t1PUSH a; PUSH t1; ADD; POP t2a t2PUSH t2; POP a但要留意真正的编译器不会真的把每个临时变量都存回内存再取出来那样会浪费大量内存和指令。实做时可以偷个懒只要临时变量只被使用一次就让它一直待在栈上不执行POP和PUSH直接用栈顶数据参与运算。我第一次做代码生成时没做这种优化生成的指令数量多了将近一倍后面加上“临时变量引计数”机制后才优化下来。做完这一步一个简单程序就能完整跑通源码输入 - Token序列 - AST - 类型检查 - 四元式 - 栈式指令 - 在虚拟机上执行。我第一次把整个流程跑通时输出结果和手算一致那种成就感是其他课程给不了的。4. 常见问题与排查技巧实录4.1 语法分析死循环左递归还没消除症状程序运行后卡死或者用不了几步就栈溢出。原因文法里存在左递归比如expr - expr term这种产生式被直接翻译成函数调用导致无限递归。排查方法先检查产生式看是否存在“某个非终结符的第一个符号就是它自己”的情况。把文法改写为右递归或EBNF循环形式代码里用while循环代替函数递归。4.2 符号表作用域错乱变量越权访问症状另一个作用域的变量被错误地解析到了或者声明在函数里的变量被函数外访问。原因符号表作用域链没有正确“压栈”和“弹栈”。进入函数体时忘了压入一层新作用域退出时忘了弹出。排查方法在每次进入复合语句块花括号内时明确执行scope_enter()离开时执行scope_exit()。可以在调试模式下打印当前作用域栈的深度对照代码的缩进层次检查是否匹配。4.3 Token丢失或重复前瞻字符没处理好症状词法分析结果少了一个Token或者多出了一个意想不到的Token。原因读取到一个Token结束字符时直接把它消费掉了没有作为下一个Token的起始字符。排查方法写一个统一的next_char()和peek_char()接口。peek_char()不移动索引next_char()才移动。状态机里判断“当前Token结束”之后先peek_char()确认下一个字符属于后续Token再通过unread逻辑回退或者直接把索引指向上一个字符的位置。4.4 类型检查误报布尔和整型的经典混淆症状if (1)被报类型错误但你的语言设计允许非零即真或者while (x)中的x是整型却被要求必须是布尔型。原因语义分析阶段把条件表达式的类型检查写得太严格。排查方法先确认你的语言规格。如果你参考的语言是C那if (1)合法编译器只需要检查条件表达式类型是算术类型即可如果你的语言是严格类型语言类似Java或Rust那么必须要求布尔类型。实验文档通常会写明允许哪些隐式转换照着文档做就不会错。4.5 中间代码顺序错乱控制流语句的标签管理混乱症状if语句的两个分支会同时执行或while循环只执行一次。原因跳转指令的目标标签生成不唯一或者条件跳转的方向反了。常见于多个if语句嵌套时标签名重复。排查方法用全局计数器生成标签每生产一个新标签就label_id。条件跳转指令要仔细检查语义JMP_IF_FALSE L1表示条件为假时跳转到L1JMP_IF_TRUE L1表示条件为真时跳转。调试时可以把生成的指令和标签打印出来人工模拟执行一两条路径对照预期看跳转是否对得上。5. 从实验一到八我的工程经验沉淀整套实验做完收获最大的不是“我知道编译器怎么回事了”而是“我知道一个规模不大的编译系统应该怎么组织它的代码”。说实话这套实验锻炼的设计能力比算法能力更多。比如你要决定AST节点结构用统一结构体一个类型字段加一个union还是每个节点类型单独定义结构体、用继承或组合方式管理你要决定符号表是集中式全局管理还是分布在各节点中你要决定中间表示用数组还是链表存储。这些设计决策没有绝对的对错但每个选择都会在下个阶段的代码量上给你反馈。再分享一个实用技巧每个实验开始前先用一晚上把所有阶段的接口定义好。比如预先定义好Token结构、ASTNode结构、Symbol结构、Quadruple结构并约定它们的创建和销毁函数。这样你做实验一的时候已经把实验三要用的数据结构模板搭好了。后面每个实验只是往既定骨架里填充逻辑就不会返工。只要你愿意静下心来按“词法 - 语法 - 语义 - 中间代码 - 代码生成”这条主线走一遍并在每个阶段留下干净的接口和足够的调试输出到实验五之后你会觉得越来越顺甚至开始想给自己的小语言加加法器、字符串、数组这些扩展功能。这其实就是编译原理实验想带给你最核心的东西把一个看似玄乎的“魔法”拆成一个一个可以落地、可以调试、可以扩展的工程问题。本文还有配套的精品资源点击获取