简介面向编译原理课程设计与实验这套电子科技大学实验代码完整覆盖词法分析器与语法分析器两大核心模块整体按输入处理、词法分析、语法分析等层次组织便于理解编译器前端的完整流程。压缩包共21个文件包含5个C源文件、4个头文件、2个Pascal源文件以及docx运行说明文档、exe可执行程序和vcxproj/sln/pro等工程配置整体仅203KB结构精简。已有2112人下载学习适合计算机专业学生作为编译器实现的参考样例。代码中词法分析器基于有限状态自动机识别关键字、标识符、常量与运算符语法分析器在此基础上自底向上或自顶向下解析token流并构造抽象语法树运行说明文档对环境配置与预期结果做了细致说明配合可执行程序可快速验证结果有助于掌握编译前端的关键流程与排错思路也能作为课程报告或毕业设计的参考资料。1. 为什么很多人卡在编译原理实验不是算法难是三个阶段的接口对不齐电子科技大学编译原理实验代码这套资源核心价值不在于某一个算法写得有多炫而是把词法分析、语法分析、语义分析与中间代码生成串成了一条能跑通的完整流水线。每个阶段的输入输出都留好了接口token流怎么进语法分析器、语法树怎么喂给语义检查、四元式怎么落盘全部对得上。很多同学写实验最大的痛苦在于词法分析输出的token流有问题语法分析根本没法查错语法树建得不对语义分析只能干瞪眼。这份代码正好把这种断层补上了适合正在写编译原理实验、需要一份参考实现来对照调试的人也适合想看看真实实验代码怎么组织模块的同学。有了它你的目标很明确看懂接口约定跑通全流程然后改造成自己的实现。2. 实验代码的整体结构从源文件到四元式的编译流水线拆解2.1 三个阶段的模块划分与教材章节的对应关系拿到实验代码先别急着跑把目录结构看明白比写第一行代码更重要。常见实现里模块按词法分析、语法分析、语义分析与中间代码生成三块独立划分对应编译原理教材的前几章。词法分析器接收源文件字符流输出token流语法分析器接收token流输出语法树语义分析器遍历语法树一边做类型检查一边生成四元式。src/ lexer/ Lexer.java // 词法分析器入口 Token.java // token定义 TokenType.java // token类型枚举 parser/ Parser.java // 递归下降或LR驱动入口 ASTNode.java // 语法树节点 sema/ SymbolTable.java // 符号表 TypeChecker.java // 语义检查与四元式生成 main/ Main.java // 命令行入口 test/ case1.txt // 测试用例 case2.txt代码结构严格按照编译流程分层每层只依赖前一层的输出数据结构。词法分析器不知道语法分析器怎么处理token语法分析器也不知道语义分析器怎么用语法树。这种分层的好处是你可以单独替换某个模块而不影响其他模块——把词法分析从手写改成用自动生成器或者把语法分析从LL(1)改成LR(1)接口不变其他模块都不用动。我见过不少同学为了省事把词法和语法写在一个文件里到后面才发现token类型、行号信息、位置信息全部耦合在一起改一个实验牵一发而动全身。这份代码的模块边界就是教科书上的阶段划分照着分层写后患少很多。中间代码生成环节四元式的结构放在Quad.java里和符号表、临时变量编号管理分开语义检查只负责产出四元式序列不做代码优化边界清楚。2.2 token流、语法树和四元式之间的数据契约三个实验之间的接口是数据结构和数据结构之间的约定不是函数调用那么简单。词法分析器吐出的每个token至少要有类型、字面量、行号和列号四个字段语法分析器拿到token流后按文法归约出语法树语义分析器遍历语法树时需要掌握每个节点的类型信息这依赖符号表。public class Token { public TokenType type; // 关键字、标识符、数字、运算符、分隔符 public String lexeme; // 原始字面量比如int或123 public int line; // 行号报错和调试都靠它 public int column; // 列号精度到字符位置 } public class Quad { public String op; // 操作符比如、-、、jmp public String arg1; // 第一个操作数可能是变量名或临时变量 public String arg2; // 第二个操作数可能为空 public String result; // 结果存到变量或临时变量里 }Token类里的line和column不是可有可无的装饰字段它是整个错误报告机制的地基。语法分析器在报语法错误时如果没有token的位置信息只能告诉你“语法错误”没法告诉你错在第几行第几列语义分析器报类型错误也一样。四元式的op字段不只是运算符还包括跳转指令比如jmp、jz、jnz跳转目标用result字段存标号。临时变量用t1、t2这样递增的编号这要求语义分析器里有一个临时变量计数器每次生成新临时变量就自增。最关键的是四元式序列不依赖具体目标机器它只是中间表示。你之后要生成汇编代码可以直接把这个四元式序列翻译成目标代码不生成的话实验验收打印四元式序列也足够展示结果。理解了这几个数据结构的字段含义再读代码基本不会迷路。2.3 构建与命令行约定实验环境区分度挺大有的机房是JDK 8有的是JDK 11还有用C的。使用这份代码先确认你的环境能编译再跑测试用例。以Java版本为主编译器用javac入口类在main.Main命令行传参指定源文件和输出文件。javac -d out src/main/Main.java src/lexer/*.java src/parser/*.java src/sema/*.java java -cp out main.Main test/case1.txt output.txt第一个命令把所有Java源文件编译到out目录第二个命令运行入口类从test目录读取源文件把四元式输出写到output.txt。命令行参数定义得直接第一个参数是输入源文件路径第二个参数是输出文件路径。如果只传一个参数默认把结果打到标准输出方便快速调试。这里有一个常见的坑不同版本的JDK对源码的语法要求不同比如JDK 8不支持var推断JDK 11支持另外如果代码用了Files.readString这类新APIJDK 11以下会直接报NoSuchMethodError。我一般建议先编译TokenType.java和Token.java这两个底层的类确认基础环境没问题再编译整棵树。构建时不需要额外依赖第三方库整个项目是纯JDK实现的——这一点在教室环境很重要机房机器没网配Maven或Gradle反而麻烦。3. 词法分析实验状态转换图代码化与关键字表设计3.1 手写DFA还是正则表达式库实验语境下的选型词法分析器的实现有两条路一条是教材里讲的根据正则表达式构造NFA再转DFA最后用状态转换表驱动另一条是直接用正则表达式库比如Java里的Pattern类每个token类型写一个正则。实验场景下我的建议是手写手写状态机而不是用正则库。原因有三条。第一编译原理实验的目的是理解DFA工作原理正则库把底层细节全封装了你写完代码还是不懂状态转换是怎么回事。第二正则库写长token类型时比如识别带下划线的标识符、十六进制数字、字符串字面量里的转义字符表达式会变得又长又难调运行时的性能也是线上的问题。第三手写DFA的错误恢复更好控制——遇到非法字符时你可以精确知道当前状态和下一个字符从而报出“第几行第几列出现了非法字符”正则库遇到不匹配的情况只能返回“整体不匹配”定位不到具体位置。手写DFA的写法也比较固定用一个状态变量记录当前状态逐个字符读取并依据状态转换表跳转每次进入终态就切分出一个token。状态转换表可以是二维数组也可以是一组switch分支。二维数组适合状态多、字符类型多的场景switch分支适合状态少的小实验。常见做法是两种混着用核心状态跳转用switch状态和字符类型的映射用枚举。3.2 关键字、标识符、数字和运算符的识别代码下面这段代码是词法分析器的核心循环实现了关键字与标识符识别、整数与浮点数识别、运算符识别以及空白与注释跳过。这是一个能直接编译运行的骨架版你可以在此基础上加自己的token类型。public class Lexer { private final String src; // 源程序文本 private int pos 0; // 当前读取位置 private int line 1, column 1; // 行列号从1开始 // 关键字集合查到这个字符串就判定为关键字 private static final SetString KEYWORDS Set.of( int, float, if, else, while, return ); public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos src.length()) { char c src.charAt(pos); if (Character.isWhitespace(c)) { // 跳过空白 if (c \n) { line; column 1; } else { column; } pos; } else if (Character.isLetter(c) || c _) { tokens.add(readIdentifier()); // 标识符或关键字 } else if (Character.isDigit(c)) { tokens.add(readNumber()); // 数字常量 } else if (c /) { tokens.add(readOperatorOrComment()); // 除法或注释 } else { tokens.add(readOperator()); // 其他运算符 } } tokens.add(new Token(TokenType.EOF, , line, column)); return tokens; } private Token readIdentifier() { int start pos, startLine line, startCol column; while (pos src.length() (Character.isLetterOrDigit(src.charAt(pos)) || src.charAt(pos) _)) { pos; column; } String text src.substring(start, pos); TokenType type KEYWORDS.contains(text) ? TokenType.KEYWORD : TokenType.IDENTIFIER; return new Token(type, text, startLine, startCol); } private Token readNumber() { int start pos, startLine line, startCol column; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; column; } // 小数部分如果下一个字符是.且后面跟的是数字继续识别 if (pos 1 src.length() src.charAt(pos) . Character.isDigit(src.charAt(pos 1))) { pos; column; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; column; } return new Token(TokenType.FLOAT, src.substring(start, pos), startLine, startCol); } return new Token(TokenType.INTEGER, src.substring(start, pos), startLine, startCol); } private Token readOperatorOrComment() { /* 略 */ } private Token readOperator() { /* 略 */ } }这段代码的逻辑说明tokenize方法里用一个主循环每轮根据当前字符的类型分发到不同的读取子程序。readIdentifier从第一个字母或下划线开始尽可能多地吞掉字母、数字和下划线然后查关键字表判断是关键字还是普通标识符。readNumber先吞掉所有数字再看下一个字符是不是小数点且小数后面有数字——这里用pos 1 src.length()做边界检查避免读取越界。判断顺序有讲究必须先判断isLetter再判断isDigit因为下划线被算作letter的一部分。上面代码里几个参数值得留意KEYWORDS用Set.of声明查找操作是常数时间如果你要支持更多关键字直接往里加字符串即可不需要改动判断逻辑。行列号在每次读取字符时手动维护readIdentifier里在循环体自增column在遇到换行时tokenize主循环会重置column为1。这个看似不起眼的细节在你后续写语法分析报错时会起到决定性作用。另外数字识别处的注释处理属于简化版——实际的数值常量还可能涉及八进制、十六进制、科学计数法实验要求如果没提不要自己提前加加多了一旦有歧义反而难调。3.3 注释跳过与非法字符恢复的实操处理注释处理是词法分析最容易翻车的地方。代码里如果只有//风格的单行注释处理简单读到两个斜杠后一直读到行尾即结束。如果要支持/* ... */块注释就得处理跨行注释这时行号维护就要小心。核心逻辑是读到/后看下一个字符是不是*是则进入注释状态不断往后读直到遇到*/中间如果碰到换行line加一特别注意*/之间不能有其他字符隔开。非法字符的处理策略有两种一种是一遇到非法字符就报错退出适合验收严格的实验另一种是在词法层跳过非法字符并打印警告继续分析后续内容适合你想多拿几个正确token的调试场景。我倾向第二种因为编译实验的测试用例通常是一批正确程序加一批带错误的程序你希望一个错误只报一条错误而不是因为第一个非法字符直接把整个程序拒掉。词法分析器扫描到无法识别的字符记下行列号打印Lexical error: illegal character # at line 3然后跳过这个字符继续扫描这样后面如果还有真正的语法错误也能一起发现。文件结束符的处理也值得一说。token流末尾必须放一个TokenType.EOF的token而不是让token流直接结束。原因很简单语法分析器的递归下降函数或LR分析表都依赖一个明确的结束标记来决定“分析成功”。如果不放EOF token语法分析器会在读完整段token后无所适从要么越界要么当作错误处理。代码里最后一行tokens.add(new Token(TokenType.EOF, , line, column))就是为了这个。4. 语法分析实验LR(1)表驱动与递归下降的取舍4.1 从文法形式出发选择分析算法语法分析器的实现方案主要取决于实验要求的文法类型。教材里经典的表达式文法通常写成E - E T | T的形式这是左递归文法递归下降不能用必须先消除左递归。而LR(1)分析表可以天然处理左递归文法。做选择时问自己三个问题文法是自己设计的还是给定的语法树生成是必须的还是可选加分希望语法树的节点类型能直接对应AST还是只要判定输入是否合法对比项递归下降分析LR(1)表驱动左递归文法需要手工消除左递归天然支持语法树构建在递归函数返回时自底向上构造在规约动作里构造错误定位直观知道当前在哪个非终结符依赖栈顶状态和符号定位稍难调试难度较易可以打印调用路径较难分析表是黑匣子代码量较小直接对应文法产生式需要加载分析表代码量中等实验代码里通常两种都有建议你至少读懂递归下降版因为它的数据结构更直观改起来不用每次重新查表。LR(1)版适合验收时作为对照——同一份输入文件两个版本输出一样的四元式序列说明你的语义动作实现是一致的。如果实验指导书明确要求用LR分析器那就直接做题驱动版别逆着题目要求来。4.2 手写递归下降解析器表达式优先级与左递归消除递归下降的本质是对每个非终结符写一个函数函数内部按产生式右端匹配token。优先级靠函数之间的嵌套调用来体现——越优先级的非终结符被越下层的函数处理。表达式文法E - E T | T存在左递归直接写会死循环所以要改写为等价的E - T EE - T E | ε。class Parser { private ListToken tokens; private int idx 0; // E - T E ASTNode parseE() { ASTNode left parseT(); // 先解析第一个项 return parseEPrime(left); // 处理后续的或-运算 } // E - T E | - T E | ε ASTNode parseEPrime(ASTNode left) { if (match(TokenType.PLUS) || match(TokenType.MINUS)) { String op previous().lexeme; ASTNode right parseT(); // 解析右操作数 ASTNode node new ASTNode(op, left, right); // 构造二元运算节点 return parseEPrime(node); // 继续解析左结合通过递归实现 } return left; // ε产生式直接返回 } // T - F T同E的模式 ASTNode parseT() { /* 类似实现 */ } private boolean match(TokenType type) { if (tokens.get(idx).type type) { idx; return true; } return false; } }这段代码体现了递归下降两个关键点。第一左递归消除后的parseEPrime用一个left参数累积已经解析出来的左操作数当它匹配到或-时把左操作数和右操作数拼成新节点再递归往下。这样做能正确处理左结合——1 - 2 - 3会被解析为(1 - 2) - 3而不是1 - (2 - 3)。第二ASTNode的构造函数接收运算符和左右子树节点字段里的op直接复用token的lexeme这样后面语义分析做四元式生成时读node.op就能决定发出一条add、sub还是mul指令。递归函数里判据match使用向前看一个token的策略不匹配就返回false外层判断当前token是不是或-。你要知道这种实现有一个取舍产生式选择全靠函数调用顺序不支持任意向前看多个token。文法比较复杂时会有性能坑但实验语言的文法固定且简单这在合理范围内。4.3 LR(1)分析器的表驱动核心循环LR(1)实验核心难点是分析表本身怎么加载、怎么驱动。很多实验只要求你给定一个文法然后用自动生成工具产出分析表再把表文件交给一个通用驱动程序。所以在代码层面真正属于你自己的工作是实现下面这个循环void run() { StackInteger stateStack new Stack(); // 状态栈 StackString symbolStack new Stack(); // 符号栈 stateStack.push(0); // 初始状态0 int idx 0; while (true) { int state stateStack.peek(); Token token tokens.get(idx); Action action actionTable[state][token.type.ordinal()]; if (action.type ActionType.SHIFT) { stateStack.push(action.target); symbolStack.push(token.lexeme); idx; } else if (action.type ActionType.REDUCE) { // 按产生式右端长度弹出状态和符号 int popCount action.production.rhsLength; for (int i 0; i popCount; i) { stateStack.pop(); symbolStack.pop(); } String nonTerminal action.production.lhs; int gotoState gotoTable[stateStack.peek()][nonTerminal]; stateStack.push(gotoState); symbolStack.push(nonTerminal); // 这里可以插语义动作归约时构建AST节点或输出四元式 } else if (action.type ActionType.ACCEPT) { break; } else { throw new ParseException(Syntax error at line token.line); } } }分析表驱动循环的逻辑就是一个状态栈维护过程。SHIFT动作表示“把当前输入符号压入符号栈把目标状态压入状态栈”接着读下一个token。REDUCE动作表示“识别出一个产生式右端”操作是弹出右端数量的状态和符号然后根据左端非终结符去查goto表压入对应的状态和左端符号。ACCEPT说明整个输入匹配完毕分析成功。每次执行REDUCE时是插入语义动作的最佳时机——你可以在这里根据产生式的类型构建语法树节点或者直接生成四元式。这张表有一个关键参数actionTable和gotoTable占用了比较大的二维数组空间。一个含有几十个状态、几十个终结符的文法表规模在几千个条目手写不现实通常由一个独立的表生成器产出。你如果拿到的是文本格式分析表要先把它解析成二维数组注意这里的行列索引是乱序的。有两个落地细节可以特别留意一是action表中每格有三种状态SHIFT要记录目标状态REDUCE要记录产生式编号所以Action要设计成带类型和两个可选字段的结构体二是查表时用token.type.ordinal()做列索引要求TokenType枚举顺序和表生成器约定的顺序完全一致否则查出来的表项全是错的而且这种错非常隐蔽不会立即报错只在统计数据对不上时才露馅。5. 语义分析与中间代码生成符号表与四元式避坑实录5.1 符号表作用域覆盖导致后续变量类型全错现象一个代码块里声明了变量int x内层代码块里又声明了float x内层使用x进行浮点运算时语义检查却报了“类型不匹配期望int”。用调试器看符号表发现内层的float x没有覆盖外层的int x查询时总是拿到外层定义。原因符号表实现只有一张全局哈希表插入时直接put(name, type)但退出内层作用域时没有删除内层条目二次查询时命中旧条目。多数实现会在enterScope时用一个列表记录本层所有插入的键退出作用域时按列表删除漏了这一步就会翻车。解决符号表改成链式作用域结构SymbolTable内部维护一个ListMapString, Symbol scopes。lookup从最内层往外逐层查insert只插入当前最内层。退出作用域时scopes.remove(scopes.size() - 1)。这样不需要手动删条目靠作用域链自然隔离。注意每次insert前先查当前作用域是否已存在同名变量存在时按实验要求决定报重复定义错误还是覆盖。5.2 四元式临时变量编号冲突现象生成的四元式里t1一会儿存整数加法的结果一会儿存比较运算的结果后面又出现在跳转指令的目标位置运行时语义完全错乱。更隐蔽的是两段独立运算生成的临时变量编号重复比如两个不相干的子表达式都用了t1。原因临时变量计数器是局部变量每次进入表达式求值函数时初始化为0或者每遇到一个表达式都重置计数导致不同子树生成了同号临时变量。中间代码和教科书里的伪代码不一样它没有“上下文”的概念靠的就是编号唯一性。解决把临时变量计数器做成语义分析器的成员变量从进入分析到结束只自增不自减。每生成一个新临时变量就t t (tempCount)保证全局唯一。跳转标号也同理用一个独立的labelCount每生成一个jmp目标就自增。这属于代码里最简单但要命的那类问题建议每次写完中间代码生成后都跑一段包含多个表达式和控制流的测试程序检查四元式编号是否有断号或重号这是最直接的排查手段。5.3 短路求值被错误翻译成顺序求值现象测试程序if (a ! 0 b / a 1)当a等于0时程序运行时仍然执行了b / a导致整数除法异常。期望是短路求值只要a ! 0为假后边整个表达式不用再算。原因四元式生成时把简单翻译成先求左操作数、再求右操作数、再执行逻辑与没有为短路计算插入跳转指令。真正的编译做法是的左侧生成条件表达式求值如果结果为假直接跳到为整个表达式为假的标号跳过右操作数的求值。解决把和||当作控制流指令来生成而不仅是运算指令。对先在左操作数末尾生成jz T_false右操作数求完后再jmp T_true。对||则反过来——左操作数为真就直接跳真为假才继续求右操作数。需要维护两个标号一个真出口一个假出口表达式树归约时把这两个标号传给子节点。如果验收不要求短路的运行时行为只检查四元式序列这个坑可能看不出来一旦要求解释程序或生成代码运行它必定暴露。5.4 数组维度信息在语义检查阶段丢失现象声明int arr[3][4]后代码里写arr[5]类型检查没有报错。再排查发现符号表里只存了typeARRAY没有存各维度的长度检查下标是否越界时无从查起遇到二维数组的取值语句还要等运行时才知道错。原因数组类型在符号表里的定义过于简略只记了一个数组标记维度数量、每维上下界、元素类型全都没有保存。解决Symbol的类型字段不要用字符串或简单枚举要支持嵌套结构。数组类型至少包含四个字段元素类型、维度数、每维的起始下标与长度。检查下标时先确认下标表达式的类型是整数再比较下标值和当前维度的长度越界就报错。另一个问题是数组整体赋值时类型比较——类型相同的判断要递归比较元素类型和各维度长度不能只看名字是否相同。实验语言里数组类型通常不允许隐式转换类型检查直接比较两个数组类型的结构即可。5.5 词法层错误恢复不当导致语法层连锁报错现象源文件第2行有个非法字符词法分析器直接抛出异常终止结果语法分析器连第3行到第50行的所有错误都检测不到。等词法层修好语法层一次性爆出二十条错误每条都指向同一行。原因词法分析器遇到非法字符就throw new LexException整个程序中断。这个设计看起来很合理但在实验验收阶段不好用因为测试用例可能故意包含多个错误你希望一次跑完看到全部错误而不是修一个重新跑一次。解决词法分析器记住当前非法字符的位置打印一行错误信息然后把它当作普通字符跳过继续分析后面的内容。这样语法分析器至少能处理正确的那部分token后续阶段的错误也能同时上报。在实际调试时词法漏斗会少很多因为你不用为了看真正的语法错误而反复修词法测试文件。为了不刷屏可以限定最大错误数比如报满20条词法错误后就终止防止一个测试文件产生几百行无意义的海量报错。6. 验证方法写一个批测脚本把三个实验串成回归测试三个实验写完最怕的不是代码编译不过而是你改了一句词法分析结果语法分析跟着出问题你加了短路求值结果之前能跑通的测试用例不再产出一模一样的四元式。手动一个个跑测试文件费力又不可靠。我习惯把验证过程自动化准备一个测试目录放上几十个覆盖不同功能的输入程序用一个脚本统一编译、统一执行、统一对比输出。#!/bin/bash # 需要验证的测试用例目录 TEST_DIRtest # 批量编译 javac -d out src/main/*.java src/lexer/*.java src/parser/*.java src/sema/*.java # 逐个跑测试 for f in $TEST_DIR/*.c; do base$(basename $f .c) java -cp out main.Main $f out/$base.ir /dev/null if [ -f expected/$base.ir ]; then if diff -q out/$base.ir expected/$base.ir /dev/null; then echo [PASS] $base else echo [FAIL] $base fi else echo [NO_REF] $base fi done这个脚本的逻辑就是自动化回归。expected目录放着你验收时确认正确的四元式输出脚本把当前跑的生成结果和基准对比diff一致才输出PASS。测试用例要有针对性一组覆盖表达式优先级一组覆盖嵌套控制流一组覆盖数组声明与访问一组故意包含词法错误和类型错误。错误类用例的基准文件用expected_error.txt存出错行号和错误信息对比时看错误信息的行号是否一致。从那以后我每次改完代码都强制走一遍这个回归流程。词法分析的手写状态机、语法分析的递归下降、LR(1)的表驱动、语义分析的四元式不管是哪一个环节动了跑一遍批测脚本几秒钟就能看出来哪里翻车。这比对着单个测试用例一遍遍调试节约的时间不是一点半点。希望这个验证习惯能帮到你上手这套实验代码时少走弯路。本文还有配套的精品资源点击获取