简介：这份编译原理实验文档面向学习语法分析与编译器构造的高校学生，聚焦自上而下的递归下降分析。内容以简单语言文法为对象，覆盖函数体、声明语句块与表达式等规则，完整记录实验目的、题目文法、消除直接与间接左递归、改写产生式、计算各非终结符FIRST集和FOLLOW集并验证LL(1)性的过程；同时说明在词法分析器中加入float关键字识别、设置种别编码26的方法，并给出Java递归下降分析程序及运行结果，便于对照理解各递归函数与产生式的对应关系。资源包共1个doc文件，约80KB，篇幅紧凑，适合课程实验报告参考、考前复习与动手复现。已有534人学习，可帮助读者把文法改造、集合计算、词法衔接和语法分析代码串联起来，并排查常见解析失败问题。

1. 递归下降不是玄学：两百行 Java 手写一个能跑通的语法分析器

先说个反直觉的结论：编译原理课里最难落地的不是理论，而是把一张 FIRST/FOLLOW 表翻译成能跑通的代码。这份实验工程做到了——一段不到两百行的 Java，先用手写词法分析器把源码切成种别码序列，再用九个互递归函数把{ int a; a = 1 + 2 * 3; }这样的输入整个吃掉。它适合两类人：正在被递归下降实验卡住的在校生，和想给自研 DSL、配置语言补一个最小解析器、又不想为这点需求引入 ANTLR 的工程开发。整套东西零第三方依赖，纯 JDK 加一个文本输入文件，编译原理里词法分析器和语法分析这两块被压成了一个可以单步调试的样本，断点打在哪个函数上，你就能看见游标停在哪。

2. 文法改造与 LL(1) 判定：从带左递归的产生式到 FIRST/FOLLOW 表

2.1 先认清符号约定：A/M/P/D/N/Q/E/T/F 各代表什么

原始文法用的是中文非终结符，写起来又长又难对齐，所以实验里把它换成了单字母，这套映射关系必须先记住，否则后面看代码会一脸茫然：

词法层面，i代表标识符、d代表整数常量、t代表int、f代表float，界符{ } ( ) = + - * / ;直接用字符本身当种别。这套「用元字符代替种别码」的约定非常省事，递归下降里所有判断都写成list.get(index).equals("t")这样的字符串比较，调试时打印出来一眼能看懂，不用回头查编码表。代价是有额外一次字符串比较开销，但对一个几百 token 的实验输入来说完全可以忽略。

原始文法的表达式部分是典型的二义性写法：E → E + T | E - T | T，左递归明晃晃摆在那里。直接照着写递归下降，E()的第一件事就是调用E()，栈会一路涨到 StackOverflowError。所以改造是必须的，不是可选步骤。

2.2 消除左递归：两条直接左递归和一条被误认的右递归

加减层和乘除层各有一条直接左递归，标准改法是引入新非终结符，把左递归变成右递归：

改造前： E → E + T | E - T | T T → T * F | T / F | F 改造后（新非终结符记作 G、H）： E → T G G → + T G | - T G | ε T → F H H → * F H | / F H | ε F → ( E ) | i | d

这套改写的好处不只是消除左递归，它顺手把运算符优先级也编码进去了：E管加减、T管乘除、F管原子，三层下来1 + 2 * 3天然按1 + (2 * 3)结合，不需要额外写优先级爬升逻辑。很多人第一次写表达式解析时喜欢在一个函数里堆if (op == '+')的判断，最后发现括号和优先级搅在一起改不动，问题就出在没做这层分层。

声明块和语句块这两条要特别说清楚，它们不是左递归：

M → ε | P M // 右递归，M 出现在 P 的右边 N → ε | Q N // 右递归

右递归在递归下降里反而是最舒服的形态，它可以直接改写成while循环，既省栈又直观。但原始代码偏偏把它写成了递归调用，还配了一个全局flag去控制退出——这就是后面死循环的根源。我在第 4 章会给出迭代版写法，这里先记住结论：左递归必须改，右递归可以留，但能改迭代就改迭代。

2.3 FIRST 集与 FOLLOW 集：一张表验证 LL(1)

