简介面向编译原理课程设计与实验环节的资料包适合计算机专业学生、课程设计选题者以及需要补齐词法、语法分析实践的人使用。内容围绕一个小型编译器的完整链路展开从词法分析器到LL(1)语法分析再到LR(0)与SLR(1)方法处理简单语句如ii*i并延伸到四元式生成与汇编代码生成同时附课程设计报告便于对照实验目标理解各阶段输入输出与实现取舍。压缩包共14个文件、约557KB以cpp、c与h源码为主对应分析器与编译流程实现txt承担文法与样例说明doc为实验报告体量轻便适合在本地快速搭建与修改。已有2350人学习可作为课程设计参考底稿、实验复核材料与文法实现示例帮助读者梳理从词法到目标代码生成的步骤并借鉴报告的组织方式与结果分析思路。1. 从字符流到四元式为什么编译器要拆成三段流水线如果把“编译原理课程设计”当成一次大作业很多人第一反应是把词法分析、语法分析当成两个独立打分项各写各的。真正跑起来才发现这两段共享同一套数学骨架一端是有限自动机另一端是带栈的下推自动机中间只差“是否允许递归计数”这一条。小型编译器之所以值得亲手写一遍不是因为它能跑几个表达式而是因为它把“正则—上下文无关文法—语法制导翻译”这条抽象阶梯压缩成三百行代码就能观测的物理过程一个字符进来状态怎么跳一个记号进来栈怎么压一棵语法树回去四元式怎么发。看懂这条流水线的接口约定比背会几个算法重要得多。后面几节就按“字符怎么变成记号、记号怎么变成树、树怎么变成三地址码”的顺序把每一段的设计动机和实现细节拆开。2. 词法分析正则表达式为什么能机械地变成一台状态机写扫描器之前先要接受一个事实词法层故意把自己降级成“没有记忆”的机器。标识符有多长、括号嵌套几层词法器一概不关心它只认“当前字符加上此刻状态”决定下一步去哪。这个限制看似是能力退化实则是把“可判定性”换成了“可实现性”有限状态机没有任何回退栈所以扫描一个长度为 n 的输入严格是 O(n)不存在指数回溯的玄学。词法分析的正则描述、状态机实现、最长匹配策略三者是同一件事的三个视图缺一个都会在后期调试时翻车。2.1 从正则到 ε-NFAThompson 构造到底在保留什么Thompson 构造的核心不是“把正则画成图”而是刻意保留了 ε 边。字符边代表“消耗一个输入字符”ε 边代表“不消耗输入、只做状态跳转”。有了 ε 边三种基本运算可以拼装成固定形状连接就是前一个片段的接受态用 ε 边接到后一个片段的起始态选择就是一个新起点用两条 ε 边分别指向两个分支两个分支的接受态再用 ε 边汇到同一个新终点闭包则在片段前后各加一个状态用 ε 边构成“可以跳过”和“可以循环”两条路径。整台机器的状态数随正则长度线性增长代价是出现了大量“同一时刻可能同时处于多个状态”的情形这正是子集构造要解决的问题。常见的实现思路是用一个字典存邻接表边上用None表示 εclass NFA: def __init__(self): self.trans {} # state_id - [(char 或 None, next_state)] self.start None # 起始状态编号 self.accept None # 唯一接受状态 def build_char(c): 单个字符片段s --c-- a n, s, a NFA(), new_state(), new_state() n.trans.setdefault(s, []).append((c, a)) n.start, n.accept s, a return n def build_star(frag): 闭包片段新增 s/a三条 ε 边负责跳过与循环 n, s, a NFA(), new_state(), new_state() n.trans[s] [(None, frag.start), (None, a)] # 直接跳过 或 进入循环 n.trans[frag.accept] [(None, frag.start), (None, a)] # 再来一遍 或 结束 n.start, n.accept s, a return nbuild_char只产生一条字符边build_star产生四条边且其中三条是 ε 边。参数frag必须是已经构造好的子片段这样递归拼装能保证每个片段仍然只有一个起始态和一个接受态——这个不变量是后续子集构造能正确工作的前提整个 NFA 最后只会有一个全局接受态判定“是否接受”就退化成“当前状态集合是否包含那个编号”。2.2 子集构造与 DFA 最小化状态爆炸的真正来源子集构造做的是把“同时处于多个 NFA 状态”这件事显式化DFA 的每一个状态就是 NFA 状态集合的一个子集。算法从一个初始闭包出发对字母表中每个字符求“先走字符边、再取 ε 闭包”得到的新集合如果这个集合没出现过就入队继续扩展。它之所以能保证停机是因为幂集有限它之所以在实践中不总是爆炸是因为真正可达的子集数远小于 2^n——大多数 NFA 状态彼此互斥不会同时被激活。def epsilon_closure(states, trans): 从给定状态集合出发沿 ε 边能到达的全部状态含自身 stack, seen list(states), set(states) while stack: s stack.pop() for ch, t in trans.get(s, []): if ch is None and t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def subset_construct(nfa, alphabet): start epsilon_closure({nfa.start}, nfa.trans) dfa, queue, seen {}, [start], {start} while queue: cur queue.pop() for c in alphabet: move {t for s in cur for ch, t in nfa.trans.get(s, []) if ch c} if not move: continue nxt epsilon_closure(move, nfa.trans) dfa[(cur, c)] nxt # 转移表当前子集 字符 - 新子集 if nxt not in seen: seen.add(nxt) queue.append(nxt) return dfa, startepsilon_closure里用frozenset而不是普通集合是因为它要当字典键subset_construct返回的转移表以(子集, 字符)为键这样后续做最长匹配时可以直接查表而无需再遍历。真正需要警惕的是字母表大小如果按 Unicode 全字符集展开每个子集都要跑一遍上百个字符状态数没爆、时间先爆。常见的工程做法是把字母表压缩成等价类——所有数字归一类、所有字母归一类、其余每个字面字符各算一类这样字母表规模通常能压到几十个构造时间立刻降下来。DFA 最小化Hopcroft 或填表法是在子集构造之后做的第二道压缩把“对所有输入行为完全相同”的状态合并。它的价值不在运行速度——DFA 本来就是 O(1) 查表——而在转移表体积尤其是要把它塞进实验报告做状态图时几十个状态和十几个状态的图可读性差一个量级。2.3 最长匹配、前瞻与回退手写扫描器为什么常常不用生成器正则能描述的是“某个前缀是不是一个合法记号”但真实源码里if和iffy前缀相同、和前缀相同、123和123.45前缀相同。词法层必须选最长匹配只要当前状态还能接受并且下一个字符还能转移就继续吞直到不能吞为止然后回退到最后一个接受位置。这就是所谓的“前瞻一个字符 回退”也是自动生成的扫描器和手写扫描器都必须实现的东西。手写版通常不建自动机而是用几十个分支加一个字符指针原因很实在生成的表驱动扫描器查表逻辑统一、但错误信息难定制手写版可以在读到而字符串未闭合时立刻报“第 12 行第 5 列字符串常量缺少结束引号”而不是含糊的“invalid token”。在课程设计这种需要展示错误处理能力的场景手写扫描器的可解释性优势远大于那点性能差异。提示词法层的错误信息一定要带行列号并且列号按字符算而不是按字节算否则中文注释一出现后面的报错位置全会偏移这是最容易被忽略的一处细节。3. 语法分析FIRST/FOLLOW 与 LR 项集多一个栈换来了什么词法分析只能识别“记号是不是合法”识别不了“这串记号能不能组成一句话”。a b )里每个记号都合法但整体不是表达式。语法分析的职责就是给词法层输出的线性序列补上结构而结构一旦允许嵌套有限状态机就不够用了——因为嵌套深度无界必须有栈。LL 和 LR 的区别不在于谁更“高级”而在于栈里存的东西不同LL 的栈存的是“我期待接下来看到什么”LR 的栈存的是“我已经看到了什么现在可以归约成什么”。这个差异直接导致了两者对左递归、冲突类型、错误定位能力的迥异表现。3.1 FIRST/FOLLOWLL(1) 预测表本质是做集合分割LL(1) 的核心问题只有一个在当前非终结符 A 面前给定一个向前看记号 a我该选哪条产生式答案是查表M[A, a]。要建这张表必须回答“某条产生式展开后第一个能出现的终结符是什么”FIRST以及“如果它能推出空串那它后面紧跟的终结符是什么”FOLLOW。FIRST 集的作用是给每条产生式的“入口字符”打标签如果一个格子里同时被两条产生式占了说明这个文法在这一点上信息不足LL(1) 就不成立。def first_of_seq(seq, first, nullable): 求符号序列的 FIRST 集nullable 记录可推出 ε 的非终结符 out, all_nullable set(), True for X in seq: if X in first: out | first[X] - {ε} if X not in nullable: # 该符号不能推空后面就看不到了 all_nullable False break if all_nullable: out.add(ε) return out def build_table(grammar, first, follow, nullable): table {} for lhs, rhs in grammar.items(): for alt in rhs: f first_of_seq(alt, first, nullable) for a in f - {ε}: table[(lhs, a)] alt # 直接入口FIRST 里的终结符 if ε in f: for a in follow[lhs]: table[(lhs, a)] alt # 推空时继承 FOLLOW return tablefirst_of_seq的循环一旦遇到“不能推空的符号”就中断这是 FIRST 计算的经典陷阱A → B CB 能推空时 FIRST(A) 要包含 FIRST(C)B 不能推空时就到此为止。build_table里f - {ε}去掉空串标记ε in f那条分支处理可空产生式。实际调试时最有效的做法是把 FIRST、FOLLOW 两个表整张打印出来手工核对尤其看 FOLLOW 集里有没有漏掉开始符号的$——漏了它整个文件的最后一个记号就没有归属的格子解析器会在文件末尾神秘地报错。递归下降是 LL(1) 最直白的实现每个非终结符一个函数函数入口按查表结果选择分支。它天然支持继承属性往下传参数和综合属性往上 return 值写起来和文法几乎同构。它唯一的死穴是左递归E → E T展开就是无限调用自己必须改写成E → T EE → T E | ε。改写后语义动作的位置也跟着变加法要从“进函数时算”变成“在循环里累加”这是很多人改写完发现1-2-3算成(1-2)-3变成1-(2-3)的根源。3.2 LR(0) 项集闭包与移进-归约冲突LR 的思路是把“当前看到哪了”写进项里一条产生式A → α·β表示“我已经识别出 α期待接下来看到 β 推出的东西”。项集闭包的规则是如果点号后面是非终结符 B那么 B 的所有产生式都要以“点在开头”的形式加进来因为“等 B 出现”等价于“准备开始识别某个 B 的产生式”。def closure(items, grammar, first, nullable, lookaheadNone): items: {(产生式编号, 点位置, 向前看符)}lookaheadNone 即 LR(0) 闭包 items set(items) changed True while changed: changed False for pid, dot, la in list(items): lhs, rhs grammar[pid] if dot len(rhs) or not rhs[dot].isupper(): continue # 点已到末尾 或 后面是终结符无需展开 B, beta rhs[dot], rhs[dot 1:] for j, (l, _) in enumerate(grammar): if l ! B: continue new_la la if la is not None: # LR(1)βla 的 FIRST 决定新向前看符 new_la first_of_seq(beta [la], first, nullable) - {ε} for x in (new_la if isinstance(new_la, (set, frozenset)) else {new_la}): item (j, 0, x) if item not in items: items.add(item) changed True return items参数lookahead是区分 LR(0) 与 LR(1) 的开关传None时闭包只加点号得到的是 LR(0) 项集传入具体向前看符时新加入的项要继承由βla推出的向前看集这就是 LR(1) 的“向前看符传播”。beta [la]这个拼接是理解 LR(1) 的关键点号后面的串决定了归约时到底要看到什么记号才能动手。闭包算完就该建 GO 函数和状态转移图了。每个状态在遇到某个符号时如果点号后面正好是该符号就“移进”点号形成新项集。当某个项的点号到了末尾它就是可归约项。冲突就在这里诞生如果同一个状态里既有“点号后面是终结符 a”的移进项又有“点号在末尾且向前看符含 a”的归约项解析器就不知道该移进还是该归约——这就是移进-归约冲突。经典的悬空 else 就是它if E then S与if E then S else S在then S之后看到else既可以归约成内层 if也可以移进给外层 if。LR(0) 完全不看向前看符所以冲突最频繁SLR(1) 的补丁是“归约时只看 FOLLOW 集”只要 FOLLOW 里没有那个引发冲突的终结符就没事LR(1) 的补丁是“每个项自带精确的向前看符”能区分的场景更多代价是状态数暴涨同一个项因为向前看符不同被拆成好几个状态LALR(1) 则是折中把 LR(1) 里“核心项相同、只有向前看符不同”的状态合并状态数回到 LR(0) 的量级冲突数基本接近 LR(1)。3.3 SLR(1)/LR(1)/LALR(1) 的取舍向前看符号放在哪这三者的差别可以一句话概括向前看符号的作用域是“整个非终结符”SLR用 FOLLOW、“单个项”LR(1)随项携带还是“合并后的项集”LALR把同核心的向前看符取并集。课程设计里最常被问的问题是“为什么我的 SLR 有冲突换 LALR 就没了”答案往往是 FOLLOW 集太粗某个非终结符在所有上下文里后面都可能跟某个终结符但当前这个状态根本不在那个上下文里SLR 却依然允许在此归约导致冲突。LALR 把向前看符绑定到项上相当于给每个状态加了局部上下文冲突自然消失。代价是合并带来的“归约-归约冲突”风险两个本不相同核心的项集合并后可能同时出现两条可归约产生式且向前看符有交集此时解析器无法决定用哪条产生式归约。这类冲突不能靠加向前看符解决只能改文法。选择哪种方案实际取决于三件事文法本身有多“难”表达式优先级、嵌套语句、可空产生式实验报告需不需要展示状态图LR(1) 的状态数常常是 LALR 的两三倍画出来密密麻麻错误恢复想做到什么粒度。初学阶段用 SLR 快速跑通报告里专门讨论“某状态为什么冲突、LALR 如何消解”比一上来硬写 LR(1) 然后卡在状态爆炸里更有说服力。4. 语义落地语法制导翻译怎么把语法树压成四元式语法分析只回答了“这句话结构对不对”没回答“这句话是什么意思”。语义层要做三件事查符号表确认名字存在、检查类型能不能这么用、把树形结构线性化成中间代码。这三件事在实现上高度耦合——你不可能先生成一堆四元式再回头补类型检查因为类型决定了该发ADD还是FADD也决定了临时变量该声明成什么宽度。所以常见的做法是把语义动作直接挂在文法产生式上边归约边发码这就是语法制导翻译。4.1 属性文法综合属性与继承属性怎么落到递归函数返回值上属性文法在纸面上是“给文法符号挂属性、给产生式挂计算规则”落到代码里就是递归下降函数的参数与返回值。综合属性是“子节点的值汇总到父节点”天然对应return继承属性是“父节点的上下文传给子节点”天然对应函数入参。比如表达式E → E1 TE1和T的值是综合属性E的类型要取两者的公共类型这也是综合的而声明int x y;里y需要知道的“期望类型”是从左边继承下去的这就是继承属性。这个对应关系一旦理清很多“为什么我的语义动作位置不对”的问题就自解了。LL 分析里产生式右部的符号从左到右被识别所以“需要前面结果的动作”要写在后面“需要向下传上下文的动作”要写在最前面。LR 分析里所有动作都在归约时执行此时右部所有符号的属性都已就绪写起来更统一但如果某个属性需要在右部符号识别之前就确定比如给变量分配存储位置就得用“标记非终结符”在中间埋一个空产生式靠它的归约时机插入动作。4.2 符号表作用域链、哈希桶与“先声明后使用”的检查时机符号表是语义层的中枢。最常见也最够用的结构是“哈希表 父指针”构成的作用域链每进入一个块函数体、{}复合语句、for的初始化部分就新建一层查找时从当前层往上走插入时只插当前层。这样“内层遮蔽外层”天然成立退出块时把这一层整个丢掉就等于销毁了局部变量。class Scope: def __init__(self, parentNone, kindblock): self.table {} # name - {type:..., kind:..., offset:...} self.parent parent self.kind kind # global / function / block def declare(self, name, info): if name in self.table: # 同层重复声明直接报错 raise SemanticError(f重复定义: {name}) self.table[name] info def lookup(self, name): s self while s is not None: if name in s.table: return s.table[name] s s.parent return None # 未声明就使用 def lookup_current(self, name): return self.table.get(name) # 只查本层用于检测遮蔽declare里那次“同层查重”是必须的C 语言允许内层遮蔽外层但不允许同一层重复定义漏掉这个检查int a; int a;就能通过编译后面的偏移分配会直接对不上。lookup从内往外走返回第一个命中的符号这实现了“最近的声明生效”。lookup_current单独存在是为了在报错时区分“重复定义”和“遮蔽外层”两者的错误提示完全不同。一个容易被忽略的时序问题是“先声明后使用”到底在哪一刻检查。如果放在解析完整个函数体之后统一检查那x 1; int x;也会通过因为x最终确实声明了。正确做法是在解析到标识符引用的那一刻就查表查不到立刻报错。这就是为什么语义动作必须和语法分析同步执行而不能等整棵树建完再遍历——后者虽然也能实现但错误位置会丢失报错只能说“某处有未定义变量”没有行列号。4.3 四元式与临时变量为什么中间代码要三地址中间代码的形式有很多种课程设计里最常选四元式(op, arg1, arg2, result)本质是三地址码的一种紧凑表示。选三地址而不是直接生成目标机器码是因为三地址码把“求值顺序”和“寄存器分配”解耦了t1 a b明确了运算和结果但没规定用哪个寄存器、什么时候溢出这些留给后面的优化和目标代码生成阶段。class QuadGen: def __init__(self): self.quads [] # [(op, arg1, arg2, result)] self.temp_id 0 # 临时变量计数器 def new_temp(self): self.temp_id 1 return ft{self.temp_id} # 形如 t1、t2后续可映射到寄存器或栈槽 def emit(self, op, a1, a2, res): self.quads.append((op, a1, a2, res)) def gen_binop(self, op, left, right): t self.new_temp() self.emit(op, left, right, t) # 二元运算两个源操作数 一个临时变量 return tnew_temp的编号单调递增不做复用这是有意的复用会让调试时的四元式序列难以对照源码而临时变量数量在课程设计的规模下根本不成问题。gen_binop返回临时变量名这样上层表达式可以继续把它当作操作数使用形成嵌套求值链。真正的坑在表达式语句的归约上a b;求值完产生一个临时变量如果直接丢掉四元式里就多出一条毫无意义的赋值正确处理是只在结果被使用时才保留或者在语句层显式丢弃。另一个坑是布尔表达式的短路求值a b不能先算完a再算b再合并必须生成条件跳转def gen_and(self, gen_left, gen_right, label_false): a b 的短路a 为假直接跳到 label_false不算 b t1 gen_left() self.emit(jnz, t1, -, L_continue) # a 为真继续算 b self.emit(jmp, -, -, label_false) # a 为假短路 self.emit(label, -, -, L_continue) return gen_right()这段代码里jnz的语义是“第一操作数非零则跳到第四元”-是占位符表示该位置无参数。如果忽略短路把当成普通二元运算0 (1/0)就会真的触发除零这是语义层最经典的血泪经验之一。5. 常见问题排查词法与语法分析器最容易翻车的五处细节课程设计的调试时间八成花在这几类问题上它们的共同点是“程序不崩、只是结果微妙地不对”比直接报错更难定位。5.1 词法阶段的坑现象一123abc被拆成123和abc两个记号后面的错误位置整体偏移报错行号对不上源码。原因是最长匹配的终止条件写错了扫描器在数字状态里看到字母时应该判定“数字常量结束”但如果实现里“只要当前状态是接受态就返回”就会在读到1时就返回把23abc留给下一轮。解决是把“接受态”和“终止态”分开一边吞字符一边记录“最近一次处在接受态时的位置和状态”直到某次转移失败才回退到那个记录点同时把指针停在该记号之后。这样123abc会被完整识别为数字常量然后在语法层报“数字常量后紧跟标识符”这类更准确的错误。现象二未闭合的块注释把整个文件剩余部分吞掉程序最后只报“意外的文件结束”。原因是注释在状态机里被建模成“进入注释态后一直自环直到遇到结束符”但没有为文件结束设置出口。解决是在扫描主循环里对每次状态跳转检查是否读到 EOF如果此时仍处于注释态、字符串态这类“必须显式闭合”的状态就抛出“第 X 行注释未闭合”的专门错误而不是让循环自然退出。现象三中文字符出现在标识符或字符串里时列号计算整体偏移。原因是按字节索引算列号一个汉字占三个字节报错位置就差了两位。解决是扫描器内部统一按码点推进指针列号按码点计数如果源码以字节流读入就在入口处先解码成字符数组再扫描。5.2 语法与语义阶段的坑现象四递归下降解析器读到左递归文法时栈溢出或者在没有递归深度限制的容器里越来越慢。原因很直接E → E T展开第一步就又要解析E没有任何消耗输入的进展形成死循环。解决是把左递归改写成右递归加循环E → T { T }用while累积左结合的结果。改写时注意语义动作的顺序——每次循环里先取右操作数再用“当前累积值”和它做运算这样1-2-3才会算成(1-2)-3。现象五if 分支里声明的变量在分支结束后依然能被查到类型检查放过了本应报错的引用。原因是符号表只压栈不弹栈进入复合语句时新建了作用域退出时忘记把当前层恢复成父层。解决是把“进入作用域”和“退出作用域”成对写在一个包装函数里用try/finally保证即使解析过程中抛出异常作用域也能正确回退或者在 AST 遍历时给每种节点配一个leave钩子节点处理完必然触发。注意错误恢复策略要早定。只报第一个错误最省事但学生答辩时最常被追问“如果源码有十个错你怎么一次性告诉用户”。常见的折中做法是词法错误直接跳过该字符继续扫描语法错误在同步集合如;、}处恢复这样一次编译能报出多个错误而不至于连篇累牍。6. 实验报告与可验证性怎么证明这套编译器不是“看着像对”小型编译器最容易出现的自欺是拿几个简单表达式跑通就认为整条流水线正确。真正能说明问题的是一组覆盖边界条件的测试用例矩阵以及在报告里记录“每个阶段的可观测量”。词法阶段可以记录状态数、DFA 转移表大小、最长匹配回退次数语法阶段可以记录状态数、冲突数、每个冲突状态涉及的产生式编号语义阶段可以记录符号表最大深度、四元式条数、临时变量数。这些数字比“运行成功”四个字有说服力得多也让报告从“我做了什么”变成“我观测到了什么”。测试用例的设计要按维度而不是按数量堆。下面这张表是我习惯在报告里给出的最小集合维度用例示例期望行为词法边界最长标识符、数字后紧跟字母、未闭合字符串精确定位行列号并给出专门错误码嵌套结构三层括号、嵌套 if-else、嵌套函数调用语法树深度与栈深一致无溢出优先级与结合性a-b-c、abc、ab*c四元式顺序体现左结合与优先级短路求值0 f()、1 || f()f()不出现在四元式序列中作用域内层遮蔽外层、分支内声明、块内重复声明遮蔽合法、重复声明报错、越界引用报错这张表的价值在于每一条都对应一个可以在报告里贴出的“实际输出片段”而不是靠嘴说。举例来说短路求值那条报告里应该直接贴出0 f()生成的完整四元式列表读者一眼就能看到f()的调用四元式确实缺席——这比写三段解释都管用。在这套设计里最大的取舍是“要不要为了报告好看而追求 LR(1) 的完整实现”。我的经验是如果你的文法里存在典型的悬空 else 或表达式优先级冲突用 SLR 起步、在报告里专门分析冲突状态、再给出 LALR 的消解方案这条路径既有深度又跑得通一上来硬啃 LR(1) 的完整项集族往往把时间全耗在状态爆炸的可视化上语义层反而草草了事。另一个取舍是中间代码的形式四元式比三元式多一个 result 字段看起来冗余但它让“结果”永远是一个可以引用的名字后续做常量折叠和公共子表达式消除时少一层间接寻址的麻烦。从那以后我每次带人做这类课程设计都强制要求先写一张“阶段可观测量清单”每完成一个阶段就填一次数字数字对不上就回去查而不是等到最后跑大用例时靠猜。有了这份清单实验报告自然就有了骨架调试也不再是黑匣子里碰运气。这份资源把词法、语法、语义三段拆成了可以单独编译运行的模块配上覆盖上表各维度的测试用例和一份完整的实验报告自己从头跑一遍、对着中间结果核一遍比读十篇讲原理的文章都扎实。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/29 11:45:38 · 阅读 1.2k 从词法分析到四元式：小型编译器三段流水线实现与调试
简介面向编译原理课程设计与实验环节的资料包适合计算机专业学生、课程设计选题者以及需要补齐词法、语法分析实践的人使用。内容围绕一个小型编译器的完整链路展开从词法分析器到LL(1)语法分析再到LR(0)与SLR(1)方法处理简单语句如ii*i并延伸到四元式生成与汇编代码生成同时附课程设计报告便于对照实验目标理解各阶段输入输出与实现取舍。压缩包共14个文件、约557KB以cpp、c与h源码为主对应分析器与编译流程实现txt承担文法与样例说明doc为实验报告体量轻便适合在本地快速搭建与修改。已有2350人学习可作为课程设计参考底稿、实验复核材料与文法实现示例帮助读者梳理从词法到目标代码生成的步骤并借鉴报告的组织方式与结果分析思路。1. 从字符流到四元式为什么编译器要拆成三段流水线如果把“编译原理课程设计”当成一次大作业很多人第一反应是把词法分析、语法分析当成两个独立打分项各写各的。真正跑起来才发现这两段共享同一套数学骨架一端是有限自动机另一端是带栈的下推自动机中间只差“是否允许递归计数”这一条。小型编译器之所以值得亲手写一遍不是因为它能跑几个表达式而是因为它把“正则—上下文无关文法—语法制导翻译”这条抽象阶梯压缩成三百行代码就能观测的物理过程一个字符进来状态怎么跳一个记号进来栈怎么压一棵语法树回去四元式怎么发。看懂这条流水线的接口约定比背会几个算法重要得多。后面几节就按“字符怎么变成记号、记号怎么变成树、树怎么变成三地址码”的顺序把每一段的设计动机和实现细节拆开。2. 词法分析正则表达式为什么能机械地变成一台状态机写扫描器之前先要接受一个事实词法层故意把自己降级成“没有记忆”的机器。标识符有多长、括号嵌套几层词法器一概不关心它只认“当前字符加上此刻状态”决定下一步去哪。这个限制看似是能力退化实则是把“可判定性”换成了“可实现性”有限状态机没有任何回退栈所以扫描一个长度为 n 的输入严格是 O(n)不存在指数回溯的玄学。词法分析的正则描述、状态机实现、最长匹配策略三者是同一件事的三个视图缺一个都会在后期调试时翻车。2.1 从正则到 ε-NFAThompson 构造到底在保留什么Thompson 构造的核心不是“把正则画成图”而是刻意保留了 ε 边。字符边代表“消耗一个输入字符”ε 边代表“不消耗输入、只做状态跳转”。有了 ε 边三种基本运算可以拼装成固定形状连接就是前一个片段的接受态用 ε 边接到后一个片段的起始态选择就是一个新起点用两条 ε 边分别指向两个分支两个分支的接受态再用 ε 边汇到同一个新终点闭包则在片段前后各加一个状态用 ε 边构成“可以跳过”和“可以循环”两条路径。整台机器的状态数随正则长度线性增长代价是出现了大量“同一时刻可能同时处于多个状态”的情形这正是子集构造要解决的问题。常见的实现思路是用一个字典存邻接表边上用None表示 εclass NFA: def __init__(self): self.trans {} # state_id - [(char 或 None, next_state)] self.start None # 起始状态编号 self.accept None # 唯一接受状态 def build_char(c): 单个字符片段s --c-- a n, s, a NFA(), new_state(), new_state() n.trans.setdefault(s, []).append((c, a)) n.start, n.accept s, a return n def build_star(frag): 闭包片段新增 s/a三条 ε 边负责跳过与循环 n, s, a NFA(), new_state(), new_state() n.trans[s] [(None, frag.start), (None, a)] # 直接跳过 或 进入循环 n.trans[frag.accept] [(None, frag.start), (None, a)] # 再来一遍 或 结束 n.start, n.accept s, a return nbuild_char只产生一条字符边build_star产生四条边且其中三条是 ε 边。参数frag必须是已经构造好的子片段这样递归拼装能保证每个片段仍然只有一个起始态和一个接受态——这个不变量是后续子集构造能正确工作的前提整个 NFA 最后只会有一个全局接受态判定“是否接受”就退化成“当前状态集合是否包含那个编号”。2.2 子集构造与 DFA 最小化状态爆炸的真正来源子集构造做的是把“同时处于多个 NFA 状态”这件事显式化DFA 的每一个状态就是 NFA 状态集合的一个子集。算法从一个初始闭包出发对字母表中每个字符求“先走字符边、再取 ε 闭包”得到的新集合如果这个集合没出现过就入队继续扩展。它之所以能保证停机是因为幂集有限它之所以在实践中不总是爆炸是因为真正可达的子集数远小于 2^n——大多数 NFA 状态彼此互斥不会同时被激活。def epsilon_closure(states, trans): 从给定状态集合出发沿 ε 边能到达的全部状态含自身 stack, seen list(states), set(states) while stack: s stack.pop() for ch, t in trans.get(s, []): if ch is None and t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def subset_construct(nfa, alphabet): start epsilon_closure({nfa.start}, nfa.trans) dfa, queue, seen {}, [start], {start} while queue: cur queue.pop() for c in alphabet: move {t for s in cur for ch, t in nfa.trans.get(s, []) if ch c} if not move: continue nxt epsilon_closure(move, nfa.trans) dfa[(cur, c)] nxt # 转移表当前子集 字符 - 新子集 if nxt not in seen: seen.add(nxt) queue.append(nxt) return dfa, startepsilon_closure里用frozenset而不是普通集合是因为它要当字典键subset_construct返回的转移表以(子集, 字符)为键这样后续做最长匹配时可以直接查表而无需再遍历。真正需要警惕的是字母表大小如果按 Unicode 全字符集展开每个子集都要跑一遍上百个字符状态数没爆、时间先爆。常见的工程做法是把字母表压缩成等价类——所有数字归一类、所有字母归一类、其余每个字面字符各算一类这样字母表规模通常能压到几十个构造时间立刻降下来。DFA 最小化Hopcroft 或填表法是在子集构造之后做的第二道压缩把“对所有输入行为完全相同”的状态合并。它的价值不在运行速度——DFA 本来就是 O(1) 查表——而在转移表体积尤其是要把它塞进实验报告做状态图时几十个状态和十几个状态的图可读性差一个量级。2.3 最长匹配、前瞻与回退手写扫描器为什么常常不用生成器正则能描述的是“某个前缀是不是一个合法记号”但真实源码里if和iffy前缀相同、和前缀相同、123和123.45前缀相同。词法层必须选最长匹配只要当前状态还能接受并且下一个字符还能转移就继续吞直到不能吞为止然后回退到最后一个接受位置。这就是所谓的“前瞻一个字符 回退”也是自动生成的扫描器和手写扫描器都必须实现的东西。手写版通常不建自动机而是用几十个分支加一个字符指针原因很实在生成的表驱动扫描器查表逻辑统一、但错误信息难定制手写版可以在读到而字符串未闭合时立刻报“第 12 行第 5 列字符串常量缺少结束引号”而不是含糊的“invalid token”。在课程设计这种需要展示错误处理能力的场景手写扫描器的可解释性优势远大于那点性能差异。提示词法层的错误信息一定要带行列号并且列号按字符算而不是按字节算否则中文注释一出现后面的报错位置全会偏移这是最容易被忽略的一处细节。3. 语法分析FIRST/FOLLOW 与 LR 项集多一个栈换来了什么词法分析只能识别“记号是不是合法”识别不了“这串记号能不能组成一句话”。a b )里每个记号都合法但整体不是表达式。语法分析的职责就是给词法层输出的线性序列补上结构而结构一旦允许嵌套有限状态机就不够用了——因为嵌套深度无界必须有栈。LL 和 LR 的区别不在于谁更“高级”而在于栈里存的东西不同LL 的栈存的是“我期待接下来看到什么”LR 的栈存的是“我已经看到了什么现在可以归约成什么”。这个差异直接导致了两者对左递归、冲突类型、错误定位能力的迥异表现。3.1 FIRST/FOLLOWLL(1) 预测表本质是做集合分割LL(1) 的核心问题只有一个在当前非终结符 A 面前给定一个向前看记号 a我该选哪条产生式答案是查表M[A, a]。要建这张表必须回答“某条产生式展开后第一个能出现的终结符是什么”FIRST以及“如果它能推出空串那它后面紧跟的终结符是什么”FOLLOW。FIRST 集的作用是给每条产生式的“入口字符”打标签如果一个格子里同时被两条产生式占了说明这个文法在这一点上信息不足LL(1) 就不成立。def first_of_seq(seq, first, nullable): 求符号序列的 FIRST 集nullable 记录可推出 ε 的非终结符 out, all_nullable set(), True for X in seq: if X in first: out | first[X] - {ε} if X not in nullable: # 该符号不能推空后面就看不到了 all_nullable False break if all_nullable: out.add(ε) return out def build_table(grammar, first, follow, nullable): table {} for lhs, rhs in grammar.items(): for alt in rhs: f first_of_seq(alt, first, nullable) for a in f - {ε}: table[(lhs, a)] alt # 直接入口FIRST 里的终结符 if ε in f: for a in follow[lhs]: table[(lhs, a)] alt # 推空时继承 FOLLOW return tablefirst_of_seq的循环一旦遇到“不能推空的符号”就中断这是 FIRST 计算的经典陷阱A → B CB 能推空时 FIRST(A) 要包含 FIRST(C)B 不能推空时就到此为止。build_table里f - {ε}去掉空串标记ε in f那条分支处理可空产生式。实际调试时最有效的做法是把 FIRST、FOLLOW 两个表整张打印出来手工核对尤其看 FOLLOW 集里有没有漏掉开始符号的$——漏了它整个文件的最后一个记号就没有归属的格子解析器会在文件末尾神秘地报错。递归下降是 LL(1) 最直白的实现每个非终结符一个函数函数入口按查表结果选择分支。它天然支持继承属性往下传参数和综合属性往上 return 值写起来和文法几乎同构。它唯一的死穴是左递归E → E T展开就是无限调用自己必须改写成E → T EE → T E | ε。改写后语义动作的位置也跟着变加法要从“进函数时算”变成“在循环里累加”这是很多人改写完发现1-2-3算成(1-2)-3变成1-(2-3)的根源。3.2 LR(0) 项集闭包与移进-归约冲突LR 的思路是把“当前看到哪了”写进项里一条产生式A → α·β表示“我已经识别出 α期待接下来看到 β 推出的东西”。项集闭包的规则是如果点号后面是非终结符 B那么 B 的所有产生式都要以“点在开头”的形式加进来因为“等 B 出现”等价于“准备开始识别某个 B 的产生式”。def closure(items, grammar, first, nullable, lookaheadNone): items: {(产生式编号, 点位置, 向前看符)}lookaheadNone 即 LR(0) 闭包 items set(items) changed True while changed: changed False for pid, dot, la in list(items): lhs, rhs grammar[pid] if dot len(rhs) or not rhs[dot].isupper(): continue # 点已到末尾 或 后面是终结符无需展开 B, beta rhs[dot], rhs[dot 1:] for j, (l, _) in enumerate(grammar): if l ! B: continue new_la la if la is not None: # LR(1)βla 的 FIRST 决定新向前看符 new_la first_of_seq(beta [la], first, nullable) - {ε} for x in (new_la if isinstance(new_la, (set, frozenset)) else {new_la}): item (j, 0, x) if item not in items: items.add(item) changed True return items参数lookahead是区分 LR(0) 与 LR(1) 的开关传None时闭包只加点号得到的是 LR(0) 项集传入具体向前看符时新加入的项要继承由βla推出的向前看集这就是 LR(1) 的“向前看符传播”。beta [la]这个拼接是理解 LR(1) 的关键点号后面的串决定了归约时到底要看到什么记号才能动手。闭包算完就该建 GO 函数和状态转移图了。每个状态在遇到某个符号时如果点号后面正好是该符号就“移进”点号形成新项集。当某个项的点号到了末尾它就是可归约项。冲突就在这里诞生如果同一个状态里既有“点号后面是终结符 a”的移进项又有“点号在末尾且向前看符含 a”的归约项解析器就不知道该移进还是该归约——这就是移进-归约冲突。经典的悬空 else 就是它if E then S与if E then S else S在then S之后看到else既可以归约成内层 if也可以移进给外层 if。LR(0) 完全不看向前看符所以冲突最频繁SLR(1) 的补丁是“归约时只看 FOLLOW 集”只要 FOLLOW 里没有那个引发冲突的终结符就没事LR(1) 的补丁是“每个项自带精确的向前看符”能区分的场景更多代价是状态数暴涨同一个项因为向前看符不同被拆成好几个状态LALR(1) 则是折中把 LR(1) 里“核心项相同、只有向前看符不同”的状态合并状态数回到 LR(0) 的量级冲突数基本接近 LR(1)。3.3 SLR(1)/LR(1)/LALR(1) 的取舍向前看符号放在哪这三者的差别可以一句话概括向前看符号的作用域是“整个非终结符”SLR用 FOLLOW、“单个项”LR(1)随项携带还是“合并后的项集”LALR把同核心的向前看符取并集。课程设计里最常被问的问题是“为什么我的 SLR 有冲突换 LALR 就没了”答案往往是 FOLLOW 集太粗某个非终结符在所有上下文里后面都可能跟某个终结符但当前这个状态根本不在那个上下文里SLR 却依然允许在此归约导致冲突。LALR 把向前看符绑定到项上相当于给每个状态加了局部上下文冲突自然消失。代价是合并带来的“归约-归约冲突”风险两个本不相同核心的项集合并后可能同时出现两条可归约产生式且向前看符有交集此时解析器无法决定用哪条产生式归约。这类冲突不能靠加向前看符解决只能改文法。选择哪种方案实际取决于三件事文法本身有多“难”表达式优先级、嵌套语句、可空产生式实验报告需不需要展示状态图LR(1) 的状态数常常是 LALR 的两三倍画出来密密麻麻错误恢复想做到什么粒度。初学阶段用 SLR 快速跑通报告里专门讨论“某状态为什么冲突、LALR 如何消解”比一上来硬写 LR(1) 然后卡在状态爆炸里更有说服力。4. 语义落地语法制导翻译怎么把语法树压成四元式语法分析只回答了“这句话结构对不对”没回答“这句话是什么意思”。语义层要做三件事查符号表确认名字存在、检查类型能不能这么用、把树形结构线性化成中间代码。这三件事在实现上高度耦合——你不可能先生成一堆四元式再回头补类型检查因为类型决定了该发ADD还是FADD也决定了临时变量该声明成什么宽度。所以常见的做法是把语义动作直接挂在文法产生式上边归约边发码这就是语法制导翻译。4.1 属性文法综合属性与继承属性怎么落到递归函数返回值上属性文法在纸面上是“给文法符号挂属性、给产生式挂计算规则”落到代码里就是递归下降函数的参数与返回值。综合属性是“子节点的值汇总到父节点”天然对应return继承属性是“父节点的上下文传给子节点”天然对应函数入参。比如表达式E → E1 TE1和T的值是综合属性E的类型要取两者的公共类型这也是综合的而声明int x y;里y需要知道的“期望类型”是从左边继承下去的这就是继承属性。这个对应关系一旦理清很多“为什么我的语义动作位置不对”的问题就自解了。LL 分析里产生式右部的符号从左到右被识别所以“需要前面结果的动作”要写在后面“需要向下传上下文的动作”要写在最前面。LR 分析里所有动作都在归约时执行此时右部所有符号的属性都已就绪写起来更统一但如果某个属性需要在右部符号识别之前就确定比如给变量分配存储位置就得用“标记非终结符”在中间埋一个空产生式靠它的归约时机插入动作。4.2 符号表作用域链、哈希桶与“先声明后使用”的检查时机符号表是语义层的中枢。最常见也最够用的结构是“哈希表 父指针”构成的作用域链每进入一个块函数体、{}复合语句、for的初始化部分就新建一层查找时从当前层往上走插入时只插当前层。这样“内层遮蔽外层”天然成立退出块时把这一层整个丢掉就等于销毁了局部变量。class Scope: def __init__(self, parentNone, kindblock): self.table {} # name - {type:..., kind:..., offset:...} self.parent parent self.kind kind # global / function / block def declare(self, name, info): if name in self.table: # 同层重复声明直接报错 raise SemanticError(f重复定义: {name}) self.table[name] info def lookup(self, name): s self while s is not None: if name in s.table: return s.table[name] s s.parent return None # 未声明就使用 def lookup_current(self, name): return self.table.get(name) # 只查本层用于检测遮蔽declare里那次“同层查重”是必须的C 语言允许内层遮蔽外层但不允许同一层重复定义漏掉这个检查int a; int a;就能通过编译后面的偏移分配会直接对不上。lookup从内往外走返回第一个命中的符号这实现了“最近的声明生效”。lookup_current单独存在是为了在报错时区分“重复定义”和“遮蔽外层”两者的错误提示完全不同。一个容易被忽略的时序问题是“先声明后使用”到底在哪一刻检查。如果放在解析完整个函数体之后统一检查那x 1; int x;也会通过因为x最终确实声明了。正确做法是在解析到标识符引用的那一刻就查表查不到立刻报错。这就是为什么语义动作必须和语法分析同步执行而不能等整棵树建完再遍历——后者虽然也能实现但错误位置会丢失报错只能说“某处有未定义变量”没有行列号。4.3 四元式与临时变量为什么中间代码要三地址中间代码的形式有很多种课程设计里最常选四元式(op, arg1, arg2, result)本质是三地址码的一种紧凑表示。选三地址而不是直接生成目标机器码是因为三地址码把“求值顺序”和“寄存器分配”解耦了t1 a b明确了运算和结果但没规定用哪个寄存器、什么时候溢出这些留给后面的优化和目标代码生成阶段。class QuadGen: def __init__(self): self.quads [] # [(op, arg1, arg2, result)] self.temp_id 0 # 临时变量计数器 def new_temp(self): self.temp_id 1 return ft{self.temp_id} # 形如 t1、t2后续可映射到寄存器或栈槽 def emit(self, op, a1, a2, res): self.quads.append((op, a1, a2, res)) def gen_binop(self, op, left, right): t self.new_temp() self.emit(op, left, right, t) # 二元运算两个源操作数 一个临时变量 return tnew_temp的编号单调递增不做复用这是有意的复用会让调试时的四元式序列难以对照源码而临时变量数量在课程设计的规模下根本不成问题。gen_binop返回临时变量名这样上层表达式可以继续把它当作操作数使用形成嵌套求值链。真正的坑在表达式语句的归约上a b;求值完产生一个临时变量如果直接丢掉四元式里就多出一条毫无意义的赋值正确处理是只在结果被使用时才保留或者在语句层显式丢弃。另一个坑是布尔表达式的短路求值a b不能先算完a再算b再合并必须生成条件跳转def gen_and(self, gen_left, gen_right, label_false): a b 的短路a 为假直接跳到 label_false不算 b t1 gen_left() self.emit(jnz, t1, -, L_continue) # a 为真继续算 b self.emit(jmp, -, -, label_false) # a 为假短路 self.emit(label, -, -, L_continue) return gen_right()这段代码里jnz的语义是“第一操作数非零则跳到第四元”-是占位符表示该位置无参数。如果忽略短路把当成普通二元运算0 (1/0)就会真的触发除零这是语义层最经典的血泪经验之一。5. 常见问题排查词法与语法分析器最容易翻车的五处细节课程设计的调试时间八成花在这几类问题上它们的共同点是“程序不崩、只是结果微妙地不对”比直接报错更难定位。5.1 词法阶段的坑现象一123abc被拆成123和abc两个记号后面的错误位置整体偏移报错行号对不上源码。原因是最长匹配的终止条件写错了扫描器在数字状态里看到字母时应该判定“数字常量结束”但如果实现里“只要当前状态是接受态就返回”就会在读到1时就返回把23abc留给下一轮。解决是把“接受态”和“终止态”分开一边吞字符一边记录“最近一次处在接受态时的位置和状态”直到某次转移失败才回退到那个记录点同时把指针停在该记号之后。这样123abc会被完整识别为数字常量然后在语法层报“数字常量后紧跟标识符”这类更准确的错误。现象二未闭合的块注释把整个文件剩余部分吞掉程序最后只报“意外的文件结束”。原因是注释在状态机里被建模成“进入注释态后一直自环直到遇到结束符”但没有为文件结束设置出口。解决是在扫描主循环里对每次状态跳转检查是否读到 EOF如果此时仍处于注释态、字符串态这类“必须显式闭合”的状态就抛出“第 X 行注释未闭合”的专门错误而不是让循环自然退出。现象三中文字符出现在标识符或字符串里时列号计算整体偏移。原因是按字节索引算列号一个汉字占三个字节报错位置就差了两位。解决是扫描器内部统一按码点推进指针列号按码点计数如果源码以字节流读入就在入口处先解码成字符数组再扫描。5.2 语法与语义阶段的坑现象四递归下降解析器读到左递归文法时栈溢出或者在没有递归深度限制的容器里越来越慢。原因很直接E → E T展开第一步就又要解析E没有任何消耗输入的进展形成死循环。解决是把左递归改写成右递归加循环E → T { T }用while累积左结合的结果。改写时注意语义动作的顺序——每次循环里先取右操作数再用“当前累积值”和它做运算这样1-2-3才会算成(1-2)-3。现象五if 分支里声明的变量在分支结束后依然能被查到类型检查放过了本应报错的引用。原因是符号表只压栈不弹栈进入复合语句时新建了作用域退出时忘记把当前层恢复成父层。解决是把“进入作用域”和“退出作用域”成对写在一个包装函数里用try/finally保证即使解析过程中抛出异常作用域也能正确回退或者在 AST 遍历时给每种节点配一个leave钩子节点处理完必然触发。注意错误恢复策略要早定。只报第一个错误最省事但学生答辩时最常被追问“如果源码有十个错你怎么一次性告诉用户”。常见的折中做法是词法错误直接跳过该字符继续扫描语法错误在同步集合如;、}处恢复这样一次编译能报出多个错误而不至于连篇累牍。6. 实验报告与可验证性怎么证明这套编译器不是“看着像对”小型编译器最容易出现的自欺是拿几个简单表达式跑通就认为整条流水线正确。真正能说明问题的是一组覆盖边界条件的测试用例矩阵以及在报告里记录“每个阶段的可观测量”。词法阶段可以记录状态数、DFA 转移表大小、最长匹配回退次数语法阶段可以记录状态数、冲突数、每个冲突状态涉及的产生式编号语义阶段可以记录符号表最大深度、四元式条数、临时变量数。这些数字比“运行成功”四个字有说服力得多也让报告从“我做了什么”变成“我观测到了什么”。测试用例的设计要按维度而不是按数量堆。下面这张表是我习惯在报告里给出的最小集合维度用例示例期望行为词法边界最长标识符、数字后紧跟字母、未闭合字符串精确定位行列号并给出专门错误码嵌套结构三层括号、嵌套 if-else、嵌套函数调用语法树深度与栈深一致无溢出优先级与结合性a-b-c、abc、ab*c四元式顺序体现左结合与优先级短路求值0 f()、1 || f()f()不出现在四元式序列中作用域内层遮蔽外层、分支内声明、块内重复声明遮蔽合法、重复声明报错、越界引用报错这张表的价值在于每一条都对应一个可以在报告里贴出的“实际输出片段”而不是靠嘴说。举例来说短路求值那条报告里应该直接贴出0 f()生成的完整四元式列表读者一眼就能看到f()的调用四元式确实缺席——这比写三段解释都管用。在这套设计里最大的取舍是“要不要为了报告好看而追求 LR(1) 的完整实现”。我的经验是如果你的文法里存在典型的悬空 else 或表达式优先级冲突用 SLR 起步、在报告里专门分析冲突状态、再给出 LALR 的消解方案这条路径既有深度又跑得通一上来硬啃 LR(1) 的完整项集族往往把时间全耗在状态爆炸的可视化上语义层反而草草了事。另一个取舍是中间代码的形式四元式比三元式多一个 result 字段看起来冗余但它让“结果”永远是一个可以引用的名字后续做常量折叠和公共子表达式消除时少一层间接寻址的麻烦。从那以后我每次带人做这类课程设计都强制要求先写一张“阶段可观测量清单”每完成一个阶段就填一次数字数字对不上就回去查而不是等到最后跑大用例时靠猜。有了这份清单实验报告自然就有了骨架调试也不再是黑匣子里碰运气。这份资源把词法、语法、语义三段拆成了可以单独编译运行的模块配上覆盖上表各维度的测试用例和一份完整的实验报告自己从头跑一遍、对着中间结果核一遍比读十篇讲原理的文章都扎实。希望帮到你。本文还有配套的精品资源点击获取