简介北京交通大学编译原理课程实验完整源码包面向高校计算机专业本科生、课程设计者及编译器前端自学者系统覆盖词法分析、递归下降语法分析、LL(1)分析、算符优先分析、基于SLR(1)的语法制导翻译以及中间代码生成六个核心实验模块完整演示了从源程序字符流到中间代码生成的编译器前端开发流程。资源共94个文件包含33个cpp、29个h、21个txt、6个Makefile、3个c源文件等头文件负责接口声明cpp/c实现具体算法txt提供输入测试用例与文法定义Makefile用于各实验独立构建运行压缩包仅66KB目录按Lab01至Lab06清晰分模块便于对照学习。目前已有92人学习浏览可直接用于课程实验参考、期末复习或自学实践。通过源码注释与模块化工程组织读者能直观对比不同语法分析策略的处理差异理解LL(1)预测分析表构建、算符优先关系确定以及SLR(1)移进-规约冲突消解等关键细节从而掌握编译前端核心原理与实现技巧是一份高性价比的优质实验材料。1. 编译原理课程实验源码集合六个模块不是六个作业是一条完整编译前端流水线北交大这份编译原理课程实验源码集合把最常见的六个实验打包在一起词法分析、递归下降语法分析、LL1文法分析、算符优先文法、基于SLR1分析法的语法制导翻译、中间代码生成。我第一次拿到时也以为这就是六个独立作业的答案但真正动手跑通后才发现它们其实是同一套编译器前端在不同阶段下的切片。你需要的前端核心算法这里基本都有尤其是从语法分析过渡到语法制导翻译那一段很多教材讲得抽象而这个集合把从token流到四元式的路径直接摆在了面前。适合正在做编译原理课程设计、想对照验证自己实现、或者准备面试前想快速复习编译前端的人。这篇笔记不讲空泛理论只讲怎么理解、怎么跑通、怎么避坑。2. 先把六个模块在编译前端里的位置对齐从词法分析到中间代码生成的依赖链很多同学做编译原理实验的习惯是“一个实验一个文件夹”直到最后联调才发现模块之间接不上。这里建议先别急着编译代码而是把六个模块看成一条流水线词法分析输出token流语法分析消费token流生成语法树或动作序列语法制导翻译在语法分析过程中或之后触发语义动作最终产出中间代码。下面逐个模块拆开看它们在流水线里的职责和接口约定。2.1 词法分析模块DFA驱动的最小实现和保留字表怎么设计词法分析是所有后续模块的数据源头。实验里最稳妥的实现不是纯字符串匹配而是先画出识别标识符、整数、运算符、界符的状态转移图再把它转换成状态转移表或直接写DFA驱动。这样处理的好处是遇到不合法的输入能在状态转移过程中尽早发现而不是等parser跑起来才报错。我一般会先把保留字单独维护一张表然后在状态转移识别完一个标识符之后先查保留字表再决定token类型。下面这段Python代码演示了最精简的DFA思想不依赖第三方库# 简化版 DFA识别标识符、整数、保留字 import sys KEYWORDS {if, else, while, int, float} def lexer(code): tokens [] i 0 n len(code) while i n: c code[i] if c.isspace(): i 1 continue if c.isalpha() or c _: start i while i n and (code[i].isalnum() or code[i] _): i 1 word code[start:i] if word in KEYWORDS: tokens.append((KEYWORD, word)) else: tokens.append((IDENT, word)) elif c.isdigit(): start i while i n and code[i].isdigit(): i 1 tokens.append((NUM, code[start:i])) else: tokens.append((OP, c)) i 1 return tokens if __name__ __main__: print(lexer(int x 42;))这段代码里的状态机其实只有两层判断遇到字母进标识符状态遇到数字进整数状态。参数上KEYWORDS集合是可扩展的你后续如果要加return、void直接往里面加。这里最关键的是顺序先读完整个单词再判断是否保留字。如果你在第一个字符就判断关键字那ifx会被错切成两个token。词法分析模块的输出格式决定了语法分析器怎么接手我对接时习惯用二元组(类型, 属性值)。类型是KEYWORD、IDENT、NUM或OP属性值保存实际字符串或数字字面量。北交大这套源码里很可能还有行号列号那是为后面错误定位预留的建议保留别在传参时丢掉。2.2 递归下降与LL1语法分析模块自顶向下两种路线坑都在左递归和回溯递归下降和LL1都用于自顶向下分析。递归下降是手写函数每个非终结符对应一个解析函数LL1则面向文法自动化先求FIRST/FOLLOW集构造预测分析表再表驱动。两种路线的共同死穴是文法左递归E-ET这种产生式会让递归下降无限递归也会让LL1求不出FIRST集。递归下降适合表达式和语句混合的文法写起来直观报错位置也准确。比如写一个解析加减乘除表达式的递归下降函数常见做法是这样#include stdio.h // 最简单递归下降处理 数字 数字 * 数字不含左递归 // 文法expr - term ( term)* // term - factor (* factor)* // factor - num | ( expr ) extern int lookahead; // 从词法器拿来的当前token void expr(); void term(); void factor(); void expr() { term(); while (lookahead ) { // 匹配 后继续解析下一个 term lookahead getNextToken(); term(); } } void term() { factor(); while (lookahead *) { lookahead getNextToken(); factor(); } } void factor() { if (lookahead () { lookahead getNextToken(); expr(); if (lookahead ! )) { // 报错 } lookahead getNextToken(); } else if (lookahead num) { lookahead getNextToken(); } else { // 报错 } }这段代码把左递归用循环转成了右递归形式while部分就对应原来的E-ET但不会无限递归。参数上lookahead是前瞻tokengetNextToken()是词法器接口每个函数在消费token后必须主动前移。忘记前移是初学者最常见的问题表现就是死循环。如果是LL1实验核心是求FIRST和FOLLOW集。很多同学手算都算得对一写代码就漏掉epsilon传播的情况。这里有个实用技巧FIRST集合的迭代固定点可以用一个布尔数组标记某个非终结符是否推出空串然后反复扫描产生式直到集合不再变化。表驱动部分分析栈和输入串要配合打印后面避坑章节再详细说。2.3 算符优先与SLR1分析模块自底向上的表驱动处理表达式和文法冲突算符优先分析是自底向上的简化版专门处理表达式中的运算符优先级比如低于*。它的核心是一张算符优先关系表两个终结符之间是小于、大于还是等于。而SLR1是更通用的LR分析变种基于LR(0)项目集规范族利用FOLLOW集来决定归约时机。实验里算符优先通常给表达式文法做代码多数体现为一张类似下面的关系矩阵 * ( ) # * ( error ) error error # error 这张表的含义是矮栈顶和高输入时移进高栈顶和矮输入时归约。实际代码会用一个二维数组pri[top][input]保存这几个关系再配一个算符栈和符号栈。这里最容易错的是#的初始化必须在表达式两端都压入#否则表边界对不上。SLR1模块则要复杂一些它先计算LR(0)项目集族再为每个状态填充ACTION和GOTO表。拿到表后表驱动代码非常机械# 表驱动的LR分析框架action和goto表由外部生成 def slr_driver(tokens, action, goto): stack [0] # 状态栈初始状态0 index 0 while True: state stack[-1] token tokens[index] a token.type if action[state][a] is None: raise SyntaxError(syntax error near line) act action[state][a] if act[0] S: # shift stack.append(act[1]) # 新状态入栈 index 1 elif act[0] R: # reduce by production p lhs, rhs productions[act[1]] for _ in range(len(rhs)): stack.pop() stack.append(goto[stack[-1]][lhs]) # 这里通常还要做语义动作 elif act acc: break return True这段代码里的stack保存的是状态编号不是符号。每次移进时新状态入栈归约时弹出len(rhs)个状态再按GOTO表压入新的状态。注意别把状态栈和符号栈混淆很多SLR1翻车都在这里。补一句算符优先和SLR1在课程设计里往往是二选一但如果你的文法里有一元负号或者比较运算符算符优先表的error项会越来越多此时SLR1反而更好维护。2.4 语法制导翻译与中间代码生成模块语义动作什么时候触发四元式怎么攒到了这个模块前面所有分析都开始产生“副作用”。语法制导翻译的核心是给每条产生式挂语义动作动作里调用gen()生成中间代码通常用四元式(op, arg1, arg2, result)表示。实验里比较典型的是把赋值语句x y 1翻译成三地址码或四元式。我推荐的做法是做一个全局的四元式数组再维护一个临时变量编号计数器。比如翻译x y 1大致流程是# 四元式生成示意地址 100 开始 quads [] temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def gen(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) # 假设已经解析出 y 1 并知道目标变量 x t new_temp() gen(, y, 1, t) # t1 y 1 gen(:, t, -, x) # x t1参数里op是运算符arg1、arg2是操作数result是结果存放位置。这里有个容易错的地方四元式的arg2当没有右操作数时要写占位符而不是留空数组。留空会让后续优化或代码生成按错位索引访问。这六个模块一旦串起来实际路径就是词法分析出token语法分析按产生式驱动语义动作在归约或推导的某个时机被触发最后四元式数组被写满。拿到这份源码集合第一步不是改按钮而是先找到那几条最核心的产生式上挂的语义动作理解它们什么时候被调用。理解了触发时机你就掌握了整个前端的中枢。3. 把整套源码在本地跑通环境准备、模块编译和联调顺序有了理论地图接下来就是动手。这套源码集合无论用C、Java还是Python写的跑通的步骤基本一样。不要从头到尾逐行读代码先把“能编译、能输出token流、能输出四元式”这件事做成再回头补细节。3.1 拿到压缩包后先做这三件事目录结构、语言版本和测试用例解压后不要急着双击运行先看一眼目录。常见结构是src/、docs/或README。我会依次执行以下命令了解情况# 解压注意穿透子目录 unzip -o compiler_lab.zip -d compiler_lab # 进入目录后查看顶层结构 cd compiler_lab ls -la # 是否有 README 或 Makefile优先看构建说明 find . -maxdepth 2 -name README* -o -name Makefile* -o -name CMakeLists.txt这一步的目的是判断语言和构建方式。如果是Java找src/*.java和主类如果是C/C找.c/.cpp和Makefile如果是Python找入口main.py或run.py。信息往往不在压缩包名里而在项目文件里。压缩包里的README即使是老师写的也值得先读一遍里面很可能写了每个模块的输入输出格式。不要跳过这一步直接开IDE你会白白踩很多“运行不出来”的坑。3.2 词法分析模块先出token流最小运行命令和输入输出改造词法分析模块通常是独立的可以先单独编译运行。最稳妥的测试方式是把一个很小的输入写到文件然后把输出重定向到另一个文件方便对比# 假设入口是 clex输入文件 test.in输出 token 序列 ./clex test.in tokens.out cat tokens.out如果命令跑不通先检查是否少编译了依赖文件。常见做法是make lexer或者直接编译整个src。输出格式一般是每行一个token例如1 KEYWORD int 2 IDENT x 3 OP 4 NUM 0 5 OP ;这里每行的第一列是行号第二列是token类型第三列是属性值。如果你的词法器输出没有行号列我建议在联调前先加上。加行号的方式很简单在词法器维护一个line变量遇到\n自增每次生成token时把它塞进结果里。这是后面语法分析报错定位的重要依据。3.3 语法分析模块怎么消费token流递归下降和LL1的接口差异词法分析能出token流之后就需要对接语法分析。递归下降和LL1的接口差异主要体现在“取token”的方式。递归下降倾向“当前token主动向前拉取”所以词法器要提供getNextToken()或peek()。LL1表驱动通常一次性读入全部token放到数组里再按下标推进。如果你打算整合两部分我会先把词法分析器的接口统一成下面这样方便两种parser都能用// 词法分析器统一接口返回值类型通过参数带回属性值 typedef struct { int type; char lexeme[64]; int line; } Token; Token getNextToken(); // 返回并消费一个token Token peekToken(int n); // 往前看n个token不消费有些源码集合里还会在词法分析模块里自带一个缓冲队列目的就是支持peek。如果没有你可以自己包一层。这个接口抽象能让语法分析模块不依赖词法分析的具体实现。跑语法分析时的典型命令是./parser tokens.out parse_tree.txt不过更常见的是语法分析器直接调用词法分析函数不需要中间文件。无论哪种方式你都要注意parser的退出条件——读不到EOF或者#就继续循环容易死循环。3.4 中间代码生成模块联调从语法树到四元式的触发点中间代码生成模块往往是整个包里的“重头戏”但也是最少被单独运行的模块因为它的输出依赖前面所有模块。跑通它的最小路径是输入一段合法源代码经过词法分析和语法分析最终把生成的四元式写出来。命令看包里的设计# 有的包直接把前端串成一条命令 ./compiler test.c -emit-ir ir.out cat ir.out如果编译链较长我建议分两步跑第一步先看tokens.out确认词法无误第二步再看ir.out确认四元式顺序。很多同学一上来就跑总命令结果报错了不知道是哪一步。联调顺序一定是先词法、再语法、最后语义。如果包是Python写的那么入口多半长这样python3 main.py --input source.c --output ir.txt参数上主要关注--input和--output源码集合里可能还有--debug打开后能看到分析栈和当前移进归约的动作。联调时务必开调试输出这是后面排查问题的捷径。跑通的标准不是“能运行”而是输入的if、while、赋值语句都能生成对应的四元式而不是只处理。4. 避坑指南编译原理实验联调的6个常见问题与排查方法这一章写给被“为什么我的代码一跑就崩”困住的你。以下问题我基本都在课程设计里踩过一遍每一条都按现象、原因、解决写清楚。4.1 词法分析把关键字当成标识符TINY测试直接错乱现象输入if x 1词法分析输出IDENT(if)而不是KEYWORD(if)后续语法分析器不认识这个token整个测试中断。更隐蔽的是输入intx时被分成KEYWORD(int)和IDENT(x)。原因保留字判断逻辑写反了最常见的是在状态转移过程中读到i就判断是不是if或者识别完整个单词后没查保留字表。一旦intx这种标识符出现就会被错误切分。解决先完整读取一个单词再统一查保留字表。我一般会用unordered_set或map存保留字查到返回KEYWORD类型查不到才返回IDENT。同时给词法分析加一个“标识符不能以数字开头”的状态判断避免1abc被当作合法标识符。4.2 递归下降解析无限递归或栈溢出终端刷屏到崩现象程序一运行就疯狂递归终端不停吐错误然后栈溢出崩溃。代码里每个函数都在调用下一个非终结符但始终等不到终止。原因文法有左递归比如expr - expr term。递归下降函数里就表现为expr()先调用expr()无限循环且没有消费任何token。还有一种情况是while循环里忘记将lookahead前移永远停留在同一个token上。解决先把文法改写成右递归或循环形式。对expr - expr term改成expr - term { term }实现时用while (lookahead ) { match(); term(); }。同时每匹配一个终结符都要调用getNextToken()并在函数入口打印当前函数名和lookahead就能立刻定位卡住的位置。4.3 LL1分析表有多重入口动作冲突不知道走哪条现象用程序求FIRST/FOLLOW集后预测分析表里某个格子同时有两条产生式比如action[state][IDENT]既想移进又想归约。运行时选择错误导致解析失败。原因FIRST或FOLLOW集合计算有误最常见的是忘记处理epsilon。比如产生式B - epsilon那么FOLLOW(A) 需要并入 FOLLOW(B)很多手推初始条件没做全。另一个常见原因是文法本身不是LL1存在公共左因子。解决先用课本算法手工验证小文法比如E - T E、E - T E | ε。再写一个独立的集合计算脚本输出每个非终结符的FIRST和FOLLOW与手算结果核对。确认无误后如果仍有冲突那就提取公共左因子或者接受二义性并改用优先级规则解决比如if嵌套问题。4.4 SLR1分析表冲突shift/reduce搞不清报错又像黑匣子现象SLR1驱动在符号或)处报语法错误但文法怎么看都没问题。打开调试发现状态里既有移进项又有归约项分析器无法确定走哪条。原因文法不是SLR1也就是说某条产生式的归约项被某些FOLLOW集错误地“放大”了导致不该归约的地方也允许归约。也可能是构建LR(0)项目集时求闭包漏了某个产生式。解决别抠SLR1一种方法先打印出冲突状态的完整项目集。观察冲突点是移进和某条产生式归约之间的矛盾如果该产生式在栈上可以出现说明需要更精确的LALR或LR1分析而不是强行调表。课程设计里我会把冲突的上下文打印出来然后调整文法优先级或用语义动作去消解而不是碰运气。4.5 中间代码生成空转或乱序四元式顺序和表达式计算反了现象输入a b c * d生成的中间代码先算加后算乘或者直接没有输出。更隐蔽的是四元式多了几行临时变量赋值但最终目标变量没有赋值。原因语义动作挂错了位置。语法制导翻译中动作放在产生式右侧的不同位置会导致执行时机不同。比如E - T E和E - T { 动作 } E就有差别。另一个常见原因是临时变量编号没维护好两次使用同一个t1后来的四元式覆盖了前面的。解决把四元式打印放在每个gen()调用的后面执行到哪打印到哪。检查new_temp计数器是否在每次解析前复位以及最终赋值动作是否挂在包含目标变量的产生式上。典型对比是x y 1先对y 1生成加法四元式再用独立四元式把结果赋值给x不要合并成一条伪指令。4.6 文件包含红色中文注释后词法分析直接崩溃现象输入文件里写了// 注释或/* 注释 */程序报错或者生成的token串里混入了一堆乱码。把注释删掉就正常。原因词法分析器没有跳过注释状态。它把/当作除号还把中文注释里的每一个字节都当成了普通字符导致状态机进入未知状态。如果源码集合是C或Java还可能与字符编码有关。解决在词法分析状态转移表里增加注释状态遇到//就一直读到行尾遇到/*就跳转到注释状态直到*/。中文项目里通常还需要把输入以UTF-8方式读取避免strlen在字节流里数错。代码上就是在循环开头做两个额外判断成本很低收益很大。5. 把这套源码改造成你答辩时能讲清楚的项目增量改进和边界扩展跑通原始包只算“做完了课程实验”如果想在答辩或简历里描述得漂亮需要做一些看得见的改进。这里给你三个方向每个都能独立成一小节。5.1 给词法分析加行号定位和错误恢复报错不再像“None”很多原始包的词法分析报错就一句lexical error!你都不知道错误在第几行。答辩时老师一定会问“你的编译器能不能定位错误”。我给词法分析加错误恢复后的做法是维护line变量遇到换行自增如果发现非ASCII字符或非法字符记录行号并跳过让分析继续而不是中断。# 词法分析错误恢复非法字符跳过并记录行号 def lexer_with_error_recovery(code): tokens [] errors [] i 0 line 1 n len(code) while i n: c code[i] if c \n: line 1 i 1 continue if c.isspace(): i 1 continue # 非法字符非字母数字且不是运算符 if not (c.isalnum() or c in -*/(){};,): errors.append((line, c, invalid character)) i 1 continue # 正常识别token... i 1 return tokens, errors这段代码的核心在于“错误恢复”不是恢复状态而是不因单个错误而退出整次分析。对课程设计来说这个改动很好讲它能一次性报告多个错误。注意参数里errors是一个三元组列表方便统一格式化输出。5.2 把LL1文法扩展成支持赋值语句和条件语句别只算表达式原始包的LL1或递归下降很可能只支持简单算术表达式。扩展语法的第一步是设计多条新产生式例如stmt - ID : expr stmt - if ( expr ) stmt expr - term expr expr - term expr | ε把新产生式加进数据结构后需要重新求FIRST/FOLLOW集并重建预测分析表。这里我踩过一个坑新增产生式时忘了更新非终结符集合导致表驱动里的GOTO表维度不够。解决方法是抽出符号集合从文法文件动态生成而不是写死在二维数组里。改造后建议写一个专门的测试函数用类似下面的断言检查def test_assignment_parse(): tokens lexer(x : y 1;) result parser.parse(tokens) assert result is not None, assignment should parse这种自动化断言能让你的扩展看起来“工程化”。答辩时老师要看到的不只是一堆输出还有你测试的代码和边界覆盖。注意断言里包含;或#的结束处理很多文法分析在读到尾部时缺少终止符号。5.3 从四元式走向后端寄存器分配和汇编打印的扩展点中间代码生成之后常见的课程设计终点是输出汇编或某种伪指令。但有些同学想做得更深一点。一个低成本的扩展是给四元式加一个简单寄存器分配器——把所有临时变量映射到R0、R1、R2不够时溢出到栈。核心代码只涉及一个映射表# 简单寄存器分配以四元式结果为粒度 reg_map {} next_reg 0 def allocate_reg(var): global next_reg if var in reg_map: return reg_map[var] if next_reg 8: reg_map[var] fR{next_reg} next_reg 1 else: reg_map[var] fSTACK{x} # 超出寄存器数就压栈 return reg_map[var]这个扩展点能让你的项目从“前端”延伸到“后端基础”。答辩时可以讲清楚为什么超过8个临时变量就压栈而不是反复刷新寄存器。注意你的四元式里变量作用域可能重叠简单映射表适合不包含优化的演示别强行和全局寄存器分配相混淆。6. 一个验证技巧用脚本批量比对中间代码输出确保改动不回退课程设计最怕的不是写不出代码而是改了一处词法逻辑导致后面所有语法分析结果全变。这里分享一个我养成很久的习惯建立一组固定输入文件把每次跑出来的tokens.out和ir.out快照下来改动后做一次回归比对。写一个简单的回归脚本放在项目根目录下每次改动后跑一遍#!/bin/bash # 回归测试对每个 .in 文件生成中间代码与 .expected 对比 for f in tests/*.in; do base${f%.in} ./compiler $f -emit-ir $base.ir if diff -q $base.expected $base.ir /dev/null; then echo PASS $base else echo FAIL $base diff $base.expected $base.ir fi done脚本里tests/*.in是输入测试文件.expected是你在修改前保存的正确输出。diff -q只比较内容是否一致不一致时打印详细差异。参数上注意把每次改动前的正确输出先保存好否则你对比的就是“错误版本”。这个验证方法的价值在于它让实验从“能跑”变成“可维护”。我当年拿到类似的源码集合后第一件事不是去读代码而是先生成一组黄金快照。之后每一个算法调整比如把词法分析的状态转移表从二维数组改成switch都要看脚本是不是全绿。有一次我以为LL1表的冲突修复没影响其他模块结果回归脚本立刻抓出了中间代码顺序变化节省了我大半天手工验证的时间。这也是我现在做任何编译前端改动时的固定动作。希望帮到你。本文还有配套的精品资源点击获取