改造完文法只是第一步，还得证明它是 LL(1) 的，否则递归下降在某些输入上会出现「不知道选哪个产生式」的岔路。判据有两条：同一个非终结符的多个候选式，FIRST 集两两不相交；含 ε 的候选式，其 FIRST 集（去掉 ε）与所属非终结符的 FOLLOW 集不相交。

先把表算出来：

推导过程里最容易出错的是 ε 的传递。规则很简单：若X → α Y β，则 FOLLOW(Y) 包含 FIRST(β) 去掉 ε；若 β 能推出 ε（包括 β 为空），则 FOLLOW(Y) 还要并上 FOLLOW(X)。举个具体例子，M → P M这一条里 P 在 M 之前，所以 FOLLOW(P) 要先拿到 FIRST(M) 去掉 ε 的部分，也就是{t, f}；又因为 M 可空，FOLLOW(P) 还得并上 FOLLOW(M) ={i, }，最终是{t, f, i, }。

按这张表逐条检查，G的两个非 ε 分支 FIRST 是{+}和{-}，不交，且都和 FOLLOW(G) ={;, )}不交；F三个分支 FIRST 是{、i、d，两两不交。所有非终结符都过关，文法确实是 LL(1) 的，可以放心写递归下降。

提示：网上流传的 FIRST/FOLLOW 表经常漏掉}这一项，原因是算到M时忘了N → ε这条路径会把A右花括号传上来。表算错，代码里 ε 分支的判断条件就跟着错，最后表现为「正确输入被判失败」，而且极难查。手算完之后，我一般会拿几组边界输入反推一遍，确认 ε 分支真的被走到了。

3. 词法分析器：字符流怎么变成 t/f/i/d 这四类种别码

3.1 种别码表：先把「编码」和「类标记」两层分开

实验要求里有一条很具体的约束：词法分析器要新增识别关键字float，单词种别编码设为 26。但递归下降那边只认t和f两个标记，直接混用会乱。成熟的写法是分成两层：底层按实验要求维护真实的种别码，上层给语法分析器一份它能看懂的类标记。

// 关键字 -> 种别码。实验要求 float 固定为 26，其余按前置词法分析实验的约定编号 private static final Map<String, Integer> KEYWORDS = new HashMap<>(); static { KEYWORDS.put("int", 1); KEYWORDS.put("if", 3); KEYWORDS.put("void", 4); KEYWORDS.put("main", 5); KEYWORDS.put("float", 26); // 新增：float 单独编号，不能和标识符混在一起 } // 语法分析器视角的类标记：把关键字压扁成 t/f，其他一律当标识符 i private static String tokenClass(String word) { if ("int".equals(word)) return "t"; // 数据类型 int if ("float".equals(word)) return "f"; // 数据类型 float if (KEYWORDS.containsKey(word)) { return word; // 文法里没有 if/void/main，原样保留，便于报错 } return "i"; // 普通标识符 }

tokenClass返回word而不是i这点是有意为之：文法的产生式里根本不出现if、void、main，如果把它们也当成标识符i，递归下降会在Q → i = E ;这条路上试着把if当左值，然后在一堆莫名其妙的位置失败。原样保留，语法分析阶段遇到不认识的种别直接报错，错误位置就精准得多。

整数常量统一归到d，值本身不保留。这在纯语法分析实验里没问题，但一旦要做语义分析、常量折叠或者类型检查，d就必须带上字面值了，这是二次开发时第一个要动的点。

3.2 扫描循环：手写状态机比正则更值得学

词法分析器主体就是一个手写的字符状态机，按「跳过空白 → 读标识符/关键字 → 读整数 → 读界符」的顺序分流：

