简介这是一份面向编译原理课程设计与实验的IF-ELSE条件语句翻译程序采用LL(1)分析法完成语法解析并生成四元式中间代码实现覆盖了词法分析、语法分析到中间代码产出的完整编译前端流程适合计算机专业学生用于编译原理实验或课设参考。资源包共17个文件整体仅417KB包含C核心源码.cpp/.h、Visual Studio工程文件.sln/.vcproj、资源与配置.rc/.res/.manifest、编译调试信息.pdb/.obj/.idb及文本说明.txt/.htm下载后可直接加载工程运行与调试。目前已有540人学习下载。代码重点处理了条件跳转、嵌套IF-ELSE等场景通过LL(1)预测分析表驱动语法分析并输出测试条件、跳转标签等四元式可帮助理解自顶向下语法分析器的构造、语义动作的插入以及中间代码生成的具体实现是进行编译原理相关设计时值得对照参考的完整实例。1. IF-ELSE翻译程序为什么值得自己写一遍LL(1)与四元式的结合点很多初学者第一次接触编译原理课程设计挑题目时都躲着 IF-ELSE 走觉得“不就是个 if 吗能有多难”。真动起手才发现这门课最难的不是词法分析也不是语法树而是“跳转地址到底什么时候确定”你是先知道 if 体有多长还是先记录下跳转指令的位置等到 else 体出现再把缺口填上。这种地址回填一旦处理不好四元式就全是乱跳程序跑起来像在猜。这里提到的翻译程序设计核心就是用 LL(1) 分析法做自上而下的语法分析并在分析过程中同步生成三地址形式的四元式专门解决分支条件与跳转目标之间的绑定问题。LL(1) 方法适合这个题目是因为它的分析方向天然可控从左到右读 token每一步只依赖当前非终结符和下一个输入符号做决定。正因为预测性强编译器可以在“读到 else”这个确定时刻执行回填动作而不需要回溯改前面的分析结果。而四元式作为中间代码输出是把 IF-ELSE 语义变成一条跳转指令、一条条件跳转指令以及赋值语句的合集结构简单、便于调试也方便后续再做代码生成。适合的人群很明确正在做编译原理课程设计的学生、想手写一个小型翻译器验证理论的应用开发者、以及准备把编译器前端的“最后一段”补齐的从业者。这篇笔记就按我实际做这类翻译器的顺序来讲从文法设计、预测分析表到语义栈和回填实现最后是排坑和验证。2. 从四元式需求反推文法带 Tail 的 IF-ELSE 文法怎么做到 LL(1)2.1 目标形态IF-ELSE 最终要输出什么样的四元式写翻译程序之前先别急着写分析器而是要把“最终产物”想清楚。IF-ELSE 语句翻译成四元式大致都是这个骨架先对条件表达式求值得到一个临时变量接着是一条条件为假就跳转的指令跳到 else 分支或整条语句的结束位置然后排列 if 体语句if 体结束后有一条无条件跳转跳到整个 IF-ELSE 之后之后排列 else 体语句最后是整条语句的结束位置。我一般采用三地址风格的四元组四个分量分别是操作符、第一操作数、第二操作数和结果。给出一段简单赋值语句作为参考if (a 3) a 1; else a 2;它期望生成的四元式大致是这样编号操作符操作数1操作数2结果含义1a3t1比较 a 和 3结果放入临时变量 t12jpct1空5t1 为假时跳转到 5 号四元式3assign1空a把 1 赋给 a4jmp空空6无条件跳转到 6 号四元式5assign2空a把 2 赋给 a6空空空空整个语句的后续位置这里 2 号四元式的第 4 个分量在刚生成时是未知的因为 else 分支的第一条语句还没有被分析到。同理 4 号的跳转目标也要等整条 IF-ELSE 结束后才知道。这两个“未知数”就是回填的对象。把目标形态定下来后面所有文法设计和语义动作安排才能有依据。2.2 消除公共前缀为什么必须带 Tail 而不是两条并列产生式很多人第一次写 IF-ELSE 文法喜欢用两条产生式一条是Stmt - if ( Bool ) Stmt else Stmt end另一条是Stmt - if ( Bool ) Stmt end想用这种方式区分“有 else 的 if”和“没有 else 的 if”。这个文法在语义上很好理解但在 LL(1) 面前它不合格两条产生式都以if ( Bool ) Stmt开头当预测分析器看到栈顶是 Stmt、当前输入符号是 if 时它不知道该选哪条展开SELECT 集产生交集分析表出现冲突。这是最典型的公共左因子问题。解决办法很常见提取公共前缀把“后面的尾巴”单独用一个新的非终结符表示。我习惯把这个尾巴命名为 Tail文法写成下面这样Stmt - IF LP Bool RP Stmt Tail Stmt - ID ASSIGN NUM Tail - ELSE Stmt END Tail - END Bool - ID LT NUM注意这里终结符我用了全大写词法分析时把 if、else、end、赋值号、左右括号分别映射成 IF、ELSE、END、ASSIGN 等 token。Tail 的两个产生式一个以 ELSE 开头一个以 END 开头彼此不会冲突。这样整个文法就是无回溯的 LL(1) 文法。这种做法比“用两条并列产生式”多绕了一步但换来的是预测分析表干干净净后续写主循环时不需要处理任何二义。另一个容易忽略的点是 END 终结符。因为 LL(1) 不带回溯if 体内部如果又出现一个 if那么内层的 END 必须明确返回否则分析器会一直读下去。Tail 这种设计天然保证每个 IF 都对应一个 ENDELSE 则只出现在需要的地方。嵌套时if ... if ... end ... end的匹配关系也能被正确表达不会出现抢占 else 的情况。2.3 FIRST、FOLLOW 与 SELECT 集验证LL(1) 条件成立的关键文法选完之后不能直接开写代码还得先验证一下它到底是不是 LL(1)。手工计算这几个集合是固定动作我每次换文法都要重新演算一遍。对于上面这份文法FIRST(Stmt) { IF, ID }FIRST(Tail) { ELSE, END }FIRST(Bool) { ID }。FOLLOW(Stmt) 要小心算。产生式Tail - ELSE Stmt END里END 跟在 Stmt 的后面所以 END 一定在 FOLLOW(Stmt) 里又因为开始符号 Stmt 本身也会出现在输入串结尾$ 也要算进去。因此 FOLLOW(Stmt) { END, $ }。FOLLOW(Tail) 只在产生式Stmt - IF LP Bool RP Stmt Tail的末尾出现等于 FOLLOW(Stmt) { END, $ }。FOLLOW(Bool) 只有一个右括号。由此得到 SELECT 集Stmt - IF LP Bool RP Stmt Tail的 SELECT 集是 { IF }Stmt - ID ASSIGN NUM的 SELECT 集是 { ID }Tail - ELSE Stmt END的 SELECT 集是 { ELSE }Tail - END的 SELECT 集是 { END }Bool - ID LT NUM的 SELECT 集是 { ID }每个非终结符在不同输入符号下最多只有一个产生式可选冲突为零可以确认这是 LL(1) 文法。预测分析表也可以据此填出来表格结构很稀疏只有五个关键表项其余空格都代表语法错误。这张表就是后面主循环里查表展开的依据我在实现时直接用一个字典存它查不到就报语法错误定位也方便。2.4 语义动作的插入点LL(1) 分析器如何附带翻译动作有了纯语法产生式还不够翻译程序还要在分析过程中输出四元式。我的做法是在 LL(1) 产生式右侧插入若干语义动作标记这些标记不属于任何终结符也不会出现在输入串里只在分析栈展开时被临时弹出并执行。引入动作标记之后产生式变成这样Stmt - IF LP Bool RP M Stmt N Tail Tail - ELSE K Stmt END Tail - END Bool - ID LT NUM字母 M、N、K 在这里是语义动作占位符分别代表M 在布尔表达式分析完成后执行负责生成条件比较四元式和一条“假跳”的占位指令N 在 if 体语句生成完毕、即将处理 else 或 end 时执行负责生成一条无条件跳转占位指令K 在读到 ELSE 之后执行负责把之前 M 留下的假跳目标回填到当前四元式编号。到 Tail 归约完成时再把 N 留下的跳到结尾的无条件跳转目标回填。这样的插入点设计遵循一个原则回填动作尽量安排在“能确定目标地址”的边界位置。比如 else 出现时当前已经分析完 if 体else 体的第一条语句编号是明确的此刻回填假跳最安全。这个思想说完后面实现代码时就不容易迷失在栈操作里。你只要记住LL(1) 分析器与翻译动作的关系不是先做完整个语法树再翻译而是每走一步该生成的四元式已经生成该记的地址也已经记下。3. 手写 LL(1) 预测分析翻译器语义栈与四元式回填的实现路径3.1 主循环骨架两层栈怎么配合动手写代码时我习惯先实现一个只做语法分析的预测分析器跑通之后再往里面塞语义动作。这个中间版本虽然不生成四元式但它能验证分析表有没有填错也能帮你在语义栈崩溃时快速区分“是语法分析坏了”还是“是回填坏了”。主循环的骨架长这样def predictive_parse(tokens, table, start_symbol): stack [#, start_symbol] # 语法栈放分析方法 sem_stack [] # 语义栈放临时属性与语法栈同步维护 ip 0 # 输入指针指向当前 token while stack: X stack.pop() if X # and tokens[ip].type EOF: return True # 正常结束 if X in terminals: # X 是终结符 if X tokens[ip].type: ip 1 else: raise SyntaxError(f期望 {X}实际得到 {tokens[ip].type}) elif X in nonterminals: # X 是非终结符查预测分析表 prod table[X].get(tokens[ip].type) if prod is None: raise SyntaxError(f在栈顶 {X} 下遇到不能匹配的终结符 {tokens[ip].type}) for sym in reversed(prod): stack.append(sym) # 产生式右部逆序入栈 else: execute_semantic_action(X, sem_stack, quads) # 语义动作标记这段代码的核心在于语法栈、语义栈、输入指针三者同步推进。stack管“接下来要匹配什么”sem_stack管“刚才匹配到的东西带了什么属性”quads则是全局的四元式列表。查表展开时产生式右部的符号要逆序压栈才保证栈顶先处理最左边的符号。语义动作标记和终结符、非终结符放在同一个栈里弹出时统一判断分支代码非常干净。这里有三个值得注意的参数选择。第一语义栈和语法栈的入栈时机必须同步不能先压语法符号再压属性否则嵌套一深就错位。第二动作标记在展开产生式时也会被压栈它相当于一个“零宽”的符号不消费输入只在弹出的瞬间执行动作。第三遇到分析错误直接抛异常不要尝试在 LL(1) 里做恢复恢复逻辑会污染后面四元式编号的连续性。输出四元式要求编号连续跳过任何一步都会让回填地址全面错乱。3.2 emit、new_temp、backpatch三个最小工具函数四元式翻译器有三个最常用的工具函数我先把它写成一个独立的工具组后续所有语义动作都调它们。代码不长但每个都有讲究quads [] # 四元式表下标从 0 开始打印时显示为编号1 temp_count 0 def nextinstr(): return len(quads) 1 # 下一个四元式的编号从 1 开始 def emit(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) def new_temp(): global temp_count temp_count 1 return ft{temp_count} def backpatch(index_list, target): for idx in index_list: op, arg1, arg2, _ quads[idx] quads[idx] (op, arg1, arg2, target)nextinstr()返回的是“下一条将要生成的四元式编号”。因为quads列表从 0 开始计数len(quads) 1恰好映射到人看的第 N 条。这个函数是回填的灵魂所有“当前到哪了”的判断都靠它。emit()就是往列表里追加一条四元组第四个分量先可以填 None等 backpatch 的时候再改。new_temp()生成临时变量名用来存放布尔表达式的比较结果。backpatch()接收一个待回填地址列表和一个目标编号批量把跳转目标写进去。设计成列表而不是单个整数是为了应对多个跳转指令指向同一个位置的情况比如逻辑或运算里多个条件可能跳同一目标。IF-ELSE 场景下通常只需要回填一两个地址但接口统一成列表后面扩展 while、for 循环时不用改代码。3.3 语义动作清单四条产生式各自的属性变换把语义动作单独列成清单比在代码里东一句西一句直观得多。我按产生式分组每个动作的职责写清楚这样写代码时就是照着清单填。产生式语义动作属性栈变化Bool - ID LT NUM生成比较四元式结果放入新临时变量弹出 ID 和 NUM 的词法值压入临时变量名Stmt - ID ASSIGN NUM生成赋值四元式弹出 ID 和 NUM不压入任何属性Stmt - IF LP Bool RP M Stmt N TailM 动作bool 属性出栈生成四元式和jpc占位把 jpc 的地址压栈N 动作生成jmp占位把地址压栈M 弹出临时变量名压入回填地址N 压入另一个回填地址Tail - ELSE K Stmt ENDK 动作弹出 M 留下的回填地址回填到当前 nextinstrK 弹出地址不压新属性Tail - END弹出 N 留下的无条件跳转地址回填到当前 nextinstr弹出地址不压新属性这里容易踩雷的是属性栈的弹出顺序。IF-ELSE 场景里M 动作生成 jpc 地址先压栈N 动作生成 jmp 地址后压栈但回填时先回填 jpc在 K 动作再回填 jmp在 END 归约。所以 K 动作弹出的必须是栈顶之下那个地址而不是栈顶。如果你用同一个列表简单地pop()取到的会是无条件跳转地址回填就错位了。解决起来有两条路。一是严格按“后进先出”设计动作顺序让后压的先回填二是在压栈时同时压一个类型标签比如( jpc, 2 )和( jmp, 4 )回填时按标签取。我推荐第二种直观、不容易在嵌套两层 if 时搞混就是语义动作代码会稍微长一点。四元式生成规则说到底只有三条布尔比较生成加jpc赋值语句生成assign分支和结束处生成jmp并回填。翻译动作全部围绕这三条规则展开。3.4 走一遍流程一个 IF-ELSE 样例的逐行翻译理论讲完拿一个具体输入完整走一遍。输入的 token 序列是IF LP ID(a) LT NUM(3) RP ID(a) ASSIGN NUM(1) ELSE ID(a) ASSIGN NUM(2) END分析栈初始为[ #, Stmt ]输入指针指向 IF。查预测分析表Stmt 在 IF 下的产生式是IF LP Bool RP M Stmt N Tail逆序压栈后栈变成[ #, IF, LP, Bool, RP, M, Stmt, N, Tail ]IF、LP 依次和输入匹配弹出。接着 Bool 归约时执行比较生成动作读入a 3的符号值生成四元式(, a, 3, t1)再生成占位四元式(jpc, t1, None, None)。此刻 quads 里有两条nextinstr()返回 3。M 动作把 jpc 所在的下标 1 压入语义栈。RP 匹配后进入 if 体的 Stmt。这个 Stmt 匹配赋值语句生成(assign, 1, None, a)成为 3 号四元式。随后 N 动作生成(jmp, None, None, None)成为 4 号四元式地址 3 压入语义栈因为 quads 从 0 计数所以打印为 4。接着 Tail 看到 ELSE展开ELSE K Stmt END。K 动作执行回填取语义栈中的 jpc 地址 1目标填nextinstr()的值 5于是 2 号四元式变成(jpc, t1, None, 5)。else 体的赋值语句生成(assign, 2, None, a)成为 5 号四元式。最后 Tail 归约 END取出 jmp 地址 3目标填nextinstr()的值 64 号变成(jmp, None, None, 6)。最终输出如下1: (, a, 3, t1) 2: (jpc, t1, None, 5) 3: (assign, 1, None, a) 4: (jmp, None, None, 6) 5: (assign, 2, None, a) 6: (None, None, None, None)这个执行过程每一步都有编号可查。我建议你在自己的实现里也把这样的 trace 打到控制台而不是只打印最终结果。四元式翻译里大部分 bug 发生在中间过程能看清“哪一步回填了什么、目标值是多少”比任何调试器都好用。4. IF-ELSE 翻译程序常见问题5 个最容易翻车的地方4.1 现象查表查到冲突条目分析器一会儿匹配这个一会儿匹配那个最直接的翻车现场是运行时字典访问报错或者分析器进入某种“摇摆”状态同一个栈顶对同一个输入符号有两套展开方案。原因基本只有一个文法没有做到 LL(1)常见的是用两条Stmt - if ...分别表示带 else 和不带 else导致 ELSE 归属出现公共左因子SELECT 集重叠。这种问题的解决思路不是去调分析器而是回到文法层面。把公共前缀提取出来用 Tail 非终结符承接 else 和 end 的区分就是我前面给的写法。改完文法后重新计算 FIRST、FOLLOW、SELECT确认表项没有重复再跑测试用例。记住一条原则LL(1) 的冲突不能靠查表顺序或优先级掩盖必须从文法本身消除。4.2 现象else 分支永远不执行或者条件为假时反而执行四元式输出后跑一个简单样例发现 jpc 的方向反了。比如条件为真时直接跳到了 else 体if 体反而被跳过。原因是对 jpc 的解释约定不一致有的教材把 jpc 定义成“真跳”有的定义成“假跳”。跳转方向一旦记错整个翻译器的行为就全面反转。我遇到过最隐蔽的版本是单层 if 看不出问题嵌套一深就开始混乱。解决方法是把语义规定写死在代码注释里并且让生成逻辑照此执行。我的约定是jpc表示“条件为假时跳转”jmp是无条件跳转。那么 M 动作生成的(jpc, t1, None, target)里target 必须指向 else 体或整个语句的结束位置而不是 if 体。你可以用一个小样例测试把条件改成必真和必假两组分别看四元式跳转去向。这个约定一旦确立后面不再改。4.3 现象嵌套 IF 的 ELSE 被外层抢走END 不够用当输入是if (a1) if (b2) b3; else b4; end end时有些实现会把 else 匹配到外层 if导致内层 end 之后多出一个无法归约的符号。原因有两个层面文法层面没有把 IF 与 END 的配对关系绑定或者语义分析时没有处理好嵌套上下文。解决办法就是我前面强调的 Tail 文法。每个 IF 必须由 END 收尾ELSE 是可选分支这样内层 if 的 END 会先把内层 Tail 归约完成外层再继续。你在测试时专门构造三层以下嵌套的用例逐步验证 end 数量。如果分析器报“期望 END 却遇到 EOF”那就说明输入的 end 少了或者文法里 End 没有进入正确非终结符的 FOLLOW 集。回头看 FOLLOW(Stmt) 计算确认 END 已经在集合里。4.4 现象回填之后所有跳转目标都指向同一个四元式编号打印四元式时发现多条 jmp、jpc 的 target 全是同一个值或者目标指向自身程序进入死循环。原因是对nextinstr()的调用时机不对在生成占位四元式之前调用拿到的是占位指令自己的编号在占位之后又忘了保存地址。还有一种常见误用是把nextinstr()的返回值直接当成固定地址传给 emit后续插入新四元式时地址没有同步偏移。解决方式是统一用 backpatch 机制。生成占位四元式时先记录emit_index len(quads) - 1把这个索引压栈。到回填时机再用backpatch([emit_index], nextinstr())把新编号写回去。不要在占位四元式生成后立刻计算目标因为中间还会插入 if 体和 else 体的大量语句目标必然变化。血泪经验就是谁先调用 nextinstr谁就要承担后续变动的风险所以只允许回填瞬间调用。4.5 现象样例一大就栈溢出四元式还没生成完程序先没了深层嵌套的 IF-ELSE 一旦达到几十层有的递归下降实现会直接 RecursionError或者语义栈里塞满了重复拷贝的属性对象内存暴涨。原因往往不是递归深度本身而是实现时把“语义值”每次分析都深拷贝了一份比如把整个临时变量属性当作不可变对象重复入栈导致栈帧越来越大。排查方法是给语义值打印 id看同一属性是否在多个位置指向不同对象。如果不同说明你在传值时写了构造新对象的逻辑。解决方式是把语义栈设计成真正的栈结构每个属性只存一次弹栈时移动引用而不是复制。对于需要保存的跳转地址这种整数直接存 int对于符号表项存索引而不是字符串副本。做到这一点后几千层嵌套都不会崩四元式数量也只是线性增长。5. 验证再用用 trace 盯一遍三嵌套 IF-ELSE再顺手扩展 while先写一个简单的 trace 函数。在预测分析主循环里每次弹出符号并执行动作之前打印一行内容包括当前步数、栈顶符号、当前输入 token、语义栈内容、以及待生成的下一条四元式编号。这个函数非常简单但价值极高。def trace(step, stack, sem_stack, quads, token): print(fstep{step} top{stack[-1] if stack else #} ftoken{token} sem{sem_stack} nextinstr{len(quads)1})用三嵌套样例验证if (a1) a1; else if (b2) b2; else b3; end end手工预测它的四元式最外层 jpc 跳过外层 if 体、跳到内层 IF 的开始内层 jpc 再跳过内层 if 体内层 END 回填内层 jmp外层 END 回填外层 jmp。跑一遍 trace重点观察每次 backpatch 前后 quads 的变化。如果所有跳转目标编号都落在对应 END 之后的那条四元式上翻译就是正确的。这个验证过程不是玄学是实打实的断言检查比用解释器去执行四元式更直接。验证通过后可以考虑顺手做扩展。把 while 循环加进这套框架只需要改文法加上Stmt - WHILE LP Bool RP M Stmt END然后语义动作多一个“循环入口地址”。生成四元式时记录循环开始的编号M 动作生成假跳占位循环体结束时生成无条件跳回循环开始并在 END 处回填假跳目标。这段代码写完后你就拥有一个同时支持 IF-ELSE 和 WHILE 的迷你翻译器后面接上简单代码生成器就能跑出真实目标代码。我自己的习惯是每次做完翻译器都在临时文件里保留 trace 输出遇到问题先看最后几步的状态变化而不是从头数。很多看似深夜才能解决的“灵异现象”最后都只是 nextinstr 早调了一步。希望这篇笔记能帮你把 LL(1) 和四元式的结合点想清楚少走几步弯路希望帮到你。本文还有配套的精品资源点击获取