简介围绕OUC中国海洋大学编译原理课程的全部实验代码合集覆盖2020年春季学期8个实验从词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成到错误处理与编译器综合并附实验要求文档适合正在学习编译器构造或需要完整实验参考的本科生。压缩包共74个文件以C源码18个.c、Flex/Bison文法文件8个.l、4个.y、头文件与生成文件、可执行程序、Makefile及说明文档为主整体仅774KB便于按目录对照实验要求逐项运行与修改。已有4408人学习浏览。内容还提供lex.yy.c、parser.tab.c、AST相关代码等中间产物以及test*.p测试文件能帮助理解从源码到目标代码的完整编译流程。实验要求文档对每个实验的目标、输出和评估标准做了明确说明配合代码可快速定位关键实现适合课程设计、期末复习或自学编译原理时参考。1. 先看懂实验地图一学期编译实验都在做什么很多同学拿到实验文档就急着动手结果写了两星期发现方向错了。我的建议是第一周不要写代码先把整个实验体系在脑子里过一遍。编译原理这门课实验往往比期末考试更能让人崩溃但也是最能建立成就感的一环。我当年做OUC编译原理全部实验的时候从词法分析一路写到中间代码生成几乎每个阶段都要经历一次“看不懂实验要求”和“编译器报错看不懂”的双重折磨。这篇内容就把这些实验的整体脉络、每一步的核心思路和踩过的坑整理出来给正在被FIRST集、LR(1)项集和四元式折磨的同学一份可以照着走的参考。不管你是刚上手词法分析还是已经卡在语法分析、中间代码生成这篇都能帮你把“这实验到底要我干嘛”变成“原来就这么回事”。1.1 每个实验对应编译器的哪个阶段编译器的经典阶段划分是词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。高校的实验课通常把前四个阶段拆成2到5个独立实验每个实验都有明确的输入和输出要求。如果你手里是王生原老师那本编译原理教材清华大学出版社第三版你会发现实验内容和课本章节的对应关系非常整齐词法分析对应“词法分析”一章语法分析对应“语法分析”那一章语义分析部分会用到语法制导翻译和中间代码生成。很多同学搜课后答案是为了刷概念题但实际上实验报告里真正卡人的不是概念而是怎么把课本上的算法翻译成可运行的代码。所以我的建议是课后题可以用来校验FIRST集、FOLLOW集、LR项集这些手算结果但写代码时别老想着翻答案算法本身比答案重要得多。1.2 用什么语言写一句话讲清楚理论上任何语言都能写一个实验编译器但实际选择会直接影响调试效率。如果老师没有强行限制语言Java是更省心的选择理由是类语法天然适合表达Token、语法树节点和符号表条目IDE的调试体验好JUnit写单元测试很方便能支撑“跑一个用例看一个阶段”的实验节奏。当然如果你的实验环境是C语言也不是不能做用struct加函数指针一样能组织出一套清晰的代码。C写起来更贴近“编译器底层”的感觉但内存管理会多消耗很多时间尤其是字符串处理和对象生命周期管理极易出错。我见到过不少小组用C写到语法分析阶段就崩掉大多不是算法问题而是malloc和字符串拷贝翻车。提示选语言之前先问清楚老师对提交物有没有限制。有的课程要求最终提交C/C代码这种情况下直接放弃Java别做无谓的切换成本。1.3 动手前先读三样东西第一是实验文档里的“输入输出示例”这部分决定了你测试用例怎么写第二是这门课的评分标准看看哪个实验权重高哪个可以“能跑就行”第三是老师给的基础代码框架如果实验平台已经给了Token定义和Parser骨架你的工作量会少很多但也要清楚模板里哪些地方是留给你填的。别一上来就喊“老师模板有bug”很可能是你没有注意到模板里预留的TODO。2. 词法分析把源文件变成Token流词法分析是整个编译前端最不性感但最不能出错的部分。它做的事很简单读入字符流跳过空白和注释识别出标识符、关键字、数字、运算符和界符输出一串带位置信息的Token。很多同学的第一个实验就挂在这里大部分不是因为算法多难而是边界情况没处理干净。2.1 手工构造DFA而不是写一堆if-else正规的实验做法是手工设计一个确定有限自动机把扫描逻辑写成状态转移。核心思路很简单读进一个字符根据当前状态决定下一个状态状态改变说明一个Token结束了。这个过程中最关键的两个原则是最长匹配和词素定界。给你们一个极简的状态图设计思路。识别标识符和关键字时进入identifier状态后持续读字母、数字和下划线直到遇到空白或界符为止。识别数字时进入digit状态支持整数和开头是小数的实数注意指数部分是否需要支持要提前对照实验文档。识别运算符时对单字符运算符如、-、*、/、、、等直接返回对可能组成双字符的运算符比如、、、!、、||得分状态处理读到一个后不能立刻返回必须试读下一个字符如果是则返回否则把字符“退回去”。这里最典型的坑是“最长匹配”输入是时如果贪心不足先返回了再返回后续语法分析绝对会疯掉。注意空白、换行和注释不要直接丢弃就完事行号和列号是错误定位的关键信息。token结构里至少要有type、lexeme、line、col四个字段。2.2 Token设计与保留字表的处理Token类型建议用枚举表达IDENT、INT_LITERAL、REAL_LITERAL、KEYWORD、OP、DELIMITER。这里有一个最常见的错误把关键字当成标识符处理。正确做法是先按标识符的规则识别出整个词素再查保留字表如果在保留字表里就标记为KEYWORD否则才是IDENT。反过来做先判断首字母是不是某个关键字开头会出现把ifx识别成if加x这种低级问题。推荐在词法分析器里维护一个HashMap做保留字表这样查表是常数时间。如果实验结果要求输出词法分析报告通常需要打印token类型、词素、所在行号一个简单的循环遍历输出就行。写词法分析器要记得把每个识别逻辑拆成独立函数比把所有状态都堆在一个大while里好调试得多。2.3 注释与除法的恩怨类C语言的注释是/* .../和//两种风格。扫描到/时必须向后看一位如果是进入注释状态一直读到*/如果是/读到行尾否则才把/当除号返回。处理/*/时一定要考虑注释未闭合就遇到文件末尾的情况这时候要给出明确报错而不是静默结束或死循环。我做实验时就在这个分支里挂过一次原因是只判断了读到但没有判断流是否已经到EOF结果程序卡死。代码骨架用Java大概是这个样子public Token nextToken() throws IOException { skipWhitespaceAndComments(); if (!reader.ready()) return new Token(TokenType.EOF, , line, col); char c reader.peek(); if (Character.isLetter(c) || c _) return readIdentifierOrKeyword(); if (Character.isDigit(c)) return readNumber(); return readOperatorOrDelimiter(); }测试用例至少覆盖空程序、纯注释程序、关键字与标识符混输、带小数的数字串、连续运算符、不合法字符以及“ifx这类以关键字开头的标识符”。3. 语法分析两种主流路线的落地细节词法分析跑通之后实验难度会瞬间上一个台阶因为语法分析要求你把上下文无关文法变成可执行的识别程序。常见的实验路线有两条递归下降分析以及基于预测分析表的LL(1)分析。很多课程还会单独安排一个LR分析实验这个我放到下一节单独讲。3.1 先手算一遍FIRST和FOLLOW再写代码写语法分析器之前一定要先把你给定文法的FIRST集和FOLLOW集手算出来这个步骤省不得。手算的目的不是为了交报告而是为了让你知道代码里每个非终结符在什么输入下应该做什么选择。计算FIRST集的要点是如果X能推导出ε那ε就算进FIRST(X)里并且这个“可推导出ε”的信息会向前传播。计算FOLLOW集时要关注产生式右部某个非终结符后面跟的是什么如果后面是另一个非终结符要看它能推出的第一个终结符集合如果后面什么也没有就把左边非终结符的FOLLOW集继承过来。这个“继承”环节特别容易漏一旦漏了后面构建预测分析表时就会缺表项。期末试题里手算FIRST、FOLLOW的题也是高频考点实验里算过一遍考试基本送分。3.2 递归下降写法函数代替状态机递归下降分析器本质上是把文法直接翻译成一组互相调用的函数每个非终结符对应一个函数。它的实现思路是函数开头先读取当前的lookahead token然后按产生式右侧的顺序依次匹配终结符或调用其他非终结符函数。需要特别注意的是递归下降直接支持的是LL(1)类文法遇到左递归必须先处理。比如文法E - E T | T直接写成递归会无限递归必须先消除左递归变成E - T EE - T E | ε。用循环结构可以更直观地实现E先parseT()再看当前lookahead是不是号是就继续循环直到没有号为止。这个写法在报告里描述为“用循环等价实现了右递归文法”即可不必把E单独拆成一个函数写到死。代码结构往往是parseE() { parseT(); while (lookahead.type PLUS) { match(PLUS); parseT(); } }是不是很像在写表达式求值对递归下降本来就是一种“看见什么就吞什么”的匹配逻辑写起来非常直观。而它的坑也出在直观如果文法存在公共左因子比如stmt - if E then stmt | if E then stmt else stmt直接写两个branch代码会不知道选哪个必须先提取公共左因子。3.3 预测分析表和表驱动分析程序如果你选的路线是LL(1)那核心工作是构建一张预测分析表行是非终结符列是终结符表项填产生式。构建规则很简单对每个产生式A - α把α能推出的每个首终结符对应的格子填上这条产生式如果α能推出ε就把FOLLOW(A)里的终结符对应格子也填上这条产生式。表驱动的分析程序维护一个分析栈初始把#和开始符号压栈然后不断读输入、查表、弹栈遇到匹配的终结符就吃掉一个输入token遇到非终结符就把栈顶弹出后按产生式右部逆序压入。这部分的调试我强烈建议打印分析栈的状态变化每一步都输出“当前栈、当前输入、查表结果”一旦走偏立刻能看出是哪一步压错了栈。3.4 错误处理不能报个错就完事语法分析实验往往会被忽略错误恢复但评分老师非常看重这一点。最简单的做法是恐慌模式发现错误时不断丢弃输入token直到遇到同步集合中的token一般是语句结束符、右括号、分号等然后继续分析。这样一次输入可以报告多个语法错误而不是死在一个错误上。你别小看这个细节很多同学的代码遇到一个错误就退出测试用例一多直接崩最后分数拉不开差距往往就靠这些。4. LR分析手工构造分析表的完整思路LR分析是很多同学觉得最抽象的一环其实它和LL(1)的差异只在“如何决策”上。LL(1)靠的是递归下降或预测表LR靠的是状态机加ACTION/GOTO两张表。我不建议只背算法要理解它到底在记录什么。4.1 为什么需要LR分析左递归文法比如E - E T | T对递归下降不友好但对LR来说完全没问题因为它天生就是从右向左规约的思路。LR分析时看到的是栈上已有的符号序列和接下来的输入它决定当前应该“移进”还是“规约”本质上是在用有限状态机模拟一个推导过程。很多课程把这个实验安排在后半段就是为了让你跳出“手写递归下降很爽”的舒适区真正理解编译器的通用识别框架。4.2 手工构造项集族和ACTION/GOTO表构造步骤是先给文法加一个S - S的拓广产生式然后计算LR(0)项集族。每个LR(0)项集是一个闭包闭包规则是如果项中圆点后面是非终结符B就把所有B - γ的产生式加进去圆点放在最左端。通过move函数也就是读入某个文法符号后圆点右移得到状态转换关系。随后给每个可以规约的项目打上规约标签填ACTION表时遇到终结符移进填s遇到可以规约的项目填r(产生式编号)根据FOLLOW集判断哪些输入列可以规约这是SLR简化之处所以叫SLR(1)。GOTO表则记录遇到非终结符后的状态跳转。如果某一格同时被填了移进和规约就产生冲突说明文法不是SLR(1)这时可能要考虑LR(1)或LALR不过课程实验里通常不会难到这一步。用一个极小的例子来感受一下过程。文法S - S S - (L) | a L - S | L, S手工构造时会看到在初始项集里圆点后的S是非终结符所以要同时加入S - (L)和S - a读入左括号后进入一个新状态那里圆点后面是L于是又加入L - S和L - S右部的展开。把每一条状态转移写下来就是一张状态图。这个过程确实繁琐但理解之后任何LR分析表题都只是体力活。手算题建议对照着教材的表格多练几次用Excel或者纯手写都行重点是别跳过。哈工大陈鄞老师的编译原理课程对这一部分讲得特别清楚如果课堂没听明白可以去看那套视频补一下理论再回到实验里手动构造一次印象会深很多。4.3 表驱动LR程序的调试技巧实现上LR分析程序比LL(1)还简单维护状态栈和符号栈循环里查ACTION表。真正的难点是调试。我第一次运行时状态栈里全是数字根本不知道自己在哪。后来我在每次移进、规约时打印一行日志包含“状态栈顶、符号栈顶、当前输入token、执行的动作”逻辑一下子清楚了很多。遇到归约后GOTO跳错十有八九是表里的状态编号填错了对照着状态图逐行查。建议把ACTION表和GOTO表存成二维数组或哈希表打印成易读的表格格式方便对照检查。直接手写一堆switch-case是维护噩梦我不推荐。5. 语义分析与中间代码生成让程序真正“有含义”前面几关通过的代码还只是“能识别语言结构”到了语义分析编译器开始关心“这句话到底是什么意思”需要维护符号表做声明检查和类型检查再把表达式翻译成中间代码。5.1 符号表设计作用域和遮蔽关系的处理最简单的符号表设计是作用域栈进入一块代码时往栈里压一层退出代码块时弹出。查找符号时从栈顶往栈底找这样内层变量能遮蔽外层同名变量符合大多数语言的语义。如果你们实验要求支持函数那符号表里还要记录参数列表、返回类型这些信息函数符号和普通变量符号建议分开建表或者用统一的符号条目加个kind字段。这一阶段很容易出现“变量明明声明了却报未定义”的问题原因几乎都是符号表作用域没有正确压栈和弹栈。建议在进入和退出作用域时打印一行日志观察符号表的层次变化这比反复读代码管用。5.2 类型检查宁可多报不可漏报实验里的类型检查不用做得很复杂但至少要做到赋值表达式左右类型兼容、二元运算的两个操作数类型一致、数组下标是整数、条件表达式是布尔类型。实现方式是在语义动作里对每个节点做类型推断子节点类型不符合要求时输出语义错误。这一步最容易出错的是“类型谁兼容谁”的判断逻辑我见过有人把int和float直接判不相等导致所有浮点表达式都报错调试半天才发现是不小心用了引用比较而不是值比较。5.3 四元式与语法制导翻译中间代码常见形式是三地址码落地实现常用四元式结构(op, arg1, arg2, result)表达式 a b * c 会生成(*) b c t1 () a t1 t2 () t2 - x生成四元式时递归下降的返回值不能只是布尔“是否匹配成功”得把该表达式的“结果位置”传出来。比如parseExpr里解析完每一项后知道这项的临时变量名是什么就能正确拼出运算的四元式。这其实就是标准教材里说的语法制导翻译思想在语法分析过程中嵌入语义动作。5.4 控制流语句回填的想法if和while的翻译要用到标签跳转。最简单的做法是先生成一个无目标地址的跳转四元式等条件翻译完、目标位置确定后再把地址填回去这就是回填。先在纸上画好if-then-else流程图的四元式接入点再写代码能省很多事。break语句要维护一个待回填链否则不知道跳去哪。如果你们实验没到中间代码生成就结束了那这一节可以直接跳过但要理解“为什么这个阶段存在”因为期末复习时经常会考到回填和四元式之间的对应关系实验里见过一遍印象完全不同。同样如果老师追加了目标代码生成实验核心就是把四元式映射到汇编指令加寄存器分配思路仍然是逐条翻译加临时变量管理。6. 高频报错与调试技巧速查这个部分集中整理我实际做实验时反复踩过的坑按症状和解决思路列出来省得你们一个个去搜索引擎试。编译原理实验的排错和普通编程作业不一样问题常常横跨好几个阶段找对定位点是第一步。6.1 高频问题速查表现象常见原因排查思路FIRST集计算时程序死循环没有正确计算可推出ε的非终结符集合先单独算出nullable集合再算FIRST避免循环依赖词法分析把ifx识别成关键字用了首字母匹配而非完整词素匹配识别完整标识符后查保留字表多行注释不结束程序卡死没处理EOF在注释循环里检查文件是否读完递归下降栈溢出文法存在左递归未消除先消除左递归再写parse函数预测分析表同一格多个产生式文法不是LL(1)提取公共左因子或检查FIRST/FOLLOW是否计算错误LR分析时状态栈数字完全看不懂缺少动作日志每次移进/规约都打印状态栈、符号栈、输入token类型检查不报任何错语义动作没有真正执行或符号表作用域没处理好打印符号表单独构造类型不匹配的用例验证四元式顺序与表达式运算优先级不符递归下降子函数返回顺序与优先级层级不匹配用a b * c这种用例逐步跟踪生成的四元式6.2 调试编译器的实用工具与习惯调试编译器这种“输出巨大、状态复杂”的程序靠println是最高效的不要一上来就上断点。设定一个环境变量或命令行参数来开关调试日志比如-debug开启日志正式运行时关掉。别忘了用专门的测试用例目录每次改完代码跑一遍全量测试这就是回归测试。不用复杂框架写一个简单的shell脚本或者Java main函数遍历测试目录就行。排查错误时有一个通用套路先确认当前阶段输出对不对再看下一阶段。比如中间代码生成了但结果不对先用一个已知正确的Token流喂给语义分析模块确认是前面传来的Token有误还是语义分析本身出错。这样可以快速切断问题链条。6.3 测试用例怎么造才能兜住老师我的经验是宁可自己多造50组测试不要在评分时让老师发现一个边界bug。测试用例至少包括最简单的合法程序、复杂的嵌套表达式、包含嵌套块和作用域遮蔽的代码、大量注释和空行干扰、未声明变量、类型错误的程序、缺少分号的错误恢复场景。每种错误类型至少准备一个用例记录期望输出再逐一核对你的程序输出。如果实验要求支持语法错误定位用例里还要包含“错误发生在文件中间位置”的情况检查报错的行号和列号是否准确。这个细节经常被忽视但编译器的错误提示质量其实是评分里很看重的一个维度。最后再说几句我实际做完这一整套实验最大的感受是编译器不是玄学它就是一个输入输出极其明确的软件问题变得复杂只是因为每个阶段的输出都变成了下一阶段的输入调试链条拉长了。所以你别试图一次写完一个大文件词法、语法、语义一层层拆开每一层跑通并产出独立结果再进下一层出问题只查当前层效率会高很多。最后再分享一个小建议每个实验阶段都留一个一键运行的入口测试用例统一放在一个目录里从词法阶段开始全程保留这样写到中间代码生成时随时可以回来回归测试前几关。这个方法帮我省下的时间足以让我多刷两套编译原理期末试题。祝你们顺利跑通编译器前端。本文还有配套的精品资源点击获取