简介这份资源是北京邮电大学计算机学院编译原理课程中词法分析与语法分析器的完整实现包面向正在学习编译原理、需要动手完成课程项目的计算机相关专业学生以及对编译器前端构建感兴趣的开发者。包内共12个文件以cpp源码、txt文法说明、md实验报告和c示例程序为主压缩包约27KB涵盖词法分析、LL与LR语法分析等核心模块并配有测试用例与设计文档。已有200人学习下载。读者可参考其中的自动机设计、正则表达式与上下文无关文法处理思路对照抽象语法树构建与语法错误检测的实现细节快速理解编译器前端的工作流程也可将其作为课程实验的对照方案用于调试自己的分析器或补充实验报告内容为后续语义分析与代码生成打下基础。1. 北邮计算机学院编译原理词法、语法分析器一份能跑通的实验底稿如果你正在搜「北京邮电大学计算机学院编译原理词法、语法分析器.zip」大概率不是想收藏一个压缩包而是被课程实验卡住了词法分析器写完了Token 流能出来但一接到语法分析就报错或者语法分析器能跑却不知道自己的 FIRST/FOLLOW 集算得对不对符号表该在哪一层挂。这个标题背后其实是一套完整的编译器前端最小闭环——词法分析把字符流切成 Token语法分析把 Token 流组织成语法树中间还要维护符号表。它适合两类人一是正在做编译原理实验、需要一份可对照的参考实现二是想从零手写一遍前端、但不想被某个特定框架绑死的工程师。我下面讲的不是某个压缩包里的代码而是这类实验最稳的落地路径你照着能自己搭出来也能拿它去校验你手里的那份实现。2. 词法分析器从字符流到 Token 流的最小实现2.1 为什么先定 Token 结构再写扫描逻辑很多人一上来就写while循环读字符结果写到一半发现关键字和标识符的边界处理不了回头改 Token 结构前面的代码全废。血泪经验是先把 Token 的类型枚举和数据结构定死再写扫描器。编译原理实验里常见的 Token 类型包括关键字、标识符、常量、运算符、界符每类对应一个枚举值。Token 结构至少要有类型、原始字符串、行号三样行号是后面报错定位的后悔药。// Token.java —— 先定结构再写扫描 public class Token { public enum Type { KEYWORD, IDENT, NUMBER, OPERATOR, DELIMITER, EOF } public Type type; public String lexeme; // 原始字符串报错时直接打印 public int line; // 行号语法分析报错定位靠它 public Token(Type type, String lexeme, int line) { this.type type; this.lexeme lexeme; this.line line; } Override public String toString() { return String.format(%s, %s, line%d, type, lexeme, line); } }这段代码的关键不在语法而在字段选择。lexeme保留原始字符串是为了后面语法分析做语义动作时不用回查源文件line是给报错用的没有它语法分析报「unexpected token」时你根本不知道去哪一行找。类型枚举里我一般会留一个EOF扫描到文件末尾时返回它语法分析器靠它判断输入结束比用null判断稳。2.2 手写扫描器的状态推进与关键字识别Token 结构定好后扫描逻辑就是一个确定有限自动机的手写版本。核心是维护一个当前位置指针每次根据当前字符决定进入哪个分支字母开头走标识符/关键字数字开头走常量符号走运算符匹配。关键字识别最简单的做法是先把标识符读出来再查一张关键字表命中就改类型。// Lexer.java —— 核心扫描循环 public class Lexer { private final String src; private int pos 0; private int line 1; private static final SetString KEYWORDS Set.of( if, else, while, for, int, float, return ); public Lexer(String src) { this.src src; } public Token nextToken() { skipWhitespace(); if (pos src.length()) { return new Token(Token.Type.EOF, , line); } char c src.charAt(pos); if (Character.isLetter(c)) return readIdentOrKeyword(); if (Character.isDigit(c)) return readNumber(); return readOperatorOrDelimiter(); } private Token readIdentOrKeyword() { int start pos; while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) { pos; } String word src.substring(start, pos); Token.Type type KEYWORDS.contains(word) ? Token.Type.KEYWORD : Token.Type.IDENT; return new Token(type, word, line); } private Token readNumber() { int start pos; while (pos src.length() Character.isDigit(src.charAt(pos))) { pos; } return new Token(Token.Type.NUMBER, src.substring(start, pos), line); } private Token readOperatorOrDelimiter() { char c src.charAt(pos); // 双字符运算符优先匹配比如 、、 if (pos src.length()) { char next src.charAt(pos); String two c next; if (two.equals() || two.equals() || two.equals() || two.equals(!)) { pos; return new Token(Token.Type.OPERATOR, two, line); } } Token.Type type -*/.indexOf(c) 0 ? Token.Type.OPERATOR : Token.Type.DELIMITER; return new Token(type, String.valueOf(c), line); } private void skipWhitespace() { while (pos src.length()) { char c src.charAt(pos); if (c \n) { line; pos; } else if (Character.isWhitespace(c)) { pos; } else break; } } }逻辑说明nextToken是唯一对外入口每次调用返回一个 Token语法分析器循环调用它就能拿到完整 Token 流。readIdentOrKeyword先按字母数字读满再查关键字表这样if和ifx不会混淆。readOperatorOrDelimiter里双字符优先匹配是必须的否则会被拆成两个语法分析阶段直接翻车。参数方面KEYWORDS集合按你实验要求的语言子集调整多一个少一个都会影响语法分析的分支判断line只在skipWhitespace里遇到换行时递增别在别处乱加。2.3 用测试用例验证 Token 流写完扫描器别急着接语法分析先单独验证 Token 流。我一般会准备三段输入纯关键字、混合标识符和常量、带双字符运算符的表达式。跑一遍看输出是否符合预期尤其是行号和双字符运算符。// LexerTest.java —— 最小验证 public class LexerTest { public static void main(String[] args) { String src int a 10;\nif (a 5) return a;; Lexer lexer new Lexer(src); Token t; do { t lexer.nextToken(); System.out.println(t); } while (t.type ! Token.Type.EOF); } }预期输出里int是 KEYWORDa是 IDENT是一个 OPERATOR 而不是两个第二行的if行号应该是 2。如果行号不对检查skipWhitespace里换行处理如果被拆开检查双字符匹配分支。这一步过了词法分析器就算立住了。3. 语法分析器递归下降与符号表的配合3.1 递归下降的选型理由与文法预处理语法分析常见做法有递归下降、LL(1) 表驱动、LR 系列。编译原理实验里最稳的是递归下降因为代码结构直接对应文法产生式调试时能一眼看出是哪条产生式出错。但递归下降要求文法不能有左递归也不能有公共左因子。所以动手前先做两件事消除左递归、提取左因子。比如表达式文法E - E T | T要改写成E - T EE - T E | ε。这一步不做递归下降会直接栈溢出。符号表在这一层的角色是当语法分析走到变量声明或引用时把标识符登记进去或查出来。我一般把符号表做成一个栈式结构进入作用域压一层退出弹一层这样能支持嵌套作用域。3.2 递归下降分析器的代码骨架下面是一个支持表达式和简单语句的递归下降骨架配合前面的 Lexer 使用。核心是每个非终结符对应一个方法方法内部按产生式右部依次匹配 Token。// Parser.java —— 递归下降骨架 public class Parser { private final Lexer lexer; private Token lookahead; // 当前向前看 Token private final DequeMapString, String scopes new ArrayDeque(); public Parser(Lexer lexer) { this.lexer lexer; this.lookahead lexer.nextToken(); scopes.push(new HashMap()); // 全局作用域 } private void match(Token.Type expected) { if (lookahead.type expected) { lookahead lexer.nextToken(); } else { throw new RuntimeException(String.format( 语法错误 line %d: 期望 %s, 实际 %s, lookahead.line, expected, lookahead.type)); } } // statement - decl | ifStmt | returnStmt public void statement() { if (lookahead.type Token.Type.KEYWORD) { switch (lookahead.lexeme) { case int: case float: decl(); break; case if: ifStmt(); break; case return: returnStmt(); break; default: throw new RuntimeException( 未知关键字 line lookahead.line); } } else { throw new RuntimeException( 非法语句开头 line lookahead.line); } } // decl - type ident ( expr)? ; private void decl() { String type lookahead.lexeme; match(Token.Type.KEYWORD); String name lookahead.lexeme; match(Token.Type.IDENT); scopes.peek().put(name, type); // 登记符号表 if (lookahead.type Token.Type.OPERATOR lookahead.lexeme.equals()) { match(Token.Type.OPERATOR); expr(); } match(Token.Type.DELIMITER); // 分号 } // expr - term ((|-) term)* private void expr() { term(); while (lookahead.type Token.Type.OPERATOR (lookahead.lexeme.equals() || lookahead.lexeme.equals(-))) { match(Token.Type.OPERATOR); term(); } } private void term() { if (lookahead.type Token.Type.NUMBER || lookahead.type Token.Type.IDENT) { match(lookahead.type); } else { throw new RuntimeException( 表达式错误 line lookahead.line); } } private void ifStmt() { match(Token.Type.KEYWORD); // if match(Token.Type.DELIMITER); // ( expr(); match(Token.Type.DELIMITER); // ) statement(); } private void returnStmt() { match(Token.Type.KEYWORD); // return expr(); match(Token.Type.DELIMITER); // ; } }逻辑说明lookahead是递归下降的核心它始终指向下一个待匹配的 Tokenmatch成功就推进失败就抛带行号的异常。decl里在匹配到标识符后立刻写入当前作用域这就是符号表最基础的登记动作。expr用循环处理左递归改写后的Eterm只处理最底层的数字和标识符。参数方面scopes用Deque模拟栈peek()拿当前作用域进入if或函数体时可以push新作用域退出时pop。报错信息里带上lookahead.line这是前面 Token 结构里留行号的回报。3.3 符号表的插入、查找与作用域管理符号表不是一张平表实验里至少要支持插入、查找、作用域进出三个操作。下面是一个最小实现配合上面的 Parser 使用。// SymbolTable.java —— 栈式作用域 public class SymbolTable { private final DequeMapString, Symbol scopes new ArrayDeque(); public static class Symbol { public String name; public String type; public int line; public Symbol(String name, String type, int line) { this.name name; this.type type; this.line line; } } public SymbolTable() { scopes.push(new HashMap()); // 全局作用域 } public void enterScope() { scopes.push(new HashMap()); } public void exitScope() { scopes.pop(); } public boolean insert(Symbol s) { MapString, Symbol cur scopes.peek(); if (cur.containsKey(s.name)) return false; // 重复定义 cur.put(s.name, s); return true; } public Symbol lookup(String name) { for (MapString, Symbol scope : scopes) { Symbol s scope.get(name); if (s ! null) return s; } return null; // 未定义 } }逻辑说明insert只查当前作用域允许内层遮蔽外层同名变量lookup从内到外逐层查找符合大多数语言的作用域规则。参数方面Symbol里的line用于报「重复定义」或「未定义」时定位。注意exitScope直接pop如果当前已经是全局作用域会抛异常调用方要保证进出配对。4. 避坑与排查词法语法分析器最常见的 5 个翻车点4.1 现象双字符运算符被拆成两个单字符原因扫描器在匹配运算符时没有做「向前看一位」的判断遇到就直接返回没检查下一个字符是不是。解决在readOperatorOrDelimiter里先尝试匹配双字符表命中再消费两个字符否则退回单字符逻辑。这个坑在语法分析阶段表现为「期望 OPERATOR 实际 DELIMITER」报错行号往往还对但就是过不去。4.2 现象递归下降栈溢出原因文法里存在左递归比如E - E T递归下降直接按产生式写就会无限调用expr()。解决动手写之前先做文法预处理消除左递归、提取左因子。改写后的E - T E用循环处理E就不会溢出。如果实验要求保留原文法那就得换 LL(1) 表驱动或 LR别硬用递归下降。4.3 现象符号表查不到刚声明的变量原因声明语句里先匹配了标识符但忘了在匹配后立刻insert或者insert写到了错误的作用域层。解决在decl方法里匹配完标识符马上调用symbolTable.insert并且确认当前scopes.peek()是声明所在的作用域。如果声明在if块里要确保进入块时enterScope已经调用。4.4 现象报错行号永远是 1原因line只在初始化时设了一次skipWhitespace里遇到换行没有递增或者递增了但 Token 构造时传的是旧值。解决在skipWhitespace里遇到\n就line并且所有new Token都传当前的line。测试时用多行输入验证第二行的 Token 行号必须是 2。4.5 现象关键字被识别成标识符原因关键字表不全或者查表时机不对——先返回了 IDENT 再查表。解决readIdentOrKeyword里先读满整个单词再查KEYWORDS集合命中才改类型。关键字表要和你实验要求的语言子集完全一致多一个少一个都会让语法分析的分支判断出错。5. 进阶把分析器接上语法树与错误恢复前面四章跑通的是「能识别、能报错」的版本但真正做实验时老师往往要求输出语法树甚至要求错误恢复后继续分析。我一般会在递归下降的每个非终结符方法里返回一个 AST 节点而不是只做匹配。比如expr返回ExprNodedecl返回DeclNode这样语法分析结束就能拿到一棵完整的树后面做语义分析或代码生成都有地方挂。// AstNode.java —— 最小 AST 节点 public class AstNode { public String label; // 节点名如 Decl、Expr public ListAstNode children new ArrayList(); public String value; // 叶子节点的原始值 public AstNode(String label) { this.label label; } public AstNode(String label, String value) { this.label label; this.value value; } public void addChild(AstNode child) { children.add(child); } }改造expr时把原来只做匹配的逻辑改成「匹配的同时构造节点」遇到就建一个Add节点左右子节点分别是前后两个term的返回值。这样递归下降的返回值就从void变成AstNode整棵树的形状和文法推导过程一一对应调试时打印出来一目了然。错误恢复是另一个进阶点。递归下降默认遇到错误就抛异常终止但实验里常要求「报错后跳到下一个分号继续」。做法是在statement层面加一层try-catch捕获异常后循环消费 Token 直到遇到;或}然后继续解析下一条语句。这样一次运行能报出多个错误而不是改一个跑一次。验证方法上我习惯准备一组「正确输入 三类错误输入」缺分号、括号不匹配、未定义变量。正确输入要能完整输出 AST错误输入要能报出准确行号和错误类型并且错误恢复后还能继续解析后面的语句。如果这三类都过了这份词法、语法分析器就达到了课程实验的验收标准也具备了继续往上做语义分析的基础。我自己做这类实验最大的教训是别一上来就追求大而全的文法先把最小子集跑通再逐个加产生式。每加一条就补一个测试用例翻车了立刻能定位到是哪条产生式的问题。这个习惯帮我省下了大量对着报错发呆的时间。希望帮到你。本文还有配套的精品资源点击获取