简介：编译原理课程中语法分析环节的典型实验资料，聚焦自上而下的递归下降分析法。资料完整展示了从文法改造、消除左递归、求解FIRST与FOLLOW集以验证LL(1)条件，到结合词法分析器（扩展float关键字识别）构造递归下降分析程序的整个过程，并附有可运行的Java代码与运行结果。适合正在学习编译原理、需要完成类似实验或想理解递归下降分析器实现细节的高校学生及自学者参考，也可作为课程设计或实验报告的写作蓝本。资源包为1个doc文档，大小80KB，内容包含实验目的、题目要求、改造后的文法、FIRST/FOLLOW集合表、完整程序代码及结果截图。目前已由531人学习下载，内容详实且组织清晰，对于希望快速掌握自上而下语法分析实践方法、独立完成同类实验的读者具有不错的参考价值。
1. 语法实验最卡的一关：为什么递归下降分析值得亲手写一遍
做编译原理实验，多数人卡住的不是词法分析，而是语法分析。拿到的文法稍微带点括号、优先级，手写递归下降就各种翻车：要么无限递归栈溢出，要么匹配错分支返回一堆错误。递归下降分析是“自上而下语法分析”里最直观、最不需要查表的一类方法——每个非终结符对应一个分析函数，文法产生式长什么样，代码就怎么写。这个实验能帮你把 FIRST 集、FOLLOW 集、左递归消去这些抽象概念一次性落到具体代码上，跑起来能看到分析树，也能看到每一步匹配的 Token 流。适合正在做编译原理课程实验的学生，也适合想快速捡回语法分析手感、准备手写解析器的从业者，比如要做配置解析、DSL 解释器的人。下面我把这个实验从文法设计到代码实现、从测试到踩坑完整拆开讲。
2. 设计一个适合递归下降的表达式文法：先把左递归和回溯问题解决掉
递归下降分析的第一个坑不在代码里，而在文法的设计上。很多教材直接给出这样的表达式文法：
E → E + T | T
T → T * F | F
F → (E) | id
这个文法符合人的数学直觉，也适合做 EBNF 讲解，但它不能直接拿来做递归下降分析，原因是它包含直接左递归。如果照着这条文法写分析函数 parseE，第一件事就是调用 parseE，然后无限递归，一跑就爆栈。递归下降分析要求每个非终结符在最开始就能根据当前 Token 决定走哪个产生式，也就是说必须先消除左递归、提取公共左因子，把它改写成 LL(1) 可用的形式。
2.1 消除左递归后的标准表达式文法长什么样
对上面的左递归文法做消除处理，把 E 的产生式改写为右递归形式，得到如下经典文法：
E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id这样改写之后，每个非终结符对应的产生式之间都有明确的 FIRST 集区分。E 只有一个产生式，开头一定是 T；E' 的两个产生式一个以 + 开头，一个是空串，用当前 Token 是不是 + 就能判定。这是递归下降分析能顺利写下去的前提条件。设计文法时要逐个检查：是否存在左递归，是否有多个产生式开头 Token 相同，是否有产生式能推导出空串但 FOLLOW 集和别的产生式冲突。
实际做实验时，用一个简单表达式文法最省事，但也最容易出现的问题是把 id 定义得过窄，比如只支持单个字母 a。测试时写 a+a*a 没问题，换成 var1+var2 就报错，因为词法分析器把 var1 识别成一个整体 id 还是三个 Token 会直接影响分析结果。我们后面实现时会做一个小型的数字表达式，直接支持多位数和变量名，省掉这套边界问题。
2.2 先画递归调用树再写代码：把设计图落到纸面上
写递归下降代码之前，习惯性做法是先把分析树的调用关系画出来。一个输入串id + id * id，经过文法推导后，递归下降分析的调用树是：外层 parseE 调用 parseT 和 parseE'，parseT 调用 parseF 和 parseT'，parseF 匹配到 id 后返回，parseT' 发现当前 Token 不是 * 便接受空串返回，以此类推。把这个调用顺序写成中序遍历，得到的叶子节点恰好事后还原出原来的 Token 序列。
我一般会先画这样一棵调用树，然后对着它写三个函数的骨架：parseExpression、parseTerm、parseFactor。有了调用关系，每个函数里什么时候取 Token、什么时候匹配 Token、什么时候允许空串返回，都一目了然。跳过这一步直接写代码，十有八九会出现 Token 匹配错位的情况——后面的函数把前面的 Token 吃掉了，然后报一个让人摸不着头脑的语法错误。
3. 用 Java 实现递归下降分析器：核心代码与运行结果逐段解读
实验要求一般是“含代码和结果”，下面给出一份可以直接跑通的 Java 实现。词法分析部分我们做得很轻量：接受输入字符串，逐个字符扫描，把数字和标识符提取成 Token，运算符和括号单独成 Token。语法分析部分按照上面消除左递归后的文法实现三个核心函数，外加一个错误恢复机制。
3.1 最小可用的词法分析器：Token 类型与扫描逻辑
代码首先定义 Token 枚举和词法扫描器。这里的 Token 类型只做四种：数字、标识符、运算符（+、-、*、/）、括号。关键字和分号这类不做，实验范围外的东西不引入。
enum TokenType { NUMBER, ID, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } class Token { TokenType type; String text; int pos; Token(TokenType type, String text, int pos) { this.type = type; this.text = text; this.pos = pos; } public String toString() { return type + "(" + text + ")@" + pos; } }词法扫描器逐个字符读入，遇到空白跳过，遇到数字就连续读直到非数字字符，遇到字母就连续读直到非字母数字字符，遇到运算符和括号直接生成对应 Token。这样能保证123 + abc * (456)这样的输入被正确切分成六个 Token 加一个结束符。扫描器的位置信息要保留，后面报错时能直接告诉用户是第几个字符附近出了问题。
class Lexer { String input; int pos = 0; Lexer(String input) { this.input = input; } Token next() { while (pos < input.length() && Character.isWhitespace(input.charAt(pos))) { pos++; } if (pos >= input.length()) { return new Token(TokenType.END, "<EOF>", pos); } char ch = input.charAt(pos); if (Character.isDigit(ch)) { int start = pos; while (pos < input.length() && Character.isDigit(input.charAt(pos))) { pos++; } return new Token(TokenType.NUMBER, input.substring(start, pos), start); } if (Character.isLetter(ch)) { int start = pos; while (pos < input.length() && Character.isLetterOrDigit(input.charAt(pos))) { pos++; } return new Token(TokenType.ID, input.substring(start, pos), start); } pos++; switch (ch) { case '+': return new Token(TokenType.PLUS, "+", pos - 1); case '-': return new Token(TokenType.MINUS, "-", pos - 1); case '*': return new Token(TokenType.STAR, "*", pos - 1); case '/': return new Token(TokenType.SLASH, "/", pos - 1); case '(': return new Token(TokenType.LPAREN, "(", pos - 1); case ')': return new Token(TokenType.RPAREN, ")", pos - 1); default: throw new RuntimeException("无法识别的字符 '" + ch + "' 在位置 " + (pos - 1)); } } }这里有个细节：pos++放在 switch 前面，返回 Token 时用pos - 1作为起始位置，这是为了统一处理单字符 Token 的位置。对多位数数字，start 保存起始位置，pos 已经移动到下一个字符。这样扫描后的 Token 流自带定位信息，语法分析报错时可以直接回显具体位置。词法部分做到这个程度，已经足够支撑递归下降实验，不需要引入状态机或正则库。
3.2 递归下降核心：三个函数一个套路
语法分析器维护一个 Token 队列和一个当前指针。核心函数只有三个：parseExpression 处理加法和减法，parseTerm 处理乘法和除法，parseFactor 处理数字、标识符和括号内表达式。每个函数的写法遵循统一模式：先调用低层函数，然后循环检查当前 Token 是否属于自己的运算符，是则匹配并继续循环，否则把当前 Token 留给上层函数。这种模式叫“循环替代递归”，比反复调用 E' 函数更直观，也不容易写错。
class Parser { Lexer lexer; Token lookahead; Parser(Lexer lexer) { this.lexer = lexer; this.lookahead = lexer.next(); // 预读第一个 Token } void match(TokenType type) { if (lookahead.type != type) { throw new RuntimeException("语法错误：期望 " + type + "，实际遇到 " + lookahead.text + " 在位置 " + lookahead.pos); } lookahead = lexer.next(); // 匹配成功后读取下一个 Token } // E -> T { (+|-) T } void parseExpression() { parseTerm(); while (lookahead.type == TokenType.PLUS || lookahead.type == TokenType.MINUS) { match(lookahead.type); parseTerm(); } } // T -> F { (*|/) F } void parseTerm() { parseFactor(); while (lookahead.type == TokenType.STAR || lookahead.type == TokenType.SLASH) { match(lookahead.type); parseFactor(); } } // F -> NUMBER | ID | '(' E ')' void parseFactor() { if (lookahead.type == TokenType.NUMBER || lookahead.type == TokenType.ID) { match(lookahead.type); } else if (lookahead.type == TokenType.LPAREN) { match(TokenType.LPAREN); parseExpression(); match(TokenType.RPAREN); } else { throw new RuntimeException("语法错误：意外的 Token " + lookahead.text + " 在位置 " + lookahead.pos); } } void parse() { parseExpression(); if (lookahead.type != TokenType.END) { throw new RuntimeException("语法错误：多余的内容 '" + lookahead.text + "' 在位置 " + lookahead.pos); } } }这段代码的 key point 在 match 函数：它先对比当前 Token 类型，一致则消费并预读下一个，不一致则直接抛异常。这个“预读一个 Token”的设计，让每个分析函数随时知道自己接下来面对的是什么，不需要回溯。比如 parseExpression 调用 parseTerm 之后，如果当前 Token 是 +，说明后面还有一层 Term 要解析；如果是别的东西，说明 Expression 已经结束了，控制权交还给调用者。
3.3 让结果可见：输出分析过程和最终判定
实验要求“含结果”，至少要输出两类结果：一是每个产生式的展开过程，二是最终的分析成功判定。可以加一个很简单的 trace 开关，在进入每个 parse 函数时打印当前层级、当前 Token 和匹配动作，这样能看到完整的推导流程。
void traceEnter(String rule) { System.out.println(indent + rule + " [当前Token: " + lookahead.text + "]"); indent += " "; } void traceExit(String rule) { indent = indent.substring(2); System.out.println(indent + "/" + rule); }在 parseExpression 等函数开头调用 traceEnter，返回前调用 traceExit，跑一遍a + b * (c + 1)，输出里就能看到：parseExpression 进入时当前 Token 是 id(a)，parseTerm 进入时还是 id(a)，parseFactor 匹配 id(a) 后 lookahead 变成 +，parseTerm 退出，parseExpression 看到 + 进入 while 循环…… 这个过程和教材上的最左推导几乎逐行对应。把这段输出配合输入串一并写在实验报告里，就是一个很有说服力的“结果”。
4. 让测试用例覆盖全部产生式：设计打表验证的正确姿势
只跑一条id + id过不了实验验收，因为老师会检查你的分析器是不是真的覆盖了整个文法。测试用例设计至少要覆盖以下五类情况：单一因子、左结合运算、右结合或嵌套括号、运算符优先级、错误输入。下面直接给出我习惯用的测试输入清单和预期行为，照着用即可。
| 输入串 | 预期结果 | 覆盖点 |
|---|---|---|
123 | 成功 | 最小表达式，只有 Factor |
a+b*c | 成功 | 乘法优先级高于加法 |
(a+b)*c | 成功 | 括号改变优先级 |
a*(b+c/(d-1)) | 成功 | 嵌套括号、递归下降回退 |
a+b* | 失败，报错位置在末尾 | 缺少操作数 |
(a+b | 失败，报错位置在末尾 | 括号不匹配 |
a b | 失败，报错位置在 b | 两个相邻 id 缺少运算符 |
用这份表测试时，重点观察失败场景的错误位置是否准确。如果报错位置离真正出错点隔了好几个 Token，说明你的 match 函数预读逻辑写错了，或者某个 parse 函数提前消费了不该消费的 Token。错误定位的准确性是递归下降实现是否正确的直观标尺，也是实验报告里最好写的一段分析。
5. 递归下降分析避坑指南：四个高频翻车点与排查方法
做完上面这套代码，你已经能跑通基本实验了。但实验报告和答辩环节最常被问到的不是“代码怎么写的”，而是“出错时怎么处理”“某个输入为什么分析失败”。下面四条是我自己写这个实验时踩过、也在帮学弟学妹调代码时反复见过的坑。按“现象 → 原因 → 解决”的顺序写，排查时直接对号入座。
5.1 无限递归导致栈溢出
现象：运行程序后抛出 StackOverflowError，或者程序卡死几秒后崩溃。
原因：文法存在左递归没消除，或者写代码时把三个函数写成了相互直接调用。最常见的是直接照着 E→E+T 的原文法写parseExpression第一行就调用parseExpression。
解决：先把文法改写为右递归形式，再来写代码。注意“间接左递归”同样致命，比如 A→B、B→A x 这种两个非终结符互相引用，也必须先消去。排查的时候在 parseExpression 函数入口打印一行日志，如果日志无限刷屏，基本可以确定是这个问题。
5.2 回溯导致重复解析但 Token 已被消费
现象：对某些输入能够正确识别，但对另一些输入抛出“期望 XXX，实际遇到 YYY”的错，而且错误位置明显偏后。
原因：文法存在公共左因子，比如两个产生式都以同一个 Token 开头，分析器先选了第一个分支，匹配一部分后失败，但 Token 已经消费掉了，无法回到进入分支前的位置重新尝试。
解决：先检查文法是否需要提取公共左因子，然后检查代码中每个 if 分支的条件是否互斥。递归下降的“下降”必须保证每个非终结符在入口处就能确定走哪个分支，因为它的核心机制是预读而不是回溯。如果你想偷懒加一个 try-catch 实现回溯，可以，但要小心 Token 流的状态备份和恢复，否则只能掩盖问题。更干净的做法是把文法改成 LL(1)，让每个分支的 FIRST 集不相交。
5.3 空产生式的处理时机错位
现象：分析a+这类缺操作数的输入时，程序没有报错反而分析成功。
原因：如果你的文法里有 E'→+ T E' | ε 这种空产生式，代码里处理空串的时机太早——看到当前 Token 不是 E' 的 FIRST 集成员就直接返回空，但此时当前 Token 可能是根本不该出现的非法字符。
解决：判断空产生式之前，必须先确认当前 Token 是不是合法的 Follow 集合成员。比如我们的循环实现里，parseExpression 的 while 循环只在当前 Token 是 + 或 - 时才继续，否则直接返回。这样如果有非法 Token 残留，最终的 parse 函数会在检查 END 类型时抛出“多余的内容”。排查时可以在 parse 方法末尾的 END 校验处打印当前 Token，看是不是非法残留。
5.4 运算符优先级在递归下降里被反转
现象：输入a+b*c，有人期望得到(a+b)*c即从左到右求值，但程序输出的是a+(b*c)的意义，或者反过来。
原因：递归下降分析本身就通过函数调用层级来表达优先级。parseExpression 调用 parseTerm，说明 Term 的优先级更高，会先被归约。如果把 parseTerm 里的乘除循环写在 parseExpression 之前，或者把三个函数的调用关系写反了，优先级就反了。
解决：用文法推导树检验。画出a+b*c的分析树，如果根节点是加号、左子树是 a、右子树是 b*c，说明优先级正确。如果根节点是乘号，说明调用层级反了，把 parseExpression 和 parseTerm 的循环内容互换即可。这个错误在代码里很难一眼看出来，画树是最高效的验证办法。
6. 让实验报告更完整：给输出上 AST 显示与错误恢复插件的收尾技巧
基本功能跑通后，如果想在实验验收时拿到更高的完成度评价，我给两个小的进阶改进方案：一是输出抽象语法树，二是实现简单的错误恢复。这两个都不需要大改现有代码，却能显著提升实验的完整度。
AST 输出的做法是在现有三个 parse 函数中增加返回值。parseFactor 返回一个节点，内容为数字或标识符；parseTerm 把 parseFactor 返回的节点和后续乘除运算组合成一棵子树；parseExpression 同理。最后把根节点打印出来，格式可以设计成(+ (* a b) c)这种 S 表达式。这样表的左结合性、右结合性、优先级在 AST 上一目了然。
class ASTNode { String op; List<ASTNode> children = new ArrayList<>(); ASTNode(String op) { this.op = op; } public String toSExpr() { if (children.isEmpty()) return op; StringBuilder sb = new StringBuilder("(").append(op); for (ASTNode child : children) { sb.append(" ").append(child.toSExpr()); } return sb.append(")").toString(); } }把这个 ASTNode 接入 parseTerm：循环内遇到 * 或 / 时，把已经解析的 left 节点和新的 parseFactor 结果组合成一个新节点，继续循环。最终返回的节点就是整个 Term 的子树。打印a+b*c，输出为(+ a (* b c))，实验报告里可以直接解释这棵树的含义，比单独丢一段匹配日志更有说服力。
错误恢复的常见做法是给 Parser 增加一个同步集合 syncSet，包含上层函数期待的 Token 集合。当 match 抛出异常时，跳过当前 Token 流直到遇到 syncSet 中的元素，再恢复分析。这样做让一个输入串里能连续报告多个错误位置，而不是在第一个错误处直接退出。具体实现就是在 catch 块里循环调用 lexer.next 直到 Token 类型属于 syncSet 或到达 END 标记。
import java.util.Set; class ErrorRecoveringParser extends Parser { Set<TokenType> syncSet = Set.of(TokenType.PLUS, TokenType.RPAREN, TokenType.END); void recover() { while (!syncSet.contains(lookahead.type)) { lookahead = lexer.next(); } } }有了错误恢复，输入a+*b会先报“期望操作数但遇到 *”，然后跳过 * 继续分析 b，最终还能给出“表达式不完整”的提示。这个技巧在真实编译器的语法分析阶段几乎都会用到，实验里提前做出来，答辩时能聊的深度完全不一样。
我自己的习惯是，每完成一个语法分析实验，都会跑一遍那七条测试用例，把成功和失败的全部输出贴进实验报告，失败用例的报错位置标在原始输入串上。这个动作看着简单，实际上是在验证两件事：分析器没有吞 Token，错误定位没有飘。递归下降分析的能力边界也就是这两条——预读一个 Token，不回溯，能自顶向下构造分析树。守住这个边界，这套方法在配置解析器、脚本解释器、甚至 SQL 的 WHERE 子句解析里都能直接用。希望这篇文章能帮你的语法分析实验少走几段弯路，一次跑通。
本文还有配套的精品资源，点击获取
