编译原理课程设计：用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 终结符种别码与词法约定

资源配套的词法分析器把单词分成下面几类，种别码在符号表和四元式里都会用到。

有一个词法细节提醒你注意：多字符运算符<=、>=、==、!=必须在词法扫描时先于单字符运算符匹配，否则输入<=会被切分成<和=。我在词法主循环里先查双字符集合再查单字符集合，这一点在后面避坑章节还会展开。

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:i+2] in ('<=', '>=', '==', '!='): two = src[i:i+2] 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。跳转类四元式是本实验的重点，我一共只用了三条指令，约定如下。

因为比较操作符<、>等已经被语义动作翻译成“真假值”，所以这里不区分具体大小关系，统一生成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 语句的语义动作与出口布局

归约 P7（IF_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)

P8（IF_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) # a>=b 为假链，跳到 else 块首 101: (=, 1, _, x) # then 块：x = 1 102: (j, _, _, 104) # then 块结束，跳过 else 103: (=, 2, _, x) # else 块：x = 2 104: (后续语句的四元式首地址)

注意jz的语义是“条件为假则跳”，所以它在第 100 行就出现了，而j在第 102 行出现。刚接触回填的人最容易在这两种跳转上犯迷糊：jz是假的走 else，j是执行完 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 悬空 else：else 认了外层 if 做爸爸

现象：嵌套 if 时，else归属错乱。输入if (a) { if (b) { x=1; } else { x=2; } }，翻译出的四元式里x=2被放到外层 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 (a<b)跑一遍全流程，确认两个跳转方向都对了，才敢继续嵌套测试。

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 (a<b) { x=1; }这种不带 else 的；连续两个 if 并列的；if 块里再嵌 if 且内层没有 else 的；条件表达式里同时出现!=和<=的；数字超过两位数导致词法切分错误的。每类用例都在资源里准备了对应的基准四元式序列。从那以后我每改一次语义动作，都会把这组边界用例完整跑一遍，确认旧功能没被新改动碰坏，才敢说这次实现是稳的。说实话，LL(1) 加四元式的组合并不神秘，它就是文法、分析表、回填三件事的排列组合，把这三件事各自的边界都摸清楚，你也能一遍过。希望帮到你。

本文还有配套的精品资源，点击获取