编译原理课程设计：用LL(1)和四元式实现IF-ELSE翻译-北京尧图网络

简介面向编译原理课程设计与实验的IF-ELSE条件语句翻译程序实现包采用LL(1)预测分析并生成四元式中间代码适合计算机专业学生、编译器入门开发者用来对照词法/语法/语义分析流程完成或改进同类翻译任务。压缩包共17个文件约417KB核心包括C源文件与头文件cpp/h、Visual Studio工程与解决方案vcproj/sln、RC资源描述及APS资源脚本、compare.txt说明文档另有Debug目录下的obj、pdb等编译中间产物便于直接打开工程查看构建结果。已有540人浏览学习。从中可以获取完整的IF-ELSE翻译程序设计思路包括LL(1)文法的预测表构造、条件与跳转四元式的生成方法、嵌套IF-ELSE及空语句的边界处理同时可参考其中比较操作相关四元式实例理解从词法分析到语法分析和中间代码输出的整体实现细节。1. 一条 IF-ELSE 的翻译程序凭什么让四元式无处躲藏IF-ELSE 条件语句的翻译程序设计LL(1)法、输出四元式几乎是每个编译原理课程设计绕不过去的一道坎。表面上看if (a b) { x 1; } else { x 2; }只是个二选一的跳转但一旦嵌套多几层“跳往哪里、地址是多少”就得靠手工推稍不留神就把真链和假链搞反。用 LL(1) 法做这件事的核心价值在于文法先行、预测分析表驱动读一个终结符就查一次表归约时按产生式发射四元式回填时按链改地址整套流程可验证、可调试。这份资源适合正在做编译原理课程设计的学生、想补 LL(1) 表驱动实现细节的从业者以及需要一份“能跑、能截图、能答辩”的完整中间代码生成器的人。我拆完这套实现后最大的感受是难的不是 LL(1) 本身而是你愿不愿意把每一个跳转地址都当成变量来管理。2. 文法与终结符设计先把 FIRST/FOLLOW 的冲突掐死在摇篮里2.1 为什么原始 IF-ELSE 文法进不了 LL(1)经典的 IF-ELSE 文法长这样S - if E S | if E S else S | 其他语句。这条文法符合人的直觉但有两个致命问题一是两个产生式都以if开头公共左因子没有提取LL(1) 查表时 M[S][if] 这一格会出现两条候选直接冲突二是“悬空 else”问题else既可能属于最近的if也可能属于更外层的if换句话说else同时出现在某个非终结符的 FIRST 和 FOLLOW 里预测分析表没法给出唯一动作。常见的修复手段是引入一个尾巴非终结符S - if E S TAIL | ...TAIL - else S | ε。但这样改造后else依然会出现在 FOLLOW(S) 里分析器读到else时到底该不该归约TAIL - ε仍然要靠人为约定。我在这个资源里的做法更彻底把 then 分支和 else 分支都强制用花括号块包起来让STMT_LIST的 FOLLOW 里只剩}else只作为 else 块的起始终结符出现。这一刀切下去FIRST 和 FOLLOW 的冲突就真正消失了。2.2 本资源采用的 LL(1) 文法全集下面这份文法就是代码里实际使用的版本每个产生式都有编号后面的表驱动分析器和语义动作都按这个编号来。P0: PROG - STMT_LIST P1: STMT_LIST - STMT STMT_LIST P2: STMT_LIST - ε P3: STMT - IF_STMT P4: STMT - ASSIGN P5: STMT - BLOCK P6: BLOCK - { STMT_LIST } P7: IF_STMT - if B THB P8: IF_STMT - if B THB ELSEB P9: THB - { STMT_LIST } P10: ELSEB - else { STMT_LIST } P11: ASSIGN - id E ; P12: E - T E1 P13: E1 - T E1 | ε P14: T - F T1 P15: T1 - * F T1 | ε P16: F - id | num | ( E ) P17: B - C B1 P18: B1 - || C B1 | ε P19: C - E REL E P20: REL - | | | | | !P12 到 P16 是普普通通的算术表达式文法提取过左因子满足 LL(1)。P17 到 P19 负责比较条件||支持多条件“或”连接单条件的“与”关系可以照抄 B1 的写法再加一层。注意这里有个设计取舍IF_STMT的两个产生式仍然共享前缀if B THB这在标准 LL(1) 里是冲突的所以代码里我把 P8 改写为在归约 P7 时主动“偷看”下一个终结符是不是else是则继续归约 P8否则就用 P7。这是递归下降里最常见的“超前看符号”手法放在表驱动里也完全成立。2.3 终结符种别码与词法约定资源配套的词法分析器把单词分成下面几类种别码在符号表和四元式里都会用到。单词类别种别码说明id 标识符1变量名存入符号表num 数字2整型常数if3关键字else4关键字运算符 - * /5 6 7 8算术运算关系符 !9-14比较运算界符 ( ) { } ; 15-21括号、分号、赋值号#0输入结束标记有一个词法细节提醒你注意多字符运算符、、、!必须在词法扫描时先于单字符运算符匹配否则输入会被切分成和。我在词法主循环里先查双字符集合再查单字符集合这一点在后面避坑章节还会展开。3. 表驱动分析器骨架栈上做语法分析边上产四元式3.1 预测分析表和驱动器的工作方式LL(1) 表驱动分析器的核心是一个二维表行是非终结符列是终结符表项是“该采取的产生式编号”或“报错”。分析器维护一个符号栈栈顶放待匹配的符号输入串由词法分析器逐个吐终结符。查表有两种结果如果栈顶是终结符且与当前输入相等就弹出栈顶、读入下一个 token如果栈顶是非终结符就查表取产生式把产生式右部逆序压栈。这个过程不依赖任何递归调用所有语义动作都挂在“按产生式归约”的时机上。为了在归约时拿到产生式右部各非终结符的属性我让每个栈元素都附带一个属性指针指向该符号对应的“语义信息”。终结符的属性是它在符号表里的索引或常数本身非终结符的属性则是后面要讲的“链头”和“链尾”用于四元式回填。实际工程里常把属性栈单独拎出来与分析符号栈并行维护我这里采用的是“每个符号节点带一个 attr 字段”的方式代码上更直观。3.2 词法分析器和主控制循环的 Python 实现资源里的词法分析器不复杂核心任务是产出(种别码, 值, 行号)三元组并在文件末尾补一个#。下面是关键实现可以直接跑。import sys token_map { if: 3, else: 4, : 5, -: 6, *: 7, /: 8, : 9, : 10, : 11, : 12, : 13, !: 14, (: 15, ): 16, {: 17, }: 18, ;: 19, : 20, #: 0 } def lexer(src): tokens [] i, n 0, len(src) while i n: c src[i] if c.isspace(): i 1 continue if c.isalpha(): j i while j n and (src[j].isalnum() or src[j] _): j 1 word src[i:j] if word in token_map: tokens.append((token_map[word], word)) else: tokens.append((1, word)) # 标识符 i j continue if c.isdigit(): j i while j n and src[j].isdigit(): j 1 tokens.append((2, int(src[i:j]))) i j continue # 先匹配双字符运算符再匹配单字符 if i 1 n and src[i:i2] in (, , , !): two src[i:i2] tokens.append((token_map[two], two)) i 2 continue if c in token_map: tokens.append((token_map[c], c)) i 1 continue raise SyntaxError(f无法识别的字符: {c} 在第 {src.count(chr(10), 0, i) 1} 行附近) tokens.append((0, #)) return tokens词法这块最容易踩的坑就是双字符运算符的匹配顺序。如果不先于匹配词法结果就变成和两个 token语法分析立刻翻车。另外我在循环末尾对也做了映射这样赋值号和比较符在词法层就被区分开了。3.3 驱动器主循环与栈操作def ll1_driver(tokens, table, grammar, sem_actions): stack [(#, -1)] # 压入栈底标记后再压入开始符号 PROG stack.append((PROG, None)) idx 0 lookahead tokens[idx] while stack: top_sym, top_attr stack[-1] if top_sym lookahead[1]: # 栈顶终结符与当前输入相同 stack.pop() idx 1 lookahead tokens[idx] continue if top_sym not in table or lookahead[1] not in table[top_sym]: raise SyntaxError(f语法错误: 栈顶 {top_sym} 遇到输入 {lookahead}) rule_no table[top_sym][lookahead[1]] stack.pop() rhs grammar[rule_no] # 语义动作在压栈前执行具体见第 4 章 sem_actions[rule_no](stack, top_attr, lookahead) # 产生式右部逆序压栈 for sym in reversed(rhs): stack.append((sym, None))这里的table是第 2 章文法的预测分析表grammar是产生式右部列表sem_actions是一组按产生式编号绑定的回调函数。驱动器本身不关心语义它只负责“该移进就移进、该归约就归约”四元式全部在sem_actions里发射。有一个容易忽略的点逆序压栈时最左的符号要最后压入才能保证下一轮循环处理的是产生式右部的最左符号。如果压栈顺序写反查表时拿到的一定是右部最后一个符号分析过程会变成最右推导结果完全不可用。栈顶是终结符但属性为 None 的情况出现在归约完成后的压栈动作里此时终结符如数字、标识符的属性还没有绑定。我在语义动作里会对这类情况做一次“从 token 里补属性”的操作确保后面生成四元式时操作数有值可取。4. 四元式与拉链回填IF-ELSE 的跳转地址不靠猜4.1 四元式的结构与跳转指令约定四元式统一用(op, arg1, arg2, result)表示。算术运算和赋值运算的四元式很好理解(, a, b, t1)表示把 a 和 b 相加的结果存入临时变量 t1(, 1, _, x)表示把常数 1 赋给 x。跳转类四元式是本实验的重点我一共只用了三条指令约定如下。四元式含义说明(j, _, _, L)无条件跳转到 L用于 then 分支末尾跳过 else 块(jnz, a, b, L)若 a 为真则跳 L条件成立时进入 then 块(jz, a, b, L)若 a 为假则跳 L条件不成立时跳到 else 块或整体出口因为比较操作符、等已经被语义动作翻译成“真假值”所以这里不区分具体大小关系统一生成jz和jnz。我在代码里专门做了一个小函数把比较结果的真假链区分开jz走假链、jnz走真链这样回填时就不容易把出口搞反。4.2 拉链回填的三个基本函数回填机制说白了就是先发射一个目标地址未知的跳转四元式占住一个四元式序号把这个序号挂到链上等知道真实目标地址后再回头去改那个四元式的 result 字段。三个核心函数代码如下。def makelist(quad_no): 新建一条只含一个四元式序号的链 return [quad_no] def merge(list1, list2): 合并两条链返回新链头 if not list1: return list2 if not list2: return list1 return list1 list2 def backpatch(chain, target): 把链上所有四元式的跳转目标改为 target for quad_no in chain: q quads[quad_no] q[3] target这三个函数加起来不到二十行却解决了一整类问题。makelist在发射条件跳转时调用把当前未定四元式的编号保存进链merge用来合并多出口比如||左右两个条件条件都为假时的假链backpatch在做完整个 then 块或 else 块后把链上所有四元式一次性改成正确的地址。我在实际调试时发现多数回填错位问题都出在把链结构和四元式列表混为一谈——链里存的是四元式序号不是栈里的符号下标这两者差了十万八千里。4.3 IF-ELSE 语句的语义动作与出口布局归约 P7IF_STMT - if B THB时布尔表达式 B 的语义动作已经产出了它的真假链真链挂在条件成立时跳转的四元式上假链挂在条件不成立时跳转的四元式上。接下来按下面的步骤生成完整布局。def sem_P7(stack, attr, lookahead): # 此时栈顶往下依次是 THB 的属性、B 的属性 # 取出 B 的真链和假链 b_true, b_false pop_attr(stack, 1) # 伪代码实际从栈底方向取属性 # 无条件跳转then 块执行完要跳过 else 块目标先留空 q emit(j, _, _, None) # then 块出口就是这条 j 的位置登记到链上 then_chain makelist(q) # 条件为假时跳到 else 块或整体出口先回填假链再占位 backpatch(b_false, next_quad_no()) push_attr(stack, b_true, then_chain)P8IF_STMT - if B THB ELSEB的处理要再收一把else 块结束后的整体出口才是整个 IF 语句的出口。P7 在 then 块后已经发射了一条占位的j四元式P8 归约时要把这条j的回填目标定到 else 块结束后的下一个四元式序号同时把 B 的真链回填到 then 块首条四元式。整个布局如下表所示我用一个具体的输入串走一遍。输入: { if (a b) { x 1; } else { x 2; } } 四元式序列: 100: (jz, a, b, 102) # ab 为假链跳到 else 块首 101: (, 1, _, x) # then 块x 1 102: (j, _, _, 104) # then 块结束跳过 else 103: (, 2, _, x) # else 块x 2 104: (后续语句的四元式首地址)注意jz的语义是“条件为假则跳”所以它在第 100 行就出现了而j在第 102 行出现。刚接触回填的人最容易在这两种跳转上犯迷糊jz是假的走 elsej是执行完 then 块后强制跳过 else两者方向完全不同。我在语义动作里用两条独立的链分别维护它们绝不混用。4.4 布尔条件的真链与假链生成比较条件C - E REL E归约时需要先计算左右两个算术表达式的值然后发射一条带占位目标的跳转四元式。下面的代码演示了单条件如何处理多条件||在此基础上用 merge 拼链。def sem_C(stack, attr, lookahead): e2 pop_attr(stack, 1) rel pop_attr(stack, 1) e1 pop_attr(stack, 1) # 先算比较结果再按关系符决定跳转方向 t new_temp() emit(rel, e1, e2, t) # 生成 (, a, b, t1) 这类四元式 jz_quad emit(jz, t, _, None) # 为假跳 else jnz_quad emit(jnz, t, _, None) # 为真进 then push_attr(stack, makelist(jnz_quad), makelist(jz_quad))这里多了一个中间临时变量t它承载的是比较结果的真假值。jz和jnz都消费同一个t一个进真链、一个进假链。对于a b这种条件翻译出的四元式序列总共三条比较、假跳、真跳。后续if归约时真链会被回填到 then 块首假链会被回填到 else 块首或整体出口。如果你在调试时发现输出里jz和jnz的目标地址一模一样那大概率是回填顺序错了而不是代码逻辑的问题。5. 避坑实录五个让课程设计翻车的细节5.1 悬空 elseelse 认了外层 if 做爸爸现象嵌套 if 时else归属错乱。输入if (a) { if (b) { x1; } else { x2; } }翻译出的四元式里x2被放到外层 if 的 else 分支而不是内层。原因文法的 STMT_LIST 里 ε 归约时机不对。LL(1) 表驱动读到}或else时会优先考虑把当前未归约的非终结符归约为 ε而else写在文法里既能作为内层 if 的继续又能在 FOLLOW(STMT) 里合法出现分析器选了前者。解决在本资源里我强制要求 then 和 else 分支都用花括号块包裹else只作为ELSEB的起始终结符出现在文法中STMT_LIST 的 FOLLOW 里彻底移除else。如果你坚持不用花括号那就必须在归约 P7 时做一次“超前看”只有看到else才继续按 P8 处理否则立即完成当前 if 的归约。5.2 真链假链颠倒条件成立跳 else条件失败进 then现象四元式输出的跳转方向完全反了jz在条件为真时跳入 then 块jnz却跳到了 else程序运行结果和源代码语义恰好相反。原因语义动作里把 jz 和 jnz 与真假链的对应关系写反了。我调试时发现往往是“觉得 jz 是 jump if zero条件为假就是 zero应该跳出去”的直觉害了人——没错方向对但jz的跳转目标应该是 else 块而 else 块入口要从 B 的假链里取。解决把比较条件的语义动作固定成一条铁律真链只挂jnz假链只挂jz。归约 IF_STMT 时backpatch(b_false, 下一四元式序号)永远先于backpatch(b_true, then块首序号)执行这样即便条件表达式复杂出口方向也不会乱。从那以后我每次写完语义动作都会先用一个最简单的if (ab)跑一遍全流程确认两个跳转方向都对了才敢继续嵌套测试。5.3 属性栈和符号栈不同步错位一个元素四元式操作数全是符号表索引用错现象归约一个三元素的产生式时取出来的属性不是对应符号的值而是上一个符号的四元式形如(, t1, _, x)但 t1 实际是别的变量。原因压栈和归约的时机不同步。我的驱动器在压入产生式右部符号时没有同步压入属性等到归约时又按“从栈底方向数第几个”去取属性栈里残留的属性顺序和分析栈的顺序不一致。解决把属性和符号绑进同一个栈节点。压栈时右部符号的 attr 初值设为 None但左部非终结符归约后生成的属性一定要在“弹完右部符号后、压入左部符号前”压回栈里。我后来在栈节点上加了调试打印每次归约都把栈内所有符号和 attr 打出来错位问题一眼就能看出来。5.4 多字符运算符匹配顺序被切成了和现象输入if (a b)词法分析器输出和两个 token语法分析在遇到时报错程序直接崩溃。原因词法扫描时把当成了后再匹配。很多初版词法器喜欢按字符逐个判断先命中就立即返回完全没考虑两位运算符。解决在词法主循环里先检查当前位置往后两位的子串是否属于双字符运算符集合命中后才进入单字符分支。顺带把也纳入同样的优先匹配逻辑否则会被拆成和赋值号和比较符在语义层就搅成一团。这个坑藏得深因为单个也能合法进入语法分析错误往往到回填阶段才暴露。5.5 ε 归约时机读到 } 时忘记先归约 STMT_LIST现象带花括号的语句块里最后一条语句之后直接出现}分析器在}上查表失败报“栈顶 STMT_LIST 无法匹配 }”。原因STMT_LIST 的 ε 产生式只在STMT_LIST, 当前输入符号这一格有定义而 STMT_LIST 必须先归约为 ε 才能让 BLOCK 去匹配}。没有在分析表中把}列入 STMT_LIST 的 ε 归约触发列分析器看到}时无路可走。解决构造预测分析表时把 STMT_LIST 的 ε 产生式填到 FOLLOW(STMT_LIST) 的所有终结符列上也就是}和#这两列。同时检查 BLOCK 的归约动作确保压入{ STMT_LIST }后STMT_LIST 在读到}时有明确的归约路径。表驱动器不会替你推理表里没有的项就是死路。6. 验证与调试一张纸推出目标四元式序列再让机器对照6.1 手工推演一个含嵌套的完整例子选一个不复杂的输入但必须覆盖 then、else 和 if 之后的语句。以{ if (a b) { x 1; } else { x 2; } y x a; }为例我用手工推导出下面的四元式序列作为验证基准。100: (jz, a, b, 102) # a b 为假跳到 else 块 101: (, 1, _, x) # then 块 102: (j, _, _, 105) # then 块结束跳过分 if 出口 103: (, 2, _, x) # else 块 104: (, x, a, t1) # 求 x a 105: (, t1, _, y) # 赋给 y对照一下条件为真时走 101 再跳 105条件为假时走 103 再接 104、105。这个手工序列是唯一真理程序输出的四元式序列必须逐行与它一致。我把这个基准序列写成 Python 列表在测试脚本里做逐行断言四元式文本完全匹配才算通过。6.2 自动化断言脚本与调试手段下面这几十行脚本是我的验证工具核心思路是把程序输出的四元式转成格式化的字符串再和基准列表比对。如果你不想引入测试框架直接用assert一行行比较也行。expected [ (jz, a, b, 102), (, 1, _, x), (j, _, _, 105), (, 2, _, x), (, x, a, t1), (, t1, _, y), ] def run_and_compare(src): tokens lexer(src) quads ll1_parse(tokens) # 返回格式化后的四元式字符串列表 for i, (got, exp) in enumerate(zip(quads, expected)): if got ! exp: print(f第 {i} 行不一致: 程序{got}, 期望{exp}) return False return True如果断言失败我一般先在驱动器主循环里打开“轨迹模式”每处理一个终结符就打印一遍当前符号栈和四元式列表。栈的变化能直接反映归约顺序是否正确四元式列表能看出哪一步回填的目标地址偏了。还有一个土办法非常有效把backpatch函数加一行打印输出“链上序号 → 目标序号”这样你能看到每条链在哪个时刻被回填到了哪里。从调试经验来看八成回填错误都发生在第一次 backpatch 之前那说明占位四元式的发射顺序本身就错了。6.3 边界用例清单最后再给一组必测用例if (ab) { x1; }这种不带 else 的连续两个 if 并列的if 块里再嵌 if 且内层没有 else 的条件表达式里同时出现!和的数字超过两位数导致词法切分错误的。每类用例都在资源里准备了对应的基准四元式序列。从那以后我每改一次语义动作都会把这组边界用例完整跑一遍确认旧功能没被新改动碰坏才敢说这次实现是稳的。说实话LL(1) 加四元式的组合并不神秘它就是文法、分析表、回填三件事的排列组合把这三件事各自的边界都摸清楚你也能一遍过。希望帮到你。本文还有配套的精品资源点击获取

编译原理课程设计：用LL(1)和四元式实现IF-ELSE翻译

相关推荐

AI协作者工作流：从提问到共舞的实战方法论

VS2022安装避坑指南：工作负载选择、离线布局与幽灵错误排查

Token到底是什么？一文讲透编程、认证与大模型三种身份

更多资讯

384维句向量空间探秘：all-MiniLM-L6-v2的语义压缩学

图像去卷积实战：Hyper-Laplacian先验与IRLS快速求解

马赛克去除的工程真相：从图像重建原理到可部署实践

从聊天客户端到 Agent 运行时：LibreChat 在开源 AI 基建版图里的新坐标

LangAlpha多渠道使用指南：在Slack、Discord、Telegram里和AI投研Agent对话

带长度限制的最大子数组和：前缀和+单调队列全解析

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？