简介本资源是北京交通大学《编译原理》课程配套的完整实验源码集合面向计算机科学与技术专业本科生及编译器开发初学者系统覆盖编译器前端六大核心环节词法分析、递归下降语法分析、LL(1)文法分析、算符优先文法分析、基于SLR(1)的语法制导翻译、中间代码生成。压缩包共94个文件含33个C源文件cpp实现核心算法逻辑、29个头文件h封装数据结构与接口、21个文本文件txt提供测试用例与文法定义、6个Makefile支持一键编译另有README.md和说明文档辅助理解整体架构。资源仅66KB轻量精炼目录按Lab01–Lab06清晰划分六大实验模块每个模块均含可运行示例、测试输入与预期输出便于逐层验证与调试。目前已有88人学习下载是深入理解编译流程、掌握语法分析表构建、语义动作嵌入及三地址码生成等关键技术的高质量实践材料。1. 项目概述从课程实验到编译器前端的完整拼图最近在整理过往的学习资料时翻出了一个压箱底的“宝藏”——我在北京交通大学攻读计算机专业期间完成的《编译原理》课程全套实验项目的完整源码集合。这个压缩包可以说是我学生时代在系统软件领域投入心血最多的结晶。它不是一个玩具而是一个严格按照课程要求从零开始逐步构建出一个具备完整前端功能的编译器的实践记录。里面包含了从最基础的词法分析到递归下降、LL(1)、算符优先、SLR(1)等多种语法分析方法的实现最终抵达语法制导翻译和中间代码生成这六个核心实验模块。每一个模块都像是一块拼图单独看是一个精巧的算法实现组合起来则构成了一个编译器前端的完整工作流。对于计算机专业的学生尤其是正在或即将学习编译原理的同学来说编译原理这门课常常被誉为“天书”。它充满了抽象的概念、复杂的算法和严谨的数学理论。课堂上的有限自动机、上下文无关文法、LR分析表听起来都离实际的编程很远。而实验正是打通理论与实践的桥梁。这个源码集合的价值就在于它提供了一个可运行、可调试、可修改的完整参考。你不仅能看懂每一行代码在做什么更能通过运行它直观地看到一个简单的源程序是如何被一步步“肢解”成单词词法分析再根据语法规则组装成树语法分析最后被翻译成一种更接近机器、但独立于具体机器的中间表示中间代码生成。这个过程是理解编译器如何工作的最佳途径。无论你是想预习课程、完成作业、准备考试还是单纯对编译器内部机制感到好奇这个项目都能给你带来实实在在的帮助。它基于Java实现结构清晰注释详尽避免了过于复杂的工程化封装将核心算法逻辑直接呈现在你面前。接下来我将带你深入这个“六合一”的编译器前端实验项目拆解每一个模块的设计思路、实现细节并分享我在实现过程中踩过的坑和总结的经验。2. 项目整体架构与设计哲学2.1 模块化设计六个实验的递进关系这个项目的结构并非随意堆砌而是严格遵循了编译器前端经典的处理流程并对应了课程实验的六个阶段性目标。理解这个递进关系是读懂整个项目的关键。第一层词法分析器Scanner/Lexer这是所有工作的起点。它的任务无比纯粹读入源代码字符串忽略空格、换行、注释等无关内容识别出一个个具有独立意义的“单词”即“词法单元”Token。例如对于语句int a 10 b;词法分析器会输出序列KEYWORD, int、ID, a、OPERATOR, 、INTEGER, 10、OPERATOR, 、ID, b、DELIMITER, ;。它为后续所有分析提供了原材料。在这个项目中词法分析器被设计为一个独立的类提供getNextToken()这样的接口供语法分析器驱动。第二层语法分析器Parser——多种方法的实践这是项目的核心和难点。语法分析器接收词法单元流根据预定义的语法规则通常用BNF范式表示检查其结构是否符合规范并通常构建出一棵“语法分析树”。课程实验的精妙之处在于它要求我们用四种不同的方法来实现语法分析每一种都对应着编译原理理论中的一个重要流派递归下降分析法最直观的方法。为语法规则的每一个非终结符编写一个递归函数。这种方法手工编写方便特别适合表达式、控制语句等结构但它要求文法必须是LL(1)的且左递归必须消除。LL(1)分析法一种表驱动的自顶向下分析方法。需要预先计算FIRST集和FOLLOW集并构造LL(1)预测分析表。分析器根据当前栈顶符号和输入符号查表决定使用哪条产生式。它比递归下降更形式化是理解自顶向下分析自动化的关键。算符优先分析法专门为表达式语法设计的一种简单、高效的自底向上分析方法。它不严格基于语法树而是通过比较相邻运算符的优先级来决定归约顺序适合快速处理表达式但文法适用范围窄。SLR(1)分析法一种自底向上的、能力更强的LR分析方法。需要构造项目集规范族和SLR(1)分析表。它能处理更广泛的文法是实践中许多编译器生成器如Yacc的理论基础。实现SLR(1)分析器是对LR分析理论最深入的实践。第三层语法制导翻译与中间代码生成这是语法分析的升华。我们不再仅仅满足于检查语法是否正确还要赋予语法结构以“语义”。语法制导翻译将“属性”如类型、值、代码地址与文法符号关联并在语法分析过程中通过嵌入在递归函数或分析动作中的代码计算这些属性。最终产出不再是树而是一种中间表示常见的有三地址码如t1 10 b,a t1或抽象语法树的某种线性化形式。这个模块将前端分析与后端优化、代码生成连接起来。2.2 技术选型为什么是Java你可能会问经典的编译原理教材多用C工业级的编译器多用C或Rust为什么这个项目选择Java这背后有几点非常实际的考量教学友好性Java语言本身相对简洁内存管理自动化让学生能将精力集中于算法逻辑本身而不是指针、内存泄漏等底层细节。其丰富的标准库尤其是集合框架ArrayList,HashMap非常适合实现符号表、分析表等数据结构。快速原型能力Java的面向对象特性让模块化设计变得自然。我们可以轻松地定义Token、Production、LRItem等类并通过继承和多态来管理不同的分析器。编写和调试效率高。跨平台与可交付性“一次编写到处运行”的特性使得这份代码可以在任何装有JVM的机器上编译运行极大方便了同学之间的交流、以及老师的统一评测。最终打包成一个清晰的、包含所有依赖的工程如Maven或Gradle项目交付体验非常好。与课程理论的契合度编译原理中的很多概念如状态集合、表驱动用Java的集合类来实现非常直观。构造LR(0)项目集规范族时对项目集合的哈希去重、比较等操作用Java写起来比C流畅得多。注意选择Java并不意味着牺牲性能或深度。这个项目的目标是教学与实践而非打造产品级编译器。用Java清晰地实现出LL(1)或SLR(1)分析表的构造算法其教育意义远大于用C写一个模糊难懂的版本。事实上许多现代语言的处理工具如Antlr也是用Java编写的。2.3 代码结构导览项目的目录结构大致如下体现了清晰的模块分离思想compiler-frontend-experiments/ ├── src/ │ ├── lexer/ # 词法分析模块 │ │ ├── Token.java # 词法单元类类型值行号 │ │ ├── TokenType.java # 词法单元类型枚举INT, ID, PLUS等 │ │ └── Lexer.java # 词法分析器核心类 │ ├── parser/ # 语法分析模块 │ │ ├── rd/ # 递归下降分析器 │ │ ├── ll1/ # LL(1)分析器含FIRST/FOLLOW集计算 │ │ ├── op/ # 算符优先分析器 │ │ └── slr/ # SLR(1)分析器含项目集、ACTION/GOTO表构造 │ ├── grammar/ # 文法定义相关 │ │ ├── Production.java # 产生式类 │ │ └── Grammar.java # 文法管理类从文件读取计算闭包等 │ ├── symbol/ # 符号表管理 │ │ └── SymbolTable.java │ ├── sdts/ # 语法制导翻译与中间代码生成 │ │ ├── Attribute.java # 属性类 │ │ ├── Quadruple.java # 四元式中间代码表示 │ │ └── SDTVisitor.java # 基于访问者模式的语法制导翻译器 │ └── main/ # 主程序入口用于测试各个模块 │ └── CompilerFrontendDemo.java ├── grammars/ # 存放不同分析器测试用的文法文件 │ ├── expression_grammar.txt │ └── slr_grammar.txt ├── test_cases/ # 测试用例正确的和错误的 │ ├── source_code.simple │ └── ... └── README.md # 项目说明构建与运行指南这种结构保证了每个实验模块的独立性你可以单独运行词法分析器看输出也可以单独测试SLR(1)分析器更可以串联起整个流程。3. 核心模块深度解析与实现要点3.1 词法分析器编译器视角下的“分词工具”词法分析器是编译器的“眼睛”。它的实现看似简单但健壮性要求极高。核心是有限自动机DFA的思想。我们并没有显式地画出状态转换图而是在代码中用条件分支逻辑隐式地实现了一个DFA。实现核心Lexer.java中的getNextToken()方法这个方法是一个大的循环每次调用都从输入流中读取字符直到识别出一个完整的Token。public Token getNextToken() { // 跳过空白字符空格、制表符、换行 skipWhitespace(); if (pos source.length()) { return new Token(TokenType.EOF, , line); } char currentChar source.charAt(pos); // 识别标识符和关键字以字母或下划线开头 if (Character.isLetter(currentChar) || currentChar _) { return parseIdentifierOrKeyword(); } // 识别数字字面量 else if (Character.isDigit(currentChar)) { return parseNumber(); } // 识别运算符和分隔符 else if (isOperator(currentChar)) { return parseOperator(); } // 识别字符串字面量 else if (currentChar \) { return parseString(); } // 处理注释 else if (currentChar / peekNextChar() /) { skipSingleLineComment(); return getNextToken(); // 递归调用跳过注释后继续识别 } // ... 其他情况处理 }parseIdentifierOrKeyword函数会持续读入字母数字形成一个字符串然后去关键字表中查找。这里的关键是关键字表的组织。我使用了一个HashSetString来存储所有关键字识别出标识符后用keywords.contains(word)来判断是否是关键字。这种方式比一堆if-else判断高效且易于维护。实操心得与避坑指南行号与列号的维护为了在报错时能精确定位必须在读字符的过程中仔细维护行号和列号。每次遇到\n行号加1列号重置。这个细节很容易出错特别是在处理跨多行的注释或字符串时。向前看字符Lookahead的必要性像、、!这样的双字符运算符以及/*注释的开始都需要预读下一个字符才能确定。peekNextChar()方法只看不移动指针在这里至关重要。错误恢复策略简单的词法分析器在遇到无法识别的字符如、$时可能直接抛出异常终止。一个更健壮的实现应该记录错误“非法字符”然后跳过该字符尝试继续分析下一个可能的Token这样能一次报告所有词法错误。字符串和字符字面量的处理要正确处理转义字符如\n、\t、\。这需要一个小型的转义字符映射表。3.2 递归下降语法分析最直观的“手工”解析递归下降分析法将文法规则直接映射为代码中的递归函数调用非常符合人类的直觉。例如对于一个简单的算术表达式文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id | num我们可以编写如下函数伪代码void parseE() { parseT(); parseEPrime(); } void parseEPrime() { if (currentToken.type PLUS) { match(PLUS); // 消耗掉‘’ parseT(); parseEPrime(); } // 否则对应 ε什么都不做 } void match(TokenType expected) { if (currentToken.type expected) { currentToken lexer.getNextToken(); } else { throw new SyntaxError(Expected expected , but found currentToken.type); } }实现要点消除左递归上述文法是已经消除了左递归的。原始文法E - E T会导致函数parseE()无限递归调用自身。必须先将文法转换为等价的非左递归形式这是使用递归下降的前提。处理 ε 产生式对应函数中的空分支通常通过判断当前Token是否在某个集合如FOLLOW集中来决定是否选择该分支。回溯问题纯递归下降在遇到不确定选择时可能需要回溯效率低。因此我们通常使用预测性递归下降即通过查看当前Token的FIRST集来唯一确定使用哪条产生式这就要求文法是LL(1)的。踩坑记录我曾在一个if-else语句的文法上栽过跟头。文法规则是Stmt - if ( Expr ) Stmt else Stmt | ...。在解析if (x0) if (y0) a1; else b1;时else应该匹配第二个if还是第一个if这就是经典的“悬空else”问题。纯递归下降会将其匹配到最近的if这符合大多数语言的语义但需要在设计文法时就意识到这一点。我的经验是为这种有歧义的结构编写递归下降函数时要特别小心函数返回的时机和else的匹配逻辑。3.3 LL(1)分析法从手工到自动化的桥梁LL(1)分析将递归下降的“预测”过程表格化、自动化。实现一个LL(1)分析器分为两个主要阶段分析表构造和表驱动分析。第一阶段计算FIRST集和FOLLOW集这是整个LL(1)分析中最容易出错的理论计算部分必须通过代码精确实现。FIRST(α)串α能推导出的开头终结符集合。计算时需递归处理特别是当非终结符能推出ε时需要继续看后面的符号。FOLLOW(A)紧跟非终结符A后面出现的终结符集合。计算时需要遍历所有产生式寻找A的出现位置并考虑其后的串的FIRST集如果后面的串能推出ε还要并入产生式左部符号的FOLLOW集。我在LL1TableBuilder类中实现了这两个集合的计算。算法本质上是图上的不动点迭代反复应用规则直到所有集合不再变化。这里一定要用while循环配合一个changed标志确保计算到收敛。第二阶段构造预测分析表规则是对每条产生式A - α将(A, a)对应的表项填入A - α其中终结符a属于FIRST(α)如果ε在FIRST(α)中则对FOLLOW(A)中的每个终结符b也将(A, b)填入A - α。 构造完成后必须检查每个表项是否最多只有一个产生式否则文法就不是LL(1)的。第三阶段表驱动分析使用一个分析栈。初始时栈底为$栈顶为文法开始符号。根据栈顶符号X和当前输入符号a若X a $分析成功。若X是终结符且X a弹出X消耗输入a。若X是非终结符查表M[X, a]。如果为空报错否则将表项中的产生式右部符号逆序压入栈中保证最左推导。// 简化版分析循环 while (!stack.isEmpty()) { Symbol top stack.peek(); Token current inputToken; if (top.isTerminal()) { if (top.equals(current.type)) { stack.pop(); advanceInput(); } else { error(); } } else { Production prod parsingTable.get(top, current.type); if (prod null) { error(); } else { stack.pop(); // 将产生式右部逆序压栈 for (int i prod.rhs.size() - 1; i 0; i--) { if (!prod.rhs.get(i).isEpsilon()) { // 不压入 ε stack.push(prod.rhs.get(i)); } } } } }提示调试LL(1)分析器时最有效的方法是打印出每一步的分析栈、剩余输入和将要执行的动作。这能帮你清晰地看到推导过程快速定位是FIRST/FOLLOW集算错了还是分析表填错了。3.4 算符优先分析法快速处理表达式的利器算符优先分析跳出了严格的语法树框架它不关心完整的语法结构只关注运算符之间的优先级关系。它需要两张表优先关系表,,。核心思想比较栈顶运算符θ1和当前输入运算符θ2的优先关系。若θ1 θ2θ2入栈移进。若θ1 θ2通常只有括号配对时出现脱括号弹出。若θ1 θ2进行归约在栈顶寻找一个最左的形如非终结符 运算符 非终结符的序列将其归约为一个非终结符。实现难点优先关系的确定优先关系不是任意的需要根据文法推导。对于简单的表达式文法我们可以手动定义。例如对于、-、*、/、(、)通常定义、-优先级低于*、/。相同优先级的运算符左结合。(的优先级低于所有运算符但在栈内时(的优先级极低遇到)时需要找到匹配的(。 在我的实现中我使用了一个二维枚举数组Relation[][]来存储这个关系表。实操过程分析器维护一个符号栈。栈中交替存放着操作数和运算符实际上为了简化我们只存运算符和作为分隔符的非终结符操作数由另一个值栈管理。算法流程是一个经典的移进-归约循环但归约动作不是基于产生式而是基于“可归约串”的模式匹配。while (输入未结束) { a 当前输入符号; if (栈顶是操作数 a 是操作数) { 错误 // 不允许两个操作数相邻 } if (栈顶是终结符 θ) { 关系 优先关系表[θ][a]; if (关系 LESS) { // θ a 移进 a; } else if (关系 GREATER) { // θ a 进行归约; // 归约后栈顶变为一个非终结符N // 此时需要比较新的栈顶符号可能是运算符和 a 的关系 } else if (关系 EQUAL) { // 通常是 ( ) 脱括号弹出 (); 消耗输入 ); } else { 错误 // 优先关系未定义语法错误 } } else { // 栈顶是非终结符将其视为一个整体操作数直接移进输入符号a 移进 a; } }算符优先分析速度快但能力有限无法处理复杂的非运算符语法结构。它是我在项目中实现的“特化工具”专门用于演示如何高效处理表达式。3.5 SLR(1)分析法自底向上分析的经典实践SLR(1)是LR分析家族中相对简单但能力足够强的一种。实现一个SLR(1)分析器是编译原理实验的“毕业设计”它综合了DFA构造、集合运算和表驱动分析。第一步构造LR(0)项目集规范族这是最复杂的一步。一个LR(0)项目形如A - α·β圆点表示分析进度。我们从初始项目S - ·S开始通过计算闭包Closure和读符号转移Goto函数逐步构造出所有的状态项目集。闭包操作如果项目是A - α·Bβ那么对于B的所有产生式B - γ要把B - ·γ加入闭包。这是一个递归过程。Goto操作对于状态I和文法符号XGoto(I, X)是所有形如[A - αX·β]的项目的集合其中[A - α·Xβ]在I中。然后再对这个集合求闭包。我使用了一个ListLR0State来存储所有状态并用一个MapPairLR0State, Symbol, LR0State来记录Goto关系。为了避免生成重复状态每次生成新状态时都要与已有状态比较项目集是否相等。第二步构造SLR(1)分析表对于每个状态i移进动作ACTION[i, a] sj如果项目[A - α·aβ]在状态i中且a是终结符且Goto(i, a) j则ACTION[i, a] 移进j。归约动作ACTION[i, a] rk如果项目[A - α·]在状态i中则对所有a ∈ FOLLOW(A)ACTION[i, a] 按产生式k归约。这里用到了FOLLOW集来解决冲突这也是SLR(1)中“S”的由来。接受动作如果项目[S - S·]在状态i中则ACTION[i, $] 接受。GOTO表如果Goto(i, X) j且X是非终结符则GOTO[i, X] j。第三步表驱动分析分析器同样使用一个状态栈和一个符号栈。stack.push(initialState); // 状态栈 symbolStack.push(END_MARKER); // 符号栈 Token lookahead lexer.getNextToken(); while (true) { int state stack.peek(); Action action actionTable[state][lookahead.type]; if (action.type SHIFT) { // 移进 stack.push(action.number); // 新状态 symbolStack.push(lookahead); lookahead lexer.getNextToken(); } else if (action.type REDUCE) { // 归约 Production prod productions[action.number]; // 从栈中弹出右部符号及其对应的状态 for (int i 0; i prod.rhs.size(); i) { stack.pop(); symbolStack.pop(); } // 获取归约后的左部符号A Symbol lhs prod.lhs; // 根据归约前的状态和新符号A查找GOTO表得到新状态 int newState gotoTable[stack.peek()][lhs]; // 压入新状态和A stack.push(newState); symbolStack.push(lhs); // 可以在这里执行语义动作生成四元式 executeSemanticAction(prod); } else if (action.type ACCEPT) { // 接受成功 break; } else { // 报错 reportSyntaxError(state, lookahead); // 错误恢复... } }经验之谈调试SLR(1)分析器调试SLR(1)分析器极具挑战性。我的建议是可视化状态机将构造出的LR(0)项目集规范族和Goto关系以图的形式打印出来。这能帮你直观地检查状态是否完整转移是否正确。分步跟踪分析过程像调试LL(1)一样打印每一步的状态栈、符号栈、剩余输入和即将执行的动作。这是定位分析表错误的唯一有效方法。关注归约-归约和移进-归约冲突如果文法不是SLR(1)的构造表时会在同一表项出现多个动作。你需要分析冲突原因是文法有二义性还是需要更强的LR(1)或LALR(1)分析。在实验项目中我们通常通过修改文法来消除冲突。FOLLOW集的计算务必准确SLR(1)利用FOLLOW集来缩小归约动作的适用范围。如果FOLLOW集算大了会导致无效的归约算小了会导致该归约时找不到动作。这是SLR(1)分析器最常见的错误来源之一。3.6 语法制导翻译与中间代码生成赋予语法以意义语法分析只解决了“结构对不对”的问题而语法制导翻译SDT要解决“做什么”的问题。我们选择在SLR(1)分析器进行归约时执行相应的语义动作从而生成中间代码。语义动作的设计我们为每个产生式关联一段语义子程序。这些子程序可以访问和修改与文法符号相关的属性。最常见的属性是综合属性自底向上传递如表达式的值、类型有时也需要继承属性自顶向下传递如变量的声明类型。在这个项目中我们主要实现三地址码的生成。三地址码的基本形式是x y op z。我们用一个Quadruple四元式类来表示包含操作符op、两个操作数arg1、arg2和一个结果result。实现模式在SLR(1)分析器的归约动作中我们根据归约所用的产生式编号调用对应的语义例程。private void executeSemanticAction(int productionIndex) { switch (productionIndex) { case 0: // S - E // E的属性比如它的值存放的临时变量名就是整个S的结果 break; case 1: // E - E T String temp newTemp(); // 生成新的临时变量如t1, t2... String eAddr getAttribute(stack, -3); // 获取E的属性地址 String tAddr getAttribute(stack, -1); // 获取T的属性 emit(new Quadruple(, eAddr, tAddr, temp)); // 生成四元式temp eAddr tAddr setAttribute(stack, -3, temp); // 将新生成的临时变量作为这个E的综合属性 break; case 2: // E - T // 直接传递属性 break; case 3: // T - T * F // 类似加法生成乘法四元式 break; // ... 其他产生式 case 10: // F - id String idName getTokenValue(stack, -1); // 获取标识符的名字 setAttribute(stack, -1, idName); // 属性就是标识符的名字本身 break; } }这里的关键是属性栈的管理。我们需要一个与符号栈平行的属性栈每当符号入栈或出栈时其对应的属性也同步操作。在归约时我们从属性栈中弹出右部符号的属性计算得到左部符号的属性再压入栈中。符号表的管理为了生成正确的代码我们必须知道标识符的类型、存储位置等信息。这就需要符号表。在分析到声明语句如int a;时我们将标识符a及其类型信息插入符号表。在后续表达式中使用a时就从符号表中查找其信息确保使用前已声明静态语义检查并获取其类型以进行可能的类型转换。中间代码的优化简单示例在生成四元式时我们可以进行一些简单的优化。例如对于常量表达式3 5我们可以在语义动作中直接计算出结果8并生成t1 8而不是生成t1 3 5。这称为常量折叠是编译器优化中最基本的一步。4. 项目集成、测试与常见问题排查4.1 如何串联六个模块进行端到端测试单独测试每个模块是基础但真正的成就感来自于将它们串联起来看着一段简单的源代码最终变成一串三地址码。我编写了一个集成测试的主类CompilerFrontendDemo它提供了命令行接口允许用户选择不同的分析器并指定源代码文件。集成流程如下初始化读取文法文件初始化对应的分析器如SLR(1)分析器需要预先构造分析表。词法分析将源代码文件送入词法分析器得到一个Token流。可以在这里选择是否打印Token序列以供调试。语法分析与翻译将Token流送入选定的语法分析器如SLR(1)分析器。该分析器在工作的同时会驱动语法制导翻译模块在归约时生成四元式。输出结果如果源代码语法正确则打印“语法分析成功”并输出生成的三地址码序列。如果中途发现错误则输出详细的错误信息包括错误类型、位置和可能的修正建议。一个典型的测试用例test.simple可能如下int main() { int a, b, c; a 10; b 20; c a b * 2; print(c); }期望的中间代码输出可能类似于t0 10 a t0 t1 20 b t1 t2 2 t3 b * t2 t4 a t3 c t4 param c call print, 14.2 常见编译错误、警告与排查技巧在实现和测试过程中你会遇到各种各样的错误。下面是一个快速排查指南问题现象可能原因排查步骤与解决方案词法分析阶段识别标识符时吞掉了后面的数字。parseIdentifier函数没有在遇到非字母数字字符时及时停止。检查读取字符的循环条件确保在Character.isLetterOrDigit()为 false 时跳出。字符串字面量处理出错转义字符\n被当成两个字符。没有实现转义字符的逻辑。在parseString函数中当读到反斜杠\时预读下一个字符根据转义映射表如\n - 换行符进行转换。递归下降/LL(1)阶段陷入无限递归。文法存在左递归未消除。检查文法使用标准方法如引入新的非终结符消除直接和间接左递归。预测分析时选择错误产生式。FIRST/FOLLOW集计算错误或文法不是LL(1)。1. 打印并仔细核对每个非终结符的FIRST和FOLLOW集。2. 检查预测分析表是否有冲突项。如有可能需要改写文法。算符优先阶段对表达式a b * c归约顺序错误。算符优先关系表定义错误*的优先级未高于。重新检查并修正优先关系表确保符合算术规则。遇到括号匹配错误。在优先关系表中(和)的关系未正确定义或栈内(的特殊优先级处理不当。确保(在栈外时优先级最低在栈内时优先级特殊(和)相遇时是“”关系并脱括号。SLR(1)阶段构造项目集规范族时程序死循环。Closure或Goto函数实现有误导致不断生成“新”的等价状态。1. 检查项目相等性的判断逻辑比较核心项目和闭包项目。2. 在生成新状态时打印其内容与已有状态对比。分析表出现“移进-归约”冲突。文法不是SLR(1)的。FOLLOW集可能无法解决冲突。1. 分析冲突状态和符号理解冲突原因。2. 尝试修改文法例如引入新的非终结符来推迟归约。3. 高级考虑实现LR(1)或LALR(1)分析器。分析过程在某个状态报“未定义动作”。ACTION/GOTO表构造不完整存在空白项。检查构造表的算法逻辑确保对所有状态和所有终结符/非终结符都进行了处理。特别是GOTO表要对所有非终结符进行填写。语法制导翻译阶段生成的中间代码中临时变量数目爆炸。每次运算都生成新临时变量没有复用。实现简单的临时变量管理策略例如在一个基本块内如果一个临时变量的值不再被使用可以复用其名字。属性栈与符号栈不同步。在移进或归约时属性栈的压入弹出操作有遗漏或错误。在每一步分析动作后打印两个栈的内容进行比对确保它们的高度和对应关系始终一致。符号表查找失败。1. 标识符未声明就使用。2. 作用域处理错误本实验通常只有全局作用域。1. 在表达式中遇到标识符时先在符号表中查找若未找到则报“未定义变量”错误。2. 确保在声明语句中正确将标识符插入符号表。4.3 性能优化与扩展思考虽然这是一个教学项目但思考如何优化和扩展它能极大提升你的工程能力。文法抽象与解析当前文法是硬编码在代码里或读自文件。可以设计一个更通用的文法描述语言类似Yacc的规格说明并编写一个“分析器的分析器”来读取它自动构造分析表。这会让你的项目变成一个“编译器生成器”的雏形。错误恢复机制目前的错误处理大多是遇到第一个错误就停止。可以实现简单的错误恢复策略如恐慌模式跳过一些Token直到同步词法单元或短语层恢复插入/删除Token使分析器能报告更多错误。更丰富的中间表示除了三地址码可以实现抽象语法树AST。AST能保留更多的结构信息对于后续的优化非常有利。可以在递归下降分析器中直接构建AST。面向更复杂的语言特性尝试支持数组、结构体、函数调用等更复杂的语法和语义。这会极大地挑战你的符号表设计需要支持类型系统、作用域嵌套和中间代码生成能力如数组地址计算、函数调用规约。完成这六个实验你收获的远不止是几份能运行的代码。你获得的是对编译器前端工作流程的肌肉记忆级理解是对复杂算法如集合闭包、表构造的工程化实现能力以及面对一个庞大系统时如何分模块设计、编码、调试和集成的完整经验。这份源码集合正是这段充满挑战又收获颇丰的学习旅程的最佳见证。希望我的拆解和分享能帮助你更好地理解它并在此基础上构建出属于你自己的、更强大的编译工具。本文还有配套的精品资源点击获取
简介本资源是北京交通大学《编译原理》课程配套的完整实验源码集合面向计算机科学与技术专业本科生及编译器开发初学者系统覆盖编译器前端六大核心环节词法分析、递归下降语法分析、LL(1)文法分析、算符优先文法分析、基于SLR(1)的语法制导翻译、中间代码生成。压缩包共94个文件含33个C源文件cpp实现核心算法逻辑、29个头文件h封装数据结构与接口、21个文本文件txt提供测试用例与文法定义、6个Makefile支持一键编译另有README.md和说明文档辅助理解整体架构。资源仅66KB轻量精炼目录按Lab01–Lab06清晰划分六大实验模块每个模块均含可运行示例、测试输入与预期输出便于逐层验证与调试。目前已有88人学习下载是深入理解编译流程、掌握语法分析表构建、语义动作嵌入及三地址码生成等关键技术的高质量实践材料。1. 项目概述从课程实验到编译器前端的完整拼图最近在整理过往的学习资料时翻出了一个压箱底的“宝藏”——我在北京交通大学攻读计算机专业期间完成的《编译原理》课程全套实验项目的完整源码集合。这个压缩包可以说是我学生时代在系统软件领域投入心血最多的结晶。它不是一个玩具而是一个严格按照课程要求从零开始逐步构建出一个具备完整前端功能的编译器的实践记录。里面包含了从最基础的词法分析到递归下降、LL(1)、算符优先、SLR(1)等多种语法分析方法的实现最终抵达语法制导翻译和中间代码生成这六个核心实验模块。每一个模块都像是一块拼图单独看是一个精巧的算法实现组合起来则构成了一个编译器前端的完整工作流。对于计算机专业的学生尤其是正在或即将学习编译原理的同学来说编译原理这门课常常被誉为“天书”。它充满了抽象的概念、复杂的算法和严谨的数学理论。课堂上的有限自动机、上下文无关文法、LR分析表听起来都离实际的编程很远。而实验正是打通理论与实践的桥梁。这个源码集合的价值就在于它提供了一个可运行、可调试、可修改的完整参考。你不仅能看懂每一行代码在做什么更能通过运行它直观地看到一个简单的源程序是如何被一步步“肢解”成单词词法分析再根据语法规则组装成树语法分析最后被翻译成一种更接近机器、但独立于具体机器的中间表示中间代码生成。这个过程是理解编译器如何工作的最佳途径。无论你是想预习课程、完成作业、准备考试还是单纯对编译器内部机制感到好奇这个项目都能给你带来实实在在的帮助。它基于Java实现结构清晰注释详尽避免了过于复杂的工程化封装将核心算法逻辑直接呈现在你面前。接下来我将带你深入这个“六合一”的编译器前端实验项目拆解每一个模块的设计思路、实现细节并分享我在实现过程中踩过的坑和总结的经验。2. 项目整体架构与设计哲学2.1 模块化设计六个实验的递进关系这个项目的结构并非随意堆砌而是严格遵循了编译器前端经典的处理流程并对应了课程实验的六个阶段性目标。理解这个递进关系是读懂整个项目的关键。第一层词法分析器Scanner/Lexer这是所有工作的起点。它的任务无比纯粹读入源代码字符串忽略空格、换行、注释等无关内容识别出一个个具有独立意义的“单词”即“词法单元”Token。例如对于语句int a 10 b;词法分析器会输出序列KEYWORD, int、ID, a、OPERATOR, 、INTEGER, 10、OPERATOR, 、ID, b、DELIMITER, ;。它为后续所有分析提供了原材料。在这个项目中词法分析器被设计为一个独立的类提供getNextToken()这样的接口供语法分析器驱动。第二层语法分析器Parser——多种方法的实践这是项目的核心和难点。语法分析器接收词法单元流根据预定义的语法规则通常用BNF范式表示检查其结构是否符合规范并通常构建出一棵“语法分析树”。课程实验的精妙之处在于它要求我们用四种不同的方法来实现语法分析每一种都对应着编译原理理论中的一个重要流派递归下降分析法最直观的方法。为语法规则的每一个非终结符编写一个递归函数。这种方法手工编写方便特别适合表达式、控制语句等结构但它要求文法必须是LL(1)的且左递归必须消除。LL(1)分析法一种表驱动的自顶向下分析方法。需要预先计算FIRST集和FOLLOW集并构造LL(1)预测分析表。分析器根据当前栈顶符号和输入符号查表决定使用哪条产生式。它比递归下降更形式化是理解自顶向下分析自动化的关键。算符优先分析法专门为表达式语法设计的一种简单、高效的自底向上分析方法。它不严格基于语法树而是通过比较相邻运算符的优先级来决定归约顺序适合快速处理表达式但文法适用范围窄。SLR(1)分析法一种自底向上的、能力更强的LR分析方法。需要构造项目集规范族和SLR(1)分析表。它能处理更广泛的文法是实践中许多编译器生成器如Yacc的理论基础。实现SLR(1)分析器是对LR分析理论最深入的实践。第三层语法制导翻译与中间代码生成这是语法分析的升华。我们不再仅仅满足于检查语法是否正确还要赋予语法结构以“语义”。语法制导翻译将“属性”如类型、值、代码地址与文法符号关联并在语法分析过程中通过嵌入在递归函数或分析动作中的代码计算这些属性。最终产出不再是树而是一种中间表示常见的有三地址码如t1 10 b,a t1或抽象语法树的某种线性化形式。这个模块将前端分析与后端优化、代码生成连接起来。2.2 技术选型为什么是Java你可能会问经典的编译原理教材多用C工业级的编译器多用C或Rust为什么这个项目选择Java这背后有几点非常实际的考量教学友好性Java语言本身相对简洁内存管理自动化让学生能将精力集中于算法逻辑本身而不是指针、内存泄漏等底层细节。其丰富的标准库尤其是集合框架ArrayList,HashMap非常适合实现符号表、分析表等数据结构。快速原型能力Java的面向对象特性让模块化设计变得自然。我们可以轻松地定义Token、Production、LRItem等类并通过继承和多态来管理不同的分析器。编写和调试效率高。跨平台与可交付性“一次编写到处运行”的特性使得这份代码可以在任何装有JVM的机器上编译运行极大方便了同学之间的交流、以及老师的统一评测。最终打包成一个清晰的、包含所有依赖的工程如Maven或Gradle项目交付体验非常好。与课程理论的契合度编译原理中的很多概念如状态集合、表驱动用Java的集合类来实现非常直观。构造LR(0)项目集规范族时对项目集合的哈希去重、比较等操作用Java写起来比C流畅得多。注意选择Java并不意味着牺牲性能或深度。这个项目的目标是教学与实践而非打造产品级编译器。用Java清晰地实现出LL(1)或SLR(1)分析表的构造算法其教育意义远大于用C写一个模糊难懂的版本。事实上许多现代语言的处理工具如Antlr也是用Java编写的。2.3 代码结构导览项目的目录结构大致如下体现了清晰的模块分离思想compiler-frontend-experiments/ ├── src/ │ ├── lexer/ # 词法分析模块 │ │ ├── Token.java # 词法单元类类型值行号 │ │ ├── TokenType.java # 词法单元类型枚举INT, ID, PLUS等 │ │ └── Lexer.java # 词法分析器核心类 │ ├── parser/ # 语法分析模块 │ │ ├── rd/ # 递归下降分析器 │ │ ├── ll1/ # LL(1)分析器含FIRST/FOLLOW集计算 │ │ ├── op/ # 算符优先分析器 │ │ └── slr/ # SLR(1)分析器含项目集、ACTION/GOTO表构造 │ ├── grammar/ # 文法定义相关 │ │ ├── Production.java # 产生式类 │ │ └── Grammar.java # 文法管理类从文件读取计算闭包等 │ ├── symbol/ # 符号表管理 │ │ └── SymbolTable.java │ ├── sdts/ # 语法制导翻译与中间代码生成 │ │ ├── Attribute.java # 属性类 │ │ ├── Quadruple.java # 四元式中间代码表示 │ │ └── SDTVisitor.java # 基于访问者模式的语法制导翻译器 │ └── main/ # 主程序入口用于测试各个模块 │ └── CompilerFrontendDemo.java ├── grammars/ # 存放不同分析器测试用的文法文件 │ ├── expression_grammar.txt │ └── slr_grammar.txt ├── test_cases/ # 测试用例正确的和错误的 │ ├── source_code.simple │ └── ... └── README.md # 项目说明构建与运行指南这种结构保证了每个实验模块的独立性你可以单独运行词法分析器看输出也可以单独测试SLR(1)分析器更可以串联起整个流程。3. 核心模块深度解析与实现要点3.1 词法分析器编译器视角下的“分词工具”词法分析器是编译器的“眼睛”。它的实现看似简单但健壮性要求极高。核心是有限自动机DFA的思想。我们并没有显式地画出状态转换图而是在代码中用条件分支逻辑隐式地实现了一个DFA。实现核心Lexer.java中的getNextToken()方法这个方法是一个大的循环每次调用都从输入流中读取字符直到识别出一个完整的Token。public Token getNextToken() { // 跳过空白字符空格、制表符、换行 skipWhitespace(); if (pos source.length()) { return new Token(TokenType.EOF, , line); } char currentChar source.charAt(pos); // 识别标识符和关键字以字母或下划线开头 if (Character.isLetter(currentChar) || currentChar _) { return parseIdentifierOrKeyword(); } // 识别数字字面量 else if (Character.isDigit(currentChar)) { return parseNumber(); } // 识别运算符和分隔符 else if (isOperator(currentChar)) { return parseOperator(); } // 识别字符串字面量 else if (currentChar \) { return parseString(); } // 处理注释 else if (currentChar / peekNextChar() /) { skipSingleLineComment(); return getNextToken(); // 递归调用跳过注释后继续识别 } // ... 其他情况处理 }parseIdentifierOrKeyword函数会持续读入字母数字形成一个字符串然后去关键字表中查找。这里的关键是关键字表的组织。我使用了一个HashSetString来存储所有关键字识别出标识符后用keywords.contains(word)来判断是否是关键字。这种方式比一堆if-else判断高效且易于维护。实操心得与避坑指南行号与列号的维护为了在报错时能精确定位必须在读字符的过程中仔细维护行号和列号。每次遇到\n行号加1列号重置。这个细节很容易出错特别是在处理跨多行的注释或字符串时。向前看字符Lookahead的必要性像、、!这样的双字符运算符以及/*注释的开始都需要预读下一个字符才能确定。peekNextChar()方法只看不移动指针在这里至关重要。错误恢复策略简单的词法分析器在遇到无法识别的字符如、$时可能直接抛出异常终止。一个更健壮的实现应该记录错误“非法字符”然后跳过该字符尝试继续分析下一个可能的Token这样能一次报告所有词法错误。字符串和字符字面量的处理要正确处理转义字符如\n、\t、\。这需要一个小型的转义字符映射表。3.2 递归下降语法分析最直观的“手工”解析递归下降分析法将文法规则直接映射为代码中的递归函数调用非常符合人类的直觉。例如对于一个简单的算术表达式文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id | num我们可以编写如下函数伪代码void parseE() { parseT(); parseEPrime(); } void parseEPrime() { if (currentToken.type PLUS) { match(PLUS); // 消耗掉‘’ parseT(); parseEPrime(); } // 否则对应 ε什么都不做 } void match(TokenType expected) { if (currentToken.type expected) { currentToken lexer.getNextToken(); } else { throw new SyntaxError(Expected expected , but found currentToken.type); } }实现要点消除左递归上述文法是已经消除了左递归的。原始文法E - E T会导致函数parseE()无限递归调用自身。必须先将文法转换为等价的非左递归形式这是使用递归下降的前提。处理 ε 产生式对应函数中的空分支通常通过判断当前Token是否在某个集合如FOLLOW集中来决定是否选择该分支。回溯问题纯递归下降在遇到不确定选择时可能需要回溯效率低。因此我们通常使用预测性递归下降即通过查看当前Token的FIRST集来唯一确定使用哪条产生式这就要求文法是LL(1)的。踩坑记录我曾在一个if-else语句的文法上栽过跟头。文法规则是Stmt - if ( Expr ) Stmt else Stmt | ...。在解析if (x0) if (y0) a1; else b1;时else应该匹配第二个if还是第一个if这就是经典的“悬空else”问题。纯递归下降会将其匹配到最近的if这符合大多数语言的语义但需要在设计文法时就意识到这一点。我的经验是为这种有歧义的结构编写递归下降函数时要特别小心函数返回的时机和else的匹配逻辑。3.3 LL(1)分析法从手工到自动化的桥梁LL(1)分析将递归下降的“预测”过程表格化、自动化。实现一个LL(1)分析器分为两个主要阶段分析表构造和表驱动分析。第一阶段计算FIRST集和FOLLOW集这是整个LL(1)分析中最容易出错的理论计算部分必须通过代码精确实现。FIRST(α)串α能推导出的开头终结符集合。计算时需递归处理特别是当非终结符能推出ε时需要继续看后面的符号。FOLLOW(A)紧跟非终结符A后面出现的终结符集合。计算时需要遍历所有产生式寻找A的出现位置并考虑其后的串的FIRST集如果后面的串能推出ε还要并入产生式左部符号的FOLLOW集。我在LL1TableBuilder类中实现了这两个集合的计算。算法本质上是图上的不动点迭代反复应用规则直到所有集合不再变化。这里一定要用while循环配合一个changed标志确保计算到收敛。第二阶段构造预测分析表规则是对每条产生式A - α将(A, a)对应的表项填入A - α其中终结符a属于FIRST(α)如果ε在FIRST(α)中则对FOLLOW(A)中的每个终结符b也将(A, b)填入A - α。 构造完成后必须检查每个表项是否最多只有一个产生式否则文法就不是LL(1)的。第三阶段表驱动分析使用一个分析栈。初始时栈底为$栈顶为文法开始符号。根据栈顶符号X和当前输入符号a若X a $分析成功。若X是终结符且X a弹出X消耗输入a。若X是非终结符查表M[X, a]。如果为空报错否则将表项中的产生式右部符号逆序压入栈中保证最左推导。// 简化版分析循环 while (!stack.isEmpty()) { Symbol top stack.peek(); Token current inputToken; if (top.isTerminal()) { if (top.equals(current.type)) { stack.pop(); advanceInput(); } else { error(); } } else { Production prod parsingTable.get(top, current.type); if (prod null) { error(); } else { stack.pop(); // 将产生式右部逆序压栈 for (int i prod.rhs.size() - 1; i 0; i--) { if (!prod.rhs.get(i).isEpsilon()) { // 不压入 ε stack.push(prod.rhs.get(i)); } } } } }提示调试LL(1)分析器时最有效的方法是打印出每一步的分析栈、剩余输入和将要执行的动作。这能帮你清晰地看到推导过程快速定位是FIRST/FOLLOW集算错了还是分析表填错了。3.4 算符优先分析法快速处理表达式的利器算符优先分析跳出了严格的语法树框架它不关心完整的语法结构只关注运算符之间的优先级关系。它需要两张表优先关系表,,。核心思想比较栈顶运算符θ1和当前输入运算符θ2的优先关系。若θ1 θ2θ2入栈移进。若θ1 θ2通常只有括号配对时出现脱括号弹出。若θ1 θ2进行归约在栈顶寻找一个最左的形如非终结符 运算符 非终结符的序列将其归约为一个非终结符。实现难点优先关系的确定优先关系不是任意的需要根据文法推导。对于简单的表达式文法我们可以手动定义。例如对于、-、*、/、(、)通常定义、-优先级低于*、/。相同优先级的运算符左结合。(的优先级低于所有运算符但在栈内时(的优先级极低遇到)时需要找到匹配的(。 在我的实现中我使用了一个二维枚举数组Relation[][]来存储这个关系表。实操过程分析器维护一个符号栈。栈中交替存放着操作数和运算符实际上为了简化我们只存运算符和作为分隔符的非终结符操作数由另一个值栈管理。算法流程是一个经典的移进-归约循环但归约动作不是基于产生式而是基于“可归约串”的模式匹配。while (输入未结束) { a 当前输入符号; if (栈顶是操作数 a 是操作数) { 错误 // 不允许两个操作数相邻 } if (栈顶是终结符 θ) { 关系 优先关系表[θ][a]; if (关系 LESS) { // θ a 移进 a; } else if (关系 GREATER) { // θ a 进行归约; // 归约后栈顶变为一个非终结符N // 此时需要比较新的栈顶符号可能是运算符和 a 的关系 } else if (关系 EQUAL) { // 通常是 ( ) 脱括号弹出 (); 消耗输入 ); } else { 错误 // 优先关系未定义语法错误 } } else { // 栈顶是非终结符将其视为一个整体操作数直接移进输入符号a 移进 a; } }算符优先分析速度快但能力有限无法处理复杂的非运算符语法结构。它是我在项目中实现的“特化工具”专门用于演示如何高效处理表达式。3.5 SLR(1)分析法自底向上分析的经典实践SLR(1)是LR分析家族中相对简单但能力足够强的一种。实现一个SLR(1)分析器是编译原理实验的“毕业设计”它综合了DFA构造、集合运算和表驱动分析。第一步构造LR(0)项目集规范族这是最复杂的一步。一个LR(0)项目形如A - α·β圆点表示分析进度。我们从初始项目S - ·S开始通过计算闭包Closure和读符号转移Goto函数逐步构造出所有的状态项目集。闭包操作如果项目是A - α·Bβ那么对于B的所有产生式B - γ要把B - ·γ加入闭包。这是一个递归过程。Goto操作对于状态I和文法符号XGoto(I, X)是所有形如[A - αX·β]的项目的集合其中[A - α·Xβ]在I中。然后再对这个集合求闭包。我使用了一个ListLR0State来存储所有状态并用一个MapPairLR0State, Symbol, LR0State来记录Goto关系。为了避免生成重复状态每次生成新状态时都要与已有状态比较项目集是否相等。第二步构造SLR(1)分析表对于每个状态i移进动作ACTION[i, a] sj如果项目[A - α·aβ]在状态i中且a是终结符且Goto(i, a) j则ACTION[i, a] 移进j。归约动作ACTION[i, a] rk如果项目[A - α·]在状态i中则对所有a ∈ FOLLOW(A)ACTION[i, a] 按产生式k归约。这里用到了FOLLOW集来解决冲突这也是SLR(1)中“S”的由来。接受动作如果项目[S - S·]在状态i中则ACTION[i, $] 接受。GOTO表如果Goto(i, X) j且X是非终结符则GOTO[i, X] j。第三步表驱动分析分析器同样使用一个状态栈和一个符号栈。stack.push(initialState); // 状态栈 symbolStack.push(END_MARKER); // 符号栈 Token lookahead lexer.getNextToken(); while (true) { int state stack.peek(); Action action actionTable[state][lookahead.type]; if (action.type SHIFT) { // 移进 stack.push(action.number); // 新状态 symbolStack.push(lookahead); lookahead lexer.getNextToken(); } else if (action.type REDUCE) { // 归约 Production prod productions[action.number]; // 从栈中弹出右部符号及其对应的状态 for (int i 0; i prod.rhs.size(); i) { stack.pop(); symbolStack.pop(); } // 获取归约后的左部符号A Symbol lhs prod.lhs; // 根据归约前的状态和新符号A查找GOTO表得到新状态 int newState gotoTable[stack.peek()][lhs]; // 压入新状态和A stack.push(newState); symbolStack.push(lhs); // 可以在这里执行语义动作生成四元式 executeSemanticAction(prod); } else if (action.type ACCEPT) { // 接受成功 break; } else { // 报错 reportSyntaxError(state, lookahead); // 错误恢复... } }经验之谈调试SLR(1)分析器调试SLR(1)分析器极具挑战性。我的建议是可视化状态机将构造出的LR(0)项目集规范族和Goto关系以图的形式打印出来。这能帮你直观地检查状态是否完整转移是否正确。分步跟踪分析过程像调试LL(1)一样打印每一步的状态栈、符号栈、剩余输入和即将执行的动作。这是定位分析表错误的唯一有效方法。关注归约-归约和移进-归约冲突如果文法不是SLR(1)的构造表时会在同一表项出现多个动作。你需要分析冲突原因是文法有二义性还是需要更强的LR(1)或LALR(1)分析。在实验项目中我们通常通过修改文法来消除冲突。FOLLOW集的计算务必准确SLR(1)利用FOLLOW集来缩小归约动作的适用范围。如果FOLLOW集算大了会导致无效的归约算小了会导致该归约时找不到动作。这是SLR(1)分析器最常见的错误来源之一。3.6 语法制导翻译与中间代码生成赋予语法以意义语法分析只解决了“结构对不对”的问题而语法制导翻译SDT要解决“做什么”的问题。我们选择在SLR(1)分析器进行归约时执行相应的语义动作从而生成中间代码。语义动作的设计我们为每个产生式关联一段语义子程序。这些子程序可以访问和修改与文法符号相关的属性。最常见的属性是综合属性自底向上传递如表达式的值、类型有时也需要继承属性自顶向下传递如变量的声明类型。在这个项目中我们主要实现三地址码的生成。三地址码的基本形式是x y op z。我们用一个Quadruple四元式类来表示包含操作符op、两个操作数arg1、arg2和一个结果result。实现模式在SLR(1)分析器的归约动作中我们根据归约所用的产生式编号调用对应的语义例程。private void executeSemanticAction(int productionIndex) { switch (productionIndex) { case 0: // S - E // E的属性比如它的值存放的临时变量名就是整个S的结果 break; case 1: // E - E T String temp newTemp(); // 生成新的临时变量如t1, t2... String eAddr getAttribute(stack, -3); // 获取E的属性地址 String tAddr getAttribute(stack, -1); // 获取T的属性 emit(new Quadruple(, eAddr, tAddr, temp)); // 生成四元式temp eAddr tAddr setAttribute(stack, -3, temp); // 将新生成的临时变量作为这个E的综合属性 break; case 2: // E - T // 直接传递属性 break; case 3: // T - T * F // 类似加法生成乘法四元式 break; // ... 其他产生式 case 10: // F - id String idName getTokenValue(stack, -1); // 获取标识符的名字 setAttribute(stack, -1, idName); // 属性就是标识符的名字本身 break; } }这里的关键是属性栈的管理。我们需要一个与符号栈平行的属性栈每当符号入栈或出栈时其对应的属性也同步操作。在归约时我们从属性栈中弹出右部符号的属性计算得到左部符号的属性再压入栈中。符号表的管理为了生成正确的代码我们必须知道标识符的类型、存储位置等信息。这就需要符号表。在分析到声明语句如int a;时我们将标识符a及其类型信息插入符号表。在后续表达式中使用a时就从符号表中查找其信息确保使用前已声明静态语义检查并获取其类型以进行可能的类型转换。中间代码的优化简单示例在生成四元式时我们可以进行一些简单的优化。例如对于常量表达式3 5我们可以在语义动作中直接计算出结果8并生成t1 8而不是生成t1 3 5。这称为常量折叠是编译器优化中最基本的一步。4. 项目集成、测试与常见问题排查4.1 如何串联六个模块进行端到端测试单独测试每个模块是基础但真正的成就感来自于将它们串联起来看着一段简单的源代码最终变成一串三地址码。我编写了一个集成测试的主类CompilerFrontendDemo它提供了命令行接口允许用户选择不同的分析器并指定源代码文件。集成流程如下初始化读取文法文件初始化对应的分析器如SLR(1)分析器需要预先构造分析表。词法分析将源代码文件送入词法分析器得到一个Token流。可以在这里选择是否打印Token序列以供调试。语法分析与翻译将Token流送入选定的语法分析器如SLR(1)分析器。该分析器在工作的同时会驱动语法制导翻译模块在归约时生成四元式。输出结果如果源代码语法正确则打印“语法分析成功”并输出生成的三地址码序列。如果中途发现错误则输出详细的错误信息包括错误类型、位置和可能的修正建议。一个典型的测试用例test.simple可能如下int main() { int a, b, c; a 10; b 20; c a b * 2; print(c); }期望的中间代码输出可能类似于t0 10 a t0 t1 20 b t1 t2 2 t3 b * t2 t4 a t3 c t4 param c call print, 14.2 常见编译错误、警告与排查技巧在实现和测试过程中你会遇到各种各样的错误。下面是一个快速排查指南问题现象可能原因排查步骤与解决方案词法分析阶段识别标识符时吞掉了后面的数字。parseIdentifier函数没有在遇到非字母数字字符时及时停止。检查读取字符的循环条件确保在Character.isLetterOrDigit()为 false 时跳出。字符串字面量处理出错转义字符\n被当成两个字符。没有实现转义字符的逻辑。在parseString函数中当读到反斜杠\时预读下一个字符根据转义映射表如\n - 换行符进行转换。递归下降/LL(1)阶段陷入无限递归。文法存在左递归未消除。检查文法使用标准方法如引入新的非终结符消除直接和间接左递归。预测分析时选择错误产生式。FIRST/FOLLOW集计算错误或文法不是LL(1)。1. 打印并仔细核对每个非终结符的FIRST和FOLLOW集。2. 检查预测分析表是否有冲突项。如有可能需要改写文法。算符优先阶段对表达式a b * c归约顺序错误。算符优先关系表定义错误*的优先级未高于。重新检查并修正优先关系表确保符合算术规则。遇到括号匹配错误。在优先关系表中(和)的关系未正确定义或栈内(的特殊优先级处理不当。确保(在栈外时优先级最低在栈内时优先级特殊(和)相遇时是“”关系并脱括号。SLR(1)阶段构造项目集规范族时程序死循环。Closure或Goto函数实现有误导致不断生成“新”的等价状态。1. 检查项目相等性的判断逻辑比较核心项目和闭包项目。2. 在生成新状态时打印其内容与已有状态对比。分析表出现“移进-归约”冲突。文法不是SLR(1)的。FOLLOW集可能无法解决冲突。1. 分析冲突状态和符号理解冲突原因。2. 尝试修改文法例如引入新的非终结符来推迟归约。3. 高级考虑实现LR(1)或LALR(1)分析器。分析过程在某个状态报“未定义动作”。ACTION/GOTO表构造不完整存在空白项。检查构造表的算法逻辑确保对所有状态和所有终结符/非终结符都进行了处理。特别是GOTO表要对所有非终结符进行填写。语法制导翻译阶段生成的中间代码中临时变量数目爆炸。每次运算都生成新临时变量没有复用。实现简单的临时变量管理策略例如在一个基本块内如果一个临时变量的值不再被使用可以复用其名字。属性栈与符号栈不同步。在移进或归约时属性栈的压入弹出操作有遗漏或错误。在每一步分析动作后打印两个栈的内容进行比对确保它们的高度和对应关系始终一致。符号表查找失败。1. 标识符未声明就使用。2. 作用域处理错误本实验通常只有全局作用域。1. 在表达式中遇到标识符时先在符号表中查找若未找到则报“未定义变量”错误。2. 确保在声明语句中正确将标识符插入符号表。4.3 性能优化与扩展思考虽然这是一个教学项目但思考如何优化和扩展它能极大提升你的工程能力。文法抽象与解析当前文法是硬编码在代码里或读自文件。可以设计一个更通用的文法描述语言类似Yacc的规格说明并编写一个“分析器的分析器”来读取它自动构造分析表。这会让你的项目变成一个“编译器生成器”的雏形。错误恢复机制目前的错误处理大多是遇到第一个错误就停止。可以实现简单的错误恢复策略如恐慌模式跳过一些Token直到同步词法单元或短语层恢复插入/删除Token使分析器能报告更多错误。更丰富的中间表示除了三地址码可以实现抽象语法树AST。AST能保留更多的结构信息对于后续的优化非常有利。可以在递归下降分析器中直接构建AST。面向更复杂的语言特性尝试支持数组、结构体、函数调用等更复杂的语法和语义。这会极大地挑战你的符号表设计需要支持类型系统、作用域嵌套和中间代码生成能力如数组地址计算、函数调用规约。完成这六个实验你收获的远不止是几份能运行的代码。你获得的是对编译器前端工作流程的肌肉记忆级理解是对复杂算法如集合闭包、表构造的工程化实现能力以及面对一个庞大系统时如何分模块设计、编码、调试和集成的完整经验。这份源码集合正是这段充满挑战又收获颇丰的学习旅程的最佳见证。希望我的拆解和分享能帮助你更好地理解它并在此基础上构建出属于你自己的、更强大的编译工具。本文还有配套的精品资源点击获取
