LL(1)语法分析实战：IF-ELSE语句到四元式的编译器前端实现

简介这份资源是编译原理课程中IF-ELSE条件语句翻译程序设计的完整实现包面向正在学习语法分析与中间代码生成的高校学生及自学者。它围绕LL(1)预测分析法展开演示如何对条件语句进行词法识别、语法解析并输出四元式中间代码帮助理解编译器前端从源码到语义表示的关键流程。压缩包共17个文件约417KB包含cpp与h源码、vcproj与sln工程文件、rc资源脚本、manifest清单及Debug目录下的obj、pdb、idb等编译产物另有txt说明与htm文档构成可直接打开编译的Visual Studio工程。资源中附带的Compare模块涉及条件比较与跳转四元式的生成实例便于对照分析嵌套IF-ELSE、空语句与复合语句的处理方式。目前已有540人学习下载适合作为课程实验参考或编译器前端入门练手项目。1. 从一段 if-else 说起这个编译器前端项目到底在干什么你可能写过无数个 if-else但有没有想过编译器看到if (a b) { ... } else { ... }这串字符时它脑子里到底在算什么这个项目就是干这件事的用 LL(1) 分析法把一段 IF-ELSE 条件语句翻译成四元式。四元式是编译原理里经典的中间代码表示格式是(操作符, 操作数1, 操作数2, 结果)比如(, a, b, t1)就表示把 a 和 b 比较的结果存到临时变量 t1 里。整个项目覆盖了词法分析、LL(1) 语法分析、语义动作、四元式生成这条完整链路适合正在学编译原理、需要交课程设计或者想亲手摸一遍编译器前端流程的开发者。代码量不大但五脏俱全跑通之后你对“语法分析器怎么把字符变成中间代码”这件事会有完全不一样的理解。2. 技术选型与整体架构为什么用 LL(1) 而不是 LR2.1 LL(1) 的适用边界与项目定位LL(1) 是自顶向下分析法里最基础的一种核心要求是文法无左递归、无回溯且每个非终结符的 FIRST 集和 FOLLOW 集不能有冲突。IF-ELSE 语句的文法天然适合用 LL(1) 处理因为它的结构是线性的先看到if然后读条件表达式再读then分支最后可选地读else分支。用递归下降或者预测分析表都能实现这个项目大概率用的是预测分析表驱动的方式因为这样更贴近教材里 LL(1) 的标准流程。选 LL(1) 而不是 LR 的原因很实际LL(1) 的分析表构造逻辑清晰手写代码量少调试的时候能直接看到栈里压了什么、当前读到的 token 是什么。LR 虽然能处理更多文法但状态机构造和规约动作的调试成本对初学者不友好。这个项目的目标不是做一个工业级编译器而是把“语法分析驱动语义动作”这条链路讲清楚LL(1) 是性价比最高的选择。2.2 模块划分与数据流整个项目按编译阶段拆成四个模块数据流是单向的源代码字符串 ↓ [词法分析器] → token 序列 ↓ [LL(1) 语法分析器] → 语法树 / 规约序列 ↓ [语义动作] → 四元式列表 ↓ [输出模块] → 格式化打印词法分析器负责把if、(、a、、b、)这些切成 token每个 token 带类型和值。语法分析器用预测分析表驱动一个栈遇到非终结符就查表展开遇到终结符就匹配并触发语义动作。语义动作是嵌在文法产生式里的比如读到if的时候生成一个条件跳转的四元式读到else的时候回填跳转地址。输出模块把四元式列表按序号打印出来方便对照检查。2.3 预测分析表的构造逻辑预测分析表是 LL(1) 的核心数据结构行是非终结符列是终结符单元格里放产生式编号。构造步骤分三步先算 FIRST 集再算 FOLLOW 集最后根据A → α把 α 的 FIRST 集填进去如果 α 能推导出空串再把 FOLLOW(A) 填进去。# 构造预测分析表的简化逻辑 def build_parsing_table(grammar, first_sets, follow_sets): table {} # key: (非终结符, 终结符), value: 产生式 for production in grammar: lhs production.left rhs production.right first_rhs compute_first_of_sequence(rhs, first_sets) for terminal in first_rhs: if terminal ! ε: table[(lhs, terminal)] production if ε in first_rhs: for terminal in follow_sets[lhs]: table[(lhs, terminal)] production return table这段代码里compute_first_of_sequence要处理符号串的 FIRST 集如果某个符号能推出空串就继续看下一个符号。follow_sets是提前算好的 FOLLOW 集。填表的时候如果发现同一个单元格被填了两次说明文法有冲突不是 LL(1) 文法需要改写。实际调试的时候我一般会在填表前打印 FIRST 和 FOLLOW 集确认没算错再往下走不然表填错了后面分析器跑起来全是玄学错误。3. 核心模块拆解词法分析、语法分析与四元式生成3.1 词法分析器把字符流切成 token词法分析器的任务很单纯从左到右扫描源代码识别出关键字、标识符、运算符、界符和常量。IF-ELSE 语句里涉及的关键字就if和else两个运算符有、、这些关系运算符界符是(、)、{、}。# 词法分析器核心逻辑 KEYWORDS {if, else} OPERATORS {, , , , , !} DELIMITERS {(, ), {, }, ;} def tokenize(source): tokens [] i 0 while i len(source): ch source[i] if ch.isspace(): i 1 continue if ch.isalpha(): # 标识符或关键字 j i while j len(source) and (source[j].isalnum() or source[j] _): j 1 word source[i:j] if word in KEYWORDS: tokens.append((KEYWORD, word)) else: tokens.append((ID, word)) i j elif ch.isdigit(): # 数字常量 j i while j len(source) and source[j].isdigit(): j 1 tokens.append((NUM, source[i:j])) i j elif ch in OPERATORS or ch in DELIMITERS: # 处理双字符运算符 if i 1 len(source) and source[i:i2] in OPERATORS: tokens.append((OP, source[i:i2])) i 2 else: tokens.append((OP if ch in OPERATORS else DELIM, ch)) i 1 else: raise SyntaxError(f非法字符: {ch} 位置: {i}) return tokens这段代码里tokenize函数逐字符扫描遇到字母就往后读直到非字母数字下划线判断是关键字还是标识符。遇到数字就读完整数字串。运算符那里有个细节要先检查双字符运算符比如不能被切成和。最后如果遇到不认识的字符直接抛异常方便定位问题。实际跑的时候建议在 tokenize 之后打印一遍 token 列表确认切分正确再喂给语法分析器不然语法分析报错你都不知道是词法切错了还是文法写错了。3.2 LL(1) 语法分析器栈驱动的推导过程语法分析器维护一个栈初始时压入开始符号。每一步看栈顶符号和当前输入 token如果栈顶是终结符且和当前 token 匹配就弹出栈并读下一个 token如果栈顶是非终结符就查预测分析表把对应产生式的右部逆序压栈如果栈顶是空串就弹出。匹配过程中触发语义动作。# LL(1) 语法分析器主循环 def parse(tokens, parsing_table, start_symbol): stack [$, start_symbol] # $ 是结束符 input_tokens tokens [(EOF, $)] ip 0 # 输入指针 quadruples [] # 四元式列表 temp_count 0 # 临时变量计数器 while stack: top stack[-1] current_token input_tokens[ip] if top $ and current_token[1] $: break # 分析成功 if top current_token[1]: # 终结符匹配 stack.pop() ip 1 elif (top, current_token[1]) in parsing_table: production parsing_table[(top, current_token[1])] stack.pop() # 逆序压栈 for symbol in reversed(production.right): if symbol ! ε: stack.append(symbol) # 触发语义动作 action production.semantic_action if action: temp_count action(quadruples, temp_count, current_token) else: raise SyntaxError(f语法错误: 栈顶 {top}, 当前 token {current_token}) return quadruples主循环里stack初始压入$和开始符号$是栈底标记。每次循环看栈顶和当前 token匹配就弹栈读下一个不匹配就查表展开。展开的时候产生式右部要逆序压栈因为栈是后进先出。语义动作在展开的时候触发比如if对应的产生式展开时生成条件跳转四元式。temp_count用来生成t1、t2这样的临时变量名每次需要新临时变量就加一。这里有个容易翻车的地方语义动作的触发时机要和产生式展开严格对应不能提前也不能延后否则四元式顺序会乱。3.3 四元式生成回填技术与控制流IF-ELSE 的四元式生成难点在跳转地址的回填。因为 LL(1) 是自顶向下分析读到if的时候还不知道else分支的代码有多长所以只能先生成一个空地址的跳转指令等分析到对应位置再回填。# 语义动作处理 if 条件为假时的跳转 def gen_if_false(quadruples, temp_count, condition_result): # 生成条件跳转四元式跳转地址暂时为空 index len(quadruples) quadruples.append((jf, condition_result, _, None)) # jf jump if false return index # 回填函数 def backpatch(quadruples, index, target): op, arg1, arg2, _ quadruples[index] quadruples[index] (op, arg1, arg2, target)gen_if_false在条件表达式求值之后调用生成一个jf四元式第四个参数先留空。backpatch在知道跳转目标之后调用把空地址填上。比如if (a b) { s1 } else { s2 }的四元式序列大概是(, a, b, t1) (jf, t1, _, 5) # 条件为假跳到第5条 (, c, d, t2) # then 分支 (, t2, _, x) (j, _, _, 8) # then 分支结束跳到第8条 (*, e, f, t3) # else 分支 (, t3, _, y)第 2 条的跳转地址 5 和第 5 条的跳转地址 8 都是回填进去的。这里的关键是维护一个待回填列表每次生成跳转指令就把索引存进去等分析到目标位置再统一回填。我一般会在回填之后打印完整四元式列表逐条检查跳转地址对不对这个步骤能省掉大量调试时间。4. 避坑与常见问题语法分析器跑不通时先查这几处4.1 文法左递归导致栈溢出现象分析器一启动就无限循环栈越压越深最后报递归深度超限或者内存溢出。原因文法里存在左递归比如E → E TLL(1) 遇到这种情况会一直展开 E 而不消耗输入 token。解决把左递归改写成右递归E → T EE → T E | ε。改写之后 FIRST 和 FOLLOW 集要重新算预测分析表也要重建。改完记得验证新文法还是不是 LL(1)有时候改写会引入新的冲突。4.2 FIRST 集和 FOLLOW 集算错导致查表失败现象分析器跑到某个 token 时报“查表失败”但文法看起来没问题。原因FIRST 集或 FOLLOW 集计算有误预测分析表里该填的单元格没填上。常见错误是忘了处理 ε 产生式或者 FOLLOW 集没有正确传播。解决单独写一个测试函数打印每个非终结符的 FIRST 和 FOLLOW 集和手工计算的结果对照。重点检查含 ε 的产生式以及 FOLLOW 集的传递规则如果A → αBβ那么 FIRST(β) 去掉 ε 要加到 FOLLOW(B)如果 β 能推出 εFOLLOW(A) 要加到 FOLLOW(B)。4.3 语义动作触发时机错位现象四元式顺序混乱跳转地址对不上或者临时变量重复使用。原因语义动作嵌在产生式里但触发时机和产生式展开的时机没对齐。比如在匹配终结符的时候触发了本该在展开非终结符时触发的动作。解决在产生式对象里明确标记语义动作展开时统一触发。建议在每次触发语义动作时打印当前产生式和生成的四元式方便追踪。临时变量计数器要全局维护不能每个动作自己维护一份。4.4 回填地址偏移量计算错误现象四元式列表打印出来跳转地址差一位或者差几条。原因回填的时候目标地址算错了常见的是把当前四元式索引和下一个索引搞混或者忘了四元式列表是从 0 开始还是从 1 开始。解决统一约定四元式编号从 0 开始回填的时候用len(quadruples)作为下一个待生成四元式的索引。每次回填后打印目标索引和实际跳转位置对照检查。如果跳转地址是相对地址还要注意基址问题。4.5 词法分析器把双字符运算符切错现象被切成和语法分析器报错。原因词法分析器逐字符扫描时没有优先匹配最长运算符。解决在识别运算符时先检查双字符组合再检查单字符。可以用一个有序列表按长度降序排列运算符匹配时从长到短尝试。这个坑很隐蔽因为单字符运算符单独看没问题只有组合出现时才暴露。5. 二次开发与改造思路从课程设计到可扩展的编译器前端这个项目跑通之后最自然的改造方向是扩展支持的语句类型。当前只处理 IF-ELSE你可以加 WHILE 循环、FOR 循环、变量声明和赋值语句。改造的核心思路是每加一种语句就往文法里加对应的产生式然后写对应的语义动作生成四元式。WHILE 循环的四元式生成和 IF-ELSE 类似也需要回填但多了一个往回跳的指令。# WHILE 循环的四元式生成骨架 def gen_while(quadruples, temp_count, condition_result): loop_start len(quadruples) # 循环开始位置 jf_index len(quadruples) quadruples.append((jf, condition_result, _, None)) # 条件为假跳出 return loop_start, jf_index def end_while(quadruples, loop_start, jf_index): quadruples.append((j, _, _, loop_start)) # 跳回循环开始 backpatch(quadruples, jf_index, len(quadruples)) # 回填跳出地址gen_while在循环条件求值后调用记录循环开始位置并生成条件跳转。end_while在循环体分析完后调用生成跳回指令并回填跳出地址。改造的时候要注意嵌套结构比如 WHILE 里面套 IF-ELSE回填列表要按嵌套层级管理不然内层跳转可能回填到外层地址上。另一个改造方向是加错误恢复机制。当前遇到语法错误直接抛异常实际编译器会跳过一些 token 继续分析尽量多报几个错误。可以在语法分析器里加一个错误恢复模式遇到查表失败时弹栈直到找到一个能匹配当前 token 的状态或者跳过当前 token 继续。这个改造对理解编译器的容错设计很有帮助。验证改造是否正确的办法是写一组测试用例覆盖各种嵌套和边界情况然后人工检查四元式序列。我一般会准备一个对照表左边写源代码右边写期望的四元式跑完自动对比。这个习惯是从一次翻车经历来的当时改完 WHILE 循环觉得没问题结果嵌套 IF-ELSE 的时候跳转地址全乱了因为没有自动化对比手工检查漏掉了一个回填点。从那以后我每次改文法或者语义动作都强制走一遍全量测试用例确认四元式序列和预期完全一致才继续。希望这个项目能帮到你跑通之后你对编译器前端的理解会扎实很多。本文还有配套的精品资源点击获取