简介：这份资源是北京邮电大学计算机学院编译原理课程中词法分析与语法分析器的实现压缩包，面向正在学习编译原理、需要完成课程实验或想动手理解编译器前端构建的学生与开发者。包内共12个文件，以4个cpp源文件、1个c文件为核心实现代码，辅以4个txt文法说明、3个md实验报告与说明文档，整体约27KB，体积轻便，便于快速阅读与二次修改。内容围绕词法单元识别、正则表达式与自动机、上下文无关文法、抽象语法树构建等关键环节展开，并同时提供LL与LR两类语法分析实现，方便对照理解不同分析策略的差异。已有200人学习下载，适合作为课程作业参考、实验排错思路来源以及复习编译前端流程的实践材料，帮助读者把课堂理论落到可运行的代码上。

1. 北邮计算机学院编译原理大作业：词法语法分析器到底在做什么

如果你正在北邮计算机学院读大三，或者选了编译原理这门课，大概率会在期中前后拿到一个压缩包，名字就叫“词法、语法分析器”。它不是一个能直接交差的完整工程，而是一份需要你补全核心逻辑的骨架。词法分析器负责把源代码字符流切成有意义的单词符号，语法分析器再把这些符号串组织成语法树。这两个模块是编译器前端最基础也最磨人的部分，直接决定了后续语义分析和代码生成能不能跑通。适合谁？适合已经学过形式语言与自动机、写过至少一门语言的课程设计、但面对递归下降和 LR 状态机仍然心里没底的人。这篇文章不替你写作业，而是把从拿到压缩包到本地跑通、再到调试通过的全路径拆开，让你少走几个通宵的弯路。

2. 词法分析器：从字符流到 Token 序列的最小实现

2.1 为什么先做词法而不是直接上语法

编译原理实验里最常见的翻车现场，就是跳过词法直接写语法分析，结果在表达式里遇到a+++b这种连续符号时彻底懵掉。词法分析器的职责非常明确：读入源程序字符串，忽略空白和注释，识别出关键字、标识符、数字、运算符和界符，输出一个 Token 列表。每个 Token 至少包含类型和值两个字段。北邮的压缩包里通常会提供一个Token类或结构体定义，以及一个Lexer的框架，你需要补全的是nextToken()或scan()方法。

常见做法是用有限自动机（DFA）来驱动。手工写一个状态转移表，或者用一组if-else加while循环模拟状态跳转。对于教学实验，后者更直观，也更容易调试。关键是要处理好最长匹配原则：遇到<=不能拆成<和=，遇到==不能拆成两个=。另外，标识符和关键字的区分通常靠查表，先按标识符规则读入完整字符串，再去关键字表里比对。

2.2 用 Java 实现一个可调试的 Lexer 核心循环

下面这段代码是一个简化但可运行的词法分析器核心，假设输入是标准 C 语言子集的源码字符串。它输出List<Token>，每个 Token 带类型和原始文本。

