语法分析+四元式生成：IF-ELSE翻译程序设计详解)
简介这是一份编译原理课程设计/实验资料面向正在学习编译原理的高年级本科生或需要做编译器前端的开发者。资料围绕IF-ELSE条件语句的翻译完整实现并演示了词法分析、基于LL(1)方法的语法分析以及生成四元式中间代码的完整过程可帮助读者理解预测分析表构造、条件跳转指令生成、真假出口回填等核心知识点。压缩包内含17个文件以C源码cpp/h、Visual Studio工程配置sln/vcproj及文本说明为主整体仅417KB下载后可直接打开工程查看实现细节。随附的C源文件与测试文本中包含了嵌套IF-ELSE处理、跳转四元式如JNZ和布尔表达式求值的典型代码便于对照实验要求逐段分析。目前已有539人学习适合作为课程设计、期末实验的参考范例或编译器设计项目的起步代码。 编译原理这门课十个人里有八个觉得理论难啃但真到了课程设计反而能做出一点成就感。“IF-ELSE条件语句的翻译程序设计LL(1)法、输出四元式”这个题目恰好把整条编译链路里最核心的三段——词法分析、LL(1)语法分析、语义动作与中间代码生成——全部串在一起。简单说就是让机器读懂“if a 5 then x 1 else x 2;”这样的代码先切词再按文法做推导最后产出一张四元式表。中间会踩到悬空else的经典坑也会用到回填backpatching这种每个编译器都会用的技术。这个项目最适合两类人一类是正在做编译原理课程设计、需要一套能跑通且能讲清楚的设计思路的学生另一类是已经工作但想复盘编译基础、搞清楚预测分析表和中间代码到底怎么配合的开发者。跟着这篇文章把整个流程走一遍你会发现LL(1)不只是卷子上的FIRST、FOLLOW集合计算四元式也不只是课本上那几行抽象符号——它们是真的能在一段代码里从头到尾协同工作的。1. 项目概述与整体设计思路1.1 这个项目要解决什么问题翻译程序设计的本质是把高级语言代码翻译成等价但更接近机器的中间表示。这个题目的输入是一条或若干条带有IF-ELSE结构的语句输出是四元式序列。四元式长这样(1) (j, a, 5, 3) (2) (j, -, -, 5) (3) (:, 1, -, x) (4) (j, -, -, 6) (5) (:, 2, -, x)每一行是一个四元式运算符、第一操作数、第二操作数、结果。j是条件跳转j是无条件跳转:是赋值。这几条指令组合起来就完整表达了if a5 then x1 else x2的执行流。整个项目要做的就是从源代码开始经过词法分析得到token流再经过LL(1)预测分析完成语法推导在推导过程中同步执行语义动作、生成四元式最后通过回填机制把跳转目标补全。这里有一个很关键的设计思路语法分析和语义动作是交织在一起的不是先完整建一棵语法树再去遍历它。这样做的好处是省内存、效率高也是语法制导翻译的标准做法。缺点是逻辑必须严谨因为每选择一个产生式就要立刻决定生成什么四元式。1.2 为什么选LL(1)法和四元式LL(1)分析是自顶向下、最左推导每次根据当前栈顶符号和当前输入符号查预测分析表就能决定用哪个产生式展开。对IF-ELSE这种结构化语句来说文法天然比较贴近LL(1)的要求只要把二义性处理好用表驱动或者递归下降都能干净地实现。比起LR(1)需要构造状态族、处理归约冲突LL(1)的工程实现要直观得多对课程设计来说信息量也足够。四元式作为中间代码形式最大的优点是结构统一、操作数显式分离。每个四元式最多三个操作数对应一条三地址指令翻译成汇编或者解释执行都很容易。更重要的是四元式天然适合回填一条跳转四元式的目标字段先空着等目标地址确定后再填进去。这在后面的语义动作设计里会大量用到。1.3 整体架构与处理流程我把整个程序分成四个模块词法分析器、预测分析器、语义动作子程序、四元式表与回填管理器。它们的关系是单向流水线源代码 → 词法分析token流 → LL(1)预测分析驱动分析栈 → 语义动作生成四元式 → 回填 → 输出词法分析器每次返回一个token给预测分析器预测分析器根据token查分析表决定展开哪个产生式每次展开产生式时调用对应的语义动作子程序向四元式表追加记录句子结束前回填管理器把所有未确定的跳转目标填满。整个流程不需要显式构建语法树运行完直接输出四元式表。2. 文法设计与LL(1)分析表构造2.1 悬空else问题必须正面处理的二义性IF-ELSE文法最经典的坑就是悬空elsedangling else。考虑嵌套语句if a5 then if b3 then x1 else x2这里的else到底匹配内层if还是外层if在C语言里它匹配内层而自然文法描述中两种理解都合法这就产生了二义性。LL(1)文法要求每个产生式选择都是唯一的二义性文法绝对进不了预测分析表。消除二义性的标准文法改写是引入“匹配语句”和“不匹配语句”两个非终结符。但这里有个残酷的事实改写后的匹配/不匹配文法在LR分析器下很好用却仍然不是LL(1)文法。这个结论我推导过很多次每次都有同学试图在LL(1)框架里彻底消除悬空else冲突最后都发现做不到。LL(1)对文法的限制就是如此严格。课程设计里最务实的做法是保留结构清晰的文法在预测分析表冲突处增加一条语义规则——else优先匹配最近的未匹配if。这条规则在编译原理教材里也有论述本质上是在语法分析层面固定二义性让行为确定化。2.2 符合LL(1)框架的IF-ELSE文法设计结合题目要求我设计了下面这套文法同时支持IF-ELSE语句和最简单的赋值语句。条件表达式刻意简化成id RELOP num这是为了把翻译重点放在IF-ELSE结构本身。1. PROG - STMT 2. STMT - IF_STMT | ASSIGN_STMT 3. IF_STMT - if COND then STMT ELSE_PART 4. ELSE_PART - else STMT | ε 5. COND - ID RELOP NUM 6. RELOP - | | | | | ! 7. ASSIGN_STMT - ID NUM ;非终结符只有五个PROG、STMT、IF_STMT、ELSE_PART、COND、RELOP、ASSIGN_STMT。终结符包括关键字if、then、else标识符ID、数字NUM、六种关系运算符、赋值号和分号;。这套文法照顾到了嵌套IF-ELSEthen后面跟的是STMTSTMT可以再展开成IF_STMT所以if a5 then if b3 then x1 else x2能够被完整地推导出来。注意ELSE_PART - ε是文法中的关键空产生式。没有它无else的IF语句就无法结束。但有它分析表里就会在else符号上出现冲突这正好是悬空else问题的另一种表现形式。2.3 FIRST集合与FOLLOW集合计算LL(1)分析表的基础就是FIRST和FOLLOW集合。这套文法的计算过程如下。FIRST集合FIRST(COND) FIRST(ID) {id}FIRST(RELOP) {, , , , , !}FIRST(ASSIGN_STMT) {id}FIRST(IF_STMT) {if}FIRST(STMT) {if, id}FIRST(ELSE_PART) {else, ε}FIRST(PROG) FIRST(STMT) {if, id}FOLLOW集合需要小心推导。从开始符号开始FOLLOW(PROG) {#}其中#表示输入结束。因为PROG只有一条产生式PROG - STMT所以FOLLOW(STMT)包含#。再看IF_STMT - if COND then STMT ELSE_PART在then STMT中STMT后面的非终结符是ELSE_PART而FIRST(ELSE_PART)里面包含else和εε要忽略所以FOLLOW(STMT)里要加入else。同时ELSE_PART在产生式末尾所以FOLLOW(ELSE_PART)继承FOLLOW(IF_STMT)再继承FOLLOW(STMT)。最终整理结果FOLLOW(STMT) {#, else} FOLLOW(IF_STMT) FOLLOW(STMT) {#, else} FOLLOW(ELSE_PART) {#, else} FOLLOW(COND) {then} FOLLOW(RELOP) {num} FOLLOW(ASSIGN_STMT) FOLLOW(STMT) {#, else}2.4 预测分析表构造与冲突的务实处理有了FIRST和FOLLOW集合构造预测分析表的规则是对产生式A - α如果终结符a在FIRST(α)中就把该产生式填入M[A, a]如果α能推导出ε则对所有在FOLLOW(A)中的终结符b把该产生式填入M[A, b]。这套规则执行下来大部分表项没有争议但ELSE_PART的两个产生式会发生冲突ELSE_PART - else STMT使得M[ELSE_PART, else]填入了这个产生式而ELSE_PART - ε结合FOLLOW(ELSE_PART) {#, else}又会让M[ELSE_PART, else]也填入空产生式。同一个表项两个产生式LL(1)条件严格来说不满足。解决办法是给分析器加一条优先级规则当输入符号是else且发生冲突时优先选择ELSE_PART - else STMT。这是什么含义呢它的效果是分析器遇到else时不会用空产生式把ELSE_PART缩掉而是继续展开else分支于是else被当前正在分析的IF语句吸收也就是匹配到最近的if。这正是我们在语言设计里想要的行为。推进到实际编码时这条规则就是解析表驱动循环里的一个if判断或者递归下降函数里的一个分支。3. 四元式生成与回填技术3.1 四元式的结构和跳转指令设计四元式的标准形式是(op, arg1, arg2, result)。翻译IF-ELSE语句时我用到三类指令运算oparg1arg2result含义j 等关系跳转左操作数右操作数跳转目标arg1和arg2满足关系时跳转到resultj--跳转目标无条件跳转到result:源值-目标变量把arg1赋给result-表示空操作数。注意j这类指令是带条件的跳转j是无条件跳转这两者的组合就能表达IF-ELSE的完整控制流。那么“真跳”和“假跳”怎么分工呢我在设计时采用一个固定模式条件为真时跳转到then分支入口条件为假时跳转到else分支入口无else时跳转到整个IF语句的结束位置。这样安排条件跳转的目标就在语义动作里非常清晰。3.2 各产生式对应的语义动作每个产生式对应一段语义动作这是语法制导翻译的核心。我把关键的几个列出来。PROG - STMT不需要额外生成指令只要在STMT翻译结束后把当前四元式表的下标作为整个程序的结束位置即可。IF_STMT - if COND then STMT ELSE_PART这个产生式横跨整个IF语句语义动作分布在多个时机执行不能简单在产生式选择时做一次。具体操作是COND翻译完成后生成条件跳转四元式比如(j, a, 5, ?)真跳目标待定紧接着生成无条件跳转(j, -, -, ?)假跳目标也待定。记录then分支第一条四元式的下标立刻回填条件跳转的目标。翻译then后的STMT生成对应的赋值四元式。STMT结束后生成一个无条件跳转(j, -, -, ?)它的作用是跳过else分支。ELSE_PART翻译完成后回填“假跳”到else分支入口或整个IF的结束位置回填“跳过跳转”到下场四元式位置。COND - ID RELOP NUM把ID、RELOP、NUM的信息存到临时结构体里并不立即生成跳转指令因为此时还不知道跳转目标。这体现了“延迟生成”的思路先翻译条件表达式把结果挂起来等拿到then分支入口再生成跳转。ELSE_PART - else STMT进入else分支STMT翻译结束后整个IF语句就结束了。此时需要回填两个位置假跳目标else分支入口和then末尾的跳过跳转IF语句结束位置。ELSE_PART - ε没有else分支那么假跳的目标直接回填到IF语句的结束位置then末尾生成的跳过跳转其实指向它自己后面的四元式这个四元式会保留一条冗余跳转。课程设计可以接受这个冗余想优化的话单独处理即可。3.3 回填Backpatching的实现机制回填技术解决的核心问题是生成跳转指令时跳转目标往往还不知道。四元式表是连续下标所以可以在生成跳转指令时先把result字段置0把这条四元式的下标记到一个待回填链表中等目标位置确定后再遍历链表把对应四元式的result字段改成真正的目标下标。我用两个链表分别维护“真链”和“假链”。真链存放所有条件为真时需要跳转的四元式下标假链存放所有条件为假时需要跳转的四元式下标。为什么必须分开因为回填目标不同真链要填then分支入口假链要填else分支入口或IF结束位置。如果混在一个链里回填时无法区分。下面是回填器的简单数据结构#define MAX_QUAD 1000 struct Quad { char op[8]; // 运算符 char arg1[20]; // 操作数1 char arg2[20]; // 操作数2 int result; // 结果/跳转目标0表示待回填 }; struct Quad quads[MAX_QUAD]; int quadIdx 0; // 下一条四元式存放位置 int trueChain[MAX_QUAD]; // 真链存放待回填的四元式下标 int falseChain[MAX_QUAD]; // 假链 int trueTop -1, falseTop -1;生成一条四元式后返回下标号当需要把目标target回填到链上所有四元式时遍历链数组把quads[chain[i]].result设为target。3.4 完整示例从源代码到四元式输入语句if a5 then x1 else x2;词法分析得到token序列if、id(a)、、num(5)、then、id(x)、、num(1)、else、id(x)、、num(2)、;。语法分析结合语义动作生成四元式的过程如下COND识别为a5此时quadIdx1先不生成跳转遇到then生成条件跳转(1) (j, a, 5, 0)再生成无条件跳转(2) (j, -, -, 0)把1号四元式加入真链2号加入假链then分支的x1生成(3) (:, 1, -, x)此时真链回填目标3所以回填1号四元式的result3then分支结束生成跳过语句(4) (j, -, -, 0)加入“跳过链”遇到else2号假链回填目标5else分支第一条四元式所以回填2号四元式的result5else分支的x2生成(5) (:, 2, -, x)整个IF语句结束跳过链回填到quadIdx6所以4号四元式的result6。最终输出(1) (j, a, 5, 3) (2) (j, -, -, 5) (3) (:, 1, -, x) (4) (j, -, -, 6) (5) (:, 2, -, x)这个输出跟前面的预期完全一致。执行逻辑如果a5跳到3号执行x1然后4号跳到6号结束否则跳到5号执行x2落到6号结束。4. 关键代码实现细节4.1 词法分析模块词法分析器的任务是从源码字符串中识别token。最容易踩的坑是关键字识别必须在标识符识别之后单独判断比如源码里的if如果先按“字母开头的都是标识符”处理就会把关键字吞掉。正确做法是先读完整段字母数字串再查关键字表是关键字就返回对应的token类型否则才是ID。int getToken() { skipWhitespace(); if (isalpha(ch)) { readLexeme(); if (strcmp(lexeme, if) 0) return TK_IF; if (strcmp(lexeme, then) 0) return TK_THEN; if (strcmp(lexeme, else) 0) return TK_ELSE; strcpy(tokenValue, lexeme); return TK_ID; } if (isdigit(ch)) { readNumber(); strcpy(tokenValue, lexeme); return TK_NUM; } switch (ch) { case : if (nextChar() ) { ch next(); return TK_LE; } return TK_LT; case : if (nextChar() ) { ch next(); return TK_EQ; } return TK_ASSIGN; case ;: return TK_SEMI; // 其他运算符类似 } }注意和必须靠向前看一个字符来区分。这个逻辑虽然简单但写错会导致后面关系运算和赋值运算全部错乱。4.2 表驱动预测分析程序表驱动的LL(1)分析器是标准的“栈查表”结构。分析栈初始状态下压入#和开始符号PROG循环处理直到栈空。核心伪代码如下void predictiveParse() { push(#); push(PROG); lookahead getToken(); while (!stack.empty()) { X stack.top(); if (isTerminal(X)) { if (X lookahead) { pop(); lookahead getToken(); } else error(terminal mismatch); } else { int prod parseTable[X][lookahead]; if (prod -1) error(no production); else { pop(); semanticActionBeforeExpand(prod); for (int i rhsLen(prod) - 1; i 0; i--) { if (rhs(prod, i) ! EPSILON) push(rhs(prod, i)); } } } } }这里的semanticActionBeforeExpand是在选择产生式展开前触发。对IF_STMT这类跨多个步骤的产生式语义动作不是一次做完而是分成“产生式选择时初始化”“遇到then时生成跳转”“STMT结束时生成跳过跳转”等多个钩子。想要在表驱动框架里表达这种时机需要额外维护一个语义状态机。这也是很多同学写着写着觉得别扭的地方。4.3 递归下降实现更直观的语义动作嵌入老实说虽然题目要求的是LL(1)法但到了真正写语义动作这步递归下降recursive descent要比表驱动直观得多。递归下降本质就是LL(1)的手写实现每个非终结符对应一个函数分析过程就是函数调用树的过程。在函数体内可以在任何位置插入语义动作。void parseIfStmt() { // IF_STMT - if COND then STMT ELSE_PART expect(TK_IF); parseCond(); // 翻译条件把条件保存到临时结构 int condJump emit(j, tempCond.arg1, tempCond.arg2, 0); int falseJump emit(j, -, -, 0); addTrueChain(condJump); addFalseChain(falseJump); expect(TK_THEN); int thenStart quadIdx; // then分支第一条四元式下标 backpatch(trueChain, thenStart); parseStmt(); // 翻译then后的语句 int skipJump emit(j, -, -, 0); // 跳过else parseElsePart(falseJump, skipJump); } void parseElsePart(int falseJump, int skipJump) { if (lookahead TK_ELSE) { match(TK_ELSE); backpatch(falseJump, quadIdx); // 假跳跳到else入口 parseStmt(); backpatch(skipJump, quadIdx); // 跳过跳到IF结束 } else { // ε无else backpatch(falseJump, quadIdx); backpatch(skipJump, quadIdx); } }这一个parseIfStmt函数就把整个IF语句的结构和语义动作摆在明面上了。代码里每一处emit、backpatch的时机都跟文法产生式一一对应讲答辩的时候也好解释。我见过不少课程设计用表驱动写了半天卡在else冲突和语义动作复杂上最后换递归下降半小时搞定本质没有改变LL(1)的性质但代码可读性完全是两个层级。4.4 四元式表与回填管理生成四元式就是往数组里追加一条记录返回当前索引。回填采用“链”的方式把同一个链上的所有待回填四元式下标依次存进数组回填时遍历数组把每条四元式的result字段统一赋值。注意每次回填完成要清空对应链的栈顶否则下一次回填会重复操作索引导致跳转目标错乱。5. 常见问题排查与经验分享5.1 悬空else匹配正确但输出四元式跳转方向反了这是新手最容易犯的问题。语义动作里条件跳转应该跳then分支入口无条件跳转应该跳else分支入口。很多同学把两个跳转的目标填反导致执行语义完全颠倒。排查方法很简单拿一条简单语句if a5 then x1 else x2手动推导一遍期望的四元式再对比程序输出。如果条件跳转的目标不是(:, 1, -, x)的那条方向就反了。5.2 回填时机和边界下的跳转目标错误回填最怕的是时序问题。常见错误是在then分支还没有生成任何四元式时就去回填真链此时quadIdx还指向条件跳转的位置结果把真跳目标填到同一个跳转自己身上。正确做法是先记录thenStart quadIdx然后调用parseStmt()最后用thenStart回填。记住一条原则先确定“目标位置”再执行“回填动作”目标位置的计算必须发生在对应代码生成之前。另一个边界情况是ELSE_PART为空。此时parseElsePart收到falseJump和skipJump两个跳转都要回填到quadIdx。这里quadIdx是IF语句之后的那个位置如果IF语句是整个程序的最后一条那么quadIdx数值就等于四元式总数加1。这个数字虽然超出了四元式表的有效范围但作为跳转目标依然合法表示“跳出程序”。5.3 嵌套IF-ELSE时的链管理多层嵌套时每一层IF都要有自己的真链、假链和跳过链。如果共用一套全局链数组内层回填时会把外层还没回填的跳转也填掉。解决办法是用局部变量保存当前层的链栈顶位置每层进入时记录下来退出时恢复。我在代码里建议把链操作设计成“压栈-保存现场-回填-恢复现场”的模式这样无论嵌套多少层每一层的回填数据都不会互相干扰。5.4 语义动作触发点在文法和代码中如何对齐很多同学写完文法到写代码时不知道语义动作该放在产生式的哪个位置。我的经验是把每个产生式写在纸上在右侧手写“此处的语义动作”然后从上到下对照代码。比如IF_STMT - if COND then STMT ELSE_PART在then和STMT之间会有生成条件跳转的动作在STMT和ELSE_PART之间会有生成跳过跳转的动作这些位置都对应产生式右侧的具体成分。把“动作位置”作为文法的扩展标记写清楚代码就只是按标记执行而已。5.5 测试用例建议测试不能只测一条简单IF-ELSE。我建议至少准备这五类用例无else的IF语句、单层IF-ELSE、多重嵌套IF-ELSE、IF中包含连续多条赋值语句、条件表达式覆盖全部六种关系运算符。尤其是嵌套用例能验证悬空else是否真的匹配最近if——在输出四元式里内层else分支的入口应该出现在内层then的跳过跳转之前这个顺序可以作为肉眼判断的快速依据。做完这套设计我对LL(1)和四元式的理解比看十遍书都深。最后再分享一个小技巧如果想把项目扩展成支持while循环或者and/or复合条件改动点其实是局部的——文法加产生式语义动作加对应的跳转生成规则四元式表结构完全不用动。这恰恰说明中间代码设计得好不好决定了整个编译器后端能走多远。本文还有配套的精品资源点击获取 LL(1)语法分析+四元式生成：IF-ELSE翻译程序设计详解
简介这是一份编译原理课程设计/实验资料面向正在学习编译原理的高年级本科生或需要做编译器前端的开发者。资料围绕IF-ELSE条件语句的翻译完整实现并演示了词法分析、基于LL(1)方法的语法分析以及生成四元式中间代码的完整过程可帮助读者理解预测分析表构造、条件跳转指令生成、真假出口回填等核心知识点。压缩包内含17个文件以C源码cpp/h、Visual Studio工程配置sln/vcproj及文本说明为主整体仅417KB下载后可直接打开工程查看实现细节。随附的C源文件与测试文本中包含了嵌套IF-ELSE处理、跳转四元式如JNZ和布尔表达式求值的典型代码便于对照实验要求逐段分析。目前已有539人学习适合作为课程设计、期末实验的参考范例或编译器设计项目的起步代码。 编译原理这门课十个人里有八个觉得理论难啃但真到了课程设计反而能做出一点成就感。“IF-ELSE条件语句的翻译程序设计LL(1)法、输出四元式”这个题目恰好把整条编译链路里最核心的三段——词法分析、LL(1)语法分析、语义动作与中间代码生成——全部串在一起。简单说就是让机器读懂“if a 5 then x 1 else x 2;”这样的代码先切词再按文法做推导最后产出一张四元式表。中间会踩到悬空else的经典坑也会用到回填backpatching这种每个编译器都会用的技术。这个项目最适合两类人一类是正在做编译原理课程设计、需要一套能跑通且能讲清楚的设计思路的学生另一类是已经工作但想复盘编译基础、搞清楚预测分析表和中间代码到底怎么配合的开发者。跟着这篇文章把整个流程走一遍你会发现LL(1)不只是卷子上的FIRST、FOLLOW集合计算四元式也不只是课本上那几行抽象符号——它们是真的能在一段代码里从头到尾协同工作的。1. 项目概述与整体设计思路1.1 这个项目要解决什么问题翻译程序设计的本质是把高级语言代码翻译成等价但更接近机器的中间表示。这个题目的输入是一条或若干条带有IF-ELSE结构的语句输出是四元式序列。四元式长这样(1) (j, a, 5, 3) (2) (j, -, -, 5) (3) (:, 1, -, x) (4) (j, -, -, 6) (5) (:, 2, -, x)每一行是一个四元式运算符、第一操作数、第二操作数、结果。j是条件跳转j是无条件跳转:是赋值。这几条指令组合起来就完整表达了if a5 then x1 else x2的执行流。整个项目要做的就是从源代码开始经过词法分析得到token流再经过LL(1)预测分析完成语法推导在推导过程中同步执行语义动作、生成四元式最后通过回填机制把跳转目标补全。这里有一个很关键的设计思路语法分析和语义动作是交织在一起的不是先完整建一棵语法树再去遍历它。这样做的好处是省内存、效率高也是语法制导翻译的标准做法。缺点是逻辑必须严谨因为每选择一个产生式就要立刻决定生成什么四元式。1.2 为什么选LL(1)法和四元式LL(1)分析是自顶向下、最左推导每次根据当前栈顶符号和当前输入符号查预测分析表就能决定用哪个产生式展开。对IF-ELSE这种结构化语句来说文法天然比较贴近LL(1)的要求只要把二义性处理好用表驱动或者递归下降都能干净地实现。比起LR(1)需要构造状态族、处理归约冲突LL(1)的工程实现要直观得多对课程设计来说信息量也足够。四元式作为中间代码形式最大的优点是结构统一、操作数显式分离。每个四元式最多三个操作数对应一条三地址指令翻译成汇编或者解释执行都很容易。更重要的是四元式天然适合回填一条跳转四元式的目标字段先空着等目标地址确定后再填进去。这在后面的语义动作设计里会大量用到。1.3 整体架构与处理流程我把整个程序分成四个模块词法分析器、预测分析器、语义动作子程序、四元式表与回填管理器。它们的关系是单向流水线源代码 → 词法分析token流 → LL(1)预测分析驱动分析栈 → 语义动作生成四元式 → 回填 → 输出词法分析器每次返回一个token给预测分析器预测分析器根据token查分析表决定展开哪个产生式每次展开产生式时调用对应的语义动作子程序向四元式表追加记录句子结束前回填管理器把所有未确定的跳转目标填满。整个流程不需要显式构建语法树运行完直接输出四元式表。2. 文法设计与LL(1)分析表构造2.1 悬空else问题必须正面处理的二义性IF-ELSE文法最经典的坑就是悬空elsedangling else。考虑嵌套语句if a5 then if b3 then x1 else x2这里的else到底匹配内层if还是外层if在C语言里它匹配内层而自然文法描述中两种理解都合法这就产生了二义性。LL(1)文法要求每个产生式选择都是唯一的二义性文法绝对进不了预测分析表。消除二义性的标准文法改写是引入“匹配语句”和“不匹配语句”两个非终结符。但这里有个残酷的事实改写后的匹配/不匹配文法在LR分析器下很好用却仍然不是LL(1)文法。这个结论我推导过很多次每次都有同学试图在LL(1)框架里彻底消除悬空else冲突最后都发现做不到。LL(1)对文法的限制就是如此严格。课程设计里最务实的做法是保留结构清晰的文法在预测分析表冲突处增加一条语义规则——else优先匹配最近的未匹配if。这条规则在编译原理教材里也有论述本质上是在语法分析层面固定二义性让行为确定化。2.2 符合LL(1)框架的IF-ELSE文法设计结合题目要求我设计了下面这套文法同时支持IF-ELSE语句和最简单的赋值语句。条件表达式刻意简化成id RELOP num这是为了把翻译重点放在IF-ELSE结构本身。1. PROG - STMT 2. STMT - IF_STMT | ASSIGN_STMT 3. IF_STMT - if COND then STMT ELSE_PART 4. ELSE_PART - else STMT | ε 5. COND - ID RELOP NUM 6. RELOP - | | | | | ! 7. ASSIGN_STMT - ID NUM ;非终结符只有五个PROG、STMT、IF_STMT、ELSE_PART、COND、RELOP、ASSIGN_STMT。终结符包括关键字if、then、else标识符ID、数字NUM、六种关系运算符、赋值号和分号;。这套文法照顾到了嵌套IF-ELSEthen后面跟的是STMTSTMT可以再展开成IF_STMT所以if a5 then if b3 then x1 else x2能够被完整地推导出来。注意ELSE_PART - ε是文法中的关键空产生式。没有它无else的IF语句就无法结束。但有它分析表里就会在else符号上出现冲突这正好是悬空else问题的另一种表现形式。2.3 FIRST集合与FOLLOW集合计算LL(1)分析表的基础就是FIRST和FOLLOW集合。这套文法的计算过程如下。FIRST集合FIRST(COND) FIRST(ID) {id}FIRST(RELOP) {, , , , , !}FIRST(ASSIGN_STMT) {id}FIRST(IF_STMT) {if}FIRST(STMT) {if, id}FIRST(ELSE_PART) {else, ε}FIRST(PROG) FIRST(STMT) {if, id}FOLLOW集合需要小心推导。从开始符号开始FOLLOW(PROG) {#}其中#表示输入结束。因为PROG只有一条产生式PROG - STMT所以FOLLOW(STMT)包含#。再看IF_STMT - if COND then STMT ELSE_PART在then STMT中STMT后面的非终结符是ELSE_PART而FIRST(ELSE_PART)里面包含else和εε要忽略所以FOLLOW(STMT)里要加入else。同时ELSE_PART在产生式末尾所以FOLLOW(ELSE_PART)继承FOLLOW(IF_STMT)再继承FOLLOW(STMT)。最终整理结果FOLLOW(STMT) {#, else} FOLLOW(IF_STMT) FOLLOW(STMT) {#, else} FOLLOW(ELSE_PART) {#, else} FOLLOW(COND) {then} FOLLOW(RELOP) {num} FOLLOW(ASSIGN_STMT) FOLLOW(STMT) {#, else}2.4 预测分析表构造与冲突的务实处理有了FIRST和FOLLOW集合构造预测分析表的规则是对产生式A - α如果终结符a在FIRST(α)中就把该产生式填入M[A, a]如果α能推导出ε则对所有在FOLLOW(A)中的终结符b把该产生式填入M[A, b]。这套规则执行下来大部分表项没有争议但ELSE_PART的两个产生式会发生冲突ELSE_PART - else STMT使得M[ELSE_PART, else]填入了这个产生式而ELSE_PART - ε结合FOLLOW(ELSE_PART) {#, else}又会让M[ELSE_PART, else]也填入空产生式。同一个表项两个产生式LL(1)条件严格来说不满足。解决办法是给分析器加一条优先级规则当输入符号是else且发生冲突时优先选择ELSE_PART - else STMT。这是什么含义呢它的效果是分析器遇到else时不会用空产生式把ELSE_PART缩掉而是继续展开else分支于是else被当前正在分析的IF语句吸收也就是匹配到最近的if。这正是我们在语言设计里想要的行为。推进到实际编码时这条规则就是解析表驱动循环里的一个if判断或者递归下降函数里的一个分支。3. 四元式生成与回填技术3.1 四元式的结构和跳转指令设计四元式的标准形式是(op, arg1, arg2, result)。翻译IF-ELSE语句时我用到三类指令运算oparg1arg2result含义j 等关系跳转左操作数右操作数跳转目标arg1和arg2满足关系时跳转到resultj--跳转目标无条件跳转到result:源值-目标变量把arg1赋给result-表示空操作数。注意j这类指令是带条件的跳转j是无条件跳转这两者的组合就能表达IF-ELSE的完整控制流。那么“真跳”和“假跳”怎么分工呢我在设计时采用一个固定模式条件为真时跳转到then分支入口条件为假时跳转到else分支入口无else时跳转到整个IF语句的结束位置。这样安排条件跳转的目标就在语义动作里非常清晰。3.2 各产生式对应的语义动作每个产生式对应一段语义动作这是语法制导翻译的核心。我把关键的几个列出来。PROG - STMT不需要额外生成指令只要在STMT翻译结束后把当前四元式表的下标作为整个程序的结束位置即可。IF_STMT - if COND then STMT ELSE_PART这个产生式横跨整个IF语句语义动作分布在多个时机执行不能简单在产生式选择时做一次。具体操作是COND翻译完成后生成条件跳转四元式比如(j, a, 5, ?)真跳目标待定紧接着生成无条件跳转(j, -, -, ?)假跳目标也待定。记录then分支第一条四元式的下标立刻回填条件跳转的目标。翻译then后的STMT生成对应的赋值四元式。STMT结束后生成一个无条件跳转(j, -, -, ?)它的作用是跳过else分支。ELSE_PART翻译完成后回填“假跳”到else分支入口或整个IF的结束位置回填“跳过跳转”到下场四元式位置。COND - ID RELOP NUM把ID、RELOP、NUM的信息存到临时结构体里并不立即生成跳转指令因为此时还不知道跳转目标。这体现了“延迟生成”的思路先翻译条件表达式把结果挂起来等拿到then分支入口再生成跳转。ELSE_PART - else STMT进入else分支STMT翻译结束后整个IF语句就结束了。此时需要回填两个位置假跳目标else分支入口和then末尾的跳过跳转IF语句结束位置。ELSE_PART - ε没有else分支那么假跳的目标直接回填到IF语句的结束位置then末尾生成的跳过跳转其实指向它自己后面的四元式这个四元式会保留一条冗余跳转。课程设计可以接受这个冗余想优化的话单独处理即可。3.3 回填Backpatching的实现机制回填技术解决的核心问题是生成跳转指令时跳转目标往往还不知道。四元式表是连续下标所以可以在生成跳转指令时先把result字段置0把这条四元式的下标记到一个待回填链表中等目标位置确定后再遍历链表把对应四元式的result字段改成真正的目标下标。我用两个链表分别维护“真链”和“假链”。真链存放所有条件为真时需要跳转的四元式下标假链存放所有条件为假时需要跳转的四元式下标。为什么必须分开因为回填目标不同真链要填then分支入口假链要填else分支入口或IF结束位置。如果混在一个链里回填时无法区分。下面是回填器的简单数据结构#define MAX_QUAD 1000 struct Quad { char op[8]; // 运算符 char arg1[20]; // 操作数1 char arg2[20]; // 操作数2 int result; // 结果/跳转目标0表示待回填 }; struct Quad quads[MAX_QUAD]; int quadIdx 0; // 下一条四元式存放位置 int trueChain[MAX_QUAD]; // 真链存放待回填的四元式下标 int falseChain[MAX_QUAD]; // 假链 int trueTop -1, falseTop -1;生成一条四元式后返回下标号当需要把目标target回填到链上所有四元式时遍历链数组把quads[chain[i]].result设为target。3.4 完整示例从源代码到四元式输入语句if a5 then x1 else x2;词法分析得到token序列if、id(a)、、num(5)、then、id(x)、、num(1)、else、id(x)、、num(2)、;。语法分析结合语义动作生成四元式的过程如下COND识别为a5此时quadIdx1先不生成跳转遇到then生成条件跳转(1) (j, a, 5, 0)再生成无条件跳转(2) (j, -, -, 0)把1号四元式加入真链2号加入假链then分支的x1生成(3) (:, 1, -, x)此时真链回填目标3所以回填1号四元式的result3then分支结束生成跳过语句(4) (j, -, -, 0)加入“跳过链”遇到else2号假链回填目标5else分支第一条四元式所以回填2号四元式的result5else分支的x2生成(5) (:, 2, -, x)整个IF语句结束跳过链回填到quadIdx6所以4号四元式的result6。最终输出(1) (j, a, 5, 3) (2) (j, -, -, 5) (3) (:, 1, -, x) (4) (j, -, -, 6) (5) (:, 2, -, x)这个输出跟前面的预期完全一致。执行逻辑如果a5跳到3号执行x1然后4号跳到6号结束否则跳到5号执行x2落到6号结束。4. 关键代码实现细节4.1 词法分析模块词法分析器的任务是从源码字符串中识别token。最容易踩的坑是关键字识别必须在标识符识别之后单独判断比如源码里的if如果先按“字母开头的都是标识符”处理就会把关键字吞掉。正确做法是先读完整段字母数字串再查关键字表是关键字就返回对应的token类型否则才是ID。int getToken() { skipWhitespace(); if (isalpha(ch)) { readLexeme(); if (strcmp(lexeme, if) 0) return TK_IF; if (strcmp(lexeme, then) 0) return TK_THEN; if (strcmp(lexeme, else) 0) return TK_ELSE; strcpy(tokenValue, lexeme); return TK_ID; } if (isdigit(ch)) { readNumber(); strcpy(tokenValue, lexeme); return TK_NUM; } switch (ch) { case : if (nextChar() ) { ch next(); return TK_LE; } return TK_LT; case : if (nextChar() ) { ch next(); return TK_EQ; } return TK_ASSIGN; case ;: return TK_SEMI; // 其他运算符类似 } }注意和必须靠向前看一个字符来区分。这个逻辑虽然简单但写错会导致后面关系运算和赋值运算全部错乱。4.2 表驱动预测分析程序表驱动的LL(1)分析器是标准的“栈查表”结构。分析栈初始状态下压入#和开始符号PROG循环处理直到栈空。核心伪代码如下void predictiveParse() { push(#); push(PROG); lookahead getToken(); while (!stack.empty()) { X stack.top(); if (isTerminal(X)) { if (X lookahead) { pop(); lookahead getToken(); } else error(terminal mismatch); } else { int prod parseTable[X][lookahead]; if (prod -1) error(no production); else { pop(); semanticActionBeforeExpand(prod); for (int i rhsLen(prod) - 1; i 0; i--) { if (rhs(prod, i) ! EPSILON) push(rhs(prod, i)); } } } } }这里的semanticActionBeforeExpand是在选择产生式展开前触发。对IF_STMT这类跨多个步骤的产生式语义动作不是一次做完而是分成“产生式选择时初始化”“遇到then时生成跳转”“STMT结束时生成跳过跳转”等多个钩子。想要在表驱动框架里表达这种时机需要额外维护一个语义状态机。这也是很多同学写着写着觉得别扭的地方。4.3 递归下降实现更直观的语义动作嵌入老实说虽然题目要求的是LL(1)法但到了真正写语义动作这步递归下降recursive descent要比表驱动直观得多。递归下降本质就是LL(1)的手写实现每个非终结符对应一个函数分析过程就是函数调用树的过程。在函数体内可以在任何位置插入语义动作。void parseIfStmt() { // IF_STMT - if COND then STMT ELSE_PART expect(TK_IF); parseCond(); // 翻译条件把条件保存到临时结构 int condJump emit(j, tempCond.arg1, tempCond.arg2, 0); int falseJump emit(j, -, -, 0); addTrueChain(condJump); addFalseChain(falseJump); expect(TK_THEN); int thenStart quadIdx; // then分支第一条四元式下标 backpatch(trueChain, thenStart); parseStmt(); // 翻译then后的语句 int skipJump emit(j, -, -, 0); // 跳过else parseElsePart(falseJump, skipJump); } void parseElsePart(int falseJump, int skipJump) { if (lookahead TK_ELSE) { match(TK_ELSE); backpatch(falseJump, quadIdx); // 假跳跳到else入口 parseStmt(); backpatch(skipJump, quadIdx); // 跳过跳到IF结束 } else { // ε无else backpatch(falseJump, quadIdx); backpatch(skipJump, quadIdx); } }这一个parseIfStmt函数就把整个IF语句的结构和语义动作摆在明面上了。代码里每一处emit、backpatch的时机都跟文法产生式一一对应讲答辩的时候也好解释。我见过不少课程设计用表驱动写了半天卡在else冲突和语义动作复杂上最后换递归下降半小时搞定本质没有改变LL(1)的性质但代码可读性完全是两个层级。4.4 四元式表与回填管理生成四元式就是往数组里追加一条记录返回当前索引。回填采用“链”的方式把同一个链上的所有待回填四元式下标依次存进数组回填时遍历数组把每条四元式的result字段统一赋值。注意每次回填完成要清空对应链的栈顶否则下一次回填会重复操作索引导致跳转目标错乱。5. 常见问题排查与经验分享5.1 悬空else匹配正确但输出四元式跳转方向反了这是新手最容易犯的问题。语义动作里条件跳转应该跳then分支入口无条件跳转应该跳else分支入口。很多同学把两个跳转的目标填反导致执行语义完全颠倒。排查方法很简单拿一条简单语句if a5 then x1 else x2手动推导一遍期望的四元式再对比程序输出。如果条件跳转的目标不是(:, 1, -, x)的那条方向就反了。5.2 回填时机和边界下的跳转目标错误回填最怕的是时序问题。常见错误是在then分支还没有生成任何四元式时就去回填真链此时quadIdx还指向条件跳转的位置结果把真跳目标填到同一个跳转自己身上。正确做法是先记录thenStart quadIdx然后调用parseStmt()最后用thenStart回填。记住一条原则先确定“目标位置”再执行“回填动作”目标位置的计算必须发生在对应代码生成之前。另一个边界情况是ELSE_PART为空。此时parseElsePart收到falseJump和skipJump两个跳转都要回填到quadIdx。这里quadIdx是IF语句之后的那个位置如果IF语句是整个程序的最后一条那么quadIdx数值就等于四元式总数加1。这个数字虽然超出了四元式表的有效范围但作为跳转目标依然合法表示“跳出程序”。5.3 嵌套IF-ELSE时的链管理多层嵌套时每一层IF都要有自己的真链、假链和跳过链。如果共用一套全局链数组内层回填时会把外层还没回填的跳转也填掉。解决办法是用局部变量保存当前层的链栈顶位置每层进入时记录下来退出时恢复。我在代码里建议把链操作设计成“压栈-保存现场-回填-恢复现场”的模式这样无论嵌套多少层每一层的回填数据都不会互相干扰。5.4 语义动作触发点在文法和代码中如何对齐很多同学写完文法到写代码时不知道语义动作该放在产生式的哪个位置。我的经验是把每个产生式写在纸上在右侧手写“此处的语义动作”然后从上到下对照代码。比如IF_STMT - if COND then STMT ELSE_PART在then和STMT之间会有生成条件跳转的动作在STMT和ELSE_PART之间会有生成跳过跳转的动作这些位置都对应产生式右侧的具体成分。把“动作位置”作为文法的扩展标记写清楚代码就只是按标记执行而已。5.5 测试用例建议测试不能只测一条简单IF-ELSE。我建议至少准备这五类用例无else的IF语句、单层IF-ELSE、多重嵌套IF-ELSE、IF中包含连续多条赋值语句、条件表达式覆盖全部六种关系运算符。尤其是嵌套用例能验证悬空else是否真的匹配最近if——在输出四元式里内层else分支的入口应该出现在内层then的跳过跳转之前这个顺序可以作为肉眼判断的快速依据。做完这套设计我对LL(1)和四元式的理解比看十遍书都深。最后再分享一个小技巧如果想把项目扩展成支持while循环或者and/or复合条件改动点其实是局部的——文法加产生式语义动作加对应的跳转生成规则四元式表结构完全不用动。这恰恰说明中间代码设计得好不好决定了整个编译器后端能走多远。本文还有配套的精品资源点击获取