LL(1)分析法与IF-ELSE语句翻译：从预测分析表到四元式生成的完整指南

简介面向编译原理课程设计与编译器初学者的IF-ELSE条件语句翻译程序资源包聚焦LL(1)预测分析法与四元式中间代码生成覆盖词法分析、语法分析到语义翻译的完整流程。资源共17个文件以C源码cpp、工程配置vcproj、sln、资源脚本rc、aps、调试信息pdb、obj及说明文档txt为主压缩包仅417KB结构紧凑便于直接打开工程对照学习。已有540人学习下载。通过源码可深入理解LL(1)分析表构建、IF-ELSE嵌套与空语句处理、条件测试及跳转四元式如JNZ的生成思路同时附带比较运算相关实现便于掌握不同条件语句的翻译差异尤其适合作为编译原理课程实验、期末设计或自学参考。1. IF-ELSE条件语句的LL(1)翻译程序从文法到四元式这是一道绕不过去的编译原理硬题几乎每个学编译原理的人都会被安排一道“IF-ELSE条件语句翻译程序设计”的课程设计要求用 LL(1) 分析法做语法分析最终输出四元式。我第一次做这道题时以为难点在“写代码”结果代码写了一千行调试了三天最后发现真正的坑全在文法设计、预测分析表和回填地址这些看不见的地方。这道题把 LL(1) 判断、预测分析表构造、自顶向下分析和中间代码生成串成了一条完整的链路适合用来验证自己对“语法分析驱动翻译”这件事是不是真懂了。它面向的是正在做课程设计的学生、想补编译原理完整流程的开发者以及想复用一套“能跑通的分析器框架”的从业者。本文把这个项目的完整实现思路、关键代码和五个高频踩坑点全部拆开讲清楚。2. 文法设计与 LL(1) 判定先解决悬空 ELSE再造表2.1 从原文法到 LL(1) 文法的三步改造IF-ELSE 语句在 C、Java、Python 里看起来很简单一旦把它形式化写成文法第一个撞上的就是悬空 ELSEDangling-ELSE的二义性问题。经典文法如下S → if E then S | if E then S else S | other E → id这个文法存在经典的“悬空 else”冲突因为if E then S后面遇到else时既可以归约到第一个产生式也可以把else S作为当前 S 的一部分继续归约。分析表里同一个表项里会出现两个产生式入口LL(1) 判定直接失败。常见的改造有两种思路。一种是直接给 ELSE 规定“就近匹配”的优先级让else必须匹配最近的未闭合if。另一种是把文法重整成下面这个等价形式S → if E then S S | other S → else S | ε E → id这两种方式的本质相同——把else从句法结构里剥离出来用 S 这个“可选后缀”表达。这样原二义文法变成了无二义文法也具备构建 LL(1) 分析表的潜质。改造完成后必须对每个非终结符计算 FIRST 集和 FOLLOW 集。这里有一个反复折磨人的细节S → else S | ε里存在 ε 产生式而 ε 的存在会触发 FOLLOW 集的计算条件。你需要先求 FIRST(S) 为{else, ε}然后根据S → if E then S S这一条产生式把 FOLLOW(S) 传递到 S。不理解这条传递链后面构造预测分析表时很容易把else和$的入口搞混。2.2 计算 FIRST 与 FOLLOW 的可执行脚本拿 Python 写一个计算 FIRST 和 FOLLOW 的小工具这是一切后续工作的地基。下面这段代码能读取文法文件自动输出每个非终结符的 FIRST 集和 FOLLOW 集# first_follow.py from collections import defaultdict def calc_first(grammar, symbol): 计算单个符号的 FIRST 集递归实现 if symbol not in grammar: # 终结符FIRST 就是自身 return {symbol} result set() for production in grammar[symbol]: for char in production: result | calc_first(grammar, char) if ε not in calc_first(grammar, char): break # 不含 ε 就停止遍历该产生式 else: result.add(ε) # 所有符号都能推出 ε 才加 ε return result def calc_follow(grammar, start, nonterms): 计算所有非终结符的 FOLLOW 集 follow defaultdict(set) follow[start].add($) # 开始符号的 FOLLOW 必须有 $ changed True while changed: changed False for A in nonterms: for production in grammar[A]: for i, symbol in enumerate(production): if symbol in nonterms: # 只算非终结符的 FOLLOW beta production[i1:] if beta: # 右边还有符号 first_beta set() for b in beta: first_beta | calc_first(grammar, b) if ε not in calc_first(grammar, b): break follow[symbol] | (first_beta - {ε}) if ε in first_beta: follow[symbol] | follow[A] else: # 产生式末尾 follow[symbol] | follow[A] changed True if len(follow[symbol]) 0 else changed return follow if __name__ __main__: grammar { S: [if E then S S\, other], S\: [else S, ε], E: [id], } nonterms [S, S\, E] for nt in nonterms: print(fFIRST({nt}) , calc_first(grammar, nt)) follow calc_follow(grammar, S, nonterms) for nt in nonterms: print(fFOLLOW({nt}) , sorted(follow[nt]))代码中 calc_first 递归地处理产生式右侧的每一个符号只要当前符号的 FIRST 里有 ε 就继续向后看把 ε 传递到集合里。calc_follow 使用不动点迭代这是书上的标准算法但自己动手写一遍才能真正理解为什么S → else S | ε会随手带来“FOLLOW(S) 包含 FOLLOW(S)这个连锁反应。打印出来的结果是FIRST(S) {if, other} FIRST(S) {else, ε} FIRST(E) {id} FOLLOW(S) {$, else} FOLLOW(S) {$, else} FOLLOW(E) {then}这里 FOLLOW(S) 里出现了else等于说 S 后面既可以碰到 else 继续归约也可能碰到 $ 走到头这就是后面回填地址时的判断依据。2.3 判定 LL(1) 的三个条件有了 FIRST 和 FOLLOW 集之后对每个非终结符做判定就非常直接了LL(1) 文法必须同时满足三个条件第一每个产生式右侧的 FIRST 集两两不相交。比如S → if E then S S | other中{if}和{other}互斥没问题。第二对存在 ε 产生式的非终结符其 FOLLOW 集与其它产生式的 FIRST 集不相交。检查SFIRST(S) 中非 ε 部分是{else}而 FOLLOW(S) 是{$, else}两者有交集else冲突说明这个文法仍然不是严格意义的 LL(1) 文法需要更进一步处理。第三不存在任何非终结符能推出多个以相同符号开头的产生式。这里必然会遇到一个矛盾if-else 结构天然在S上有 FIRST/FOLLOW 冲突。实际工程中解决它有两种路线。路线一是修改文法将 S 的产生式分裂并用额外状态去消除冲突结果会改变原来的 AST 结构路线二是用“条件选择”的方式重写预测分析表让冲突位置优先选择else S产生式不真正把冲突消除只是人为强制选择。第二种方案在编译器教科书里出现频率更高因为它对代码生成阶段的影响最小——你仍然可以按就近匹配处理 else。这个决策要在这里记录清楚它意味着你的分析程序构造预测分析表时遇到冲突条目采用“先到先得”策略而这在工程上等价于强制匹配最近的未闭合 if与绝大多数语言的语义一致。3. 预测分析表与语法分析驱动把表构建出来然后让栈动起来3.1 预测分析表的构造算法有了改造后的文法和 FIRST/FOLLOW 集下一步是构造预测分析表 M。对每个产生式A → α执行以下规则对终结符 a 属于 FIRST(α)在 M[A, a] 中填入产生式A → α。如果 ε 在 FIRST(α)对 b 属于 FOLLOW(A)在 M[A, b] 中填入产生式A → ε。其它未填的格子全部标记为 error驱动时若查表查到 error 则报语法错误。对前面那个文法执行这条规则时第二个规则里M[S, else]不仅要填S → else S同时因为 FIRST(S) 里有 εFOLLOW(S) 里有 else又要在同一个格子填入S → ε。这种冲突在处理 IF-ELSE 时无法规避工程做法就是保留else S那条。Python 里用字典来保存表结构非常合适键是 (非终结符, 终结符) 二元组。# predict_table.py from itertools import product def build_table(grammar, nonterms, terms, first_set, follow_set): table {} for A, prods in grammar.items(): for alpha in prods: # 获取 FIRST(alpha) fa set() for ch in alpha: fa | first_set[ch] if ε not in first_set[ch]: break else: fa.add(ε) if ε in fa: # 规则2FOLLOW 集的终结符都要填 for b in follow_set[A]: if (A, b) in table: print(f冲突: M[{A}, {b}] 已有 {table[(A, b)]}, 强制用 {alpha}) table[(A, b)] alpha else: for b in fa: table[(A, b)] alpha return table这段代码的关键参数是 first_set 和 follow_set它们是字典类型前者存的是每个“符号”包括终结符的 FIRST 集后者只存非终结符的 FOLLOW 集。build_table 返回值是一个以二元组为键的字典二元组的第一维是非终结符第二维是输入终止符查询时直接table[(S\, else)]就能拿到产生式右侧字符串。3.2 驱动程序的栈式实现LL(1) 分析程序必须维护一个分析栈初始状态把$和开始符号S依次压栈。每次从栈顶取符号 X从输入缓冲区取当前记号 a然后分情况处理X 是终结符且等于 a则弹栈并读下一个记号X 是终结符且不等于 a报错X 是非终结符查 M[X, a] 得到产生式将 X 弹出并把产生式右侧符号逆序压栈查不到就报错。四元式输出和语法分析是交织在这个驱动过程中的。驱动到了if E then的某个归约节点时中间代码生成代码要同步触发。这里给出驱动程序的框架# driver.py def analyze(tokens, table, grammar, startS): stack [$, start] idx 0 steps [] while stack: top stack.pop() a tokens[idx] if idx len(tokens) else $ if top in grammar: # 非终结符 key (top, a) if key not in table: raise SyntaxError(fUnexpected token {a} at position {idx}) prod table[key] print(f展开 {top} - {prod}) if prod ! ε: stack.extend(reversed(prod.split())) # 这里可以挂翻译动作 else: # 终结符 if top a: idx 1 print(f匹配 {top}) else: raise SyntaxError(fExpected {top}, got {a}) if idx ! len(tokens): raise SyntaxError(Trailing tokens) print(分析成功)代码中的tokens是一个字符串列表比如[if, id, then, other, else, other, $]。prod 是按空格分割的产生式右侧逆序压栈的逻辑保证了最左推导的顺序。如果你想跟踪更细的步骤可以把每一步的栈状态 append 到一个列表里最后输出成 CSV这个技巧对调试分析表错误极其有用。3.3 翻译动作挂载在归约时生成四元式四元式生成不建议另写一份AST遍历代码而是直接在语法分析过程中内嵌翻译动作——这叫语法制导翻译。LL(1) 分析是自顶向下的所以需要用“继承属性”或“人为维护一个语义栈”来传递信息。简单做法是用一个全局的生成器对象class QuadGenerator: def __init__(self): self.quads [] self.temp_count 1 def new_temp(self): name ft{self.temp_count} self.temp_count 1 return name def new_label(self): return fL{self.temp_count}_label def emit(self, op, arg1, arg2, result): self.quads.append((op, arg1, arg2, result)) print(f({op}, {arg1}, {arg2}, {result}))同时在分析程序的语义栈里记录每个非终结符对应的“真出口”和“假出口”列表这些列表里的地址是尚未回填的。由于篇幅限制完整嵌入动作的关键是每当S → else S归约时需要拿到之前 if-then 分支生成的无条件跳转指令序号并把地址指向 else 中的第一条四元式。这一部分留到第四章单独处理。4. 输出四元式回填技术与目标地址的重定位4.1 条件语句翻译的基本模式IF-ELSE 的四元式翻译遵循公认的模式把条件 E 翻译为跳转指令序列再配合无条件跳转把 then 和 else 两个分支连接起来。基本结构为(E) 的四元式序列 (j, a, b, 0) # 若条件为假跳转到 else 分支入口 (then 分支语句的四元式) (j, _, _, 0) # 无条件跳过 else 分支 (else 分支语句的四元式)四元式中的第 4 分量 result 是目标地址这个地址在生成时常常未知要等后面的语句块生成了才知道写在哪儿所以先填 0 占位再把这条指令的编号记下来称之为“待回填地址”。这个翻译方案里最难理解的是“回填”backpatch机制。假设S → if E then S S这个产生式归约完成时E 的假出口列表保存在语义栈里then 分支之后的语句已经生成了若干四元式而 S 处理 else 分支时又会产生新的跳转这些跳转地址全部要“回头”修改已经生成的跳转指令的目标分量。4.2 一个可运行的回填实现以 Python 写一个最小可运行的 IF-ELSE 翻译组件# backpatch.py class TreeNode: def __init__(self, kind, valueNone): self.kind kind # if / then / else / assign / id self.value value self.true_list [] # 真出口待回填列表 self.false_list [] # 假出口待回填列表 self.next_list [] # 下一指令待回填列表 def backpatch(gen, addr_list, target): 把 addr_list 中的所有指令的第4分量改为 target for addr in addr_list: print(f回填: 第{addr}条四元式跳转目标 - {target}) quad gen.quads[addr] gen.quads[addr] (quad[0], quad[1], quad[2], target) def translate_if(gen, E_node, S1_node, S2_node): if E then S1 else S2 的翻译入口 # E_node.false_list 中记录的是条件为假时要跳转的指令序号 # 把假出口回填到 else 分支的第一条指令 else_label len(gen.quads) # else 分支从当前指令序号开始 backpatch(gen, E_node.false_list, else_label) # then 分支结束时生成无条件跳转, 目的是跳过 else jmp_idx len(gen.quads) gen.emit(j, _, _, 0) # 目标待回填 # 回填跳转到 else 结束后的位置 end_label len(gen.quads) backpatch(gen, [jmp_idx], end_label) backpatch(gen, S1_node.next_list, end_label) gen.quads_repr True return end_label这个组件中最核心的参数是E_node.false_list它在 E 条件翻译阶段被填充为“条件为假时应该跳转到的指令序号”。backpatch函数接收一个指令序号列表把所有指令的第四个字段改成同一个目标地址。值得特别提醒的是len(gen.quads)在 Python 里表示“下一条指令的序号”所以它能当标签用。这块代码里有个隐蔽的错误风险点jmp_idx必须在 emit 之前记录否则会差一导致回填到了错误的指令上。这本书上可能没讲透的一点是四元式的第 4 分量result在不同运算符下含义不同对跳转类指令它是目标地址对算术运算指令它是临时变量名对赋值指令它是左值。一个通用生成器里必须想办法区分指令类型否则回填函数会误改普通运算指令的字段。4.3 临时变量和布尔表达式的翻译顺序IF 条件 E 在常见题目里被简化为id或id op id这种关系表达式。若条件为id1 id2翻译顺序是# relop.py 对应四元式生成逻辑 def translate_relop(gen, id1, op, id2): quad_index len(gen.quads) gen.emit(j op, id1, id2, 0) # 例如 j a b 0 node TreeNode(relop) # 条件为真时顺序执行后续指令, 所以真出口是下一条指令 node.true_list [quad_index 1] node.false_list [quad_index] return node注意这里真出口和假出口的赋值方式j 这条指令的条件为真时“落入下一条指令”所以真出口是紧接着的指令序号条件为假时直接跳到第 4 分量指定的目标位置因此假出口列表记录当前的指令序号。这跟很多人惯常的思路是反的我第一次写成了 true_list 记录当前序号false_list 记下一跳导致回填后程序跳转位置全部错乱。关系运算符的映射表可参考下表源码操作符四元式运算符语义j小于时跳转j小于等于时跳转j相等时跳转!j!不等时跳转j大于时跳转j大于等于时跳转真实操作时关系运算符对应的四元式参数必须严格按照(运算符, 左操作数, 右操作数, 跳转目标)的格式输出很多检测程序就按照这个格式做单元测试。如果题目要求输出为三地址码风格则可以把 result 位置替换为临时变量名但目标地址检测程序一般认的是第 4 分量。5. 避坑手册LL(1) 与四元式翻译中五个高频翻车现场5.1 悬空 ELSE 的二义性导致 FIRST/FOLLOW 冲突递归下降分析却通过了现象按照改造后的文法用 Python 写了一个递归下降分析器测试if E then if E then other else other这种嵌套语句时结果完全正确。但换成查表驱动的预测分析器预测分析表构建时报出 “Conflict at M[S, else]”表格里同时存在S → else S和S → ε两个候选。原因递归下降天然支持“贪心匹配”——看到 else 就优先走 else S 分支语法上自动实现了就近匹配。但 LL(1) 分析表构造是按定义严格计算的冲突会被显式暴露出来。很多人因此认为递归下降分析已验证文法正确不必再修 LL(1) 条件导致后续实现卡死。解决在构建预测分析表时对冲突条目显式选择S → else S并列明这个选择背后是对语义优先级的人工决策。同时在代码注释里标记 TODO说明如果想严格满足 LL(1) 需要进一步改写文法。5.2 词法分析器把 else 当成标识符的一部分处理现象输入if a then b else c分析程序在第一轮就报Unexpected token elsec或类似错误分析表里根本查不到这个输入符号。原因词法分析正则写的太宽比如用[a-zA-Z_][a-zA-Z0-9_]*匹配标识符时没有把关键字表优先匹配。else、if、then 被吞进了标识符词法单元中。解决词法分析程序先查关键字表再回退到标识符匹配。具体做法是把关键字存放在一个 set 中每次匹配到字母开头的字符串后立即判断是否在关键字集合内若是则返回对应的终结符类型。建议用 Python 的enum定义 TokenType把 key word 和 ID 分开。# lexer_keyword.py import re KEYWORDS {if, else, then} def simple_lexer(code: str): tokens [] code code.strip() pos 0 patterns [ (ID, r[a-zA-Z_][a-zA-Z0-9_]*), (NUM, r\d), (OP, r[!]), (SKIP, r\s), ] while pos len(code): for kind, p in patterns: m re.match(p, code[pos:]) if m: text m.group() if kind ID and text in KEYWORDS: kind text.upper() # IF / ELSE / THEN if kind ! SKIP: tokens.append((kind, text)) pos len(text) break else: raise SyntaxError(f无法识别的字符: {code[pos]}) return tokens这里的关键是把关键词识别放在词法层完成而不是语法层否则语法分析中写(S, else)的查表逻辑时永远匹配不上。5.3 回填时误把四元式序号从 1 开始编号现象四元式输出如下(1) (j, a, b, 0) (2) (:, x, _, t1) ...程序运行时用len(gen.quads)取当前指令序号作为跳转目标结果回填的地址全部比实际目标大一跳转位置错位。原因四元式列表在 Python 里以 0 为起点但很多教材或课程设计检测要求从 1 开始展示。如果只在打印输出时加 1 而内部编号用 0-based是安全的问题出在把“展示编号”直接当成“内部索引”使用。解决内部统一使用 0-based 索引只在最终输出四元式文本时按“线性位置 1”打印。定义两个函数intern_to_display(i)和display_to_intern(i)打印和回填之外不允许直接做索引转换。5.4 语义栈属性传递顺序错误导致真假出口拿反现象if a b then x : 1 else x : 2翻译后条件判断变成了 a b 时执行 then 分支。检查四元式发现(j, a, b, else_entry)的跳转语义搞反了。原因LL(1) 自顶向下分析时产生式S → if E then S S里 E 的语义动作在匹配到then之前就已经完成了。因为 E 是第一个符号其翻译动作在进入 then 分支前执行但有些实现错误地在看到 then 之后才去查询 E 的属性。更隐蔽的错误是把 true_list 和 false_list 接反把 j 当作条件为真时跳转的指令来填列表。解决在产生式处理函数中先翻译 E立即把 true_list/false_list 保存到局部变量再继续处理后续符号。编写代码后用一条典型的if a b then x : 1 else x : 2做单元测试断言四元式的第三行必须是(j, _, _, L)且 L 指向 else 分支结束后的地址。5.5 嵌套 IF-ELSE 时语义栈的数据混入现象连续处理两个 IF 语句时第二个 IF 的回填地址错乱第一个 IF 的 next_list 被莫名其妙回填到第二个 IF 的三元式上。原因用一个全局 list 存放待回填地址而不是用栈帧的方式管理每一个未完成的 IF 的 list。在递归实现里for 循环遍历一个共享 list 时另一个递归分支又把新地址 append 进去迭代器直接无限增长。解决每个非终结符节点用自己的实例属性保存 true_list 与 false_list回填操作只针对当前节点持有的列表副本且操作完毕后立即置空列表。绝不能把这几个 list 放在类变量或全局变量上这条血的教训我每次都会强调。6. 进阶把翻译器扩展成支持 while-do 语句并验证目标程序正确性先从一个具体问题出发课程设计要求通常是“能翻译 IF-ELSE”但实际考试或实验验收时往往会加考一道 while-do 或 for 循环语句。而加一个循环语句的难度不在于语法分析——那只是多加两条产生式真正的复杂度在于回填的“循环起点”和“循环出口”是同一个地址而这个地址必须在循环体翻译之前就确定下来。设计文法扩展时我一般会把控制语句的统一语法改成S → if E then S S | while E do S | id : E S → else S | ε这会导致 FIRST(S) 新增while终结符需要更新 FIRST 和 FOLLOW。代码生成端 while 的四元式结构如下(loop_entry): E 的四元式序列 (j, a, b, exit_addr) # 条件为假跳走 S 的四元式序列 (j, _, _, loop_entry) # 无条件跳回 (exit):关键点是 loop_entry 是已知的当前指令序号而 exit_addr 是未知的要等 S 翻译完成后才能回填。在我的实现里用一个堆栈结构保存循环的入口和出口# while_translate.py def translate_while(gen, E_node, S_node): loop_entry len(gen.quads) # 进入循环体的位置 # E_node 的 false_list 指向跳转出口 exit_list E_node.false_list # 翻译循环体 S S_node.translate(gen) # 循环体结束回头跳 gen.emit(j, _, _, loop_entry) # 回填出口地址 exit_addr len(gen.quads) backpatch(gen, exit_list, exit_addr) return exit_addr这里的退出地址 len(gen.quads) 要特别小心它必须在 emit(j循环回跳指令) 之后取值因为循环变量的出口是循环体后面“首条指令”不能包含那一条跳转指令。如果取值顺序反了每次循环结束会把最后一条跳转指令本身也当作循环体内指令执行程序进入死循环。验证翻译正确性有两种方法。第一种比较考验基本功人工模拟一段源码手推四元式再把程序输出的四元式拿来对比。第二种更省力把生成的四元式转成 Python 可执行代码构造若干测试用例做端到端验证。后一种方法需要写一个简单的解释器# interp_quads.py def execute_quads(quads, env): pc 0 while pc len(quads): op, a1, a2, r quads[pc] if op.startswith(j): # 跳转指令 cmp {j: lambda: env[a1] env[a2], j: lambda: env[a1] env[a2], j: lambda: env[a1] env[a2], j: lambda: True} if op j or cmp[op](): pc r continue elif op :: env[r] env[a1] if a1 in env else int(a1) elif op.startswith(j) is False and a1 in env: env[r] env[a1] pc 1 return env这个迷你解释器把四元式(j, a, b, target)解释成如果env[a] env[b]就把 pc 跳到 target。对赋值指令直接改环境变量。当然这个解释器只支持整数和关系比较加上变量就不支持复杂布尔表达式但足够验证最典型的 IF-ELSE 和 WHILE 翻译结果了。从那以后我每次做语法制导翻译类的课设都会强制自己先写一个执行器哪怕只有五十行也要把生成的四元式真实跑一遍。很多逻辑错误在纸上推演时根本看不出来跑一条嵌套用例立即现形。希望这个“先翻译再解释验证”的习惯也能帮到你。至于整份代码和文档的获取方式打包成了一个可以直接运行的 Python 项目包含词法分析模块、FIRST/FOLLOW 计算脚本、预测分析表构建程序、LL(1) 驱动主程序和四元式回填生成器还附带三组测试用例文件。项目根目录的 README 里标注了文件依赖关系和运行顺序照着跑一遍就能看到从源码到四元式的完整输出链路。本文还有配套的精品资源点击获取