简介这份资源面向编译原理课程学习者与编译器前端开发者聚焦IF-ELSE条件语句的翻译程序设计采用LL(1)预测分析法完成语法解析并输出四元式中间代码帮助理解词法分析、语法分析与语义分析阶段的衔接逻辑。压缩包共17个文件约417KB包含cpp与h源码、vcproj与sln工程文件、rc与res资源文件、obj与pdb等编译产物以及txt说明与htm文档构成一套可直接在Visual Studio中打开运行的完整工程。资源重点演示如何识别IF、ELSE关键字构建语法树并生成测试条件、跳转等四元式序列同时涉及嵌套IF-ELSE、空语句与复合语句的处理思路Compare相关文件可用于对照条件判断的实现细节。目前已有540人学习下载适合需要完成课程设计或深入理解LL(1)分析法与中间代码生成的读者参考。1. 从一段 if-else 到四元式为什么我建议你亲手拆一遍这个翻译程序很多人第一次接触编译原理看到“LL(1) 分析法”“输出四元式”这些词就头大觉得这是门纯理论的课考试背背 FIRST 集、FOLLOW 集就过去了。但真正做过一遍 IF-ELSE 条件语句的翻译程序设计之后你会发现它其实是一条完整的、可运行的流水线词法分析把if (a b) x 1; else x 2;拆成 token 流LL(1) 语法分析一边推导一边做语义动作最后吐出四元式这种中间代码。这套东西的价值在于它把“编译器前端”这个黑匣子拆成了你能看懂、能改、能调试的模块。适合谁正在做编译原理课程设计的学生、想补编译前端基础的初中级工程师以及需要给自研 DSL 或规则引擎做语法解析的开发者。下面我按自己复现时的顺序把选型理由、代码骨架和踩过的坑一条条摊开。2. LL(1) 文法设计与 FIRST/FOLLOW 集先把预测分析表算对2.1 为什么 IF-ELSE 翻译要选 LL(1) 而不是 LRLL(1) 的核心优势是“从左到右扫描、最左推导、只需向前看一个 token”。对于 IF-ELSE 这种结构它的文法可以写成很直观的递归下降形式手工构造预测分析表也不复杂。常见做法是先把文法写成S - if ( E ) S else S S - id E E - E T | T T - id | num但这里有个经典问题E - E T | T存在左递归LL(1) 不能直接处理。所以必须先消除左递归改写成E - T E E - T E | ε T - id | num这样每个非终结符的候选式首符号集互不相交才能做预测分析。选 LL(1) 的另一个理由是它和语义动作的结合非常自然——在递归下降的每个函数里你可以在匹配 token 的同时生成四元式不需要像 LR 那样维护复杂的状态栈和归约动作表。2.2 手算 FIRST 和 FOLLOW 集的具体步骤FIRST 集的计算规则如果 X 是终结符FIRST(X) {X}如果 X 是非终结符且有产生式 X - Y1Y2...Yk先把 FIRST(Y1) 中非 ε 的符号加入 FIRST(X)如果 Y1 能推出 ε再继续看 Y2以此类推。对于上面的改写后文法FIRST(E) FIRST(T) { id, num }FIRST(E) { , ε }FIRST(S) { if, id }FOLLOW 集的计算对于开始符号 S把$加入 FOLLOW(S)如果有产生式 A - αBβ把 FIRST(β) 中非 ε 的符号加入 FOLLOW(B)如果 β 能推出 ε 或 β 不存在把 FOLLOW(A) 加入 FOLLOW(B)。算出来FOLLOW(S) { $, else }FOLLOW(E) { ) }FOLLOW(E) FOLLOW(E) { ) }FOLLOW(T) FIRST(E) 非 ε 部分 ∪ FOLLOW(E) { , ) }这些集合直接决定预测分析表的每一行填什么。我建议你手算一遍再用代码验证因为后面写递归下降时判断“当前 token 是否属于某个候选式的 FIRST 集”就是靠这些结果。2.3 用 Python 实现预测分析表的构建下面这段代码把文法规则和 FIRST/FOLLOW 集硬编码进去生成一张预测分析表。实际写的时候你可以把文法存成字典自动算 FIRST/FOLLOW但手工课设里硬编码更直观。# 文法规则非终结符 - [候选式列表] grammar { S: [[if, (, E, ), S, else, S], [id, , E]], E: [[T, E]], E: [[, T, E], [ε]], T: [[id], [num]] } # 手工算好的 FIRST 和 FOLLOW 集 first { S: {if, id}, E: {id, num}, E: {, ε}, T: {id, num} } follow { S: {$, else}, E: {)}, E: {)}, T: {, )} } def build_table(): table {} for nt, productions in grammar.items(): for prod in productions: # 计算该候选式的 FIRST 集 first_set set() for sym in prod: if sym in first: first_set | (first[sym] - {ε}) if ε not in first[sym]: break else: first_set.add(sym) break else: first_set.add(ε) # 对 FIRST 集中每个终结符填表 for terminal in first_set - {ε}: table[(nt, terminal)] prod # 如果候选式能推出 ε用 FOLLOW 集填表 if ε in first_set: for terminal in follow[nt]: table[(nt, terminal)] prod return table table build_table() for key, val in sorted(table.items()): print(fM[{key[0]}, {key[1]}] { .join(val)})逻辑说明外层遍历每个非终结符的每条候选式先算这条候选式的 FIRST 序列。如果候选式第一个符号是终结符直接填入如果是非终结符取其 FIRST 集去掉 ε若该非终结符不能推出 ε 就停止否则继续看下一个符号。如果整条候选式都能推出 ε就用左部非终结符的 FOLLOW 集填表。参数说明grammar字典的键是非终结符值是一个列表每个元素是一条候选式的符号列表first和follow是手工算好的集合实际项目中可以用迭代算法自动求。提示预测分析表里同一个格子如果被填了两次说明文法不是 LL(1) 的需要提取左公因子或消除左递归。3. 递归下降翻译器在语法分析的同时生成四元式3.1 四元式的结构定义与生成时机四元式就是(op, arg1, arg2, result)四元组。比如x a b翻译成(, a, b, t1)和(, t1, -, x)。对于 IF-ELSE关键是控制流的跳转if (a b) x 1; else x 2;要生成条件跳转和无条件跳转。常见做法是遇到if时先记下条件表达式的四元式位置生成一个(j, a, b, 0)占位等)匹配后回填跳转目标。然后翻译 then 分支的语句。遇到else时生成一个(j, -, -, 0)跳过 else 分支并回填 if 的跳转目标到 else 分支的第一条四元式。翻译 else 分支后回填(j, -, -, 0)的目标到整个 if-else 之后。这种“回填”技术是翻译程序设计的核心技巧也是课设里最容易出错的地方。3.2 递归下降函数骨架与语义动作嵌入下面是一个简化版的递归下降翻译器只处理赋值和 if-else表达式只支持id和num的比较。代码里用next_quad记录下一条四元式的索引用emit生成四元式用backpatch回填跳转目标。quads [] # 四元式列表 next_quad 0 # 下一条四元式的索引 tokens [] # 词法分析后的 token 列表 pos 0 # 当前 token 位置 def emit(op, arg1, arg2, result): global next_quad quads.append((op, arg1, arg2, result)) next_quad 1 return next_quad - 1 def backpatch(quad_index, target): op, arg1, arg2, _ quads[quad_index] quads[quad_index] (op, arg1, arg2, target) def match(expected): global pos if pos len(tokens) and tokens[pos] expected: pos 1 else: raise SyntaxError(f期望 {expected}实际 {tokens[pos] if pos len(tokens) else EOF}) def parse_S(): if tokens[pos] if: match(if) match(() # 解析条件表达式返回 (arg1, op, arg2) arg1, op, arg2 parse_condition() match()) # 生成条件跳转占位 jmp_quad emit(fj{op}, arg1, arg2, 0) parse_S() # then 分支 if tokens[pos] else: match(else) # 生成无条件跳转占位跳过 else 分支 else_jmp emit(j, -, -, 0) # 回填条件跳转到 else 分支起点 backpatch(jmp_quad, next_quad) parse_S() # else 分支 # 回填无条件跳转到 if-else 之后 backpatch(else_jmp, next_quad) else: # 没有 else条件跳转到 if-else 之后 backpatch(jmp_quad, next_quad) elif tokens[pos] id: target tokens[pos] match(id) match() # 解析表达式返回结果临时变量或值 result parse_expr() emit(, result, -, target) else: raise SyntaxError(f无法识别的语句起始: {tokens[pos]}) def parse_condition(): # 简化处理只支持 id op id/num arg1 tokens[pos] match(id) op tokens[pos] match(op) # 假设 op 是 等 arg2 tokens[pos] if arg2.isdigit(): match(num) else: match(id) return arg1, op, arg2 def parse_expr(): # 简化处理只支持单个 id 或 num if tokens[pos].isdigit(): val tokens[pos] match(num) return val else: val tokens[pos] match(id) return val逻辑说明parse_S是入口遇到if时先解析条件生成条件跳转四元式并记下索引然后递归解析 then 分支如果后面跟着else生成一个无条件跳转占位把条件跳转的目标回填到当前next_quad即 else 分支的第一条四元式再解析 else 分支最后把无条件跳转的目标回填到 if-else 之后。参数说明tokens是词法分析输出的 token 列表pos是当前读取位置emit返回新四元式的索引供backpatch使用backpatch修改四元式的第四个字段实现跳转目标的回填。3.3 词法分析接口与 token 流准备上面的翻译器假设tokens已经准备好了。实际项目中你需要先写一个简单的词法分析器把源代码字符串转成 token 列表。常见做法是用正则表达式逐行匹配import re def tokenize(source): token_spec [ (IF, r\bif\b), (ELSE, r\belse\b), (ID, r[a-zA-Z_]\w*), (NUM, r\d), (OP, r[!]?|), (ASSIGN, r), (LPAREN, r\(), (RPAREN, r\)), (SEMI, r;), (SKIP, r[ \t\n]), ] tok_regex |.join(f(?P{name}{pattern}) for name, pattern in token_spec) tokens [] for mo in re.finditer(tok_regex, source): kind mo.lastgroup value mo.group() if kind SKIP: continue if kind IF: tokens.append(if) elif kind ELSE: tokens.append(else) elif kind ID: tokens.append(id) elif kind NUM: tokens.append(num) elif kind OP: tokens.append(value) elif kind ASSIGN: tokens.append() elif kind LPAREN: tokens.append(() elif kind RPAREN: tokens.append()) elif kind SEMI: tokens.append(;) return tokens逻辑说明token_spec定义了 token 的正则模式re.finditer按顺序扫描源代码。注意IF和ID的顺序——if必须放在ID前面否则if会被当成普通标识符。参数说明source是源代码字符串返回的tokens列表里关键字和符号直接存字符串标识符和数字统一存成id和num这样翻译器只需要判断 token 类型不需要关心具体值。实际课设里标识符的具体名字要存在另一个符号表里这里为了简化省略了。4. 四元式输出与回填把跳转目标写对4.1 四元式列表的格式化输出生成完四元式后需要按格式打印出来。常见格式是每行一条带序号def print_quads(quads): for i, (op, arg1, arg2, result) in enumerate(quads): print(f{i:3d}: ({op}, {arg1}, {arg2}, {result}))对于if (a b) x 1; else x 2;期望输出类似0: (j, a, b, 2) 1: (, 1, -, x) 2: (j, -, -, 3) 3: (, 2, -, x)注意第 0 条四元式的 result 是 2表示条件为真时跳转到第 2 条else 分支的第一条。第 2 条无条件跳转到第 3 条之后即整个 if-else 结束。这里第 3 条是 else 分支的赋值跳转目标应该是 4下一条但示例里只有 4 条四元式所以回填成 4 也可以。4.2 回填过程中的边界情况回填最容易翻车的地方是嵌套 if-else。比如if (a b) if (c d) x 1; else x 2; else x 3;这里 else 的匹配遵循“就近原则”第二个 else 属于内层 if。递归下降天然支持这种嵌套因为parse_S递归调用时每个if都有自己的jmp_quad和else_jmp局部变量。但如果你用栈来管理回填就要注意栈的压入和弹出顺序。我一般会在parse_S里用局部变量保存跳转索引递归返回后自动失效避免全局状态污染。另一个边界是条件表达式里出现函数调用或复杂表达式。上面的简化版只支持id op id/num实际课设可能要求支持a b c * d。这时候需要先翻译表达式把结果存到临时变量再用临时变量做条件跳转。临时变量的命名可以用t1, t2, ...递增。4.3 用符号表管理变量地址四元式里的arg1、arg2、result可以是变量名、常量或临时变量。如果目标代码是汇编还需要把变量名映射到内存地址或寄存器。课设里通常只要求输出四元式所以直接用变量名即可。但如果你要生成可执行代码就需要符号表symbol_table {} temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def lookup(name): if name not in symbol_table: symbol_table[name] len(symbol_table) return symbol_table[name]逻辑说明new_temp生成新的临时变量名lookup返回变量在符号表中的索引。参数说明symbol_table字典的键是变量名值是分配的内存偏移或索引temp_count是临时变量计数器。实际项目中符号表还要记录类型、作用域等信息这里只保留最简结构。5. 避坑与排查LL(1) 翻译程序设计的五个血泪经验5.1 现象预测分析表出现多重入口程序报“不是 LL(1) 文法”原因文法存在左递归或左公因子导致同一个非终结符在同一终结符下有多个候选式。比如S - if ( E ) S else S和S - if ( E ) S同时存在时遇到if就不知道选哪条。解决提取左公因子把S - if ( E ) S else S | if ( E ) S改写成S - if ( E ) S SS - else S | ε。这样S的候选式首符号集是{else, ε}互不相交。5.2 现象四元式跳转目标全是 0运行结果不对原因回填时没有正确更新next_quad或者backpatch修改的是副本而不是原列表。Python 里元组是不可变的quads[quad_index] (op, arg1, arg2, target)是重新赋值必须确保quads是列表且索引正确。解决在emit里返回索引在backpatch里用索引直接修改列表元素。调试时打印每条四元式生成时的next_quad值确认回填时机。5.3 现象嵌套 if-else 的 else 匹配错误原因递归下降里parse_S递归调用后tokens[pos]可能已经指向外层 else但内层 if 没有 else 分支导致外层 else 被内层消费。解决在parse_S里判断tokens[pos] else之前先确认当前递归层级是否允许匹配 else。常见做法是给parse_S加一个参数allow_else内层 if 没有 else 时不消费 else留给外层。5.4 现象词法分析把if识别成标识符原因正则表达式的顺序问题。ID模式[a-zA-Z_]\w*会匹配if如果IF模式放在ID后面if就被当成标识符。解决把关键字模式放在标识符模式前面或者用\b单词边界确保if独立匹配。类似地else、while、for等关键字都要优先匹配。5.5 现象表达式翻译时临时变量重复或丢失原因new_temp的计数器没有全局唯一或者递归下降时临时变量名冲突。解决用全局计数器生成t1, t2, ...每次调用new_temp递增。如果支持嵌套表达式确保每个子表达式的临时变量在父表达式使用前已经生成。调试时打印临时变量分配顺序对照四元式检查。6. 进阶技巧用栈式回填支持任意嵌套与表达式优先级上面递归下降的回填方式对嵌套 if-else 已经够用但如果你要支持while、for或者带优先级的算术表达式手动管理跳转索引会越来越乱。我后来改用一个显式的回填栈每遇到一个需要回填的跳转就把四元式索引压栈当目标位置确定时从栈里弹出并回填。这样嵌套结构天然由栈的深度管理不需要在每个递归函数里传局部变量。具体做法是维护一个backpatch_stack列表emit生成跳转四元式时把索引压入backpatch_to_here把栈里所有索引的目标设为当前next_quad。对于 if-else条件跳转压栈then 分支结束后弹出并回填到 else 起点无条件跳转压栈else 分支结束后回填到 if-else 之后。对于表达式可以用算符优先法或递归下降加优先级表把a b * c翻译成先乘后加的四元式序列。验证方法写一个简单的解释器按四元式顺序执行遇到跳转就修改程序计数器。如果解释器能正确算出if (a b) x 1; else x 2;的结果说明四元式生成正确。我一般会准备三组测试用例单层 if、单层 if-else、嵌套 if-else每组手动算一遍期望输出再和程序输出对比。从那以后我每次做翻译程序都强制先写测试用例再写回填逻辑避免跳转目标写错还找不到原因。希望帮到你。本文还有配套的精品资源点击获取