简介这份编译原理实验文档面向学习语法分析与编译器构造的高校学生聚焦自上而下的递归下降分析。内容以简单语言文法为对象覆盖函数体、声明语句块与表达式等规则完整记录实验目的、题目文法、消除直接与间接左递归、改写产生式、计算各非终结符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 各代表什么原始文法用的是中文非终结符写起来又长又难对齐所以实验里把它换成了单字母这套映射关系必须先记住否则后面看代码会一脸茫然单字母原非终结符含义A函数体一对花括号包起来的整体M声明语句块零条或多条声明P声明语句一条声明D数据类型int 或 floatN可执行语句块零条或多条语句Q赋值语句一条赋值E / G表达式/表达式加减层T / H表达式2/表达式2乘除层F表达式3括号、标识符、整数词法层面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 集不相交。先把表算出来产生式FIRST 集FOLLOW 集A → { M N }{#M → ε | P Mt, f, εi, }P → D i ;t, ft, f, i, }D → t | ft, fiN → ε | Q Ni, ε}Q → i E ;ii, }E → T G(, i, d;, )G → T G | - T G | ε, -, ε;, )T → F H(, i, d, -, ;, )H → * F H | / F H | ε*, /, ε, -, ;, )F → ( E ) | i | d(, i, d*, /, , -, ;, )推导过程里最容易出错的是 ε 的传递。规则很简单若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 MapString, 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就是只读不推进的matchprivate 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 Nstatic 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 然后落到标识符分支改了编码没同步改语法分析侧的tokenClassfloat会带着种别码 26 出现在 token 流里而递归下降只认t/fD()直接返回 false。另外isLetter一开始的边界判断如果写成Character.isLetter中文注释会被切成标识符表现成「莫名其妙多出一个 i」。解决关键字只维护一份MapString, IntegertokenClass从这张表派生加新关键字改一处就够。isLetter、isDigit老老实实写 ASCII 区间判断把中文拒之门外。5.5 现象同一份输入换台机器结果不一样原因路径硬编码成绝对路径形如D:\...\ex.txt换台机器文件找不到或者源文件编码不是 UTF-8FileReader用平台默认编码读中文注释变成乱码乱码字节又变成一堆「无法识别的字符」。还有一种更隐蔽的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()的循环条件从表里查。手写分支胜在直观、调试方便表驱动胜在加新产生式不用改代码。我一般保留手写版做参考实现再写一个表驱动版做交叉验证——两套结果对不上一定是其中一套的表或分支写错了这种互验比单测还灵。最后一条血泪经验改文法之前先把测试用例集建起来。至少覆盖「只有声明」「只有语句」「混合」「空函数体」「嵌套括号」「缺右花括号」这六类每加一条产生式就补一组。递归下降的失败往往不是崩在改动点上而是崩在某个毫不相干的输入上——因为 ε 分支的判断条件被悄悄影响了。从那以后我每次动文法都强制先把这套用例跑一遍再提交省下来的调试时间远比写用例的时间多。希望帮到你。本文还有配套的精品资源点击获取