简介：本资源是山东大学《编译原理与技术》课程新版实验一至三的完整实现代码包，面向计算机专业本科生及编译器开发初学者，聚焦编译器前端核心能力训练——词法分析与语法分析的工程实践。资源共15个文件，含8个头文件（.h）用于定义词法结构、语法节点与工具函数，5个源文件（.cpp）实现Lexer、Parser、AST生成及辅助逻辑，另有构建脚本（build.sh）和说明文档（README.md），总大小仅30KB，轻量易读、结构清晰。已有57人学习下载，适合作为课程实验参考或自主复现编译前端的学习范例。读者可直接基于该代码理解有限自动机构建词法识别器、递归下降或LR风格语法分析流程，并掌握Token流到抽象语法树的转换机制；目录中lexer.h/cpp与parser.h/cpp分离设计，配合objectStruct.h与expression.h等模块化头文件，便于分阶段调试与功能扩展。
1. 项目概述：从“纸上谈兵”到“动手造轮子”
编译原理，这门让无数计算机专业学生又爱又恨的“硬核”课程，终于迎来了它的实践环节。当看到“山东大学编译原理与技术课程新版实验一~三”这个标题时，我仿佛回到了当年在实验室里，对着满屏的语法规则和状态转换图抓耳挠腮的时光。这次的新版实验，显然不再是简单地阅读教材或理解算法，而是要求我们真正动手，去构建一个编译器前端乃至更核心的部件。这就像学开车，光看《交规》和《车辆构造》是没用的，必须得坐上驾驶位，点火、挂挡、踩油门，才能真正理解发动机的轰鸣和轮胎的抓地力。
新版实验的核心目标非常明确：将抽象的编译理论转化为具体的代码实现。实验一通常聚焦于词法分析器（Lexer）的构建，实验二深入语法分析器（Parser）与抽象语法树（AST）的生成，而实验三则可能涉及语义分析或中间代码生成的初步探索。这一系列实验的设计，遵循了编译器构建的自然流程，也完美对应了课程从“形式语言与自动机”到“语法制导翻译”的知识脉络。对于学习者而言，这不仅仅是为了完成作业，更是一次深刻的“造轮子”体验。通过亲手实现，你会彻底明白，为什么一个if语句的else分支匹配问题会引发“悬空else”的经典难题，也会对递归下降、LL(1)分析等算法的优劣有切肤之痛。
适合谁来参考这份实验指南呢？首先是山东大学选修该课程的学弟学妹们，这无疑是你们最直接的“通关秘籍”。其次，是所有正在或即将学习编译原理的高校学生，无论你用的是龙书、虎书还是鲸书，实验的核心思想和实现技术都是相通的。最后，也包括那些对编译器感兴趣、希望夯实计算机系统底层知识的开发者。即使你未来不从事编译器开发，理解代码如何从文本变成机器可执行的指令，对于你写出高性能、高质量的代码，以及深度调试复杂问题，都有着不可估量的价值。接下来，我将结合常见的实验要求和多年踩坑经验，为你拆解这三个实验的实现要点、避坑指南和升华技巧。
2. 实验一核心：手搓一个稳健的词法分析器
词法分析是编译器处理源代码的第一步，它的任务是把字符流转换成有意义的词素（Token）序列。你可以把它想象成阅读文章时的“断词”过程：我们需要把“我爱编译原理”这串连续的字符，正确地切分成“我”、“爱”、“编译原理”这几个独立的词语，并给每个词语贴上词性标签（如名词、动词）。
2.1 明确词法规则与Token设计
动手编码之前，必须严格定义词法规则。实验通常会提供一个简化版的C语言或类似语言的子集。你需要仔细阅读实验手册，明确以下内容：
- 关键字：如
if,else,while,int,return等。它们通常是固定的字符串，具有特殊含义。 - 标识符：用于命名变量、函数等。规则通常是字母或下划线开头，后跟字母、数字或下划线。
- 字面量：包括整型常量（如
123）、浮点常量（如3.14）、字符常量（如'a'）和字符串常量（如"hello"）。 - 运算符：如
+,-,*,/,=,==,!=,<,<=等。要特别注意多字符运算符（如==,!=,<=）的识别，避免被错误地切分成两个单字符运算符。 - 分隔符：如
(,),{,},;,,等。
定义好规则后，就要设计Token的数据结构。一个典型的Token类至少应包含：
public class Token { public enum Type { KEYWORD, IDENTIFIER, INTEGER, OPERATOR, DELIMITER, EOF, ... } private Type type; // Token类型 private String lexeme; // 词素文本，如“int”，“123”，“foo” private Object value; // 字面值，如整型123对应的Integer对象 private int line; // 所在行号（用于错误定位） private int column; // 所在列号 // 构造函数、Getter/Setter等方法... }注意：务必为Token添加行号和列号信息。这在后续的语法、语义分析阶段报错时至关重要。一个只告诉你“第5行有错误”的编译器，和一个能告诉你“第5行第12列，标识符未定义”的编译器，用户体验天差地别。
2.2 实现有限自动机（DFA）进行扫描
理论课上我们学了正则表达式和NFA/DFA。在实现时，我们通常手动编码一个DFA，或者使用自动生成工具（如Flex）。对于教学实验，强烈建议手动实现，这能让你对状态转换有肌肉记忆般的理解。
核心扫描逻辑是一个循环，每次从源代码字符流中读取一个字符，根据当前状态和输入字符决定下一个状态和动作。下面是一个高度简化的核心流程伪代码：
public Token getNextToken() { skipWhitespace(); // 跳过空白字符（空格、制表符、换行） if (isEndOfInput()) return createToken(Token.Type.EOF, null); char ch = peekChar(); // 预读一个字符 if (isLetter(ch) || ch == '_') { return scanIdentifierOrKeyword(); } else if (isDigit(ch)) { return scanNumber(); } else if (ch == '"') { return scanString(); } else if (ch == '\'') { return scanChar(); } else { return scanOperatorOrDelimiter(); } }以扫描标识符或关键字为例：
private Token scanIdentifierOrKeyword() { StringBuilder lexeme = new StringBuilder(); int startLine = currentLine; int startCol = currentColumn; while (isLetterOrDigit(peekChar()) || peekChar() == '_') { lexeme.append(nextChar()); } String id = lexeme.toString(); // 检查是否为关键字 Token.Type type = keywords.containsKey(id) ? Token.Type.KEYWORD : Token.Type.IDENTIFIER; return createToken(type, id, startLine, startCol); }实操心得：在
scanOperatorOrDelimiter中处理多字符运算符（如==,!=,&&）时，采用“预读”策略。例如，读到=时，预读下一个字符，如果是=，则组合成==；否则，就只是一个赋值运算符=。这比先切分再合并要优雅和高效得多。
2.3 常见陷阱与调试技巧
- 最大吞噬问题：这是词法分析最常见的错误之一。例如，对于输入
iflag，如果扫描规则是“尽可能匹配最长的字符串”，且没有正确区分关键字和标识符，可能会错误地将其识别为关键字if后跟标识符lag。正确的做法是，在识别出一个完整的标识符词素后，再去关键字表中查找匹配。 - 注释和空白符的处理：务必在扫描主逻辑开始前，妥善处理单行注释（
//）和多行注释（/* ... */）。它们不是Token，但必须被正确跳过，否则会干扰后续分析。同时，换行符\n的处理要同步更新行计数器。 - 字符串和字符常量的转义序列：处理
\",\n,\t,\\等转义字符是词法分析的一个难点。需要在扫描引号内的内容时，专门编写一个子状态机来处理反斜杠\。 - 数字常量的多样性：不仅要支持十进制整数，可能还要支持八进制（
0123）、十六进制（0x1A）、浮点数（3.14,.1,1.,1e-5）。每种格式的DFA都略有不同，需要仔细设计。 - 调试输出：为你的词法分析器实现一个
dumpTokens方法，将扫描出的所有Token及其行列信息打印出来。这是验证词法分析器是否正确工作的最直接方式。对比你的输出和预期输出，能快速定位问题。
词法分析器质量自查表：
| 检查项 | 通过标准 |
|---|---|
| 能正确识别所有定义的关键字 | 输入int while if，输出对应的KEYWORD Token |
| 能正确区分关键字和标识符 | 输入intfoo，输出一个IDENTIFIER “intfoo”，而非KEYWORD “int” + IDENTIFIER “foo” |
| 能处理多字符运算符 | 输入a == b，输出==运算符，而非两个= |
| 能跳过所有注释和空白 | 输入int a; // comment，只输出int,a,;三个Token |
| 能正确报告行列号 | Token对象中包含了准确的行列信息 |
| 能处理文件结束符EOF | 在源文件末尾返回一个特殊的EOF Token |
3. 实验二攻坚：构建语法分析器与抽象语法树
如果说词法分析是“认单词”，那么语法分析就是“组句子”。它的任务是按照预定的语法规则（通常是上下文无关文法），将Token序列转换成一棵结构化的树——抽象语法树（AST）。这棵树清晰地表达了程序的层次结构，是后续所有分析（语义分析、优化、代码生成）的基础。
3.1 文法定义与冲突消解
实验通常会给出一个用于描述语法规则的巴科斯范式（BNF）或其变体（如EBNF）。例如，一个简单的表达式文法可能如下：
Expr -> Term { ('+' | '-') Term } Term -> Factor { ('*' | '/') Factor } Factor -> '(' Expr ')' | NUMBER | IDENTIFIER{ ... }表示重复0次或多次。
在实现前，必须分析文法的性质。首先检查它是否是LL(1)文法。对于LL(1)文法，我们可以使用递归下降分析法，这是一种直观且易于实现的方法。关键步骤是计算每个非终结符的FIRST集和FOLLOW集，并确保没有冲突。
常见冲突及处理：
- 左递归：如
A -> A α | β。直接左递归会导致递归下降解析器无限递归。必须消除左递归，将其改写为等价的右递归形式（A -> β A'，A' -> α A' | ε）。 - 公共左因子：如
A -> α β | α γ。这会导致在看到α时无法决定选择哪个产生式。需要提取左公因子（A -> α A'，A' -> β | γ）。
如果实验允许使用工具（如ANTLR, Bison），这些冲突可以由工具辅助检测和解决。但对于教学实验，手动处理这些冲突是理解语法分析原理的宝贵过程。
3.2 递归下降分析法的实现
递归下降的核心思想是：为文法中的每一个非终结符编写一个对应的解析函数。这个函数负责从输入流中消耗Token，来匹配该非终结符所代表的语法结构。
以解析Expr为例：
/** * 解析表达式: Expr -> Term { ('+' | '-') Term } */ private ASTNode parseExpr() { // 解析第一个Term ASTNode node = parseTerm(); // 循环处理后续的 '+' 或 '-' Term while (true) { Token token = peekToken(); // 预读下一个Token if (token.getType() == Token.Type.OPERATOR && ("+".equals(token.getLexeme()) || "-".equals(token.getLexeme()))) { nextToken(); // 消耗掉这个运算符Token ASTNode right = parseTerm(); // 解析右边的Term // 构建一个二元运算AST节点，左子树是之前的node，右子树是新解析的right node = new BinaryOpNode(token.getLexeme(), node, right); } else { // 如果不是 '+' 或 '-'，则退出循环 break; } } return node; }对应的AST节点设计：
// AST节点的基类 public abstract class ASTNode { protected int line; protected int column; // ... getters and setters } // 二元运算节点 public class BinaryOpNode extends ASTNode { private String operator; // "+", "-", "*", "/" private ASTNode left; private ASTNode right; // ... constructor and getters } // 数字字面量节点 public class NumberNode extends ASTNode { private int value; // ... constructor and getters } // 标识符节点 public class IdentifierNode extends ASTNode { private String name; // ... constructor and getters }注意事项：递归下降分析器对文法的要求很严格（必须是LL(1)）。在编写每个解析函数时，要清晰地通过预读（Peek）一个Token来决定走哪个分支，这依赖于之前计算的FIRST集。函数结束时，当前Token应该正好消耗完该非终结符所匹配的所有输入。
3.3 错误恢复与AST可视化
一个健壮的语法分析器不能遇到第一个错误就崩溃。需要实现简单的错误恢复机制，例如“恐慌模式”恢复：当发现错误时，跳过一些Token直到遇到一个同步词法单元（如分号;、右大括号}等），然后尝试继续解析。
错误恢复的基本策略：
- 错误检测：在预期出现特定Token（如
parseFactor中预期(、NUMBER或IDENTIFIER）的位置，如果当前Token不匹配，则报告语法错误。 - 同步与恢复：在报告错误后，可以简单地跳过一个Token，然后尝试重新开始解析当前的非终结符。更复杂的策略是维护一个同步Token集合（通常是非终结符的FOLLOW集），跳过输入直到遇到集合中的Token。
AST可视化：为了调试和验证，实现一个AST的打印或图形化输出功能极其有用。可以递归地打印节点，使用缩进来表示层级：
BinaryOp(+) |-- BinaryOp(*) | |-- Number(2) | `-- Identifier(x) `-- Number(3)这能让你一目了然地看清2 * x + 3这棵语法树的结构是否正确。
语法分析器调试清单：
| 现象 | 可能原因 | 排查方向 |
|---|---|---|
| 栈溢出（StackOverflowError） | 存在（间接）左递归未被消除 | 检查文法，确保所有产生式都不是左递归的 |
| 解析提前结束，丢失部分代码 | 某个解析函数在成功匹配后提前返回，未消耗所有应匹配的Token | 检查函数逻辑，确保在分支选择后正确调用了nextToken() |
| 总是报告“意外的Token” | FIRST集计算有误，或预读（Peek）逻辑错误 | 手动推导FIRST集，调试时打印当前Token和预期Token进行对比 |
| AST结构混乱（如运算符结合性错误） | 在处理同级运算符（如+、-）时，递归调用顺序错误 | 检查parseExpr和parseTerm的调用关系，确保乘除法（Term）比加减法（Expr）更早、更深地被解析 |
4. 实验三深化：语义分析的初探与实践
语法分析确保了程序“看起来”结构正确，而语义分析则要确保程序“有意义”。实验三通常会在AST的基础上，进行一些基础的语义检查，甚至可能开始涉及符号表管理和简单的中间代码生成。这是连接前端和后端的关键桥梁。
4.1 符号表的构建与管理
符号表是记录程序中所有标识符（变量名、函数名、类型名等）及其属性（类型、作用域、存储位置等）的核心数据结构。在遍历AST进行语义分析时，我们一边收集信息填入符号表，一边查询符号表来验证标识符的使用是否合法。
符号表的设计：通常采用栈式结构，以支持作用域（Scope）。当进入一个新的作用域（如函数体、循环体、块语句）时，压入一个新的符号表子表；退出时弹出。查找符号时，从栈顶向栈底查找，这实现了标识符的“最近嵌套”规则。
public class SymbolTable { private Stack<Map<String, SymbolEntry>> scopes = new Stack<>(); public void enterScope() { scopes.push(new HashMap<>()); } public void exitScope() { scopes.pop(); } public boolean addSymbol(String name, SymbolEntry entry) { if (scopes.peek().containsKey(name)) { return false; // 当前作用域重复定义 } scopes.peek().put(name, entry); return true; } public SymbolEntry lookup(String name) { // 从栈顶向栈底查找 for (int i = scopes.size() - 1; i >= 0; i--) { SymbolEntry entry = scopes.get(i).get(name); if (entry != null) { return entry; } } return null; // 未找到 } } public class SymbolEntry { private String name; private String type; // "int", "float", "function" // ... 其他属性，如维度（数组）、参数列表（函数）等 }4.2 语义检查的遍历实现
语义分析通过对AST进行多次遍历（Pass）来完成。第一次遍历（Pass 1）可能是构建符号表：声明变量、函数等。第二次遍历（Pass 2）进行类型检查、作用域检查等。
一个典型的语义检查流程（以访问者模式遍历AST为例）：
- 变量/函数声明处理：遇到
int a;或int func(...)时，将a或func加入当前作用域的符号表。如果重复定义，报错。 - 变量使用检查：遇到
a = 5;时，在符号表中查找a。如果未找到，报错“未声明的标识符”；如果找到但类型不匹配（如对函数名进行赋值），报错“类型不匹配或非法使用”。 - 类型检查：在表达式
a + b中，查找a和b的类型。如果都是int，则表达式类型为int；如果一个是int一个是float，可能需要隐式类型转换或报错；如果一个是int一个是数组，则报错。 - 函数调用检查：遇到
func(1, 2)时，查找func的符号条目，检查其是否为函数类型，并核对实参（1, 2）的数量和类型是否与形参列表匹配。
4.3 向中间代码生成过渡
有些课程的实验三会要求生成一种简单的中间表示（IR），如三地址码、四元式或P-code。这标志着编译器前端工作的完成。
以生成三地址码为例，对于表达式a = b + c * 2，可能生成：
t1 = c * 2 t2 = b + t1 a = t2实现思路：在语义分析遍历AST的同时，不再是仅仅进行检查，而是为每个可执行的节点（如赋值、运算、函数调用）生成一条或多条中间代码指令，并维护一个临时的变量计数器（如t1, t2, ...）来存放中间结果。
// 遍历到二元运算节点时 public Object visit(BinaryOpNode node) { Object leftVal = visit(node.getLeft()); // 递归处理左子树，可能返回一个变量名（如“b”）或临时变量（如“t1”） Object rightVal = visit(node.getRight()); // 递归处理右子树 String temp = newTemp(); // 生成一个新的临时变量名，如“t3” // 生成一条三地址码指令 emit(temp + " = " + leftVal + " " + node.getOperator() + " " + rightVal); return temp; // 返回这个临时变量名，供父节点使用 }实操心得：语义分析和中间代码生成是编译器中最容易产生“蝴蝶效应”的阶段。一个早期的符号表错误可能导致后续大量的、难以理解的报错。因此，为你的符号表和AST实现一个详尽的
dump()或print()方法至关重要。在关键节点（如进入/退出作用域、生成关键指令）打印状态，能帮你快速定位问题根源。另外，对于教学实验，不必追求一次遍历完成所有工作。多遍遍历（Pass）虽然效率稍低，但逻辑清晰，更易于调试。
语义分析/中间代码生成常见问题速查：
| 问题描述 | 可能原因 | 解决方案 |
|---|---|---|
| “重复定义”错误频发 | 符号表作用域管理混乱，进入块作用域时未正确创建新子表 | 检查enterScope()和exitScope()的调用是否与AST中的块节点严格对应 |
| “未定义标识符”错误，但明明有定义 | 1. 符号查找顺序错误（应先查当前作用域） 2. 标识符在使用之后才声明（如C语言旧标准） | 1. 检查lookup函数的遍历顺序2. 确认语言是否支持“先使用后声明”，若不支持则需先进行声明收集（Pass 1） |
| 类型检查总是失败 | 类型信息未正确存入符号表，或类型推导/转换规则实现有误 | 打印出涉及运算的所有子表达式的推断类型，与预期对比 |
| 生成的中间代码顺序错乱 | AST遍历顺序（如前序、后序）选择错误，或临时变量管理混乱 | 确保在生成子节点的代码之后，再生成当前节点的代码（通常用后序遍历）。为每条指令编号并输出，观察顺序。 |
5. 实验环境、工具与工程化建议
工欲善其事，必先利其器。一个良好的开发环境和对现代工具链的了解，能让你的实验过程事半功倍。
5.1 语言与工具选型
- 实现语言：Java或Python是教学实验的绝佳选择。它们拥有丰富的标准库、清晰的语法，能让你专注于编译逻辑本身，而非内存管理等底层细节。C++也行，但对初学者挑战更大。根据“java+编译原理”这个热搜词，选择Java社区庞大，资料丰富，是稳妥之选。
- 构建工具：使用Maven或Gradle管理Java项目。它们能帮你轻松管理依赖（如JUnit用于测试），并规范项目结构。
- 测试框架：JUnit是单元测试的标准。为你的词法分析器、语法分析器编写全面的测试用例。测试驱动开发（TDD）能极大提升代码质量和调试效率。
- 可视化与调试：
- Graphviz：可以将你的AST或DFA以
.dot格式输出，然后用Graphviz生成直观的图片，便于分析和报告。 - IDE调试器：熟练掌握Eclipse或IntelliJ IDEA的调试器。设置条件断点，观察Token流、AST构建过程、符号表状态变化，是理解编译器运行机理的最快途径。
- Graphviz：可以将你的AST或DFA以
5.2 项目结构与代码组织
一个清晰的项目结构有助于管理和协作：
compiler-lab/ ├── src/main/java │ └── com/yourname/compiler │ ├── lexer/ # 词法分析包 │ │ ├── Lexer.java │ │ ├── Token.java │ │ └── TokenType.java │ ├── parser/ # 语法分析包 │ │ ├── Parser.java │ │ ├── ast/ # AST节点定义 │ │ │ ├── ASTNode.java │ │ │ ├── BinaryOpNode.java │ │ │ └── ... │ │ └── ... │ ├── semantics/ # 语义分析包 │ │ ├── SymbolTable.java │ │ ├── SemanticAnalyzer.java │ │ └── ... │ └── Main.java # 主入口 ├── src/test/java # 测试代码目录 │ └── ... # 对应的JUnit测试类 ├── resources/ # 资源文件 │ ├── test_cases/ # 测试用例源文件 │ └── grammar.txt # 文法定义文件 └── pom.xml # Maven配置文件5.3 版本控制与实验报告
- 版本控制：务必使用Git。从实验一开始就初始化仓库，定期提交（Commit）。这不仅能防止代码丢失，还能让你清晰地看到自己的开发历程。为每个实验阶段（如“实验一完成词法分析”、“实验二修复左递归bug”）打上标签（Tag）。
- 实验报告撰写：
- 理论结合实践：不要只贴代码。解释清楚你用的算法（如为什么用递归下降而不用LR？），关键数据结构的设计思路（如符号表为何用栈？）。
- 展示关键过程：附上重要测试用例的输入、输出（Token序列、AST图、符号表Dump、生成的中间代码）。
- 分析难点与解决方案：详细描述你遇到的最大挑战是什么，以及你是如何分析和解决的。这是报告最能体现你思考深度的地方。
- 性能与优化思考：即使实验不要求，也可以简单思考一下，你的词法分析器缓冲区如何设计更高效？AST节点池能否减少内存分配？这能展现你的工程素养。
完成这三个实验，你收获的将不仅仅是几个程序的源代码。你获得的是对“程序如何运行”这一根本问题的深刻理解，是处理复杂系统、设计领域特定语言（DSL）的能力基础，更是计算机科学核心思维——分层抽象与自动机思想——的一次完美演练。当你看到自己编写的编译器，能将一段简单的文本代码转换成可执行的指令或中间表示时，那种成就感是无可替代的。这或许就是编译原理这门“屠龙之术”的魅力所在：它艰难，但一旦掌握，便内力大增。
本文还有配套的精品资源，点击获取
