简介本资源是山东大学《编译原理与技术》课程新版实验一至三的完整实现代码包面向计算机专业本科生及编译器开发初学者聚焦编译器前端核心能力训练——词法分析与语法分析的工程落地。压缩包共15个文件8个.h头文件定义数据结构与接口、5个.cpp实现Lexer/Parser核心逻辑、1个build.sh提供一键编译脚本、1个README.md含使用说明总大小仅30KB轻量易读便于理解模块划分与调用关系。已有57人学习下载适合课堂实验跟进、课程设计参考或自主复现编译前端。读者可直接运行并调试完整的词法识别流程基于有限自动机、递归下降语法分析器、AST节点生成与遍历逻辑并通过预置的测试用例验证错误处理与语法树构造正确性目录结构清晰体现lexer→parser→util→objectGen分层设计为后续语义分析与中间代码生成打下坚实基础。1. 项目概述从“纸上谈兵”到“动手造轮子”的蜕变编译原理这门让无数计算机专业学生又爱又恨的“硬核”课程终于迎来了它的实践篇章。当你在课堂上听完了词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成这一整套理论流程后是不是感觉脑袋里装满了各种自动机、文法、属性文法但一合上书又觉得它们像空中楼阁不知从何下手这正是传统教学的一个痛点理论深厚实践薄弱。山东大学新版编译原理与技术课程的实验一至三正是为了打通这条“任督二脉”而设计的。它不再满足于让你用现成的工具比如Lex和Yacc跑几个示例而是要求你从零开始亲手实现一个简化版编译器或解释器的核心模块。这系列实验的核心价值在于“造轮子”。你可能听说过“不要重复造轮子”的工程哲学但在学习编译原理的初期“造轮子”是最好的学习方式。只有当你亲手实现了一个正则表达式引擎去匹配标识符和数字亲手写了一个递归下降或LR分析器去解析四则运算表达式亲手构建了一张符号表来管理变量作用域你才能真正理解理论课上那些抽象概念的精妙与权衡。实验一通常聚焦于编译器前端的基础——词法分析器Scanner/Lexer和语法分析器Parser实验二则会深入到语义分析的腹地构建符号表Symbol Table并进行类型检查实验三则可能挑战中间代码生成比如生成抽象语法树AST或一种简单的三地址码。整个过程就像在代码的世界里从读懂一门语言的字母和单词词法分析到理解它的句子结构语法分析再到把握句子的真实含义和上下文语义分析最终尝试用另一种方式复述这个句子中间代码生成。这套实验适合所有正在学习编译原理、渴望深入理解程序如何从文本变成可执行指令的同学。无论你未来的方向是从事底层系统开发、虚拟机与语言运行时研发还是想深入理解各种前端框架的编译打包过程这里的实践经验都将是一笔宝贵的财富。接下来我将以Java作为实现语言这也是当前高校和工业界结合紧密的主流选择带你逐一拆解这三个实验的核心要点、实现思路以及那些只有踩过坑才知道的“秘籍”。2. 实验一编译器前端的基石——词法与语法分析器实现实验一是整个编译之旅的起点目标是构建一个能“读懂”源代码文本的程序。这分为两个紧密相连的阶段词法分析和语法分析。2.1 词法分析器把字符流变成单词流词法分析器的任务很简单读入源代码字符串忽略空格、换行和注释将其切割成一个个具有独立意义的“单词”即词法单元Token。每个Token通常包含两部分信息类型Token Type和属性值Lexeme。例如对于代码int age 18;词法分析器应该输出KEYWORD, “int”ID, “age”OPERATOR, “”INTEGER, 18DELIMITER, “;”。实现策略与核心考量手动实现一个词法分析器主流方法是基于有限自动机DFA的理论。你不需要真的画出一个状态转换图再转化成代码而是可以直接用代码逻辑模拟这个状态机。一个典型的实现结构是一个循环逐个读取字符根据当前字符和状态决定下一步动作。核心实现步骤定义Token类型枚举这是第一步也是设计契约。你需要为你的“小语言”定义所有可能的单词类型如关键字IF, ELSE, INT, WHILE、标识符ID、整数常量INTEGER、浮点数常量FLOAT、运算符PLUS, MINUS, ASSIGN、界符SEMICOLON, LPAREN, RPAREN等。设计Token类这个类至少包含类型type和字面值lexeme两个字段。还可以附加行号、列号用于后续的错误定位。实现核心扫描循环这是词法分析器的引擎。维护一个指针或索引指向当前待处理的字符在循环中跳过空白字符空格、制表符、换行。判断当前字符的“开头”进入不同的处理分支如果是字母或下划线则进入“标识符/关键字”分支持续读取后续的字母、数字或下划线直到遇到非此类字符。将读取的字符串与关键字表比对决定是关键字Token还是标识符Token。如果是数字则进入“数字常量”分支。这里有个小坑要区分整数和小数。读取连续数字如果遇到小数点‘.’则进入小数部分读取。注意处理类似123.这种不规范的写法这属于词法错误。如果是运算符或界符如,-,,,;,(等。这里需要注意多字符运算符如,!,,。需要“向前多看一个字符”来判断。如果遇到引号则进入“字符串常量”分支需要一直读取到配对的结束引号并处理转义字符如\n,\t,\。处理注释单行注释//和多行注释/* ... */也需要在词法分析阶段被识别并跳过。当扫描到/时需要查看下一个字符是/、*还是其他以决定是进入注释跳过模式还是将其视为除法运算符。实操心得与避坑指南“向前看”字符的处理这是最容易出bug的地方。例如处理完一个Token后指针应该指向这个Token之后的下一个字符。但在识别多字符运算符如时你可能需要预读下一个字符来判断如果匹配失败这个“预读”的字符不能丢弃要留待下一轮处理。一个常见的技巧是使用Peek()方法它返回下一个字符但不移动指针。行号与列号的维护为了在语法或语义报错时能精确定位必须在词法分析阶段就记录每个Token所在的行号和开始列号。每次遇到换行符行号加一列号重置每读一个字符列号加一。错误恢复简单的词法分析器遇到无法识别的字符如,$如果你的语言不支持可以直接报错并终止。但更健壮的做法是记录错误跳过这个非法字符尝试继续分析后面的内容以便一次报告多个错误。性能小技巧关键字识别不要用一堆if-else或switch而是将扫描到的标识符字符串与一个预先构建的HashSetString关键字集合进行比对效率更高。2.2 语法分析器验证结构并构建语法树词法分析器给了我们一堆单词语法分析器则要判断这些单词按照某种规则文法排列起来是否构成一个合法的“句子”。对于a b c;词法分析器看到的是[ID(a), OPERATOR(), ID(b), OPERATOR(), ID(c), DELIMITER(;)]语法分析器则需要验证这是否符合“赋值语句”的语法结构。实现策略选型递归下降 vs. 自动化工具对于课程实验手写递归下降分析器是最佳选择。它直观易于理解和调试并且与后续的语义分析、中间代码生成可以无缝结合。虽然它要求文法必须是LL(1)的需要消除左递归和提取左公因子但这本身也是理解文法设计的重要练习。使用Yacc/Bison等自动化工具生成LALR分析器虽然强大但会隐藏太多细节不利于学习。递归下降分析器实现核心文法设计首先为你的“小语言”设计一个简洁但完整的文法。例如一个支持赋值、算术运算、if-else和while循环的语言。你需要将其改造成适合递归下降的LL(1)文法。Program - Statement* Statement - IfStmt | WhileStmt | AssignStmt | Block AssignStmt - ID Expr ; Expr - Term (( | -) Term)* Term - Factor ((* | /) Factor)* Factor - INTEGER | FLOAT | ID | ( Expr ) IfStmt - if ( Cond ) Statement (else Statement)? ...为每个非终结符编写一个解析函数这是递归下降的核心思想。函数parseExpr()负责解析表达式它内部会调用parseTerm()和parseFactor()。每个解析函数都根据当前Token的类型决定应用哪条产生式规则。匹配Match操作解析函数中当文法中需要一个特定的终结符如;,(时你需要检查当前Token是否与之匹配。如果匹配则消费consume这个Token调用词法分析器获取下一个Token如果不匹配则报告语法错误。构建抽象语法树AST语法分析器不仅要验证语法更重要的是产出一种结构化的表示即AST。每个解析函数在成功解析后都应该返回一个AST节点对象。例如parseExpr()可能返回一个BinaryOpNode二元操作节点包含操作符op、左子树left来自parseTerm()和右子树right来自另一个parseTerm()。实操心得与避坑指南错误处理与恢复递归下降中的错误处理比词法分析更复杂。简单的“遇到错误就停止”是不可接受的。常见的策略是“恐慌模式”恢复当在某个函数如parseStmt中遇到意外Token时可以跳过后续Token直到遇到一个“同步词法单元”如分号;、右大括号}等语句边界然后尝试继续解析下一条语句。这能让你在一次编译中发现多个语法错误。左递归的陷阱如果你写的递归下降解析器一运行就栈溢出十有八九是文法存在左递归如Expr - Expr Term导致parseExpr无限递归调用自己。必须将其转换为等价的右递归形式Expr - Term ExprExpr - Term Expr | ε。AST节点的设计AST是后续所有阶段的基础设计要清晰。为每种语法结构设计一个节点类通常形成一个继承体系。例如所有节点继承自ASTNode下有StatementNode和ExpressionNode。StatementNode又有IfStmtNode,AssignStmtNode等子类。每个节点类包含其特有的属性如IfStmtNode包含condition,thenBranch,elseBranch三个子节点。利用“窥探”简化代码在解析函数开头通过查看当前TokenpeekToken的类型可以决定走哪条分支这比“匹配-回溯”的模式要高效和清晰得多。例如在parseStmt函数中如果peekToken是IF则调用parseIfStmt如果是ID则可能是赋值语句调用parseAssignStmt。3. 实验二理解语义的桥梁——符号表与类型检查实验一让我们能识别出程序的结构AST但还不知道这个结构是否“有意义”。a b c;语法正确但如果变量b和c从未声明过或者一个是整数一个是字符串这个语句就是有语义错误的。实验二的任务就是赋予编译器“理解”程序含义的能力核心是构建符号表和进行类型检查。3.1 符号表程序的“户口本”符号表的核心作用是记录程序中所有标识符变量名、函数名、类型名等的“身份信息”并管理它们的作用域。你可以把它想象成一个分层的字典。设计与实现要点符号表项Symbol Entry每个标识符对应一个表项至少应包含名称name、类型type、种类kind如变量、函数、参数等、声明位置行号等。对于变量可能还需要存储其内存偏移量为后续代码生成准备对于函数则需要存储其参数列表和返回类型。作用域管理程序中的作用域是嵌套的如全局作用域、函数作用域、块作用域。符号表需要支持这种嵌套结构的“进入”和“退出”。最经典的实现方式是使用一个作用域栈。进入作用域当遇到函数定义或{时创建一个新的、空的符号表或哈希表并将其压入栈顶。这个新作用域继承可以访问外层作用域的符号。查找符号当需要查找一个标识符如变量x时从栈顶当前最内层作用域开始逐层向外查找直到找到或遍历完所有作用域。这模拟了编程语言中“就近原则”的变量遮蔽Shadowing效果。插入符号将新声明的标识符插入到栈顶的当前作用域符号表中。退出作用域当遇到函数结束或}时将栈顶的符号表弹出。这意味着该作用域内定义的所有局部变量都“失效”了。与AST遍历结合符号表的构建是在遍历AST的过程中完成的。通常需要两次遍历或一次带有副作用的遍历第一次遍历收集所有声明如变量声明、函数声明建立符号表第二次遍历则基于已建立的符号表进行引用检查和类型检查。实操心得与避坑指南区分声明与引用在AST遍历时遇到VarDecl节点声明和遇到ID节点引用时对符号表的操作完全不同。声明是向当前作用域插入新条目引用是在符号表中查找条目如果找不到则报“未定义”错误。处理函数重载如果你的语言支持函数重载那么符号表的查找逻辑会更复杂。函数名相同但参数类型不同被视为不同的符号。在插入时需要检查是否与同一作用域内同名的其他函数构成合法的重载参数列表不同在查找时需要根据调用处的实参类型来匹配最合适的函数。类型作为符号在一些语言中自定义类型如struct、class的名字本身也是一个符号需要被记录在符号表中。这通常放在一个全局的、独立的作用域中管理。循环引用与前向声明对于函数或类型的相互引用可能需要支持前向声明。即在符号表中先插入一个“不完整”的符号条目待其完全定义后再补充信息。3.2 类型检查确保运算的合法性类型检查是语义分析的重头戏它确保程序中的每一个操作赋值、算术运算、函数调用等都是类型安全的。其核心是一个递归遍历AST并推断/验证节点类型的过程。实现策略为AST节点添加type属性在遍历过程中为每个表达式节点计算并标注其类型。例如一个整数常量节点的类型是int一个二元加法节点的类型需要根据其左右子表达式的类型来决定。实现类型系统首先定义你的语言支持哪些基本类型int,float,bool,string等以及如何构成复合类型如数组、结构体。需要实现类型等价性判断、类型兼容性隐式转换规则。编写类型检查访问者为每种AST节点编写类型检查逻辑。这是一个典型的“访问者模式”应用场景。字面量节点直接返回其对应的内置类型。标识符节点从符号表中查找该标识符的定义获取其声明的类型。二元运算符节点首先递归检查左右子表达式的类型然后根据运算符判断类型是否合法。例如对于运算符左右类型通常需要都是数值型int或float并且结果类型可能是两者中“更宽”的类型如int float - float。如果类型不匹配则报告类型错误。赋值节点检查左值必须是变量或可赋值的表达式的类型与右值表达式的类型是否兼容允许隐式转换或严格相等。函数调用节点从符号表查找函数名获取其声明的参数类型列表和返回类型。然后检查实参表达式的类型与形参类型是否一一匹配。最后该调用表达式节点的类型就是函数的返回类型。类型推导对于支持var关键字或类似功能的语言还需要实现类型推导。即根据变量初始化表达式的结果类型来确定变量的声明类型。实操心得与避坑指南错误信息的友好性类型错误信息应该尽可能明确。不要只说“类型不匹配”而要说“在第X行无法将类型float赋值给类型int”或“函数foo期望第2个参数为string但传入的是int”。处理隐式类型转换这是类型检查中最繁琐的部分之一。你需要明确定义哪些转换是允许的如int到float哪些是禁止的如bool到string。在检查赋值或运算时如果类型不完全相同但允许转换可以插入一个隐式的“类型转换节点”到AST中或者记录下需要进行的转换为后续的中间代码生成做准备。左值检查赋值语句的左边必须是一个“左值”可以接受赋值的表达式通常只能是变量、数组元素、结构体成员等。像(ab) 5这样的表达式应该在类型检查阶段被捕获为错误。短路求值与类型检查对于逻辑与和或||运算符需要确保其操作数是布尔类型。同时由于它们支持短路求值这可能会影响控制流但类型检查阶段通常只关心类型短路求值的逻辑留到代码生成或解释执行阶段。4. 实验三从抽象到具体——中间代码生成经过前两个实验我们得到了一个带有类型信息的、语义正确的AST。实验三的目标是将这颗高度抽象、与机器无关的树转换成一个更接近底层、但依然与具体机器指令集无关的中间表示IR。这个步骤是连接编译器前端与后端的桥梁。4.1 中间表示选型三地址码 vs. 栈式机代码常见的教学用IR有两种三地址码和栈式机代码。三地址码更直观也更容易优化和转换成真实机器码是更推荐的选择。三地址码每条指令最多包含三个“地址”操作数形式如x y op z或if x relop y goto L。它非常接近现代CPU的RISC指令思想。栈式机代码模拟一个操作数栈所有运算都围绕栈进行如push a,push b,add。它更简洁但可读性稍差且优化空间较小。三地址码指令设计示例算术运算t1 b c赋值a t1条件跳转if a b goto L1无条件跳转goto L2标签L1:函数调用param p1param p2call foo, 2(2是参数个数)返回return x4.2 从AST生成三地址码生成过程本质上是对AST的又一次深度遍历为每一种AST节点类型编写对应的“代码生成”函数。这个函数负责生成与该节点语义等价的一系列三地址码指令并可能返回一个临时变量名代表该子表达式的计算结果。核心生成逻辑表达式生成以二元运算a b * c为例。首先递归生成右子树b * c的代码假设它返回一个临时变量t1生成的代码是t1 b * c。然后递归生成左子树a的代码它直接返回变量名a。最后生成当前节点的加法指令使用一个新的临时变量t2t2 a t1。整个表达式的“值”就存放在t2中。控制流生成这是最具挑战性的部分需要处理标签和跳转。if-else语句需要为then分支和else分支的入口、整个语句的出口创建标签。首先生成条件表达式的代码其结果存放在某个临时变量t中。然后生成条件跳转指令if t true goto L_then 紧接着生成goto L_else。随后是L_then:标签和then分支的代码最后以goto L_end结束then分支。接着是L_else:标签和else分支的代码。最后是L_end:标签。while循环需要循环开始标签L_loop和循环结束标签L_end。首先生成L_loop:标签然后生成条件表达式的代码和条件跳转if t false goto L_end。接着是循环体的代码最后生成goto L_loop跳回开头并以L_end:标签结束。临时变量管理需要维护一个临时变量计数器如t1, t2, t3...在需要存储中间结果时分配新的临时变量名。这些临时变量可以视为寄存器的一种抽象。基本块与流图生成线性的三地址码指令序列后可以进一步将其划分成基本块。一个基本块是只有一个入口点第一条指令和一个出口点最后一条指令是跳转或返回的指令序列。基本块之间通过跳转指令连接形成控制流图。这是进行后续数据流分析和优化如常量传播、死代码删除的基础结构。实操心得与避坑指南生成代码的顺序对于表达式通常采用后序遍历AST即先处理子节点再处理父节点这天然符合计算顺序。对于语句则是顺序遍历。标签命名与唯一性自动生成的标签如L1, L2, ...必须保证全局唯一避免冲突。短路求值的实现逻辑运算符和||的短路特性需要在中间代码中显式实现。例如对于a b不能简单地生成t1 a b而应该生成计算a如果为假则跳转到结果为假的分支否则计算b以其结果作为最终结果。这需要将逻辑表达式翻译成包含条件跳转的指令序列。数组与结构体访问生成数组元素访问a[i]的地址计算代码是重点。如果数组a基地址为base元素大小为size那么a[i]的地址是base i * size。需要生成计算该地址的指令然后通过间接加载/存储指令来读写值。为优化做准备在生成三地址码时可以有意识地为后续优化提供便利。例如尽量让临时变量的生命周期短作用域小避免生成显而易见的冗余代码如t a 0。虽然这些可以在独立的优化阶段完成但干净的代码生成是优化的良好基础。5. 实验进阶与调试从能跑到跑对完成三个实验的基本框架只是第一步让整个流程“跑起来”并且“跑得对”才是真正的挑战。这里分享一些集成调试和进阶思考的经验。5.1 测试驱动与调试技巧编译器的调试非常独特因为错误可能出现在任何一个阶段并且现象可能层层传递。分层测试这是最有效的方法。为词法分析器、语法分析器、语义分析器、中间代码生成器分别编写独立的测试用例。词法分析测试输入字符串检查输出的Token序列是否正确包括类型和字面值。语法分析测试输入一段代码检查生成的AST结构是否正确。可以编写一个AST的打印Pretty Print函数将AST以缩进格式输出便于人工比对。语义分析测试重点测试类型检查和符号表。输入包含类型错误或作用域错误的代码检查编译器是否能准确报告错误信息和位置。中间代码测试输入简单程序手动模拟执行生成的三地址码检查其逻辑是否正确。可以编写一个简单的三地址码解释器来验证。可视化工具辅助如果条件允许可以为AST和控制流图生成Graphviz的DOT描述文件然后用图形界面查看树和图的形状非常直观。防御性编程与断言在代码的关键位置添加断言assert例如在符号表查找时假设某个标识符必须存在在类型检查时假设节点类型不为空。这能在第一时间捕获程序逻辑的不一致。日志输出在编译器各个阶段的关键函数入口处添加详细的日志输出打印当前处理的内容、状态等。通过控制日志级别可以在调试时开启详细日志在最终发布时关闭。5.2 常见问题与排查实录即使思路清晰实现过程中也难免踩坑。下面是一些典型问题及其排查思路问题现象可能原因排查思路与解决方案词法分析器将关键字识别为标识符关键字表未正确初始化或比对逻辑有误检查关键字集合是否在扫描标识符前就已构建完成确认比对时是否区分大小写如果语言要求区分。语法分析器报告“意外的Token”但代码看起来正确1. 文法设计有歧义或不是LL(1)。2. 递归下降函数中分支判断顺序错误。3. “窥探”和“匹配”逻辑不一致。1. 使用First集和Follow集验证文法。2. 在解析函数开头打印当前Token单步调试看分支判断逻辑。3. 检查match()函数消费Token后是否正确地获取了下一个Token。变量“未定义”错误但明明前面有声明1. 作用域管理错误提前退出了作用域。2. 符号插入和查找的作用域不一致。3. 标识符字面值比对问题如大小写。1. 在进入/退出作用域时打印日志检查作用域栈的状态。2. 确认在引用变量时是从当前作用域栈顶开始查找的。3. 检查字符串比对是否使用了.equals()而不是。类型检查认为int和float不能相加隐式类型转换规则未实现或实现有误。检查类型兼容性判断函数。对于算术运算通常需要实现一个“通用类型”提升规则例如当int与float运算时结果应为float。生成的三地址码逻辑错误如循环无法退出控制流标签生成错误或跳转指令的目标标签错误。为生成的三地址码指令序列添加行号并手动模拟执行绘制简单的控制流图检查每个跳转指令是否指向了正确的标签位置。内存泄漏如果用了C/C或性能极差1. AST节点、符号表项等动态分配的对象未释放。2. 频繁的字符串拼接或临时对象创建。1. 使用智能指针或确保在编译器工作结束后有统一的清理过程。2. 对于频繁使用的字符串如标识符名可以使用“字符串驻留”技术保证相同的字符串只存储一份。5.3 从实验到扩展还能做些什么完成基础实验后如果你意犹未尽这里有几个有趣的扩展方向能让你的编译器“小玩具”变得更强大增加新的语言特性尝试实现for循环、switch语句、break/continue、简单的函数支持参数和返回值、一维数组等。每一个新特性都会让你对编译器的某个环节有更深的理解。实现一个简单的优化器在中间代码层面实现一些经典优化如常量折叠在编译时计算23为5、公共子表达式消除、死代码删除等。你需要先构建控制流图然后进行数据流分析。解释执行三地址码写一个简单的解释器来执行你生成的三地址码。这能让你立刻验证编译结果的正确性非常有成就感。解释器可以模拟一个寄存器机和一个指令指针。生成真实的汇编代码这是终极挑战。选择一种简单的目标架构如MIPS子集或RISC-V将三地址码映射到有限的物理寄存器上寄存器分配然后生成对应的汇编指令序列。你需要学习目标平台的指令集和调用约定。编译原理的实验是一场深刻的思维训练。它强迫你以机器的视角去理解高级语言将层层抽象逐一剥开。当你看到自己编写的简陋编译器成功地将一段打印“Hello World”的源代码转换成一串可以一步步执行的中间指令甚至是一段真正的汇编代码时那种透过现象触及本质的快乐是单纯调用现成编译器无法比拟的。这个过程里你收获的不仅仅是如何实现一个编译器更是一种系统性的、分层解决问题的工程能力这种能力在你未来面对任何复杂系统时都将是一把利器。本文还有配套的精品资源点击获取