简介南京航空航天大学编译原理课程设计全套资料面向计算机专业学生及需要完成词法、语法分析实验的课程设计者帮助梳理从源程序扫描到语法处理的实现路径并可作为课设报告与答辩准备的参考。压缩包共32个文件、约961KB包含源码与头文件、工程配置、可执行程序、课程设计报告、答辩演示文稿及若干说明文本覆盖词法分析、语法分析等模块目录按工程与文档分置便于对照阅读和复现实验。目前已有751人学习下载具有一定参考热度。资料中既有经检验可运行的程序工程也保留了实现代码与调试产物读者可据此理解属性字、符号表、Token识别等关键环节参考工程组织方式与报告写作框架减少环境配置和排错中的反复尝试适合作为课程设计阶段的辅助材料。1. 编译原理课程设计从零跑通五段流水线一份源码包就够课设答疑里见过的翻车现场十有八九出在同一个地方文法写出来了LL(1) 表也推完了然后盯着屏幕不知道第一行代码该写什么。这份编译原理课程设计包把整条链路拆成可以直接跑通的五段词法分析、语法分析、符号表与语义检查、四元式生成、四元式解释执行源语言是一个类 PL/0 的极小子集覆盖赋值、算术表达式、if/else、while、过程调用和一维数组。计算机专业正在做课设的同学可以整体跑通再按验收要求裁剪也可以只取其中一段去补自己的半成品——最省时间的是四元式解释器那部分它能把我的分析器到底对不对这个问题当场变成一个能看见的输出。2. 词法与语法分析落地把 800 行前端拆成三个可验证的节点前端是整个课设里最容易看着写完了其实没通的部分。常见做法是先把词法分析器单独跑起来喂一段源码把 token 流打印到文件里逐行核对token 流对了再动语法分析这样出问题时你只需要怀疑一层而不是两层一起猜。2.1 词法分析单遍扫描 最长匹配 行列号课程设计里最不该省的是位置信息。很多同学的词法分析器只返回 token 类型和字符串等到语法分析报错时只能说第 N 个 token 出错了答辩演示时非常被动。// lexer.cpp —— 单遍扫描最长匹配每个 token 带行列号便于报错定位 enum TokenType { TK_ID, TK_NUM, TK_IF, TK_WHILE, TK_PLUS, TK_ASSIGN, TK_EOF, TK_ERR }; struct Token { TokenType type; std::string lexeme; int line, col; // 报错定位用语法分析阶段原样往下传 }; class Lexer { const std::string src; size_t pos 0; int line 1, col 1; public: Token next() { skipSpaceAndComment(); // 跳过空白与 // 行注释 if (pos src.size()) return {TK_EOF, , line, col}; char c src[pos]; if (isdigit((unsigned char)c)) return number(); // 连续 digit 组成整数 if (isalpha((unsigned char)c) || c _) return identOrKeyword(); return opOrPunct(); // 运算符双字符优先于单字符 } };opOrPunct()里必须先判、、:这类双字符运算符再退到单字符。这一步顺序写反a : b会被拆成a、:、三个 token语法分析报的错误信息会把你带到完全错误的方向去。identOrKeyword()查一张关键字表命中就把TK_ID改成对应的关键字类型没命中保留标识符——关键字不要单独写一个分支否则加一个保留字就要改三处代码。2.2 递归下降还是 LL(1) 表驱动按验收标准选不按难易选这一步的选型几乎决定了后面两周的工作量。四种常见方案的差别不在哪个更高级而在你的验收要求写了什么。方案实现量能否直接处理左递归调试难度适配的验收要求递归下降每个非终结符一个函数约 300 行不能需先消除左递归低断点能停在具体函数要求手写分析器、能讲清预测过程LL(1) 表驱动分析表构造 通用驱动约 200 行不能中出错只剩栈内容和表项要求打印分析栈变化序列SLR(1)项目集规范族 ACTION/GOTO 表约 600 行能高冲突要回到状态图上看要求构造 LR 分析表LR(1)/LALR(1)在 SLR 基础上再加 300~500 行能很高作为加分项不适合赶 deadline如果验收只要求能正确识别合法程序并报告非法程序递归下降性价比最高语法树直接在函数返回值里就建好了。如果验收明确要求输出分析栈的每一步变化那就只能走表驱动——这不是难度问题是输出格式问题。LR 系列在课设里最大的价值是能处理左递归代价是状态图调试起来像黑匣子一旦 ACTION 表出现移进-归约冲突你得把项目集打印出来一个个看。2.3 用脚本核对 FIRST/FOLLOW别在纸上硬推手工推 FIRST/FOLLOW 是课设里错得最隐蔽的环节推错一个集合分析表里就少一项程序只在特定输入下才崩你根本定位不到。与其反复擦纸不如写三十行脚本让机器算然后拿结果跟你纸上的推导对。# first_follow.py —— 从文法文本算 FIRST/FOLLOW用来核对手工推导 EPS ~ # 用 ~ 表示空串避免和编码打架 VN, grammar set(), {} def load(path): for raw in open(path, encodingutf-8): line raw.split(#)[0].strip() # 支持行尾注释 if not line: continue head, body [s.strip() for s in line.split(-)] VN.add(head) for alt in body.split(|): grammar.setdefault(head, []).append(alt.split()) def first_of_seq(seq): res set() for sym in seq: f FIRST[sym] if sym in VN else {sym} res | (f - {EPS}) if EPS not in f: # 遇到推不出空的符号就停 return res return res | {EPS} load(grammar.txt) FIRST {a: set() for a in VN} changed True while changed: # 不动点迭代文法带环也能收敛 changed False for head, alts in grammar.items(): for rhs in alts: add first_of_seq(rhs) - FIRST[head] if add: FIRST[head] | add changed Truegrammar.txt一行一条产生式写成E - T E这种形式多条候选式用|分隔。脚本跑完把 FIRST 表打印出来和你纸上推的逐格对——对不上的那一格八成是你漏了某个候选式能推出空串的情况。FOLLOW 的算法结构一样只是要多一步当某个非终结符后面整段都能推空时把左部的 FOLLOW 继承过来别漏了这条。提示把grammar.txt和脚本一起放进仓库改文法的时候重跑一次比事后 debug 分析表便宜得多。3. 语义分析与四元式生成符号表和作用域栈怎么设计才不返工语法树建出来只是结构对了真正决定程序跑不跑得对的是符号表和中间代码。这两块如果一开始设计得草率后面每加一个语言特性都要回头改改到最后代码会变成一团改不动的东西。3.1 符号表作用域栈 每层一张哈希表用全局mapstring, Symbol是课设里最常见的省事写法也是递归过程出错的第一嫌疑。过程第二次被调用时形参的偏移量被覆盖返回地址算错结果就变成第一次对、第二次翻倍。// symtab.cpp —— 分层作用域栈进入/退出作用域时整层压入弹出 struct Symbol { std::string name; Type type; // int / array(lo,hi) / proc(形参表) int offset; // 相对 fp 的偏移代码生成阶段直接取用 int level; // 声明所在作用域层号 }; class ScopeStack { std::vectorstd::unordered_mapstd::string, Symbol frames; public: void enter() { frames.emplace_back(); } void leave() { frames.pop_back(); } // 退出作用域整层丢弃 bool declare(const Symbol s) { auto top frames.back(); if (top.count(s.name)) return false; // 只有同层重定义才算错 top[s.name] s; return true; } const Symbol* lookup(const std::string n) { // 由内向外逐层查 for (auto it frames.rbegin(); it ! frames.rend(); it) if (it-count(n)) return it-at(n); return nullptr; } };关键点是offset在声明那一刻就算好而不是等到代码生成时再算。这么做的好处是代码生成阶段完全不需要关心作用域拿到符号直接取偏移。计算偏移时记得数组要按hi - lo 1个单元递增而不是只占一个位置——这个疏漏会导致局部数组和后面的局部变量地址重叠表现出来就是数组一赋值别的变量跟着变。3.2 类型检查插在哪一层两种主流做法一种是语法分析时顺便算递归下降里每个表达式函数返回一个带类型的节点另一种是分析完再单独遍历一遍语法树。前者代码短后者职责清。我一般推荐在表达式函数返回时就带上类型因为类型错误的位置信息在那个时刻最准确等到单独遍历时你只有节点上的行列号报错定位会漂。类型检查至少要覆盖三件事赋值左右类型可兼容、过程调用实参个数和类型对得上、数组下标是整型。第三点最容易被跳过但它是课设演示时最容易被问到的地方。3.3 控制流回填先占位再补地址if和while的四元式生成绕不开回填。核心思路是生成跳转指令时目标地址还不知道先填一个占位值把这条指令的下标挂到一条待回填链上等目标位置确定了再统一改。int emit(Op op, int a, int b, int c); // 生成一条四元式返回其下标 void backpatch(std::vectorint chain, int target) { for (int i : chain) code[i].dst target; // 链上每一处都填同一个目标 } // if E then S1 else S2 的骨架 int jf emit(JF, exprPlace, 0, 0); // 条件为假跳走目标待定 genStmt(s1); int j emit(JMP, 0, 0, 0); // S1 执行完要跳过 else backpatch(jf, nextQuad()); // 假出口 else 的第一条 genStmt(s2); backpatch(j, nextQuad()); // S1 的跳转落在整个 if 之后nextQuad()取的是下一条将要生成的四元式下标所以必须在目标指令已经 emit 之后再取。写成backpatch(jf, nextQuad() - 1)这种写法在else分支为空时会偏一条表现出来就是简单用例全过、嵌套用例全错。4. 四元式解释执行16 条指令 一个栈式虚拟机跑通全部用例四元式生成完很多课设就停在这里交上去只有一堆打印出来的中间代码。加一个两百行的解释器你就能当场演示源码进、结果出这个差距在验收环节非常明显。4.1 指令集设计16 条够用多了是负担指令集不是越全越好。课设规模的源语言下面这张表基本能覆盖全部语义再加就是给自己找活干。操作码含义dstsrc1src2ADD/SUB/MUL/DIV算术运算目标单元左操作数右操作数ASSIGN赋值目标单元源单元空LT/LE/GT/GE/EQ/NE比较结果为 0/1目标单元左操作数右操作数JMP无条件跳转目标四元式下标空空JZ为零则跳转目标四元式下标判定单元空CALL/RET过程调用与返回入口下标实参个数空LOAD/STORE数组读/写目标单元基址单元下标单元IN/OUT输入输出目标单元空空HALT结束空空空这里的dst、src1、src2存的都是相对于当前栈帧 fp 的偏移只有跳转类指令例外它们存的是四元式下标。这个区分一定要在代码里用注释标清楚混用是后面所有诡异错误的根源。4.2 栈帧布局与主循环栈帧按固定顺序排返回值、返回地址、旧 fp、形参、局部变量、临时量。临时量放在最上面表达式求值过程中只需要一路往上递增偏移不需要回收。// vm.cpp —— 四元式解释器主循环 int fp 0, sp 0, pc 0; while (pc code.size()) { Quad q code[pc]; switch (q.op) { case ADD: stack[fp q.dst] stack[fp q.src1] stack[fp q.src2]; break; case ASSIGN: stack[fp q.dst] stack[fp q.src1]; break; case JMP: pc q.dst; break; case JZ: if (stack[fp q.src1] 0) pc q.dst; break; case CALL: { stack[sp] pc; // 保存返回地址 stack[sp 1] fp; // 保存旧 fp fp sp 2; // 新栈帧基址 sp fp frameSize(q.dst); // 按被调过程的局部量大小开栈 pc q.dst; break; } case RET: { int ret stack[fp - 2]; // 取出返回地址 sp fp - 2; fp stack[fp - 1]; // 恢复调用者栈帧 pc ret; break; } default: break; } }CALL里frameSize需要知道被调过程要多少局部单元最省事的做法是在符号表里给每个过程记一个frameSize生成 CALL 时把它塞进四元式的某个字段或者另开一张表按入口下标查。别在解释器里现场遍历符号表那样每次调用都是一次线性查找递归一深就明显变慢。4.3 用例批量比对别一条条手工看输出到这一步正确性靠眼睛核对已经不现实了。写个脚本把所有用例跑一遍逐行比对期望输出失败的打前几行差异出来。# run_tests.py —— 批量跑用例并与 .out 期望文件比对 import subprocess, pathlib, sys cases sorted(pathlib.Path(tests).glob(*.src)) fail 0 for c in cases: got subprocess.run([./compiler, str(c)], capture_outputTrue, textTrue) want c.with_suffix(.out).read_text(encodingutf-8).strip() if got.stdout.strip() ! want: fail 1 print(f[FAIL] {c.name}) print( expect:, want.splitlines()[:3]) print( actual:, got.stdout.strip().splitlines()[:3]) print(f{len(cases) - fail}/{len(cases)} passed) sys.exit(1 if fail else 0)用例目录按语法特性分组命名01_assign.src、02_if_else.src、07_recursion.src失败时看文件名就知道是哪一块出问题。这套脚本还有一个隐性价值改完代码跑一次全绿你才敢继续动下一处。5. 避坑与排查课程设计里最容易翻车的五处沉默失败这些问题的共同点是——编译器不报错程序也跑完了就是结果不对。这类沉默失败占掉了课设后期绝大部分时间提前知道能省一整周。5.1 前端阶段词法与文法里的三个坑现象输入少一个右括号程序不报错而是卡住不动。原因预测分析驱动的循环里遇到分析表中没有对应表项时直接continue但读头没有前进下一轮还是同一个 token于是死循环。 解决驱动循环里加一条硬性约束——每一轮要么消费一个 token要么显式报错退出。简单做法是记录上一轮的pos本轮结束若pos未变则直接抛错。现象带//注释的用例结果全错不带注释的全对。原因词法在识别/时先匹配了单字符除法//被当成两个除号参与表达式解析后面的代码全被吞进表达式里。 解决严格遵守最长匹配先检查两个字符的组合//、、、:、都不匹配再退到单字符。这个顺序写死在opOrPunct()的第一行别分散到多个分支里。现象while循环体里只有一条语句时正常写两条语句就只执行第一条。原因文法是S - while E do S循环体只允许单个语句第二条语句被解析成了外层程序的语句。 解决把循环体改成S - while E do begin SList end或者显式引入block非终结符。改文法后记得重跑 2.3 的脚本FIRST/FOLLOW 会跟着变。5.2 后端阶段符号表与运行时的两个坑现象递归过程比如求阶乘第一次调用结果正确第二次调用结果翻倍。原因符号表用了全局单表形参偏移在每次declare时被覆盖第二次调用用的是被改过的偏移读到了上一层栈帧的数据。 解决改成作用域栈进入过程体enter()退出leave()。同时确认offset是在声明时一次性算好并写进符号表的不在运行期动态计算。现象while里嵌两层if循环退出位置偏一条指令多执行或少执行一次。原因回填时先取nextQuad()再emit占位指令目标地址比实际位置小 1或者两条待回填链被合并到同一个vector里backpatch时把不该改的指令也改了。 解决所有跳转一律先emit占位、拿到下标再在目标位置确定后统一回填每条链单独一个vector不要图省事共用。注意这五个问题里有四个在语法正确的正常输入下不会暴露建议专门准备一组畸形输入用例缺括号、非法字符、重定义、数组越界下标跑一遍能一次性筛掉大部分隐患。6. 从能跑到能讲错误恢复、常量折叠与一份自检清单能跑通用例只是及格线验收时真正拉开差距的是两件事出错时编译器说的是不是人话以及你对自己那几千行代码有没有数。6.1 错误恢复恐慌模式 同步集二十行就能加上语法分析遇到错误直接exit(1)是最省事的做法也是最容易被追问的做法。恐慌模式的核心很简单报错之后不退出而是丢弃 token 直到遇到一个肯定能重新开始的符号然后继续分析。// 同步集这些符号出现在哪里都大概率是语句边界可以安全恢复 const std::setTokenType SYNC {TK_SEMI, TK_END, TK_ELSE, TK_EOF}; void recover(TokenType expected) { reportError(expected, cur.line, cur.col); // 先报清楚期望什么、实际是什么 while (cur.type ! TK_EOF !SYNC.count(cur.type)) cur lexer.next(); // 丢弃到同步集 }同步集的选择标准是这个符号之后大概率是一条新语句的起点分号和end是最典型的两个。加上这个之后一段代码里的多个语法错误能一次全报出来而不是改一个跑一次。6.2 四元式上的两个廉价优化不用做数据流分析在emit这一层就能拿下两个优化各二十行左右常量折叠和公共子表达式消除。常量折叠在生成算术四元式前检查两个操作数是不是都来自常量表是就直接算出来生成一条ASSIGN。公共子表达式消除用一张(op, src1, src2) - dst的哈希表生成前先查命中就复用已有的结果单元。要注意折叠的边界除法遇到除数为 0 不能折直接保留原四元式让运行时去暴露浮点如果有的话折叠顺序要和运行时一致否则会出现优化前后结果差一位的玄学问题。6.3 交付前自检表检查项判定方式不通过的表现词法行列号故意写一个非法字符看报错位置报错行号恒定或为 0左递归处理表达式用例含多层括号嵌套栈溢出或直接卡死符号表作用域同名变量在内外层各声明一次内层赋值改到了外层数组偏移局部数组后面再声明一个变量改变量时数组内容跟着变递归调用阶乘、斐波那契各跑一次并二次调用第二次结果与第一次不同回填正确性while 套两层 if 的用例循环次数多一或少一批量回归run_tests.py全绿有 FAIL 但单条手工跑是过的最后一行最值得警惕单条手工跑过、批量跑挂通常是程序里有未初始化的全局状态用例之间互相污染。从那以后我每次加完新特性都强制先跑一遍全量回归再去看单条输出不然很容易被这条明明是过的这种错觉带偏。希望帮到你。本文还有配套的精品资源点击获取