简介面向编译原理学习者与开发者这是一套覆盖山东大学编译原理与技术课程新版实验一至三的完整代码包聚焦编译器前端构建核心围绕词法分析器Lexer与语法分析器Parser的设计实现适合需要完成同类实验、复习编译原理或入门前端开发的高校学生。资源共15个文件以8个h头文件、5个cpp源文件为主辅以构建脚本与README说明整体约30KB。头文件与源码分别承载词法规则定义、语法结构体、对象生成与解析工具等模块可直接浏览、编译运行并对照学习。已有58人学习下载内容虽精简但结构清晰便于快速定位关键实现。通过实验一至三的递进练习读者可以掌握从字符流到Token识别、再到抽象语法树生成与错误处理的全流程编码方法积累有限自动机、上下文无关文法、递归下降及LR分析等核心知识的落地经验为后续开发编译器、解释器或语言工具打下扎实基础。1. 编译原理实验从零到验收词法、语法、语义三个 Lab 一次讲透如果你也是期末前一周才直面“编译原理实验”这几个字的人或者是工作中突然要接手一个类 C 语言前端解析任务那这套山东大学编译原理与技术课程的新版实验一~三值得你花一下午拆开看。它不是那种贴个 PPT 就完事的 demo而是从词法分析器lexer到语法解析parser再到语义分析和中间代码生成的一条完整链路。新版把错误恢复、符号表作用域和四元式生成的考察权重加了不少很多同学的翻车现场都集中在这三块。这套东西适合三类人正在做课程实验的本科生、准备考研复试要讲项目的人、以及想在 Java 里复刻一个微型编译器前端的从业者。2. 实验一词法分析器的状态机实现与 Token 流设计2.1 为什么课程要求手写状态机而不是正则表达式一把梭很多第一次做词法分析的同学会问Java 里Pattern和Matcher这么方便为什么实验非要手写 DFA常见做法是课程明确要求“不得使用正则表达式库”或“需展示状态转换过程”目的是让你把有限自动机的理论落到代码里。另一个现实原因是手写状态机能精确控制每个字符的消耗路径——什么时候推进、什么时候回退一个字符这在处理、这类双字符运算符时非常直观。词法分析的核心输出是 Token 流。每个 Token 至少要有三样东西种别码token type、单词文本lexeme、所在行列号。新版实验会把行号列号的正确性纳入评分因为后续语法报错要依赖它定位。种别码怎么设计常见做法是直接定义一个常量类public final class Tag { public static final int ID 1; // 标识符 public static final int NUM 2; // 数字常量 public static final int KEYWORD 3; // 关键字 public static final int OP 4; // 运算符 public static final int DELIM 5; // 分隔符 public static final int EOF 6; // 文件结束 }这里种别码用于后续语法分析的nextToken()判断分支。注意硬编码数字可读性差强烈建议在实验报告里说明每个常量的含义并把它和教材里的种别码表对应起来。关键字和标识符可以共用一个 ID 类型但需要在 Token 对象里附加一个keywordFlag字段或者把关键字表单独维护否则后面判断if、while会非常麻烦。2.2 手写 DFA 主循环与超前读回退词法分析器的骨架是一个大循环每个字符喂进状态机状态决定是继续读、停还是报错。我一般会用一个Lexer类维护输入缓冲和当前位置核心逻辑放在nextToken()public Token nextToken() throws LexerException { skipWhitespace(); int startRow row, startCol col; char c peek(); if (isLetter(c)) { StringBuilder sb new StringBuilder(); while (isLetter(peek()) || isDigit(peek())) { sb.append(peek()); advance(); } String word sb.toString(); if (keywordTable.contains(word)) { return new Token(Tag.KEYWORD, word, startRow, startCol); } return new Token(Tag.ID, word, startRow, startCol); } if (isDigit(c)) { StringBuilder sb new StringBuilder(); while (isDigit(peek())) { sb.append(peek()); advance(); } if (peek() .) { sb.append(peek()); advance(); while (isDigit(peek())) { sb.append(peek()); advance(); } } return new Token(Tag.NUM, sb.toString(), startRow, startCol); } // 双字符运算符 if (c ) { advance(); if (peek() ) { advance(); return new Token(Tag.OP, , startRow, startCol); } return new Token(Tag.OP, , startRow, startCol); } throw new LexerException(无法识别的字符: c 位于 startRow : startCol); }说完逻辑。skipWhitespace()负责吃掉空格、\t、\n和\r同时更新行列号peek()返回当前字符但不消费advance()才真正移动指针并维护行列号。标识符和关键字共用一个读取循环读完后查表判断类型这是最常用的做法。参数上注意两点第一数字后面的peek() .判断只支持小数如果要支持科学计数法需要额外加状态分支第二分支中如果第二个字符不是就直接返回单字符 Token不需要把第二个字符“放回去”因为指针本来就没有后移——advance()只调用了一次。很多初学者的血泪教训是在这里多调了一次advance()等于吞掉了下一个字符。2.3 错误恢复策略不中断整个编译过程实验一只要求“报错并跳过”但新版要求错误的后续字符不能无限死循环。常见做法是非法字符出现后跳过一个字符继续词法分析并把错误信息收集到一个ListString errors里。这样一次能暴露多个错误而不是每次只报第一个。public ListToken scan(String source) throws LexerException { ListToken tokens new ArrayList(); ListString errors new ArrayList(); while (!isAtEnd()) { int beforeRow row, beforeCol col; try { Token t nextToken(); tokens.add(t); if (t.getTag() Tag.EOF) break; } catch (LexerException e) { errors.add(e.getMessage()); advance(); // 跳过非法字符继续 } } return tokens; }这个设计的坑在于如果nextToken()已经消费了部分合法字符后才抛异常比如读到一半发现不能构成合法 Token那advance()直接跳一个字符会把上下文搞乱。更稳妥的做法是让nextToken()在异常发生时把指针恢复到本次调用前的快照位置这需要你再维护一个checkpoint。我在实验里加了mark()和reset()两个方法检测到非法字符时先复位再跳过。3. 实验二递归下降解析与预测集合的冲突处理3.1 选递归下降还是 LR为什么课程实验偏爱前者语法分析是编译原理实验里最容易让人失眠的一章。LR 自动机解析能力强但手写状态转移表和 LALR 冲突消解对课程实验来说工程量太大。递归下降则直观得多——每一个非终结符对应一个函数函数体就是产生式的右部按顺序展开。递归下降属于 LL 类方法真正的限制是文法不能含左递归。所以拿到文法第一件事就是消除左递归。比如E - E T | T要改写成E - T E E - T E | ε常见做法是直接把改写后的规则写进代码而不是先做算法转换。写代码时每个函数检查当前 Token 是否属于该产生式的 FIRST 集如果不属于就直接报语法错误。public void parseExpression() throws SyntaxException { parseTerm(); // E - T E while (isCurrentToken(PLUS) || isCurrentToken(MINUS)) { advance(); parseTerm(); } }这个写法把 E 的左递归消除直接编码进了循环while里的条件等价于判断 nextToken 是否属于 FIRST(E)。注意parseExpression没先看 Token 就调用parseTerm这意味着调用方比如parseStatement必须保证当前 Token 确实能开始一个表达式否则要在parseExpression开头加一级predictCheck。我一般会加一个断言if (!canStartExpression(currentToken)) throw new SyntaxException(...)避免错误定位到十层深的递归里。3.2 表达式优先级与左结合的实现细节表达式的优先级是实验二的核心考点。常规实现是分层parseExpression → parseTerm → parseFactor加减在一层乘除在下一层因子在最后一层。这样2 3 * 4只会被解析成2 (3 * 4)。public void parseFactor() throws SyntaxException { switch (currentToken().getTag()) { case Tag.NUM: advance(); break; case Tag.ID: advance(); break; case Tag.LPAREN: advance(); parseExpression(); expect(Tag.RPAREN); break; default: throw new SyntaxException(因子处出现非法 Token: currentToken()); } }这里最容易出错的地方有两个。第一是左括号分支里的expect(Tag.RPAREN)如果缺失错误信息会指向文件末尾而不是缺失的位置第二是parseFactor和parseTerm之间没有直接联系优先级完全靠函数调用层级体现如果有人把parseExpression和parseTerm的关系理解反了写出来的分析器会是右结合。验证方法很简单给一段1 2 * 3打印语法树或动作序列看运算顺序是否先算乘法。这个验证我后面专门会讲。3.3 语法错误的定位与同步恢复新版实验对语法错误处理的要求是能报出具体的行和列而且报错后不能无限递归。我在这个实现里用的是“恐慌模式”panic mode——捕获异常后扔掉当前输入直到找到一个同步 Token分号或右括号再恢复解析。private void synchronize() { advance(); while (!isAtEnd()) { if (currentToken().getTag() Tag.DELIM currentToken().getText().equals(;)) { return; } switch (currentToken().getTag()) { case Tag.KEYWORD: // return、if、while 等可以重新开始语句 String kw currentToken().getText(); if (kw.equals(return) || kw.equals(if) || kw.equals(while)) { return; } break; default: break; } advance(); } }这个synchronize的设计原则是分号代表一条语句结束关键字代表一条新语句开始。两者都能作为同步的安全位置。注意advance()要在循环开始前先执行一次否则当前非法 Token 永远无法被跳过造成死循环。这是我在调试时踩过最莫名其妙的一坑——从现象看是程序卡住实际上是synchronize入口没让指针动。4. 实验三语义分析与中间代码生成符号表是半个战场4.1 符号表的作用域链设计与整型类型检查实验三通常要求实现语义检查并生成四元式。语义分析的核心是符号表——它不只是“变量名到类型”的映射还要管作用域函数内局部变量不能泄漏到外面同一个名字在嵌套作用域里可以重新声明。常见做法是在树里每进入一个块就压一层符号表退出时弹掉。为了支持嵌套可以用一个栈结构public class Scope { private MapString, SymbolInfo symbols new HashMap(); private Scope parent; public SymbolInfo lookup(String name) { Scope current this; while (current ! null) { if (current.symbols.containsKey(name)) { return current.symbols.get(name); } current current.parent; } return null; } }说下这个查找逻辑。lookup从当前作用域出发不断向上找父作用域直到找到或到达顶层。这样内层可以引用外层变量外层碰不到内层的。另一个关键操作是类型检查——每次声明时记录类型每次引用变量或函数时取出类型核对public void checkBinaryOp(String op, SymbolInfo left, SymbolInfo right, int row, int col) { if (!left.getType().equals(right.getType())) { throw new SemanticException(类型不匹配: left.getName() ( left.getType() ) vs right.getName() ( right.getType() ) 位于 row : col); } if (left.getType().equals(int) right.getType().equals(int)) { return; } throw new SemanticException(仅支持整型运算位于 row : col); }类型检查最容易漏的是赋值方向int a; float b; a b;要不要禁止课程实验如果只要求整型就把类型系统做窄一点所有非 int 直接拒掉。这样能省掉隐式转换的复杂度实验报告也更好写。但切忌只报“类型不匹配”不报位置会导致你在测试时找不到是哪一行出错。4.2 四元式生成从表达式到三地址码中间代码实验最常要求的是四元式中间代码输出每一行的结构统一成(op, arg1, arg2, result)。比如a b * 2要翻译成(*, b, 2, t1) (, a, t1, t2)生成过程需要为每个中间结果分配临时变量。这里我用一个计数器从t0开始累加保证临时变量全局唯一。表达式翻译的递归模式如下public String generateExpr(ASTNode node) { if (node.getType().equals(INTEGER)) { return node.getText(); } if (node.getType().equals(IDENTIFIER)) { return node.getText(); } // 二元运算节点 String left generateExpr(node.getLeft()); String right generateExpr(node.getRight()); String temp newTemp(); emitQuad(( node.getOperator() , left , right , temp )); return temp; }注意这里有两层递归的返回值代表“这个表达式算完后结果在哪”可能是字面量、变量名或临时变量。newTemp()生成t0、t1这种名字。四元式的 result 列必须填临时变量不能直接写成表达式否则就不叫三地址码了。4.3 控制流的回填技术if 和 while 怎么转跳转指令控制流语句生成是实验三的难点。if (x 0) y 1; else y 2;不能简单线性生成因为需要条件跳转。常见做法是先生成条件判断的四元式再回填跳转目标地址。这个回填技术是很多人的“黑匣子”。// 伪代码生成 if 条件的四元式 String cond generateCondition(conditionNode); // 假设生成条件后当前四元式地址为 nextQuadIndex emitQuad((j, condLeft , condRight , ?)); // 条件为真跳转到 then 分支 int jumpIndex currentQuadIndex() - 1; generateThenBranch(thenNode); // 回填 patchQuad(jumpIndex, currentQuadIndex()); if (hasElse) { emitQuad((j, _, _, ?)); int elseJump currentQuadIndex() - 1; generateElseBranch(elseNode); patchQuad(elseJump, currentQuadIndex()); }这里patchQuad(jumpIndex, target)就是把之前占位的?替换成实际的指令地址。注意emitQuad的顺序不能乱必须先 emit 条件跳转、生成 then 分支、再回填。如果反了跳转会跳到错误位置。回填逻辑是整个实验三里最值得在报告里画图说明的部分代码本身不复杂但原理一定要想清楚。5. 避坑山大编译实验最常见的六条血泪经验5.1 Windows 下的回车换行符让行号全乱现象词法分析在 Windows 上跑报错位置总比实际多一行或少一行特别是用readLine()读文件时。原因\r\n是两个字符如果你的skipWhitespace()把\n算作换行、\r不算也没有把\r跳过那行号统计就会在每行末尾多计一次列号或者少计一次行数。解决统一走字符流逐字符判断\n加行号\r直接跳过不计列号。我还在代码里强制用Files.newBufferedReader(path, StandardCharsets.UTF_8)读入杜绝平台默认编码带来的中文注释乱码问题——中文注释乱码会导致标识符判断直接出错这是最初级也最隐蔽的坑。5.2 关键字查表顺序不对if被识别成标识符现象输入if (x 0)Token 流里出现的却是ID(if)而不是KEYWORD(if)导致语法分析在期望 KEYWORD 时直接抛错。原因代码先判断isLetter(c)后直接返回Tag.ID查关键字表的逻辑在某个分支里被跳过了或者关键字表用了HashSet但是判断的word里混了不可见字符。解决把查表逻辑放在标识符读取循环之后、返回之前并且用keywordTable.contains(word)判断。调试时打印word.length()和每个字符的 int 值能快速发现混进了不可见字符。5.3 递归下降时左递归没消干净StackOverflow 直接崩现象运行实验二时输入任何表达式都报StackOverflowError且栈顶是parseExpression。原因文法里还有左递归或者代码结构等效于左递归——最常见的是parseTerm里先调parseFactor但parseFactor里又调回parseTerm形成双向递归。另一个常见场景是在消除左递归时偷懒直接在代码里写成parseExpression开头又调了一次parseExpression。解决回到文法层面重新推一遍确保表达式层级的调用链是严格向下的expression → term → factorfactor 里只能通过括号调回 expression而不能调回 term。用一个小样例a b单步跟踪调用栈不要靠眼睛看代码。5.4 符号表作用域退栈时机不对变量作用域串了现象两个函数里都定义了i在函数 A 的末尾访问i却拿到函数 B 的值或者函数结束后还能引用函数内的局部变量。原因作用域栈的 pop 时机错误。函数体还没完全翻译完就把当前作用域弹掉了或者块级作用域没有随块结束而退出。解决统一在“离开 AST 节点时”做 pop而不是在“生成四元式时”做。我习惯在进入函数/块节点时 push 一个作用域在递归返回该节点前执行 pop这样无论中途走哪条路径都不会漏掉。5.5 四元式回填的目标是错的但语法和词法全通过现象生成的if跳转四元式里地址是 0 或者填成了四元式总数导致输出指令序列跳到自己。原因emitQuad顺序没按“先占位再回填”执行。常见误用是先生成 then 分支再 emit 条件跳转导致跳转目标索引超前或滞后。解决用一个quadList的 size 作为指令地址基准把跳转的四元式索引存下来在所有分支代码生成完毕后统一回填。我在每次emitQuad后都打印当前四元式地址校验循环里每个分支跳转目标是否落在合法范围内。6. 联调验证用一小组类 C 代码把三个实验串成流水线三份实验单独能跑只说明局部没问题真正要命的边界问题在联调时才暴露。我一直保留一个test/目录里面放几个精心构造的用例一个能完整通过的正例三个分别触发词法错误、语法错误、语义错误的负例。正例用来验证主链路负例分别验证每个阶段的报错定位是否准确。# 编译全部模块并运行主入口 javac -encoding UTF-8 -d out src/**/*.java java -cp out edu.sdu.compiler.Main test/positive.cminus java -cp out edu.sdu.compiler.Main test/lex_error.cminus我常用的正例是下面这段类 C 代码包含变量声明、表达式运算、if 分支和循环。三段实验全跑通输出应为词法阶段无报错、语法阶段无报错、语义检查通过、四元式列表数量大于预期且每条 result 列的临时变量编号单调递增。int x; int y; x 2 3 * 4; if (x 10) { y 1; } else { y 2; } while (x 0) { x x - 1; }验证时我会盯三个点第一3 * 4必须先生成四元式2 ...后生成否则优先级实现是反的第二if 分支的跳转目标回填后必须落在 then 分支的第一条四元式上不能四处乱飞第三while 循环的末尾跳转必须能回到条件判断的第一条四元式。这三个点全过实验三的主体就能保证。我自己每轮实验都会先跑这段公共样例再写自己的用例去覆盖边界数字和嵌套 if——结果导致我后来每次拿到新实验都强制自己先搭一套最小可验证用例再碰逻辑代码这个习惯帮我省了太多调试时间。希望帮到你。本文还有配套的精品资源点击获取