public static void analyze(char[] chars) { int i = 0; while (i < chars.length) { char ch = chars[i]; if (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r') { i++; // 空白只做分隔，不产生 token } else if (isLetter(ch)) { StringBuilder sb = new StringBuilder(); // 标识符是「字母开头，后跟字母或数字」，一直吃到非字母数字为止 while (i < chars.length && (isLetter(chars[i]) || isDigit(chars[i]))) { sb.append(chars[i++]); } list.add(tokenClass(sb.toString())); } else if (isDigit(ch)) { // 整数常量：连续数字，整体只产出一个 d while (i < chars.length && isDigit(chars[i])) { i++; } list.add("d"); } else { // 界符直接用字符本身作为种别，省掉一张映射表 list.add(String.valueOf(ch)); i++; } } }

几个关键点值得展开。第一，内层while用chars[i]而不是先取出来再++i，这样循环退出时i恰好停在第一个不属于当前 token 的字符上，外层循环不需要任何回退。原始代码里用的是ch = chars[++i]再i--的写法，逻辑等价但极容易在下标边界上翻车。第二，i < chars.length这个边界检查不能省，原始实现靠new char[file.length() + 1]在数组末尾留一个默认的\0来兜底，一旦把输入源换成String.toCharArray()就会直接抛 StringIndexOutOfBoundsException。第三，界符不建表而是直接入列，+、-这些在文法里本来就是一个字符，多一层编码纯属自找麻烦。

isLetter和isDigit也值得一提，原始实现是手写区间判断：

public static boolean isLetter(char c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } public static boolean isDigit(char c) { return c >= '0' && c <= '9'; }

用Character.isLetter也能跑，但会把中文、全角字符一起放进来，导致一个中文注释变成一个「标识符」，然后在语法分析阶段报一个毫无意义的错误。手写 ASCII 区间判断在这个场景下反而是更稳的选择——不认识的字符老老实实走default分支报「存在无法识别的字符」，定位成本最低。

3.3 输入读取：File.length()这个坑比想象中深

原始代码读文件的方式是这样：

File file = new File("ex.txt"); FileReader reader = new FileReader(file); int length = (int) file.length(); // 这里是字节数，不是字符数 char[] buf = new char[length + 1]; reader.read(buf); reader.close();

File.length()返回的是字节数，FileReader.read()填进去的是字符数。纯 ASCII 源文件两者相等，看不出问题；源文件里只要有一个中文注释，字节数就比字符数大，缓冲区多出来的部分是\0，分析时多出一堆空字符（大部分被空白分支放过，但末尾的\0会撞进default分支直接System.exit(0)，连错误行号都不给）。

稳妥的读法是把「读多少」和「buffer 多大」解耦：

// 按实际读到的字符数处理，不猜文件大小 String src = java.nio.file.Files.readString(java.nio.file.Path.of("ex.txt")); analyze(src.toCharArray());

一行搞定，还顺手解决了编码问题（Files.readString默认 UTF-8）。练习阶段用哪个都行，但要清楚差别在哪，否则换台机器换份输入就复现不出来——这种「在我这儿是好的」的问题最消耗时间。

4. 递归下降分析器：九个函数如何吃掉一段函数体

4.1 声明块链路：A → M → P → D 与那个肇事的flag

先看入口A()，它对应A → { M N }，逻辑上是「吃{，处理声明，处理语句，吃}」：

static boolean A() { // A → { M N } if (!match("{")) return false; if (!M()) return false; // 声明块，可以为空 if (!N()) return false; // 语句块，可以为空 return match("}"); // 右花括号必须存在，缺了就是语法错 }

match是个小工具，负责「看一眼、对得上就前移、对不上就原地不动」：

private static boolean match(String expected) { // list 末尾已经追加了哨兵 "#"，所以 index 永远不会越界 if (list.get(index).equals(expected)) { index++; return true; } return false; }

match的关键在于它只在匹配成功时才推进index，失败时不回退也不推进。这一条保证了每个函数要么消费掉一段输入，要么什么都不做直接返回 false，调用者可以放心地用if (!X()) return false;链式串起来。

再看M()。原始实现是这样的：

static void M() { // M → ε | P M P(); if (flag == 1) M(); // 靠全局 flag 决定要不要继续递归 }

P()里如果匹配失败会把flag置 0，成功了却没人把它置回 1，于是flag的状态完全取决于更外层的某个赋值——这就是典型的用一个全局变量表达本该由返回值表达的失败信号。更麻烦的是D()的失败分支写了index--，把游标往回退一格，回去之后M()又调P()，P()又调D()，D()又失败又回退……游标原地打转，栈一路加深，表现出来就是程序卡死或者栈溢出。

改成「返回值 + 循环」的写法之后，问题自然消失：

static boolean M() { // M → ε | P M // 右递归直接转循环：只要下一个 token 能开始一条声明，就一直吃 while (peek("t") || peek("f")) { if (!P()) return false; } return true; // 一条声明都没有，走 ε 分支 } static boolean P() { // P → D i ; if (!D()) return false; if (!match("i")) return false; // 声明符：标识符 return match(";"); // 分号必须显式吃掉 } static boolean D() { // D → t | f if (match("t")) return true; return match("f"); }

peek就是只读不推进的match：

private static boolean peek(String expected) { return list.get(index).equals(expected); }

这里有一处原始实现漏掉的东西：P()只吃了i，没吃;。对单条声明看不出问题，两条声明连写int a; int b;的时候，第二个int前面横着一个没被消费的分号，M()的循环条件判断成 false，声明块提前结束，后面的int b;被丢给语句块去解析，报出「语法分析失败」但位置完全不对。每条产生式右部的终结符，一个都不能少，这是递归下降里最容易犯的错，因为漏掉一个符号往往要等到特定输入才暴露。

4.2 语句块与赋值：N 和 Q 怎么处理「一条都没有」

语句块的结构和声明块对称，N → ε | Q N：

static boolean N() { // N → ε | Q N while (peek("i")) { // 语句只有赋值语句一种，i 是它的唯一首符 if (!Q()) return false; } return true; } static boolean Q() { // Q → i = E ; if (!match("i")) return false; if (!match("=")) return false; if (!E()) return false; return match(";"); }

N()的循环条件写成peek("i")而不是peek("t") || peek("f")，是因为文法的语句块里只有赋值语句一种，而赋值语句的首符一定是标识符。这也意味着{ int a; }这种「只有声明没有语句」的输入是完全合法的，N()会直接返回 true 走 ε 分支，A()接下来去吃}。

这种「用一个 FIRST 集成员做循环条件」的写法在递归下降里非常常见，前提是该分支的 FIRST 集里所有符号都要覆盖到。现在语句块只有赋值，如果要加if语句或者while语句，循环条件就得同步扩成peek("i") || peek("if") || peek("while")，漏一个就解析不了。我一般会把这类条件抽成一个canStartStatement()方法，加新语句类型时只改一处。

4.3 表达式三层：E/G/T/H/F 里的优先级和括号递归

表达式部分是整套代码里最讲究的地方，三个层级各管一段：

static boolean E() { return T() && G(); } // E → T G static boolean G() { // G → + T G | - T G | ε while (peek("+") || peek("-")) { index++; // 消费掉运算符本身 if (!T()) return false; // 右边必须是一个完整的 T } return true; // 没有运算符，走 ε 分支 } static boolean T() { return F() && H(); } // T → F H static boolean H() { // H → * F H | / F H | ε while (peek("*") || peek("/")) { index++; if (!F()) return false; } return true; } static boolean F() { // F → ( E ) | i | d if (match("i") || match("d")) return true; if (match("(")) { if (!E()) return false; // 括号里递归回到最外层 return match(")"); // 左括号必须有配对 } return false; }

index++直接写在这里而不走match("+")，是因为match只能匹配一个固定字符串，而G()要处理+和-两个符号。想写得更整齐可以加一个matchAny("+", "-")返回匹配到的符号，但在这个规模下直接index++更省事，唯一的代价是它依赖「循环条件刚刚确认过当前 token 就是运算符」这个前提，改动时别把这个前提破坏掉。

F()里的括号分支是整个递归下降里唯一一处「回头调用最外层」的地方，(1 + 2) * 3的解析路径是这样的：E → T → F看到(，消费掉，递归调E解析1 + 2，返回后必须匹配到)，然后回到H继续处理* 3。括号嵌套多深，调用栈就有多深，这是递归下降的固有特性，正常输入下没问题，但配上((((((...这类恶意输入就会栈溢出。二次开发里如果要处理不受信任的输入，括号深度得设个上限。

F()里match("i") || match("d")的短路求值也用得恰到好处：match("i")匹配成功就已经推进了index，后面的match("d")根本不会执行；失败时match不推进游标，第二个判断才有意义。如果把这两个判断拆成独立的if，就得自己保证「失败不推进」这个约定不被破坏。

4.4 main 的装配：三行代码决定成败判定

把上面这些函数串起来的就是main，逻辑非常短：

public static void main(String[] args) throws Exception { String src = java.nio.file.Files.readString(java.nio.file.Path.of("ex.txt")); analyze(src.toCharArray()); // 第一步：词法分析，产出种别码序列 list.add("#"); // 追加哨兵，让所有 peek/match 都不用判越界 System.out.println("词法分析后，程序转化为：" + list); boolean ok = A(); // 第二步：从开始符号解析 // 第三步：必须两个条件同时成立——A 返回成功，且输入被完整消费 if (ok && index == list.size() - 1) { System.out.println("文法分析成功！"); } else { System.out.println("文法分析失败！"); } }

判断条件里index == list.size() - 1是很容易漏的一环。只判A()的返回值不够：A()只保证「从当前位置开始能解析出一个函数体」，多出来的}或者后面的垃圾字符它是看不见的，{ int a; } }这种输入照样能过。补上「游标走到了哨兵位置」这个条件，才算真正校验了整段输入。加了哨兵#之后，list.size() - 1正好就是哨兵的索引，所有peek、match都不会越界，省掉一堆index < list.size()判断。

5. 避坑与排查：递归下降实现里最容易翻车的五个现场

5.1 现象：程序不退出，或者直接 StackOverflowError

原因：M()、P()、D()三个函数互相递归，但某一轮里没有任何一个成功消费 token。原始实现的D()失败分支写了index--，回退之后调用链重新进入，index推进不上去，形成无限递归。用全局flag传递失败信号还会让问题更隐蔽——flag是 0 还是 1 取决于最后一次赋值，中间某次成功了没人置回 1，外层就误以为还可以继续。

解决：一是把所有分析函数改成返回boolean，失败立刻return false，让调用栈自然展开；二是加一条不变量断言，每次进入产生式函数时记下index，退出时检查它有没有前进（ε 分支除外）：

// 调试期用：同一个非终结符两次进入之间必须至少消费一个 token private static void assertProgress(int before, String nonTerminal) { if (index == before && !"M".equals(nonTerminal) && !"N".equals(nonTerminal)) { throw new IllegalStateException(nonTerminal + " 没有消费任何 token，检查产生式"); } }

这条断言在这类代码里救过我很多次，ε 分支会误报，所以只对非空产生式开，跑通之后再关掉。

5.2 现象：IndexOutOfBoundsException，而且报错位置飘忽

原因：list.get(index)没有任何越界保护。输入{ int a;（缺右花括号）这种半截文本时，游标走到了序列末尾还在get，直接抛异常。更麻烦的是原始实现里读文件用new char[(int) file.length() + 1]，File.length()给的是字节数，源文件里有中文时缓冲区多出一截\0，这些\0会进到default分支触发System.exit(0)，程序静默退出，什么信息都不给。

解决：词法分析产出的 list 末尾追加一个哨兵#，它不会和任何合法 token 冲突，所有peek、match都不会越界；读文件改用Files.readString，直接拿字符串，不再猜大小。这两条改完，异常就从「飘忽的越界」变成「语法分析失败」，后者至少能定位。

5.3 现象：合法输入被判「文法分析失败」，但看不出哪一步错了

原因：多半是产生式右部的某个终结符被漏吃了，或者分支条件写窄了。典型例子是P()只吃了标识符没吃分号，单条声明能过、两条声明连写就崩；再比如N()的循环条件只写了peek("i")，一旦文法扩了新语句类型就漏。还有一类是第一/FOLLOW 表算错导致 ε 分支判断条件错，比如M的 FOLLOW 集漏了}，int a; }这种「声明后直接结束」的输入会被判失败。

解决：加一层带位置的错误输出，把「期望什么、实际是什么、游标停在哪」打出来，比一个布尔值有用十倍：

private static boolean expect(String expected, String where) { if (index < list.size() && list.get(index).equals(expected)) { index++; return true; } System.err.printf("%s 处期望 [%s]，实际读到 [%s]，token 位置 %d%n", where, expected, index < list.size() ? list.get(index) : "EOF", index); return false; }

P()里把match(";")换成expect(";", "P")，出错时立刻能看见是哪个产生式崩的。

5.4 现象：float被当成普通标识符，或者反过来报「无法识别的字符」

原因：关键字表和种别码映射是两份独立维护的表，加float的时候只改了其中一份。改isKey数组没同步改编码，float会返回 -1 然后落到标识符分支；改了编码没同步改语法分析侧的tokenClass，float会带着种别码 26 出现在 token 流里，而递归下降只认t/f，D()直接返回 false。另外isLetter一开始的边界判断如果写成Character.isLetter，中文注释会被切成标识符，表现成「莫名其妙多出一个 i」。

解决：关键字只维护一份Map<String, Integer>，tokenClass从这张表派生，加新关键字改一处就够。isLetter、isDigit老老实实写 ASCII 区间判断，把中文拒之门外。

5.5 现象：同一份输入，换台机器结果不一样

原因：路径硬编码成绝对路径（形如D:\...\ex.txt），换台机器文件找不到；或者源文件编码不是 UTF-8，FileReader用平台默认编码读，中文注释变成乱码，乱码字节又变成一堆「无法识别的字符」。还有一种更隐蔽的：for (int i = 0; i < chars.length - 1; i++)这种写法主动跳过最后一个字符，输入最后恰好是}的时候右花括号永远读不到，程序报失败，而你盯着文件看了半天也看不出哪少了。

解决：路径改成相对当前工作目录的ex.txt，用Files.readString显式按 UTF-8 读，循环上界用实际读到的字符数而不是length - 1。这三条是纯工程问题，和文法无关，但翻车的频率比文法错还高。

6. 二次开发：把这套实验代码推到能解析真实语法的程度

这套代码当「最小可运行样本」是合格的，但要拿去解析真实语法，第一个要动的是错误恢复。现在只要有一处匹配失败，整个流程就返回 false，用户拿到一个布尔值，不知道是第几个 token 出的问题，也没有办法一次报出多个错误。我的做法是把前面那个expect方法升级成带行号列号的Token对象：

// Token 里带上位置信息，报错才有意义 record Token(String kind, String text, int line, int col) {} private boolean match(TokenKind expected, String where) { Token t = tokens.get(pos); if (t.kind().equals(expected.name())) { pos++; return true; } // 简单恢复策略：跳到下一个分号或右花括号，继续解析后面的语句 errors.add(new ParseError(where, expected, t, t.line(), t.col())); while (pos < tokens.size() && !tokens.get(pos).kind().equals(";") && !tokens.get(pos).kind().equals("}")) { pos++; } return false; }

跳过分号再继续这个策略在「一条语句写错」的场景下效果很好，能一口气把整段代码的问题都列出来，而不是改一个跑一次。

第二个要动的是把boolean换成Node。现在这些函数只回答「对不对」，如果想让这套东西真有用，应该返回语法树节点，表达式节点带上运算类型和左右子节点，语句节点带上赋值目标。改法很机械：每个函数把return true换成return new XxxNode(...)，E()里被G()消费掉的运算符就是当前节点的算符。改完之后能干的活就多了——常量折叠、类型检查、生成三地址码，都建立在树上。

第三个方向是用表驱动替代手写分支。现在所有peek("t") || peek("f")的硬编码判断，都可以换成一张「非终结符 × 当前 token → 产生式编号」的 LL(1) 预测分析表，M()、N()的循环条件从表里查。手写分支胜在直观、调试方便，表驱动胜在加新产生式不用改代码。我一般保留手写版做参考实现，再写一个表驱动版做交叉验证——两套结果对不上，一定是其中一套的表或分支写错了，这种互验比单测还灵。

最后一条血泪经验：改文法之前先把测试用例集建起来。至少覆盖「只有声明」「只有语句」「混合」「空函数体」「嵌套括号」「缺右花括号」这六类，每加一条产生式就补一组。递归下降的失败往往不是崩在改动点上，而是崩在某个毫不相干的输入上——因为 ε 分支的判断条件被悄悄影响了。从那以后我每次动文法，都强制先把这套用例跑一遍再提交，省下来的调试时间远比写用例的时间多。希望帮到你。

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