从if-else到四元式：手写LL(1)翻译器实战指南

简介：这份资源是编译原理课程中IF-ELSE条件语句翻译程序设计的完整实现包，面向正在学习语法分析与中间代码生成的高校学生及自学者。它围绕LL(1)预测分析法展开，演示如何对条件语句进行词法识别、语法解析，并输出四元式中间代码，帮助读者理解编译器前端从源码到中间表示的完整链路。压缩包共17个文件，约417KB，包含cpp与h源码、vcproj与sln工程文件、rc资源脚本、txt说明及pdb、obj等编译中间产物，可直接在Visual Studio中打开调试。资源中附带的Compare模块涉及比较操作与条件跳转的四元式实例，便于对照理解测试条件、跳转标签等生成逻辑。目前已有540人学习下载，适合作为课程实验参考或编译器前端入门练手素材。

1. 从一段 if-else 到四元式：为什么值得亲手写一遍 LL(1) 翻译器

很多人第一次接触编译原理，看到“IF-ELSE 条件语句的翻译程序设计（LL(1) 法、输出四元式）”这个题目，第一反应是：这不就是课本上那个经典实验吗？但真正动手写的时候，你会发现它卡人的地方不在理论，而在“怎么把文法、预测分析表、语义动作、四元式生成这四件事串成一条能跑通的流水线”。LL(1) 法要求你先把 if-else 的上下文无关文法改造成无左递归、提取左公因子的形式，再手算 FIRST 集和 FOLLOW 集，构造预测分析表，最后在递归下降或栈式分析的过程中嵌入语义动作，把条件、跳转、赋值翻译成四元式。这套流程走一遍，你对“语法分析驱动语义翻译”的理解会比看十遍书都扎实。适合正在做编译原理课程设计、想搞懂四元式中间代码生成、或者需要一个小型翻译器原型来验证想法的同学和工程师。下面我按自己踩过的坑，把这份资源拆开讲清楚。

2. 文法改造与预测分析表：LL(1) 能跑起来的前提

2.1 原始 if-else 文法为什么不能直接上 LL(1)

课本上常见的 if-else 语句文法长这样：

S -> if E then S else S S -> if E then S S -> id := E E -> id

这个文法有两个致命问题。第一，S -> if E then S else S和S -> if E then S有公共左前缀if E then S，LL(1) 要求同一非终结符的多个候选式 FIRST 集不相交，这里显然冲突。第二，else的悬挂问题在 LL(1) 里表现为 FOLLOW 集和 FIRST 集的交叉，如果不处理，预测分析表里会出现多重入口。常见做法是提取左公因子，把if E then S后面的部分做成可选后缀：

S -> if E then S S' S' -> else S | ε S -> id := E E -> id