public class Lexer { private String src; private int pos; private List<Token> tokens; public Lexer(String src) { this.src = src; this.pos = 0; this.tokens = new ArrayList<>(); } public List<Token> tokenize() { while (pos < src.length()) { char ch = src.charAt(pos); if (Character.isWhitespace(ch)) { pos++; continue; } // 处理注释：跳过 // 到行尾 if (ch == '/' && pos + 1 < src.length() && src.charAt(pos + 1) == '/') { while (pos < src.length() && src.charAt(pos) != '\n') pos++; continue; } if (Character.isLetter(ch) || ch == '_') { readIdentifierOrKeyword(); } else if (Character.isDigit(ch)) { readNumber(); } else { readOperatorOrDelimiter(); } } return tokens; } private void readIdentifierOrKeyword() { int start = pos; while (pos < src.length() && (Character.isLetterOrDigit(src.charAt(pos)) || src.charAt(pos) == '_')) { pos++; } String word = src.substring(start, pos); // 关键字表可以用 Set 或 Map 实现 if (Keywords.isKeyword(word)) { tokens.add(new Token(TokenType.KEYWORD, word)); } else { tokens.add(new Token(TokenType.IDENTIFIER, word)); } } private void readNumber() { int start = pos; while (pos < src.length() && Character.isDigit(src.charAt(pos))) pos++; // 处理小数 if (pos < src.length() && src.charAt(pos) == '.') { pos++; while (pos < src.length() && Character.isDigit(src.charAt(pos))) pos++; } tokens.add(new Token(TokenType.NUMBER, src.substring(start, pos))); } private void readOperatorOrDelimiter() { char ch = src.charAt(pos); // 双字符运算符优先匹配 if (pos + 1 < src.length()) { String two = src.substring(pos, pos + 2); if (Operators.isDoubleOperator(two)) { tokens.add(new Token(TokenType.OPERATOR, two)); pos += 2; return; } } tokens.add(new Token(TokenType.OPERATOR, String.valueOf(ch))); pos++; } }

逻辑说明：主循环每次跳过空白和注释，然后根据首字符分派到三个读取函数。readIdentifierOrKeyword用最长匹配读出完整单词，再查关键字表决定类型。readNumber支持整数和小数，注意小数点后必须跟数字才继续读，否则回退。readOperatorOrDelimiter先尝试匹配双字符运算符，失败再按单字符处理。参数方面，src是输入源码，pos是当前读取位置，tokens是输出列表。关键字表和运算符表建议用static final Set<String>初始化，避免每次查表都新建对象。

提示：北邮实验里经常要求输出 Token 的行号和列号，方便后续报错。可以在 Token 类里加line和col字段，在tokenize循环里维护一个lineCount，遇到\n就加一。

2.3 词法分析器的三个必调参数与测试用例

第一个参数是缓冲区大小。如果是一次性读入整个文件，src就是完整字符串，不需要缓冲区。但有些实验要求模拟流式读取，这时缓冲区大小建议设为 4096 字节，太小会频繁触发填充逻辑，太大浪费内存。第二个参数是最大标识符长度。C 语言标准规定至少支持 31 个有效字符，但实际实现里可以设成 256，超出部分截断或报错。第三个参数是注释嵌套层数。C 语言不支持嵌套注释，但有些实验会加这个需求，如果支持，需要维护一个commentDepth计数器。

测试用例至少覆盖：纯关键字序列、标识符与关键字混合、浮点数与整数、双字符运算符、单行注释、空输入。一个典型的边界用例是int a = 1.2.3;，词法分析器应该报错或输出1.2和.3两个数字，而不是吞掉整个1.2.3。另一个是a+++++b，正确输出应该是a、++、++、+、b，而不是a、++、+++、b。这些用例在验收时经常被问到。

3. 语法分析器：递归下降与 LR 的选型与落地

3.1 递归下降适合教学实验的四个理由

语法分析器有两种主流实现路径：自顶向下的递归下降和自底向上的 LR 系列。北邮的压缩包通常两种框架都提供，但建议优先选递归下降。理由一，代码结构和文法产生式几乎一一对应，写起来直观。理由二，调试方便，可以在每个函数入口打印当前 Token，快速定位是哪个非终结符匹配失败。理由三，不需要构造 LR 状态机表，省去大量手工计算。理由四，实验验收时老师更关注你是否理解 FIRST 集和 FOLLOW 集，递归下降能直接体现这些概念。

递归下降的核心是为每个非终结符写一个函数。函数入口先根据当前 Token 和 FIRST 集决定走哪条产生式，如果产生式右部有多个符号，就依次调用对应的函数或匹配终结符。遇到ε产生式时，直接返回，不消耗 Token。关键是要处理好回溯：如果当前产生式匹配失败，需要恢复到进入前的 Token 位置。教学实验里通常要求文法经过提取左公因子和消除左递归，所以回溯不会太深。

3.2 用 Java 写一个表达式语法分析器

下面是一个支持加减乘除和括号的表达式语法分析器，采用递归下降。它接收词法分析器输出的 Token 列表，输出抽象语法树（AST）。

public class Parser { private List<Token> tokens; private int pos; public Parser(List<Token> tokens) { this.tokens = tokens; this.pos = 0; } public ASTNode parse() { return expr(); } // expr -> term (('+' | '-') term)* private ASTNode expr() { ASTNode left = term(); while (pos < tokens.size() && (tokens.get(pos).getType() == TokenType.OPERATOR) && (tokens.get(pos).getValue().equals("+") || tokens.get(pos).getValue().equals("-"))) { String op = tokens.get(pos).getValue(); pos++; ASTNode right = term(); left = new BinaryNode(op, left, right); } return left; } // term -> factor (('*' | '/') factor)* private ASTNode term() { ASTNode left = factor(); while (pos < tokens.size() && (tokens.get(pos).getType() == TokenType.OPERATOR) && (tokens.get(pos).getValue().equals("*") || tokens.get(pos).getValue().equals("/"))) { String op = tokens.get(pos).getValue(); pos++; ASTNode right = factor(); left = new BinaryNode(op, left, right); } return left; } // factor -> NUMBER | '(' expr ')' private ASTNode factor() { if (pos >= tokens.size()) { throw new ParseException("Unexpected end of input"); } Token t = tokens.get(pos); if (t.getType() == TokenType.NUMBER) { pos++; return new NumberNode(t.getValue()); } if (t.getType() == TokenType.OPERATOR && t.getValue().equals("(")) { pos++; ASTNode node = expr(); if (pos >= tokens.size() || !tokens.get(pos).getValue().equals(")")) { throw new ParseException("Missing closing parenthesis"); } pos++; return node; } throw new ParseException("Unexpected token: " + t.getValue()); } }

逻辑说明：expr处理加减，term处理乘除，factor处理数字和括号。每个函数先调用更高优先级的函数，再根据当前 Token 决定是否继续循环。pos是当前 Token 索引，tokens是词法分析器的输出。BinaryNode和NumberNode是 AST 节点类，需要自己定义。参数方面，tokens必须非空且以合法 Token 结尾，否则factor会抛异常。建议在parse()返回前检查pos是否等于tokens.size()，确保没有多余 Token。

注意：递归下降对左递归文法无能为力。如果实验文法里有expr -> expr '+' term，必须先消除左递归，改成expr -> term expr'和expr' -> '+' term expr' | ε。这一步在实验报告里要写清楚。

3.3 语法分析器的错误恢复与报错信息

实验验收时，老师通常会输入一个故意写错的表达式，看你的分析器能不能给出有意义的报错。常见错误包括括号不匹配、运算符连续出现、缺少操作数。错误恢复策略有两种：恐慌模式恢复和短语级恢复。恐慌模式是丢弃当前 Token 直到遇到同步集合（比如分号或右括号），然后继续分析。短语级恢复是插入一个缺失的 Token 或删除多余的 Token，然后继续。教学实验里建议用恐慌模式，实现简单，不容易陷入死循环。

报错信息要包含行号、列号和期望的 Token 类型。比如“第 3 行第 5 列：期望 ‘)’ 但遇到 ‘+’”。行号和列号可以从 Token 对象里取，前提是词法分析器已经记录了这些信息。如果压缩包里的 Token 类没有行列号，可以在语法分析器里维护一个currentLine变量，遇到换行 Token 时递增。但更稳妥的做法是改词法分析器，让每个 Token 都带位置信息。

4. 避坑与排查：编译原理实验里最常见的五个翻车点

4.1 现象：词法分析器把关键字识别成标识符

原因：关键字表没有初始化，或者查表时大小写敏感但输入是大写。解决：在 Lexer 构造函数里用static块初始化Set<String> keywords，加入所有关键字。查表前先toLowerCase()或严格按语言规范处理大小写。测试时专门输入IF、If、if三个变体，确认只有if被识别为关键字。

4.2 现象：语法分析器遇到空产生式时死循环

原因：递归下降里ε产生式没有正确返回，或者while循环条件永远为真。解决：在ε产生式对应的函数里直接return，不消耗 Token。在循环里每次迭代必须至少消耗一个 Token，否则加一个if (pos == lastPos) break;的保险。调试时打印每次循环的pos和当前 Token，很快就能定位。

4.3 现象：AST 构建后遍历时栈溢出

原因：表达式嵌套太深，递归遍历 AST 时递归层数超过 JVM 栈限制。解决：对于教学实验，表达式深度通常不会太大，但如果测试用例里有几百层括号，就需要改成迭代遍历或增大 JVM 栈大小（-Xss参数）。更根本的办法是在语法分析阶段限制最大嵌套深度，超过就报错。

4.4 现象：Token 列表里出现空字符串或 null

原因：readIdentifierOrKeyword里start和pos相等时没有检查，或者substring越界。解决：在每次substring前确认start < pos，否则跳过。在tokenize主循环里加一个断言，确保每次循环pos都严格递增。如果发现pos不变，说明某个分支没有推进位置，需要检查readOperatorOrDelimiter里的pos++是否遗漏。

4.5 现象：实验在本地跑通但提交后报编译错误

原因：压缩包里的 JDK 版本和本地不一致，或者用了 Java 8 不支持的语法（比如var）。解决：在pom.xml或build.gradle里明确指定sourceCompatibility和targetCompatibility为 1.8。如果实验要求用命令行编译，用javac -source 8 -target 8。另外，检查是否用了第三方库但没打包进提交文件。教学实验通常要求纯 JDK 实现，不要引入 Apache Commons 或 Guava。

5. 从能跑到好用：符号表接入与测试驱动的小技巧

5.1 把符号表挂到语法分析器上

词法和语法分析器跑通之后，下一步通常是接入符号表。符号表用来记录变量名、类型、作用域和行号，为后续语义分析做准备。最简单的做法是在Parser里维护一个Map<String, Symbol>，在解析变量声明时插入，在解析标识符时查找。作用域可以用栈来实现：进入{时压栈，退出}时弹栈。每个Symbol至少包含name、type、line、scopeLevel四个字段。

public class SymbolTable { private Deque<Map<String, Symbol>> scopes; public SymbolTable() { scopes = new ArrayDeque<>(); scopes.push(new HashMap<>()); } public void enterScope() { scopes.push(new HashMap<>()); } public void exitScope() { if (scopes.size() > 1) scopes.pop(); } public void define(Symbol sym) { scopes.peek().put(sym.getName(), sym); } public Symbol resolve(String name) { for (Map<String, Symbol> scope : scopes) { if (scope.containsKey(name)) return scope.get(name); } return null; } }

逻辑说明：scopes是一个双端队列，栈顶是当前作用域。enterScope和exitScope在解析到{和}时调用。define把符号放入当前作用域，resolve从内到外逐层查找。参数方面，Symbol类需要自己定义，建议包含name、type、line、scopeLevel。注意resolve返回null表示未声明，语法分析器可以据此报“未定义标识符”错误。

5.2 用 JUnit 做回归测试，避免改一处崩三处

编译原理实验的代码量不大，但逻辑耦合度高，改词法分析器很容易影响语法分析器。建议用 JUnit 写回归测试，每个测试用例覆盖一个边界场景。测试类放在src/test/java下，用@Test注解标记。断言 Token 列表的长度、类型序列和值序列。对于语法分析器，断言 AST 的中序遍历结果或直接比较字符串表示。

@Test public void testLexerDoubleOperator() { Lexer lexer = new Lexer("a <= b"); List<Token> tokens = lexer.tokenize(); assertEquals(3, tokens.size()); assertEquals("a", tokens.get(0).getValue()); assertEquals("<=", tokens.get(1).getValue()); assertEquals("b", tokens.get(2).getValue()); } @Test public void testParserPrecedence() { Lexer lexer = new Lexer("1 + 2 * 3"); Parser parser = new Parser(lexer.tokenize()); ASTNode root = parser.parse(); // 期望根节点是 '+'，右子节点是 '*' assertTrue(root instanceof BinaryNode); assertEquals("+", ((BinaryNode) root).getOp()); }

逻辑说明：第一个测试验证双字符运算符不被拆分。第二个测试验证乘号优先级高于加号。参数方面，assertEquals的第一个参数是期望值，第二个是实际值。如果失败，JUnit 会打印差异。建议每个实验阶段都跑一遍全部测试，确保新功能没有破坏旧功能。

5.3 一个被低估的调试习惯：打印 Token 流和 AST

很多同学调试时直接看报错行，但编译原理的错误往往在更早的阶段就埋下了。我自己的习惯是在tokenize()返回前打印整个 Token 列表，格式是类型:值，每行一个。在parse()返回前打印 AST 的括号表示，比如(+ 1 (* 2 3))。这样一眼就能看出是词法切错了还是语法结合错了。打印语句在提交前删掉或改成日志级别，避免影响性能。这个习惯帮我省下了至少三个通宵的调试时间，希望帮到你。

本文还有配套的精品资源，点击获取