分析法实现IF-ELSE翻译程序：四元式与真假链回填)
简介一份面向编译原理学习者的IF-ELSE条件语句翻译程序设计资料基于LL(1)预测分析法完成词法分析、语法分析并输出四元式中间代码。资料以Visual Studio工程形式组织共17个文件包含C源码、头文件、工程配置文件以及调试生成的中间文件便于对照完整项目结构理解编译器前端各模块的实现思路。压缩包整体约417KB体积小巧便于快速部署和运行已有540人浏览学习适合正在做编译原理课程设计或想动手实践语法分析的读者。借助该工程可查看LL(1)文法设计、预测分析表构建、IF-ELSE嵌套与跳转语句的四元式生成等关键流程同时从工程配置与调试产物中学习实际编译项目的组织方式和排错方法将编译原理理论落实到可运行的程序实现中是课程设计或实验报告的重要参考。1. 用 LL(1) 法写 IF-ELSE 条件语句翻译程序难点不在条件在真假链回填这个标题我在带编译原理课程设计时几乎每年都会被学生问到。IF-ELSE 条件语句的翻译程序设计LL(1) 法、输出四元式一句话说就是用 LL(1) 分析法做语法分析在分析过程中同步生成中间代码四元式把「条件成立走这段、否则走那段」的逻辑变成一串带跳转的四元组。适合三类人正在做编译原理课设的学生、要给自己写的脚本语言加条件分支的开发者、以及想搞懂编译前端「分析 翻译」到底怎么衔接的从业者。实际动手会发现IF-ELSE 本身不复杂复杂的是布尔表达式的真假链回填和悬空 else 的处理这两块才是四元式能不能生成对的关键。2. 文法改造与 LL(1) 判定悬空 else 是第一个坑2.1 IF-ELSE 的原始文法为什么过不了 LL(1) 判定先给一版最直觉的 IF-ELSE 文法S - IF E THEN S | IF E THEN S ELSE S | ID : E;这版文法存在两个致命问题。第一是左公因子IF E THEN S在两条产生式里重复出现导致预测分析表里M[S, IF]这一格有两个候选LL(1) 判定直接不通过。第二是悬空 else输入IF ab THEN IF bc THEN x:1 ELSE x:2时这个ELSE既可以匹配内层 IF也可以匹配外层 IF文法存在二义性。LL(1) 判定有三个硬条件同一非终结符的多个候选 FIRST 集互不相交若某个候选能推导出 ε那么 FIRST(该候选) 与 FOLLOW(该非终结符) 不能有交集每个终结符在分析表中只能落到一个格子。原始文法连第一条都满足不了所以必须改造。悬空 else 的行业共识是「就近匹配」ELSE 永远匹配离它最近的、尚未匹配的 IF。这个原则用自然语言说很简单但要在文法里把它固化下来就需要下面的改造。2.2 三步改造成 LL(1) 文法提取公因子与处理空产生式改造分三步消除左公因子、消除左递归、用显式 ENDIF 终结符收尾。第一步处理最外层 IF 语句的左公因子把IF E THEN S提出来后面接一个尾巴S由S决定是否存在 ELSE 分支。第二步处理表达式里的左递归比如E - E OR T这种写法在 LL(1) 下无解必须转成右递归。第三步给每个 IF 加一个显式ENDIF作为闭合标记这样回填跳转目标时有一个确定的锚点。改造后的完整文法如下P - SS SS - S SS | ε S - IF E THEN S S | ID : E; S - ELSE S | ENDIF E - T E E - OR T E | ε T - F T T - AND F T | ε F - NOT F | (E) | R R - ID R_tail | NUM R_tail - RELOP ID | ε逐个说下设计意图SS表示语句串可以连续出现多个 SS的两条产生式分别以IF和ID开头FIRST 集不冲突S用ELSE和ENDIF两个终结符区分有无 else 分支E系列做布尔表达式翻译OR和AND被拆成E、T两个尾巴避免左递归R处理关系表达式ID NUM这类比较其中ID RELOP ID的左公因子通过R_tail消除。这套文法里S、SS、E、T、R_tail都可能推导出 ε空产生式的启用时机要严格看当前输入 token 是否落在对应非终结符的 FOLLOW 集里这一点在 2.3 的表格里能直接查到。2.3 FIRST 与 FOLLOW 集手工算一遍分析表才有依据预测分析表不是凭空写的每一格都来自 FIRST 和 FOLLOW 集。下面这个表是按程序结束符$、以显式ENDIF闭合 IF 的简化文法算出来的常见课设和教学场景可以直接抄非终结符FIRSTFOLLOWS{ IF, ID }{ IF, ID, ENDIF, $ }S{ ELSE, ENDIF }{ IF, ID, ENDIF, $ }E{ NOT, (, ID, NUM }{ THEN, ;, ) }E{ OR, ε }{ THEN, ;, ) }T{ NOT, (, ID, NUM }{ OR, THEN, ;, ) }T{ AND, ε }{ OR, THEN, ;, ) }F{ NOT, (, ID, NUM }{ AND, OR, THEN, ;, ) }R{ ID, NUM }{ AND, OR, THEN, ;, ) }R_tail{ RELOP, ε }{ AND, OR, THEN, ;, ) }注意几个关键点。FOLLOW(S)里的IF、ID来自SS - S SS因为一个语句后面还能跟另一个语句FOLLOW(E)里的THEN来自S - IF E THEN S S;来自赋值语句ID : E;)来自F - (E)。E、T、R_tail这些带 ε 的产生式只有在当前 token 落到 FOLLOW 集时才启用这是后面查分析表最容易出错的地方。有了这张表预测分析表的构造就是机械动作对每个产生式A - α把 α 的 FIRST 集中每个终结符填入M[A, token] 产生式编号如果 α 能推导出 ε再把 FOLLOW(A) 中每个终结符也填入M[A, token] 产生式编号。手算一遍这张表比直接背任何现成分析表都靠谱。3. 四元式设计与真假链回填方案决定整个翻译程序的骨架3.1 四元式的四个字段如何表示跳转和赋值四元式是 (op, arg1, arg2, result) 四元组本质上是一条扁平化的中间指令。翻译 IF-ELSE 语句时涉及的操作符就这几类:赋值、关系比较等、逻辑跳转JZarg1 为假则跳转到 result、无条件跳转JMP直接跳转到 result。操作符arg1arg2result语义:常量或变量-变量赋值操作数操作数临时变量比较结果存临时变量JZ临时变量-四元式序号为假(0)则跳转JMP--四元式序号无条件跳转result 字段在四元式里有两种完全不冲突的用法运算型四元式里它存临时变量名或目标变量名跳转型四元式里它存跳转目标的四元式序号。初学者最容易忽略的是这一点——跳转目标往往在生成时还没确定于是 result 字段先留空等目标算出来再回填。3.2 一个 IF-ELSE 的四元式长什么样看一个具体例子。输入语句IF A B THEN C : 1 ELSE C : 2 ENDIF期望输出的四元式序列是1 (, A, B, T1) // 条件比较结果存临时变量 T1 2 (JZ, T1, -, 5) // T1 为假(条件不成立)跳到 ELSE 分支 3 (:, 1, -, C) // THEN 分支C 1 4 (JMP, -, -, 6) // 执行完 THEN 跳过 ELSE 分支 5 (:, 2, -, C) // ELSE 分支C 2 6 (后续四元式) // ENDIF 之后的代码这里第 2 条JZ一开始生成时ELSE 分支入口序号还是未知的所以 result 先留空第 4 条JMP生成时ENDIF 后的序号也是未知的同样要留空。等到语法分析继续往下走ELSE 分支第一条四元式确定了、ENDIF 之后的第一条四元式确定了才能把这两个坑填上。3.3 真假链与回填跳转目标后确定怎么处理跳转目标后确定这是翻译 IF-ELSE 的核心矛盾。解决办法是真假链 回填把「等待回填」的跳转四元式序号用链表串起来链头用一个变量保存等目标序号确定后沿着链表把每个节点的 result 字段改写成真正的目标序号。具体到 IF-ELSE 语句需要在文法产生式右部插入语义动作标记常见做法是插入M1到M5这样的标记符号S - IF M1 E M2 THEN M3 S1 M4 S S - ELSE M5 S2 | ENDIF每个语义动作标记的职责用表格列清楚标记触发位置动作M1IF 之后记录 IF 之前的四元式序号调试用M2E 分析完成处取出 E 产生的真链与假链M3THEN 之后记录 THEN 分支入口序号把 E 的真链全部回填到这里M4S1 分析完成处生成一条JMP序号入「待回填链」用于跳过 ELSE 分支M5ELSE 之后记录 ELSE 分支入口序号把 E 的假链回填到这里S - ENDIF的语义动作是最后一步收尾把 M4 积累的JMP链全部回填到 ENDIF 之后的四元式序号如果这个 IF 没有 ELSE 分支那么 E 的假链也要回填到 ENDIF 之后的序号因为条件不成立时整个 IF 语句直接结束。这套标记方案就是整个翻译程序的骨架第 4 章的代码实现完全围绕它展开。4. 预测分析表驱动的代码实现栈、回填与语义动作的配合4.1 程序框架token 流、分析栈、四元式表三件套翻译程序的整体流程分三个阶段词法分析先把源码拆成 token 流终结符包括IF、ELSE、THEN、ENDIF、ID、NUM、RELOP、:、;、(、)、OR、AND、NOT然后 LL(1) 预测分析器拿着 token 流驱动分析栈查表每次按产生式展开时触发对应的语义动作往四元式表里写记录。这里的关键设计是分析栈里存的不是单纯的文法符号而是三类元素的混合体——终结符用 token 的 type 值非终结符用自定义编号语义动作标记用另一套编号。这样在主循环里遇到栈顶元素时一眼就能看出该走「匹配终结符」还是「展开产生式」还是「执行语义动作」。4.2 核心数据结构四元式表、分析栈、符号表C 语言风格的核心数据结构如下#define MAX_QUAD 256 #define MAX_STACK 128 #define MAX_SYM 64 typedef struct { char op[8]; // 操作符:、JZ、JMP、、 等 char arg1[32]; char arg2[32]; char result[32]; } Quad; Quad quad[MAX_QUAD]; int qc 0; // 下一个可用四元式序号也是新四元式插入位置 int stack[MAX_STACK]; int top 0; char sym_table[MAX_SYM][32]; int sym_count 0; // 非终结符与语义动作编号 #define NT_S 200 #define NT_SP 201 // S #define NT_SS 202 #define NT_E 203 #define NT_EP 204 // E #define NT_T 205 #define NT_TP 206 // T #define NT_F 207 #define NT_R 208 #define NT_RT 209 // R_tail #define ACT_M1 301 #define ACT_M2 302 #define ACT_M3 303 #define ACT_M4 304 #define ACT_M5 305四元式表quad是全局数组qc是游标所有语义动作都通过qc拿到「当前四元式序号」这也是回填时最常使用的锚点。分析栈用 int 数组实现压栈的是编号符号表只做一件事——记录临时变量和用户变量的名字与值方便最后验证四元式执行结果。栈里的终结符直接复用 token 的 type 值这样主循环里比较栈顶与当前 token 时不需要额外映射。4.3 主循环展开产生式的同时执行语义动作LL(1) 预测分析的主循环是典型的「查表、压栈、匹配」三步走。核心逻辑如下while (top 0) { int sym stack[top]; if (sym token.type) { // 栈顶是终结符且与当前 token 匹配弹出并读下一个 token top--; next_token(); } else if (sym 300) { // 栈顶是语义动作标记弹出并执行对应动作 top--; switch (sym) { case ACT_M2: { // E 分析完毕此时 true_chain/false_chain 已被 E 的产生式填好 true_chain get_true_chain(); false_chain get_false_chain(); break; } case ACT_M3: { // THEN 分支入口就是当前四元式序号 int entry qc; backpatch(true_chain, entry); break; } case ACT_M4: { // THEN 分支结束生成一条 JMP 并加入待回填链 emit(JMP, , , ); jmp_chain merge_chain(jmp_chain, qc - 1); break; } case ACT_M5: { // ELSE 分支入口就是当前四元式序号回填 E 的假链 int else_entry qc; backpatch(false_chain, else_entry); break; } } } else { // 栈顶是非终结符查预测分析表展开产生式并逆序压栈 int row nt_row(sym); int col token_col(token.type); int prod parse_table[row][col]; if (prod 0) error(语法错误); top--; // 把该产生式的右部符号逆序压栈 for (int i prod_len[prod]; i 1; i--) { stack[top] prod_symbols[prod][i]; } } }这个循环里最容易写错的是最后那个逆序压栈产生式右部符号是按从左到右的顺序存的压栈必须从右往左压否则语义动作的执行顺序会整个颠倒。prod_symbols[prod][i]是预先定义好的产生式右部符号表下标从 1 开始0 留给左部非终结符。parse_table的行列索引分别由nt_row和token_col两个映射函数算出表中的值是产生式编号-1 表示该格子为空、语法错误。4.4 回填函数、四元式生成与一颗完整输出回填是四元式翻译最重要的工具函数链的每个节点就是一条等待回填的跳转四元式序号节点间的「下一跳」信息借用 result 字段存放void backpatch(int chain, int dst) { while (chain ! 0) { int next atoi(quad[chain].result); // 链的下一节点序号存在 result 中 quad[chain].result dst; // 回填真正的跳转目标 chain next; } } int merge_chain(int c1, int c2) { if (c1 0) return c2; int p c1; while (atoi(quad[p].result) ! 0) { p atoi(quad[p].result); } quad[p].result c2; return c1; } void emit(char *op, char *arg1, char *arg2, char *result) { strcpy(quad[qc].op, op); strcpy(quad[qc].arg1, arg1); strcpy(quad[qc].arg2, arg2); strcpy(quad[qc].result, result ? result : ); qc; }backpatch的参数chain是链头序号dst是回填目标merge_chain把两条链接成一条返回合并后的链头emit的四个参数与四元式四字段一一对应qc在调用后自增。注意merge_chain里借用 result 字段找链尾的写法前提是链中每个节点都是未回填状态一旦回填过就不能再入链。对IF A B THEN C : 1 ELSE C : 2 ENDIF这行输入按上述代码走完四元式表内容如下序号 op arg1 arg2 result 1 A B T1 2 JZ T1 5 3 : 1 C 4 JMP 6 5 : 2 C观察输出与语义动作的对应关系第 1 条由R - ID RELOP ID的关系表达式产生式生成第 2 条由E产生式的语义动作生成但目标留空第 3 条由赋值语句产生式生成第 4 条由 M4 触发生成第 5 条则是 M5 回填后恰好成为 ELSE 分支入口。整个过程中「生成时留空 后续回填」交替出现这就是回填机制在驱动翻译。5. 实现路上的 5 个典型踩坑从悬空 else 到回填错位5.1 悬空 else 归属翻车ELSE 总是被内层 IF 抢先匹配现象嵌套 IF 语句翻译出来的四元式逻辑不对比如IF ab THEN IF bc THEN x:1 ELSE x:2 ENDIF ENDIF里的 ELSE 被错误地匹配到外层 IF导致外层条件不成立时反而执行了x:2。原因这里通常有两种情况。一种是你偷懒用了原始二义性文法构造分析表LL(1) 判定本身就过不了另一种是递归下降实现里S看到ELSE就直接归约没有把 ELSE 绑定到「最近未闭合的 IF」的栈帧上。解决严格使用 2.2 改造后的文法S的两个候选ELSE S和ENDIF用当前 token 区分。实现递归下降时S遇到ELSE就递归处理S遇到ENDIF就返回这样每个 ELSE 天然属于最近的S。分析栈驱动版本注意假链要用栈结构管理先入栈的 IF 的假链后回填保证匹配顺序。5.2 THEN 分支执行完没跳过 ELSE四元式里少了一条 JMP现象输入包含完整 THEN 和 ELSE 分支时THEN 分支的四元式执行完直接「落入」ELSE 分支两组赋值都执行了。原因这是 M4 语义动作漏写或者只在检测到 ELSE 存在时才生成JMP。如果没有 ELSE 分支THEN 分支执行完自然走到 ENDIF 后不需要跳转但一旦存在 ELSETHEN 分支末尾必须有一条JMP跳过 ELSE 分支的代码。解决不要用「有没有 ELSE」来决定是否生成JMP在 M4 处无条件生成JMP并入待回填链。如果没有 ELSE 分支这个JMP回填到 ENDIF 后的序号等价于顺序执行多一条空跳不影响正确性如果有 ELSE 分支它精确跳过 ELSE 代码块。用这个统一策略实现时只需要一套回填代码少一个条件分支也少一个 bug。5.3 FIRST/FOLLOW 集手算对程序查表却报「无候选」现象分析表构造时某些格子缺项比如栈顶是E、当前 token 是THEN查表直接报语法错误但你手工算的 FOLLOW(E) 里明明有THEN。原因基本都是 FOLLOW 集漏算。FOLLOW(E)既要算S - IF E THEN S S里的THEN也要算S - ID : E;里的;还要算F - (E)里的)。三个来源缺一个空产生式E - ε就可能在对应 token 上无法启用。解决构造分析表前把 FOLLOW 集三个来源逐一核对右部末尾的非终结符继承左部的 FOLLOWA - αBβ中 B 的 FOLLOW 包含 FIRST(β)去掉 ε若 β 可推导出 εB 的 FOLLOW 还包含 FOLLOW(A)。自查时对着 2.3 的表格逐项勾选重点看那些带 ε 的产生式。5.4 语义动作标记入栈顺序颠倒四元式序号全乱现象生成的四元式顺序完全不对回填出来的目标序号差 1 或者指向错误四元式调试时发现qc跳变。原因产生式展开时忘了逆序压栈。S - IF M1 E M2 THEN M3 S1 M4 S的右部符号列表是正序的压栈必须从最后一个符号开始反向压入否则第一个弹出的不是IF而是S语义动作 M1 到 M5 的执行顺序会彻底倒过来。解决压栈循环统一写成for (int i prod_len; i 1; i--) push(prod_symbols[i])并且把语义动作标记也当作普通符号参与逆序。调试时在压栈后打印整个栈的内容对照产生式右部检查顺序一眼就能看出问题。5.5 布尔表达式真假链在 NOT 和 OR 处断开回填跳反现象IF NOT (A B) THEN ...或IF A B OR C D THEN ...这类条件翻译后跳转方向与预期相反真分支和假分支互换。原因F - NOT F需要把子表达式的真假链互换子表达式的真链变成整个表达式的假链假链变成真链。E - OR T E的处理更隐蔽左侧 E 的假链不能直接回填到整个 OR 表达式的假出口而应该回填到 OR 右侧操作数的入口因为只要右侧为真整个表达式就为真。很多实现把假链直接存起来最后统一回填到 ENDIF导致 OR 的「短路」语义丢失。解决对NOT在做完子表达式翻译后立即调用swap_chain()交换真假链。对OR在M2处保存假链后构造T E之前先把假链回填到右侧操作数的第一条四元式序号再把右侧生成的真链与左侧真链合并作为整个 OR 的真链。这里建议单独写一个translate_or_tail()函数别把 OR 的语义动作堆在主循环里不然短路逻辑会和普通顺序翻译混在一起。6. 验证四元式再谈进阶让这段中间代码真正跑起来6.1 用极简解释器让四元式跑起来四元式生成后最直接的验证方式是写一个几十行的极简解释器按顺序执行四元式观察变量值变化int pc 0; int temp_flag 0; while (pc qc) { Quad *q quad[pc]; if (strcmp(q-op, ) 0) { int left sym_get(q-arg1); int right sym_get(q-arg2); temp_flag left right; strcpy(temp_name, q-result); } else if (strcmp(q-op, JZ) 0) { if (temp_flag 0) { pc atoi(q-result); continue; } } else if (strcmp(q-op, JMP) 0) { pc atoi(q-result); continue; } else if (strcmp(q-op, :) 0) { sym_set(q-result, atoi(q-arg1)); } pc; }sym_get和sym_set是符号表读写函数temp_flag模拟临时变量T1的取值。验证时先给A10, B5跑一遍确认 THEN 分支执行再给A3, B5跑一遍确认 ELSE 分支执行嵌套 IF 则给多组数据交叉验证。6.2 进阶从四元式还原 AST 或直接生成目标代码四元式验证通过后这个翻译程序就算真正闭环了。更有价值的进阶方向是把四元式还原成抽象语法树跳转四元式对应 IF 节点赋值四元式对应赋值节点还原后的 AST 能做常量折叠、死代码删除等优化或者直接把四元式映射成栈式虚拟机的指令例如JZ对应条件跳转指令、JMP对应无条件跳转指令这条路走向的是完整解释器与 JIT。6.3 我的习惯我带课设时反复强调一个习惯先跑「THEN 和 ELSE 都有副作用」的测试用例例如两个分支都打印输出或都改变不同变量确认两条路径都被执行到再跑嵌套 IF 的用例专门检查悬空 else 归属最后才跑 NOT、OR 组合的复杂布尔条件。每次都把四元式输出与手推结果逐行对照而不是只看最终变量值。回填这块的玄学坑我当年也踩过不少现在回看出问题的地方几乎都集中在 5.3 的 FOLLOW 集漏算和 5.4 的压栈顺序这两个点上。希望这篇拆解能帮你把 LL(1) 翻译程序的骨架一次搭对。本文还有配套的精品资源点击获取
简介一份面向编译原理学习者的IF-ELSE条件语句翻译程序设计资料基于LL(1)预测分析法完成词法分析、语法分析并输出四元式中间代码。资料以Visual Studio工程形式组织共17个文件包含C源码、头文件、工程配置文件以及调试生成的中间文件便于对照完整项目结构理解编译器前端各模块的实现思路。压缩包整体约417KB体积小巧便于快速部署和运行已有540人浏览学习适合正在做编译原理课程设计或想动手实践语法分析的读者。借助该工程可查看LL(1)文法设计、预测分析表构建、IF-ELSE嵌套与跳转语句的四元式生成等关键流程同时从工程配置与调试产物中学习实际编译项目的组织方式和排错方法将编译原理理论落实到可运行的程序实现中是课程设计或实验报告的重要参考。1. 用 LL(1) 法写 IF-ELSE 条件语句翻译程序难点不在条件在真假链回填这个标题我在带编译原理课程设计时几乎每年都会被学生问到。IF-ELSE 条件语句的翻译程序设计LL(1) 法、输出四元式一句话说就是用 LL(1) 分析法做语法分析在分析过程中同步生成中间代码四元式把「条件成立走这段、否则走那段」的逻辑变成一串带跳转的四元组。适合三类人正在做编译原理课设的学生、要给自己写的脚本语言加条件分支的开发者、以及想搞懂编译前端「分析 翻译」到底怎么衔接的从业者。实际动手会发现IF-ELSE 本身不复杂复杂的是布尔表达式的真假链回填和悬空 else 的处理这两块才是四元式能不能生成对的关键。2. 文法改造与 LL(1) 判定悬空 else 是第一个坑2.1 IF-ELSE 的原始文法为什么过不了 LL(1) 判定先给一版最直觉的 IF-ELSE 文法S - IF E THEN S | IF E THEN S ELSE S | ID : E;这版文法存在两个致命问题。第一是左公因子IF E THEN S在两条产生式里重复出现导致预测分析表里M[S, IF]这一格有两个候选LL(1) 判定直接不通过。第二是悬空 else输入IF ab THEN IF bc THEN x:1 ELSE x:2时这个ELSE既可以匹配内层 IF也可以匹配外层 IF文法存在二义性。LL(1) 判定有三个硬条件同一非终结符的多个候选 FIRST 集互不相交若某个候选能推导出 ε那么 FIRST(该候选) 与 FOLLOW(该非终结符) 不能有交集每个终结符在分析表中只能落到一个格子。原始文法连第一条都满足不了所以必须改造。悬空 else 的行业共识是「就近匹配」ELSE 永远匹配离它最近的、尚未匹配的 IF。这个原则用自然语言说很简单但要在文法里把它固化下来就需要下面的改造。2.2 三步改造成 LL(1) 文法提取公因子与处理空产生式改造分三步消除左公因子、消除左递归、用显式 ENDIF 终结符收尾。第一步处理最外层 IF 语句的左公因子把IF E THEN S提出来后面接一个尾巴S由S决定是否存在 ELSE 分支。第二步处理表达式里的左递归比如E - E OR T这种写法在 LL(1) 下无解必须转成右递归。第三步给每个 IF 加一个显式ENDIF作为闭合标记这样回填跳转目标时有一个确定的锚点。改造后的完整文法如下P - SS SS - S SS | ε S - IF E THEN S S | ID : E; S - ELSE S | ENDIF E - T E E - OR T E | ε T - F T T - AND F T | ε F - NOT F | (E) | R R - ID R_tail | NUM R_tail - RELOP ID | ε逐个说下设计意图SS表示语句串可以连续出现多个 SS的两条产生式分别以IF和ID开头FIRST 集不冲突S用ELSE和ENDIF两个终结符区分有无 else 分支E系列做布尔表达式翻译OR和AND被拆成E、T两个尾巴避免左递归R处理关系表达式ID NUM这类比较其中ID RELOP ID的左公因子通过R_tail消除。这套文法里S、SS、E、T、R_tail都可能推导出 ε空产生式的启用时机要严格看当前输入 token 是否落在对应非终结符的 FOLLOW 集里这一点在 2.3 的表格里能直接查到。2.3 FIRST 与 FOLLOW 集手工算一遍分析表才有依据预测分析表不是凭空写的每一格都来自 FIRST 和 FOLLOW 集。下面这个表是按程序结束符$、以显式ENDIF闭合 IF 的简化文法算出来的常见课设和教学场景可以直接抄非终结符FIRSTFOLLOWS{ IF, ID }{ IF, ID, ENDIF, $ }S{ ELSE, ENDIF }{ IF, ID, ENDIF, $ }E{ NOT, (, ID, NUM }{ THEN, ;, ) }E{ OR, ε }{ THEN, ;, ) }T{ NOT, (, ID, NUM }{ OR, THEN, ;, ) }T{ AND, ε }{ OR, THEN, ;, ) }F{ NOT, (, ID, NUM }{ AND, OR, THEN, ;, ) }R{ ID, NUM }{ AND, OR, THEN, ;, ) }R_tail{ RELOP, ε }{ AND, OR, THEN, ;, ) }注意几个关键点。FOLLOW(S)里的IF、ID来自SS - S SS因为一个语句后面还能跟另一个语句FOLLOW(E)里的THEN来自S - IF E THEN S S;来自赋值语句ID : E;)来自F - (E)。E、T、R_tail这些带 ε 的产生式只有在当前 token 落到 FOLLOW 集时才启用这是后面查分析表最容易出错的地方。有了这张表预测分析表的构造就是机械动作对每个产生式A - α把 α 的 FIRST 集中每个终结符填入M[A, token] 产生式编号如果 α 能推导出 ε再把 FOLLOW(A) 中每个终结符也填入M[A, token] 产生式编号。手算一遍这张表比直接背任何现成分析表都靠谱。3. 四元式设计与真假链回填方案决定整个翻译程序的骨架3.1 四元式的四个字段如何表示跳转和赋值四元式是 (op, arg1, arg2, result) 四元组本质上是一条扁平化的中间指令。翻译 IF-ELSE 语句时涉及的操作符就这几类:赋值、关系比较等、逻辑跳转JZarg1 为假则跳转到 result、无条件跳转JMP直接跳转到 result。操作符arg1arg2result语义:常量或变量-变量赋值操作数操作数临时变量比较结果存临时变量JZ临时变量-四元式序号为假(0)则跳转JMP--四元式序号无条件跳转result 字段在四元式里有两种完全不冲突的用法运算型四元式里它存临时变量名或目标变量名跳转型四元式里它存跳转目标的四元式序号。初学者最容易忽略的是这一点——跳转目标往往在生成时还没确定于是 result 字段先留空等目标算出来再回填。3.2 一个 IF-ELSE 的四元式长什么样看一个具体例子。输入语句IF A B THEN C : 1 ELSE C : 2 ENDIF期望输出的四元式序列是1 (, A, B, T1) // 条件比较结果存临时变量 T1 2 (JZ, T1, -, 5) // T1 为假(条件不成立)跳到 ELSE 分支 3 (:, 1, -, C) // THEN 分支C 1 4 (JMP, -, -, 6) // 执行完 THEN 跳过 ELSE 分支 5 (:, 2, -, C) // ELSE 分支C 2 6 (后续四元式) // ENDIF 之后的代码这里第 2 条JZ一开始生成时ELSE 分支入口序号还是未知的所以 result 先留空第 4 条JMP生成时ENDIF 后的序号也是未知的同样要留空。等到语法分析继续往下走ELSE 分支第一条四元式确定了、ENDIF 之后的第一条四元式确定了才能把这两个坑填上。3.3 真假链与回填跳转目标后确定怎么处理跳转目标后确定这是翻译 IF-ELSE 的核心矛盾。解决办法是真假链 回填把「等待回填」的跳转四元式序号用链表串起来链头用一个变量保存等目标序号确定后沿着链表把每个节点的 result 字段改写成真正的目标序号。具体到 IF-ELSE 语句需要在文法产生式右部插入语义动作标记常见做法是插入M1到M5这样的标记符号S - IF M1 E M2 THEN M3 S1 M4 S S - ELSE M5 S2 | ENDIF每个语义动作标记的职责用表格列清楚标记触发位置动作M1IF 之后记录 IF 之前的四元式序号调试用M2E 分析完成处取出 E 产生的真链与假链M3THEN 之后记录 THEN 分支入口序号把 E 的真链全部回填到这里M4S1 分析完成处生成一条JMP序号入「待回填链」用于跳过 ELSE 分支M5ELSE 之后记录 ELSE 分支入口序号把 E 的假链回填到这里S - ENDIF的语义动作是最后一步收尾把 M4 积累的JMP链全部回填到 ENDIF 之后的四元式序号如果这个 IF 没有 ELSE 分支那么 E 的假链也要回填到 ENDIF 之后的序号因为条件不成立时整个 IF 语句直接结束。这套标记方案就是整个翻译程序的骨架第 4 章的代码实现完全围绕它展开。4. 预测分析表驱动的代码实现栈、回填与语义动作的配合4.1 程序框架token 流、分析栈、四元式表三件套翻译程序的整体流程分三个阶段词法分析先把源码拆成 token 流终结符包括IF、ELSE、THEN、ENDIF、ID、NUM、RELOP、:、;、(、)、OR、AND、NOT然后 LL(1) 预测分析器拿着 token 流驱动分析栈查表每次按产生式展开时触发对应的语义动作往四元式表里写记录。这里的关键设计是分析栈里存的不是单纯的文法符号而是三类元素的混合体——终结符用 token 的 type 值非终结符用自定义编号语义动作标记用另一套编号。这样在主循环里遇到栈顶元素时一眼就能看出该走「匹配终结符」还是「展开产生式」还是「执行语义动作」。4.2 核心数据结构四元式表、分析栈、符号表C 语言风格的核心数据结构如下#define MAX_QUAD 256 #define MAX_STACK 128 #define MAX_SYM 64 typedef struct { char op[8]; // 操作符:、JZ、JMP、、 等 char arg1[32]; char arg2[32]; char result[32]; } Quad; Quad quad[MAX_QUAD]; int qc 0; // 下一个可用四元式序号也是新四元式插入位置 int stack[MAX_STACK]; int top 0; char sym_table[MAX_SYM][32]; int sym_count 0; // 非终结符与语义动作编号 #define NT_S 200 #define NT_SP 201 // S #define NT_SS 202 #define NT_E 203 #define NT_EP 204 // E #define NT_T 205 #define NT_TP 206 // T #define NT_F 207 #define NT_R 208 #define NT_RT 209 // R_tail #define ACT_M1 301 #define ACT_M2 302 #define ACT_M3 303 #define ACT_M4 304 #define ACT_M5 305四元式表quad是全局数组qc是游标所有语义动作都通过qc拿到「当前四元式序号」这也是回填时最常使用的锚点。分析栈用 int 数组实现压栈的是编号符号表只做一件事——记录临时变量和用户变量的名字与值方便最后验证四元式执行结果。栈里的终结符直接复用 token 的 type 值这样主循环里比较栈顶与当前 token 时不需要额外映射。4.3 主循环展开产生式的同时执行语义动作LL(1) 预测分析的主循环是典型的「查表、压栈、匹配」三步走。核心逻辑如下while (top 0) { int sym stack[top]; if (sym token.type) { // 栈顶是终结符且与当前 token 匹配弹出并读下一个 token top--; next_token(); } else if (sym 300) { // 栈顶是语义动作标记弹出并执行对应动作 top--; switch (sym) { case ACT_M2: { // E 分析完毕此时 true_chain/false_chain 已被 E 的产生式填好 true_chain get_true_chain(); false_chain get_false_chain(); break; } case ACT_M3: { // THEN 分支入口就是当前四元式序号 int entry qc; backpatch(true_chain, entry); break; } case ACT_M4: { // THEN 分支结束生成一条 JMP 并加入待回填链 emit(JMP, , , ); jmp_chain merge_chain(jmp_chain, qc - 1); break; } case ACT_M5: { // ELSE 分支入口就是当前四元式序号回填 E 的假链 int else_entry qc; backpatch(false_chain, else_entry); break; } } } else { // 栈顶是非终结符查预测分析表展开产生式并逆序压栈 int row nt_row(sym); int col token_col(token.type); int prod parse_table[row][col]; if (prod 0) error(语法错误); top--; // 把该产生式的右部符号逆序压栈 for (int i prod_len[prod]; i 1; i--) { stack[top] prod_symbols[prod][i]; } } }这个循环里最容易写错的是最后那个逆序压栈产生式右部符号是按从左到右的顺序存的压栈必须从右往左压否则语义动作的执行顺序会整个颠倒。prod_symbols[prod][i]是预先定义好的产生式右部符号表下标从 1 开始0 留给左部非终结符。parse_table的行列索引分别由nt_row和token_col两个映射函数算出表中的值是产生式编号-1 表示该格子为空、语法错误。4.4 回填函数、四元式生成与一颗完整输出回填是四元式翻译最重要的工具函数链的每个节点就是一条等待回填的跳转四元式序号节点间的「下一跳」信息借用 result 字段存放void backpatch(int chain, int dst) { while (chain ! 0) { int next atoi(quad[chain].result); // 链的下一节点序号存在 result 中 quad[chain].result dst; // 回填真正的跳转目标 chain next; } } int merge_chain(int c1, int c2) { if (c1 0) return c2; int p c1; while (atoi(quad[p].result) ! 0) { p atoi(quad[p].result); } quad[p].result c2; return c1; } void emit(char *op, char *arg1, char *arg2, char *result) { strcpy(quad[qc].op, op); strcpy(quad[qc].arg1, arg1); strcpy(quad[qc].arg2, arg2); strcpy(quad[qc].result, result ? result : ); qc; }backpatch的参数chain是链头序号dst是回填目标merge_chain把两条链接成一条返回合并后的链头emit的四个参数与四元式四字段一一对应qc在调用后自增。注意merge_chain里借用 result 字段找链尾的写法前提是链中每个节点都是未回填状态一旦回填过就不能再入链。对IF A B THEN C : 1 ELSE C : 2 ENDIF这行输入按上述代码走完四元式表内容如下序号 op arg1 arg2 result 1 A B T1 2 JZ T1 5 3 : 1 C 4 JMP 6 5 : 2 C观察输出与语义动作的对应关系第 1 条由R - ID RELOP ID的关系表达式产生式生成第 2 条由E产生式的语义动作生成但目标留空第 3 条由赋值语句产生式生成第 4 条由 M4 触发生成第 5 条则是 M5 回填后恰好成为 ELSE 分支入口。整个过程中「生成时留空 后续回填」交替出现这就是回填机制在驱动翻译。5. 实现路上的 5 个典型踩坑从悬空 else 到回填错位5.1 悬空 else 归属翻车ELSE 总是被内层 IF 抢先匹配现象嵌套 IF 语句翻译出来的四元式逻辑不对比如IF ab THEN IF bc THEN x:1 ELSE x:2 ENDIF ENDIF里的 ELSE 被错误地匹配到外层 IF导致外层条件不成立时反而执行了x:2。原因这里通常有两种情况。一种是你偷懒用了原始二义性文法构造分析表LL(1) 判定本身就过不了另一种是递归下降实现里S看到ELSE就直接归约没有把 ELSE 绑定到「最近未闭合的 IF」的栈帧上。解决严格使用 2.2 改造后的文法S的两个候选ELSE S和ENDIF用当前 token 区分。实现递归下降时S遇到ELSE就递归处理S遇到ENDIF就返回这样每个 ELSE 天然属于最近的S。分析栈驱动版本注意假链要用栈结构管理先入栈的 IF 的假链后回填保证匹配顺序。5.2 THEN 分支执行完没跳过 ELSE四元式里少了一条 JMP现象输入包含完整 THEN 和 ELSE 分支时THEN 分支的四元式执行完直接「落入」ELSE 分支两组赋值都执行了。原因这是 M4 语义动作漏写或者只在检测到 ELSE 存在时才生成JMP。如果没有 ELSE 分支THEN 分支执行完自然走到 ENDIF 后不需要跳转但一旦存在 ELSETHEN 分支末尾必须有一条JMP跳过 ELSE 分支的代码。解决不要用「有没有 ELSE」来决定是否生成JMP在 M4 处无条件生成JMP并入待回填链。如果没有 ELSE 分支这个JMP回填到 ENDIF 后的序号等价于顺序执行多一条空跳不影响正确性如果有 ELSE 分支它精确跳过 ELSE 代码块。用这个统一策略实现时只需要一套回填代码少一个条件分支也少一个 bug。5.3 FIRST/FOLLOW 集手算对程序查表却报「无候选」现象分析表构造时某些格子缺项比如栈顶是E、当前 token 是THEN查表直接报语法错误但你手工算的 FOLLOW(E) 里明明有THEN。原因基本都是 FOLLOW 集漏算。FOLLOW(E)既要算S - IF E THEN S S里的THEN也要算S - ID : E;里的;还要算F - (E)里的)。三个来源缺一个空产生式E - ε就可能在对应 token 上无法启用。解决构造分析表前把 FOLLOW 集三个来源逐一核对右部末尾的非终结符继承左部的 FOLLOWA - αBβ中 B 的 FOLLOW 包含 FIRST(β)去掉 ε若 β 可推导出 εB 的 FOLLOW 还包含 FOLLOW(A)。自查时对着 2.3 的表格逐项勾选重点看那些带 ε 的产生式。5.4 语义动作标记入栈顺序颠倒四元式序号全乱现象生成的四元式顺序完全不对回填出来的目标序号差 1 或者指向错误四元式调试时发现qc跳变。原因产生式展开时忘了逆序压栈。S - IF M1 E M2 THEN M3 S1 M4 S的右部符号列表是正序的压栈必须从最后一个符号开始反向压入否则第一个弹出的不是IF而是S语义动作 M1 到 M5 的执行顺序会彻底倒过来。解决压栈循环统一写成for (int i prod_len; i 1; i--) push(prod_symbols[i])并且把语义动作标记也当作普通符号参与逆序。调试时在压栈后打印整个栈的内容对照产生式右部检查顺序一眼就能看出问题。5.5 布尔表达式真假链在 NOT 和 OR 处断开回填跳反现象IF NOT (A B) THEN ...或IF A B OR C D THEN ...这类条件翻译后跳转方向与预期相反真分支和假分支互换。原因F - NOT F需要把子表达式的真假链互换子表达式的真链变成整个表达式的假链假链变成真链。E - OR T E的处理更隐蔽左侧 E 的假链不能直接回填到整个 OR 表达式的假出口而应该回填到 OR 右侧操作数的入口因为只要右侧为真整个表达式就为真。很多实现把假链直接存起来最后统一回填到 ENDIF导致 OR 的「短路」语义丢失。解决对NOT在做完子表达式翻译后立即调用swap_chain()交换真假链。对OR在M2处保存假链后构造T E之前先把假链回填到右侧操作数的第一条四元式序号再把右侧生成的真链与左侧真链合并作为整个 OR 的真链。这里建议单独写一个translate_or_tail()函数别把 OR 的语义动作堆在主循环里不然短路逻辑会和普通顺序翻译混在一起。6. 验证四元式再谈进阶让这段中间代码真正跑起来6.1 用极简解释器让四元式跑起来四元式生成后最直接的验证方式是写一个几十行的极简解释器按顺序执行四元式观察变量值变化int pc 0; int temp_flag 0; while (pc qc) { Quad *q quad[pc]; if (strcmp(q-op, ) 0) { int left sym_get(q-arg1); int right sym_get(q-arg2); temp_flag left right; strcpy(temp_name, q-result); } else if (strcmp(q-op, JZ) 0) { if (temp_flag 0) { pc atoi(q-result); continue; } } else if (strcmp(q-op, JMP) 0) { pc atoi(q-result); continue; } else if (strcmp(q-op, :) 0) { sym_set(q-result, atoi(q-arg1)); } pc; }sym_get和sym_set是符号表读写函数temp_flag模拟临时变量T1的取值。验证时先给A10, B5跑一遍确认 THEN 分支执行再给A3, B5跑一遍确认 ELSE 分支执行嵌套 IF 则给多组数据交叉验证。6.2 进阶从四元式还原 AST 或直接生成目标代码四元式验证通过后这个翻译程序就算真正闭环了。更有价值的进阶方向是把四元式还原成抽象语法树跳转四元式对应 IF 节点赋值四元式对应赋值节点还原后的 AST 能做常量折叠、死代码删除等优化或者直接把四元式映射成栈式虚拟机的指令例如JZ对应条件跳转指令、JMP对应无条件跳转指令这条路走向的是完整解释器与 JIT。6.3 我的习惯我带课设时反复强调一个习惯先跑「THEN 和 ELSE 都有副作用」的测试用例例如两个分支都打印输出或都改变不同变量确认两条路径都被执行到再跑嵌套 IF 的用例专门检查悬空 else 归属最后才跑 NOT、OR 组合的复杂布尔条件。每次都把四元式输出与手推结果逐行对照而不是只看最终变量值。回填这块的玄学坑我当年也踩过不少现在回看出问题的地方几乎都集中在 5.3 的 FOLLOW 集漏算和 5.4 的压栈顺序这两个点上。希望这篇拆解能帮你把 LL(1) 翻译程序的骨架一次搭对。本文还有配套的精品资源点击获取
