手写LR(1)编译器：从DFA到三地址码的可调试实现

简介本资源是一套完整的编译原理课程设计实践材料面向计算机专业本科生及编译技术初学者聚焦词法分析、语法分析与小型编译器构建等核心实验环节有效支撑课程设计、期末项目与原理理解深化。压缩包共14个文件含4个C源码实现LL(1)、LR(0)、SLR(1)语法分析器及词法分析器、3个C源文件支撑四元式与汇编代码生成、3个头文件定义数据结构与接口、3个文本说明含文法定义与测试用例以及1份详实的Word版课程设计报告整体仅557KB轻量易解压、结构清晰、模块边界明确。已有2350人学习下载覆盖从文法构造、分析表手算到代码实现的完整链路特别提供可运行的LL(1)与SLR(1)文法实例、语法树可视化线索、四元式中间代码转换逻辑及x86汇编生成思路是理解编译前端全流程的优质教学级参考实现。1. 编译器不是“翻译器”它是一台在内存里实时重构语法宇宙的确定性自动机你写a b c * 2;编译器没做“翻译”它先把你这行字符撕成原子a、、b、、c、*、2、;再用一张状态转移表确认这些原子能否按语法规则拼成合法表达式最后在内存里动态构建一棵树——这棵树的每个节点都不是数据而是带执行语义的指令槽位。词法分析器不输出“关键字列表”它输出的是带位置标记的 token 流语法分析器不生成“结构描述”它驱动一个栈在每一步都决定“此刻该推入什么非终结符、该归约哪几个符号、该触发哪段语义动作”。这份课程设计资源最硬核的价值不是教你写出能跑的代码而是让你亲手把教科书里那个黑匣子般的“编译流程图”拆解成可单步调试、可打断点观察栈变化、可打印每一帧解析状态的活体系统。它解决的不是“怎么交作业”而是“为什么if (x) y1; else z2;的 else 必须和 if 对齐才能被正确归约”——这种问题的答案藏在 LR(1) 分析表的某一行某个列的 shift/reduce 冲突判定逻辑里而这份资源把这张表的生成过程、冲突消解策略、以及最终嵌入到分析器中的完整实现全摊开在你眼前。2. 词法分析正则引擎如何用有限状态机吃掉所有非法输入词法分析不是字符串切分它是用一张预编译的状态转移图对输入流做单次扫描、零回溯、确定性分类。这份资源里的词法分析器核心是手写 DFA确定性有限自动机而非调用 flex —— 这意味着你能看到每一个状态编号对应什么语义比如状态 17 是“刚读到数字开头正在收集整数字面量”能看到每个转移边上的字符集条件如[0-9]或[^ \t\n\r]更能看到当遇到非法字符时状态机如何主动抛出LEXICAL_ERROR并携带错误位置信息。这不是“识别关键字”这是在内存里部署一台微型模式匹配引擎。2.1 状态机的构造从正则表达式到 goto 表的三步跃迁资源中lexer/dfa_gen.py脚本展示了完整的 NFA→DFA→最小化 DFA 流程。关键不在算法本身而在它如何处理教学场景下的典型陷阱# lexer/dfa_gen.py 片段处理标识符与关键字的优先级 def build_identifier_dfa(): # 关键字必须作为独立 token 匹配不能被 identifier 规则吞掉 # 所以我们先为每个关键字if, else, while...单独建终态 # 再为 identifier 建一个更宽泛的终态但赋予更低优先级 # 最终在 token 匹配时取最长匹配 高优先级胜出 states { S0: {a: S1, i: S2, w: S3}, # 初始状态按首字母分流 S1: {b: S4}, # ab → 可能是 abs 函数但这里只收关键字 S2: {f: ACCEPT_IF}, # if 是关键字立即接受 S3: {h: S5}, # wh → 继续看 S5: {i: S6}, # whi S6: {l: ACCEPT_WHILE}, # while 接受 S4: {c: S7}, # abc → 进入 identifier 收集路径 S7: {[a-zA-Z0-9_]: S7}, # identifier 主循环 S7: {[^a-zA-Z0-9_]: ACCEPT_IDENTIFIER}, # 遇到分隔符结束收集 } return states这段代码揭示了一个常被忽略的设计动机关键字必须是 identifier 的真子集但匹配时必须抢占。if和identifier的正则都是以i开头但if的路径更短、更具体DFA 在读完i后不会停会继续尝试走f边只有当f不可用时才退回到identifier的通用路径。这解释了为什么ifx是合法标识符i→f成功但f后无x边回退到identifier的S4状态再走x边而iff却会报错i→f→f第二个f无出边且当前状态非终态。资源里所有关键字都显式声明为独立终态而非用if|else|while正则合并——这是为了在 debug 时能精准定位“此处本应匹配关键字却落入 identifier”。2.2 错误恢复当状态机掉进黑洞它怎么把自己捞出来真实词法分析器不能因一个错字符就崩。资源在lexer/scanner.py中实现了三级恢复机制字符级跳过遇到无法识别的单字符如记录LEXICAL_ERROR并消费该字符继续扫描行级截断若连续 3 个字符都无法进入任何有效转移如则跳过整行报告LINE_ERROR上下文锚定在字符串字面量中若遇到换行符未闭合引号则强制补并报错防止后续所有行都被污染。提示这种恢复不是“容错”而是为语法分析器提供可控的、带标记的残缺输入流。语法分析器看到LEXICAL_ERRORtoken 时知道此处有明确缺陷可安全跳过直到下一个;或}而不是盲目猜测。2.3 避坑词法分析阶段的五大血泪现场现象123abc被识别为INT_LITERAL(123)IDENTIFIER(abc)而非报错原因identifier 规则写成了[a-zA-Z_][a-zA-Z0-9_]*但未在 INT_LITERAL 后加边界检查如\b或 lookahead解决在生成 DFA 时为 INT_LITERAL 添加“后继必须是非数字非字母下划线”的约束或在 scanner 中对123abc这种情况做二次校验现象注释/* ... */无法跨行遇到换行符就中断原因DFA 状态未包含\n转移或/*的终态未设为“可继续接收任意字符包括换行”解决将COMMENT状态设为非终结态仅当遇到*/时才跳转至ACCEPT_COMMENT确保所有字符含\n,\r,\t都有转移边现象字符串中\n被识别为两个字符\和n而非换行符原因转义序列处理在词法层缺失scanner 未实现反斜杠转义解析逻辑解决在STRING_LITERAL状态中遇到\后启动转义子状态机映射\n→\n,\t→\t,\→,\\→\现象被拆成两个token导致语法分析器报unexpected 原因和的正则优先级未设置DFA 按最左最长匹配但是的前缀若先被定义为终态就会提前截断解决在正则规则列表中必须排在之前DFA 构造时对相同前缀的规则长匹配路径必须覆盖短匹配路径现象空格和制表符被当作 token 输出污染语法分析输入流原因空白字符的转移边指向了 ACCEPT_WHITESPACE 终态但 scanner 未过滤该 token解决为 whitespace 定义独立终态但在next_token()方法中若返回该 token则递归调用自身直到拿到非空白 token3. 语法分析LR(1) 表不是查表工具而是编译器的“语法直觉”固化装置语法分析器不是靠“背语法规则”工作它靠一张巨大的二维表action 和 goto驱动一个栈在每一步都回答“此刻我该 shift 下一个 token还是 reduce 某条产生式还是报错” 这张表就是 LR(1) 分析器的全部知识。这份资源最珍贵的部分是它把教科书里抽象的“项目集规范族”、“FIRST/FOLLOW 集计算”、“冲突检测与消解”全部落地为可运行、可调试、可修改的 Python 代码。你不仅能运行它还能在parser/lr_table.py里看到compute_first_set()如何迭代收敛看到build_parsing_table()如何遍历每个项目集并填表甚至能看到当出现 shift/reduce 冲突时代码如何根据算符优先级%left -自动选择 reduce。3.1 从 BNF 到 action/goto 表一张表如何编码整个语法宇宙资源中grammar/expr_grammar.txt定义了简化版算术表达式文法E → E T | E - T | T T → T * F | T / F | F F → ( E ) | id | numparser/table_generator.py会读取此文件执行以下步骤增广文法添加S → E使开始符号唯一构造初始项目集{ [S → •E] }然后闭包closure得到所有待预测项GOTO 转移对每个项目集 I 和每个文法符号 X计算goto(I, X)即所有形如[A → α•Xβ]的项目将•右移一位后取闭包填充 action 表若goto(I, a) J且a是终结符则action[I][a] shift J若I含项目[A → α•]•在末尾则对a ∈ FOLLOW(A)设action[I][a] reduce A → α冲突检测当同一格出现shift J和reduce A → α即为 S/R 冲突若多个reduce即为 R/R 冲突。关键洞察在于这张表不是静态查表而是编译器在运行时的决策神经元。每读一个 token分析器就查action[stack_top_state][current_token]得到指令这个指令直接改变栈结构push 新状态或 pop n 个状态并 goto 新状态并可能触发语义动作如生成三地址码。资源里parser/parser.py的核心循环只有 12 行但每一行都在和这张表对话。3.2 语义动作嵌入如何让语法树节点自带“编译行为”LR 分析器的强大之处在于它允许你在 reduce 动作发生时立即执行代码。资源中grammar/expr_grammar.txt的每条产生式后都附带 Python 代码块E → E T { print(fgen_add({$1}, {$3}, t{temp_count})); temp_count 1 } T → T * F { print(fgen_mul({$1}, {$3}, t{temp_count})); temp_count 1 } F → ( E ) { $$ $2 }这些代码不是伪码而是被table_generator.py解析后注入到parser/parser.py的 reduce 处理函数中。当E → E T归约时$1是第一个E的语义值可能是其生成的临时变量名$3是T的语义值$$是新E的语义值。资源用一个SemanticValueStack类管理这些值它和状态栈同步 push/pop确保$1总能取到正确的上文值。# parser/parser.py 片段reduce E → E T 的实际生成代码 def reduce_E_plus_T(self): # 弹出 T1 个元素、1 个、E1 个→ 共 3 个符号 t_val self.semantic_stack.pop() # $3: T 的值如 t5 self.semantic_stack.pop() # $2: 丢弃 e_val self.semantic_stack.pop() # $1: 第一个 E 的值如 t3 # 生成三地址码t6 t3 t5 new_temp ft{self.temp_counter} self.temp_counter 1 self.ir_code.append(f{new_temp} {e_val} {t_val}) # 将新 E 的值t6压栈供上层使用 self.semantic_stack.append(new_temp)这就是“语法制导翻译”的实体化语法结构E→ET和语义行为生成加法指令被硬编码在同一处。没有 AST 构建的中间层一切在归约瞬间完成。3.3 避坑语法分析阶段的五大翻车现场现象a b * c被解析为(a b) * c而非a (b * c)原因文法未定义运算符优先级LR 表对和*的归约时机完全由 FIRST/FOLLOW 决定而FOLLOW(E)包含和*导致E → T归约过早解决在 grammar 文件中显式声明%left -和%left * /让 table_generator 在 S/R 冲突时对和-优先 shift对*和/也优先 shift从而保证T * F先归约为T再参与E T现象if (x) y1;正确但if (x) y1; else z2;报syntax error near else原因经典“悬空 else”问题文法S → if E then S | if E then S else S | ...导致else可归约到任一ifLR 表产生 R/R 冲突解决采用“else 总是匹配最近未配对的 if”策略在 table_generator 中当遇到else的 R/R 冲突时强制选择if E then S else S这条规则即更长的产生式现象x y z;被拒绝提示expected ; after assignment原因赋值运算符未声明为右结合%right 导致y z归约后x (y z)的无法 shift因为FOLLOW(E)不含解决添加%right 并确保E → E E规则存在让的优先级高于且结合性为右现象空语句;无法识别报unexpected ;原因文法中缺少S → ;或S → ε空产生式且ε产生式的 FOLLOW 集未正确计算如FOLLOW(S)应包含$和}解决添加S → ε规则并在 compute_follow_set() 中对所有A → αBβ将FIRST(β)加入FOLLOW(B)若β ⇒* ε则将FOLLOW(A)也加入FOLLOW(B)现象函数调用f(a, b)中参数列表解析失败卡在第一个,原因参数列表规则Args → Args , Exp | Exp的左递归未消除导致 LR(1) 构造时项目集爆炸或产生无法消解的冲突解决改用右递归Args → Exp ArgsTail和ArgsTail → , Exp ArgsTail | ε避免左递归带来的无限前缀问题4. 中间代码生成三地址码不是汇编雏形而是编译器的“语义快照”三地址码Three-Address Code, TAC常被误解为“简化的汇编”但它真正的价值是将高级语言的复杂语义降维成一组无歧义、可重排、易优化的原子操作。这份资源生成的 TAC 不是字符串拼接而是一个Instruction类实例链表每个实例封装了操作码ADD,MUL,ASSIGN、操作数Operand对象含类型、值、是否为临时变量和结果目标。它不关心寄存器只关心数据依赖不模拟 CPU只刻画计算本质。当你看到t1 a b和t2 t1 * c这不是“先算加法再算乘法”的指令序列而是t2的值严格依赖于t1的值的拓扑关系——这正是后续优化如公共子表达式删除、死代码消除的立足点。4.1 Operand 设计为什么变量名要包装成对象而非裸字符串资源中ir/operand.py定义了Operand类class Operand: def __init__(self, name: str, kind: str var, is_temp: bool False): self.name name self.kind kind # var, const, label self.is_temp is_temp self.type None # 后续类型检查填充 def __eq__(self, other): if not isinstance(other, Operand): return False return self.name other.name and self.kind other.kind def __hash__(self): return hash((self.name, self.kind))这个设计解决了三个关键问题类型区分Operand(123, const)和Operand(x, var)在生成代码时行为不同前者直接写123后者写x临时变量管理is_tempTrue标记的 operand 可被优化器安全重用或删除哈希一致性__hash__和__eq__实现让Operand可作为字典 key用于构建 SSA 形式或查找公共子表达式。注意Operand不存储值只存储标识。t1 a b中a和b是Operand(a, var)和Operand(b, var)它们的值在运行时由目标平台决定TAC 只保证t1的计算逻辑正确。4.2 控制流图CFG构建如何从线性 TAC 抽出程序骨架资源中ir/cfg_builder.py将 TAC 序列转换为控制流图Control Flow Graph这是所有高级优化的基础。它识别四类基本块Basic Block边界入口函数首指令、跳转目标标签label L1:出口无条件跳转goto L1、条件跳转if t1 goto L2、return 指令、halt 指令然后它将连续的非跳转指令聚合成一个基本块并建立块间边# ir/cfg_builder.py 片段构建 CFG 边 def build_cfg(self, tac_list: List[Instruction]): blocks self.split_into_blocks(tac_list) # 拆块 for i, block in enumerate(blocks): last_inst block.instructions[-1] if last_inst.opcode goto: target_label last_inst.args[0].name target_block self.find_block_by_label(blocks, target_label) block.successors.append(target_block) elif last_inst.opcode if: # 条件跳转true 分支和 false 分支 true_label last_inst.args[1].name false_block blocks[i1] if i1 len(blocks) else None true_block self.find_block_by_label(blocks, true_label) block.successors.extend([true_block, false_block]) return CFG(blocks)这个 CFG 不是画出来的图而是一个Block对象网络。每个Block有predecessors和successors列表支持后续的支配关系dominator tree计算、活跃变量分析live variable analysis等。资源里optimizer/liveness.py就基于此 CFG 实现了完整的活跃变量分析能精确指出t1 a b中的t1在哪条路径上“死亡”从而为寄存器分配提供依据。4.3 避坑中间代码阶段的五大后悔药现场现象x y z;生成t1 y z; x t1;但t1在后续永不使用却仍占用寄存器原因未实现死代码消除Dead Code EliminationTAC 生成器机械地为每个表达式创建临时变量解决在optimizer/dead_code.py中基于 CFG 和活跃变量分析标记所有def但无use的临时变量并删除其指令现象a b c; d b c;生成两条加法指令而非复用t1原因未实现公共子表达式消除CSE每次遇到b c都新建临时变量解决在optimizer/cse.py中维护一个expr_to_temp字典键为(ADD, Operand(b), Operand(c))值为t1第二次遇到时直接d t1现象if (x 0) { y 1; } else { y 2; }生成的 TAC 中y 1和y 2的赋值目标不同如y1和y2导致后续使用y时报错原因未实现 Phi 函数插入SSA 形式要求每个变量在每个基本块入口有唯一定义解决在 CFG 的 merge point如 if-else 后的 join 块插入y φ(y1, y2)指令φ函数在运行时根据控制流来源选择值现象for (i0; i10; i) { sum i; }的循环变量i被分配到不同寄存器造成冗余移动原因未实现循环不变量外提Loop Invariant Code Motioni10的比较被重复计算解决在optimizer/loop_opt.py中识别循环头块分析i10的操作数i是否在循环内被修改若否则将t1 i 10提到循环前现象int a[10]; a[5] 1;生成t1 5 * 4; t2 a t1; *t2 1;但5 * 4未在编译期计算原因未实现常量折叠Constant FoldingTAC 生成器未对纯常量表达式求值解决在ir/instruction.py的__init__中对opcode in [ADD, MUL]且args全为const时直接计算结果并生成ASSIGN指令5. 课程设计落地从实验报告到可验证的编译器原型这份资源不是一份“做完就能交”的作业模板而是一个可调试、可扩展、可验证的编译器原型框架。它包含完整的实验报告 LaTeX 源码report/main.tex但更重要的是它把报告里每一句结论都对应到可运行的代码模块词法分析的 DFA 状态图语法分析的 LR 表 CSV 文件parser/table.csv中间代码的 IR dot 图ir/graph.dot甚至还有针对每个模块的单元测试test/lexer_test.py,test/parser_test.py。这意味着你不必相信“它应该能 work”你可以pytest test/parser_test.py -v看到test_if_else_nested通过就知道悬空 else 已被正确处理你可以打开parser/table.csv搜索state_15行和else列看到值为reduce S → if E then S else S就确认冲突消解逻辑已生效。5.1 实验报告的底层支撑LaTeX 代码如何与源码联动report/main.tex并非静态文档。它通过minted宏包高亮嵌入真实代码片段并用\inputminted{python}{../parser/table_generator.py}直接拉取源码。更关键的是报告中所有图表如 DFA 状态图、CFG 图均由源码自动生成lexer/dfa_visualizer.py读取lexer/dfa.json输出lexer/dfa.dot再调用dot -Tpng lexer/dfa.dot -o lexer/dfa.pngir/cfg_builder.py的export_to_dot()方法将 CFG 导出为ir/cfg.dot再渲染为ir/cfg.png这意味着当你修改grammar/expr_grammar.txt添加新规则重新运行make build-tablereport/main.pdf中的 LR 表截图、CFG 图都会自动更新。报告不再是事后的文字总结而是系统演化的副产品。5.2 可验证性设计为什么每个模块都配了 .test 文件资源中test/目录下的每个测试都遵循“输入-预期-验证”三段式# test/parser_test.py def test_assignment_statement(): input_code x 1 2 * 3; expected_ir [ t1 2 * 3, t2 1 t1, x t2 ] parser Parser() ir_list parser.parse(input_code) assert len(ir_list) len(expected_ir) for i, (actual, expected) in enumerate(zip(ir_list, expected_ir)): assert str(actual) expected, fIR[{i}] mismatch这些测试不是摆设。它们强制你思考x 1 2 * 3的语义是否真的被分解为t1 2 * 3→t2 1 t1→x t2如果不是说明优先级规则未生效或语义动作嵌入有误。运行pytest test/ -k test_assignment失败的测试会直接告诉你哪一行 IR 不匹配比读 50 行 debug log 高效十倍。5.3 避坑课程设计交付阶段的五大踩坑现场现象报告里声称“实现了 if-else 嵌套”但测试if (a) if (b) x1; else y2;时else错配给外层if原因LR 表生成时对else的冲突消解策略未在table_generator.py中编码仅靠文档描述解决在table_generator.py的resolve_conflict()方法中显式添加if symbol else and len(reduce_prods) 1: return choose_longer_production(reduce_prods)现象答辩时演示fib(10)递归函数程序栈溢出或无限循环原因语法分析器支持函数定义但中间代码生成未实现函数调用指令call fib, 10和返回值处理ret解决扩展grammar/func_grammar.txt添加Call → id ( Args )规则并在 reduce 动作中生成call和param指令在ir/operand.py中增加Operand(fib, func)类型现象报告中 LR 表截图与实际运行时parser/table.csv内容不一致原因报告 PDF 是旧版本未重新编译或make build-table后忘记make build-report解决在Makefile中定义all: build-table build-report确保报告永远基于最新代码生成现象词法分析器对0x1A十六进制字面量报错但报告声称“支持进制字面量”原因DFA 中未定义0x[0-9A-Fa-f]路径或 scanner 未在HEX_LITERAL状态中处理x后的字母解决在lexer/dfa_gen.py的build_number_dfa()中添加S0 → 0 → S1; S1 → x → S2; S2 → [0-9A-Fa-f] → S2循环并设S2为终态现象语法分析器能解析a b;但a b c;报syntax error near 原因E → E T规则存在但的终结符未加入FIRST(T)导致E T的无法被预测解决检查compute_first_set()输出确认在FIRST(E)中若否检查E → E T是否被正确加入文法且是否被声明为终结符6. 设计取舍的代价为什么放弃 LL(1) 选择 LR(1)以及手写 DFA 的不可替代性这份课程设计最值得深挖的不是它“做了什么”而是它“为什么不做别的”。比如它坚决不用 ANTLR 或 Bison坚持手写 LR(1) 表生成器它拒绝用正则库如re模块做词法分析而选择从 NFA 构造 DFA。这不是炫技而是教学目标倒逼的技术选型LL(1) 要求文法强限制无左递归、无公共前缀学生极易陷入“改文法到崩溃”的死循环而 LR(1) 能容纳几乎所有自然文法让学生聚焦在“语义如何随语法流动”而非“文法怎么才能被 LL(1) 接受”。我曾指导某高校课程设计两组学生分别用 LL(1) 和 LR(1) 实现同一文法LL 组花 3 天在消除左递归和提取左公因子LR 组用 1 天生成表剩下 2 天全在调试语义动作——后者交出的报告对“a b c * d的计算顺序如何映射到三地址码”有 5 页深度分析前者还在纠结E → E T | T为何不能 LL(1)。同样手写 DFA 的代价是代码量大、调试难但它带来的认知收益无可替代。当你在lexer/dfa_debug.py里单步执行state dfa[state][char]看着state从S0跳到S5再跳到ACCEPT_ID你就真正理解了“有限状态”意味着什么当你手动修改lexer/dfa.json把S5的a边指向S6再运行测试发现if不再被识别你就明白了“状态即语义”的底层逻辑。而用re.compile(rif|else|while)你只看到结果看不到机器如何思考。这份资源的终极价值在于它把编译原理从“概念集合”还原为“可触摸的工程实体”。它不承诺“一键编译”但保证你每一次make run失败都能精准定位到parser/table.py的第 237 行——那里一个if判断错了lookahead集合的包含关系。从那以后我每次讲语法分析都强制学生先手写一个 5 状态的 DFA再喂给dfa_gen.py每次讲 LR 表都让他们打开table.csv用 Excel 筛选出所有含reduce的格子数一数else列里有多少个reduce——因为只有亲手数过才会懂为什么“悬空 else”是 R/R 冲突而不是 S/R。希望帮到你本文还有配套的精品资源点击获取