这样S的两个候选式分别是if和id开头，FIRST 集不冲突。S'的候选式是else和ε，需要计算 FOLLOW(S') 来判断 ε 何时可以选。FOLLOW(S') 包含else吗？不包含，因为S'后面不会再跟else。FOLLOW(S') = FOLLOW(S) = {else, $}，但else已经在 FIRST(else S) 里，所以当 lookahead 是else时选else S，是$或其他 FOLLOW 符号时选 ε。这里有个细节：如果S出现在S' -> else S的末尾，那么 FOLLOW(S) 会包含 FOLLOW(S')，形成循环依赖，手算时要注意迭代到不动点。

2.2 FIRST 集和 FOLLOW 集的手算与验证

我一般会先用一个小脚本把 FIRST 和 FOLLOW 算出来，避免手算出错。下面这段 Python 代码可以直接跑，输入就是上面改造后的文法：

# 计算 FIRST 和 FOLLOW 集的小工具 grammar = { 'S': [['if', 'E', 'then', 'S', "S'"], ['id', ':=', 'E']], "S'": [['else', 'S'], ['ε']], 'E': [['id']] } non_terminals = list(grammar.keys()) terminals = {'if', 'then', 'else', 'id', ':=', '$', 'ε'} FIRST = {nt: set() for nt in non_terminals} FOLLOW = {nt: set() for nt in non_terminals} FOLLOW['S'].add('$') def first_of_sequence(seq): result = set() for sym in seq: if sym in terminals and sym != 'ε': result.add(sym) return result elif sym in non_terminals: result |= (FIRST[sym] - {'ε'}) if 'ε' not in FIRST[sym]: return result result.add('ε') return result changed = True while changed: changed = False for nt, prods in grammar.items(): for prod in prods: before = len(FIRST[nt]) FIRST[nt] |= first_of_sequence(prod) if len(FIRST[nt]) != before: changed = True changed = True while changed: changed = False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym in non_terminals: before = len(FOLLOW[sym]) rest = prod[i+1:] first_rest = first_of_sequence(rest) FOLLOW[sym] |= (first_rest - {'ε'}) if 'ε' in first_rest: FOLLOW[sym] |= FOLLOW[nt] if len(FOLLOW[sym]) != before: changed = True print("FIRST:", {k: sorted(v) for k, v in FIRST.items()}) print("FOLLOW:", {k: sorted(v) for k, v in FOLLOW.items()})

跑出来 FIRST(S) = {if, id}，FIRST(S') = {else, ε}，FIRST(E) = {id}。FOLLOW(S) = {$, else}，FOLLOW(S') = {$, else}，FOLLOW(E) = {then}。注意 FOLLOW(S) 里的else来自S' -> else S中 S 后面跟的是 FOLLOW(S')，而 FOLLOW(S') 又包含 FOLLOW(S)，迭代后收敛。这个结果直接决定预测分析表的填法：S遇到if选第一条，遇到id选第二条；S'遇到else选else S，遇到$选 ε；E遇到id选id。

2.3 预测分析表的构造与冲突检查

预测分析表是一个二维表，行是非终结符，列是终结符。填表规则：对每个产生式 A -> α，对 FIRST(α) 中每个终结符 a，把 A -> α 填入 M[A, a]；如果 ε 在 FIRST(α) 中，对 FOLLOW(A) 中每个终结符 b，把 A -> α 填入 M[A, b]。填完后检查每个格子是否只有一个产生式，如果有多个就是冲突，说明文法不是 LL(1) 的。上面改造后的文法填出来是：

这张表没有冲突，说明文法是 LL(1) 的。注意then列在 S 和 S' 行都是空的，因为then只出现在产生式内部，不会作为某个非终结符的 lookahead 出现在栈顶。如果你手算的表里then列有内容，大概率是 FOLLOW 集算错了。

3. 递归下降翻译器：把语义动作嵌进语法分析

3.1 递归下降框架与四元式数据结构

递归下降是最直观的实现方式，每个非终结符对应一个函数，函数内部根据 lookahead 选择产生式，并在匹配终结符的过程中执行语义动作。四元式用四元组(op, arg1, arg2, result)表示，常见操作有:=（赋值）、if（条件跳转）、el（else 跳转）、ie（if 结束跳转）。我一般用一个列表存四元式，再用一个整数记录下一条四元式的编号，方便回填跳转目标。

quads = [] # 四元式列表 temp_count = 0 # 临时变量计数 def new_temp(): global temp_count temp_count += 1 return f"t{temp_count}" def emit(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) return len(quads) - 1 # 返回当前四元式索引 def backpatch(index, target): op, arg1, arg2, result = quads[index] quads[index] = (op, arg1, arg2, target)

emit返回索引是为了后面回填。比如if四元式生成时还不知道跳转目标，先填一个占位符，等 else 部分或整个 if 语句翻译完再回填。backpatch就是干这个的。临时变量t1、t2用来存表达式结果，虽然这个文法里表达式只有id，但扩展成算术表达式时这套机制直接能用。

3.2 递归下降函数与语义动作的嵌入

下面是最核心的递归下降翻译器代码，每个函数对应一个非终结符，语义动作直接写在匹配过程中：

tokens = [] # 词法分析后的 token 列表 pos = 0 def peek(): return tokens[pos] if pos < len(tokens) else '$' def match(expected): global pos if peek() == expected: pos += 1 else: raise SyntaxError(f"期望 {expected}，实际 {peek()}") def parse_S(): if peek() == 'if': match('if') # 条件表达式翻译，这里简化成直接取 id cond = parse_E() match('then') # 生成条件跳转四元式，目标待回填 jf_index = emit('if', cond, '-', -1) parse_S() # 生成 else 跳转，目标待回填 jmp_index = emit('el', '-', '-', -1) # 回填条件跳转为当前地址（else 分支开始） backpatch(jf_index, len(quads)) parse_S_prime() # 回填 else 跳转到 if 结束 backpatch(jmp_index, len(quads)) elif peek() == 'id': var = peek() match('id') match(':=') val = parse_E() emit(':=', val, '-', var) else: raise SyntaxError(f"S 无法处理 {peek()}") def parse_S_prime(): if peek() == 'else': match('else') parse_S() elif peek() in ('$', 'else'): # ε 产生式，什么都不做 pass else: raise SyntaxError(f"S' 无法处理 {peek()}") def parse_E(): var = peek() match('id') return var

这段代码的逻辑说明：parse_S遇到if时，先翻译条件表达式得到cond，然后生成if cond - ?四元式，问号位置等 else 分支开始地址确定后回填。接着翻译 then 分支的语句，再生成el - - ?四元式，这个跳转要跳过 else 分支。然后回填if四元式的目标为当前地址（即 else 分支的第一条四元式），翻译 else 分支，最后回填el四元式的目标为整个 if 语句结束后的地址。parse_S_prime遇到else就继续翻译 else 分支，遇到$就选 ε 产生式直接返回。parse_E在这个简化文法里只返回变量名，如果扩展成算术表达式，需要在这里生成临时变量和运算四元式。

3.3 四元式序列的生成与回填验证

假设输入是if a then x := b else y := c，词法分析后 tokens 是['if', 'id', 'then', 'id', ':=', 'id', 'else', 'id', ':=', 'id', '$']。跑一遍上面的递归下降，四元式序列大致是：

0: (if, a, -, 2) 1: (:=, b, -, x) 2: (el, -, -, 4) 3: (:=, c, -, y) 4: ...

第 0 条if a - 2表示如果 a 为假，跳转到第 2 条。第 1 条是 then 分支的赋值。第 2 条el - - 4表示无条件跳转到第 4 条，跳过 else 分支。第 3 条是 else 分支的赋值。第 4 条是 if 语句结束后的下一条指令。这个序列的逻辑是：a 为真时执行第 1 条，然后第 2 条跳到第 4 条；a 为假时第 0 条直接跳到第 2 条，执行第 3 条，然后自然进入第 4 条。回填的关键是backpatch(jf_index, len(quads))在翻译 else 分支之前执行，此时len(quads)正好是 else 分支第一条四元式的索引。backpatch(jmp_index, len(quads))在翻译完 else 分支后执行，此时len(quads)是 if 语句结束后的索引。

提示：回填时机是递归下降翻译器最容易翻车的地方。如果你在翻译 else 分支之后才回填if四元式，目标地址会指向 else 分支内部，导致条件为假时跳过 else 分支，逻辑完全反了。

4. 栈式 LL(1) 分析器：非递归实现与四元式同步生成

4.1 栈式分析器的工作流程

递归下降写起来直观，但有些场景要求非递归实现，比如分析表驱动的通用框架。栈式 LL(1) 分析器用一个栈存符号，初始压入$和开始符号S，然后循环读 lookahead，查预测分析表决定展开哪个产生式。展开时把产生式右部逆序压栈，同时执行语义动作。语义动作的执行时机和递归下降不同：递归下降是在函数调用返回时执行，栈式分析器是在弹出非终结符并展开时执行。对于 if-else 翻译，关键是在展开S -> if E then S S'时生成if四元式并记录回填位置，在展开S' -> else S时生成el四元式，在S' -> ε时回填。

def parse_stack(tokens): stack = ['$', 'S'] pos = 0 while stack: top = stack.pop() lookahead = tokens[pos] if pos < len(tokens) else '$' if top in terminals or top == '$': if top == lookahead: pos += 1 if top == '$': break else: raise SyntaxError(f"终结符不匹配：栈顶 {top}，输入 {lookahead}") else: # 查预测分析表 prod = parsing_table.get((top, lookahead)) if prod is None: raise SyntaxError(f"无产生式：{top} 遇到 {lookahead}") # 语义动作：根据产生式生成四元式 if top == 'S' and prod == ['if', 'E', 'then', 'S', "S'"]: # 这里需要先翻译 E，但栈式分析器里 E 还没展开 # 常见做法是用一个语义栈暂存条件变量 pass # 逆序压栈 for sym in reversed(prod): if sym != 'ε': stack.append(sym)

这段代码只展示了框架，实际语义动作需要配合语义栈。比如展开S -> if E then S S'时，E还没被翻译，条件变量未知，所以不能立刻生成if四元式。常见做法是在语义栈里压一个占位符，等E翻译完把条件变量填进去，再生成四元式。这比递归下降麻烦，但好处是分析器完全由预测分析表驱动，换文法只需要换表。

4.2 语义栈与四元式回填的配合

栈式分析器的语义动作通常用语义栈实现。每个符号对应一个语义值，非终结符的语义值在展开时计算。对于 if-else，我一般这样设计：S的语义值是它翻译完后的下一条四元式索引，E的语义值是条件变量名，S'的语义值是回填信息。展开S -> if E then S S'时，先压入一个标记，等E展开完把条件变量传到标记位置，然后生成if四元式并记录索引。展开S' -> else S时，生成el四元式并记录索引，同时回填之前记录的if四元式目标为当前地址。展开S' -> ε时，回填el四元式目标为当前地址。这套机制和递归下降的回填逻辑等价，只是执行顺序由栈的弹出顺序决定。

注意：栈式分析器里S' -> ε的触发条件是 lookahead 在 FOLLOW(S') 中。如果你的 FOLLOW 集算错，ε 产生式可能在不该选的时候被选中，导致四元式回填目标错位。建议先用 2.2 的脚本验证 FOLLOW 集，再写分析器。

4.3 两种实现方式的对比与选型

递归下降和栈式分析器都能完成 LL(1) 翻译，选哪个取决于你的场景。递归下降代码可读性好，语义动作嵌入自然，适合课程设计和快速原型。栈式分析器更接近“表驱动”的通用框架，换文法只需要改预测分析表和语义动作映射，适合需要支持多种语句类型的翻译器。但栈式分析器的语义动作执行时机不直观，回填逻辑容易写错，调试成本高。我一般建议先用递归下降把四元式生成逻辑跑通，再移植到栈式分析器验证。如果你只需要交课程设计，递归下降足够；如果你要扩展成完整的中间代码生成器，栈式分析器更容易维护。

5. 避坑与排查：LL(1) 翻译器常见的五个翻车点

5.1 现象：预测分析表出现多重入口，程序运行时选错产生式

原因：文法没有提取左公因子，或者 FIRST 集计算时漏掉了 ε 的传播。比如S -> if E then S else S和S -> if E then S同时存在，if列会有两个产生式。解决：按 2.1 的方式提取左公因子，把else S做成可选后缀S'。如果 FIRST 集里 ε 没有正确传播，比如A -> B C，B 可以推导 ε，但 FIRST(A) 没包含 FIRST(C)，也会导致表冲突。用 2.2 的脚本重新算一遍，确认每个非终结符的 FIRST 集包含所有可能的开头终结符。

5.2 现象：四元式跳转目标指向错误，if 和 else 分支执行顺序颠倒

原因：回填时机错误。递归下降里，if四元式的目标应该在翻译 else 分支之前回填为当前地址，el四元式的目标应该在翻译完 else 分支后回填。如果顺序反了，条件为假时会跳过 else 分支。解决：在parse_S里严格按“生成 if 四元式 -> 翻译 then -> 生成 el 四元式 -> 回填 if -> 翻译 else -> 回填 el”的顺序执行。可以用 3.3 的四元式序列对照检查，第 0 条的目标应该是 else 分支第一条的索引。

5.3 现象：嵌套 if-else 时四元式回填互相覆盖

原因：嵌套结构里内层 if 的回填索引和外层冲突，或者用了全局变量存回填位置，内层覆盖了外层的值。解决：每个parse_S调用用局部变量存jf_index和jmp_index，不要用全局变量。递归下降天然支持这一点，因为每次函数调用都有独立的栈帧。栈式分析器需要用语义栈区分不同层级的回填信息，常见做法是压入一个元组(jf_index, jmp_index)，展开时弹出对应层级的。

5.4 现象：词法分析器把:=拆成:和=，导致语法错误

原因：词法分析器没有正确处理双字符运算符。:=是一个 token，不是两个。解决：在词法分析器里用最长匹配原则，遇到:时先看下一个字符是不是=，是就返回:=，否则返回:或报错。类似地，<=、>=、<>这些双字符运算符都要这样处理。如果你用的词法生成工具，检查规则里:=是否写在:前面，因为有些工具按规则顺序匹配。

5.5 现象：临时变量命名冲突，多个表达式共用同一个t1

原因：临时变量计数器没有全局递增，或者递归调用时计数器被重置。解决：用全局变量temp_count，每次new_temp递增。如果多线程或多次翻译，每次翻译前重置计数器。另外，如果表达式翻译里嵌套调用new_temp，确保计数器是全局的，不要在每个函数里重新初始化。这个坑在扩展算术表达式时特别常见，比如a := b + c + d，如果计数器不递增，三个临时变量都叫t1，四元式序列就乱了。

6. 进阶技巧：用四元式解释器验证翻译结果

写完翻译器只是第一步，怎么确认生成的四元式真的能跑？我一般会再写一个四元式解释器，模拟执行四元式序列，看变量最终值是否符合预期。这个解释器不需要复杂，支持:=、if、el三种操作就够了。下面是一个最小实现：

def execute_quads(quads, variables): pc = 0 while pc < len(quads): op, arg1, arg2, result = quads[pc] if op == ':=': # arg1 是源变量或常量，result 是目标变量 variables[result] = variables.get(arg1, arg1) pc += 1 elif op == 'if': # arg1 是条件变量，result 是跳转目标 cond = variables.get(arg1, arg1) if not cond: pc = result else: pc += 1 elif op == 'el': # 无条件跳转 pc = result else: raise RuntimeError(f"未知操作：{op}") return variables # 测试：if a then x := b else y := c # 假设 a=True, b=10, c=20 quads = [ ('if', 'a', '-', 2), (':=', 'b', '-', 'x'), ('el', '-', '-', 4), (':=', 'c', '-', 'y'), ] vars_true = {'a': True, 'b': 10, 'c': 20} execute_quads(quads, vars_true) print(vars_true) # 期望 x=10, y 未定义 vars_false = {'a': False, 'b': 10, 'c': 20} execute_quads(quads, vars_false) print(vars_false) # 期望 y=20, x 未定义

这个解释器的逻辑说明：pc是程序计数器，指向当前四元式。:=操作把arg1的值赋给result，如果arg1不在变量表里就当作常量。if操作检查arg1的值，为假时跳转到result指定的索引，为真时pc加一。el操作无条件跳转到result。跑一遍a=True的情况，第 0 条if a - 2条件为真，pc变成 1，执行第 1 条x := b，pc变成 2，第 2 条el - - 4跳转到 4，循环结束，x=10，y未定义。a=False时，第 0 条条件为假，pc直接变成 2，执行第 3 条y := c，pc变成 4，循环结束，y=20，x未定义。这个结果和 if-else 的语义一致。

提示：解释器里变量表用字典存，布尔值直接当条件用。如果你的语言里条件是真假值，确保variables.get(arg1, arg1)返回的是布尔类型。如果条件变量未定义，get返回变量名本身，非空字符串在 Python 里是真值，会导致逻辑错误。建议在解释器里加一个检查，条件变量必须在变量表里。

从那以后我每次写完翻译器，都强制走一遍“生成四元式 -> 解释执行 -> 对比预期”的流程，不再靠肉眼看四元式序列。这个习惯帮我抓出了至少三次回填目标错位的问题，尤其是嵌套 if-else 的时候，肉眼根本看不出第 7 条四元式的跳转目标应该是 12 还是 13。希望帮到你。

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