递归下降分析实验全流程：从文法改造到可运行分析器

简介这份资源面向计算机专业学习编译原理的学生聚焦自上而下语法分析中的递归下降分析法帮助读者完成从文法改造到分析程序实现的完整实验流程。压缩包内为1个doc文档约80KB集中呈现实验目的、文法规则定义、消除左递归后的产生式、各非终结符的FIRST集与FOLLOW集推导表格以及递归下降分析程序的Java代码与运行结果。内容围绕简单语言文法展开涵盖声明语句块、表达式、赋值语句等产生式的左递归消除验证其满足LL(1)文法要求并在词法分析器中加入float关键字识别、种别编码设为26再构造A、M、P、D、N、Q、E、G、T等递归函数完成解析。已有533人学习适合需要对照实验报告、理解FIRST/FOLLOW集计算与递归下降编码思路的读者参考。1. 递归下降分析实验从文法改造到可运行分析器的完整交付路径拿到「自上而下的语法分析」这道实验题很多人第一反应是打开 IDE 直接照着产生式写函数结果写到一半发现左递归把栈撑爆了或者float关键字在词法阶段就被当成普通标识符吞掉。这个实验真正要交付的不是几段能跑的代码而是一条完整链路原始文法 → 消除左递归 → FIRST/FOLLOW 集验证 LL(1) → 词法分析器补关键字 → 递归下降程序 → 正确与错误用例的对照结果。它适合正在做编译原理课设的学生也适合需要快速复现一个可演示语法分析原型的从业者。下面按这条链路逐段拆开每个环节给出可对照的实现和判断依据。2. 文法改造与 LL(1) 验证消除左递归后 FIRST/FOLLOW 集怎么算才不翻车原始文法里表达式 → 表达式 表达式2 | ...是典型的直接左递归声明语句块 → 声明语句 声明语句块这种形式在递归下降里如果照搬也会导致无限展开。改造的目标只有一个让每个非终结符的产生式右部首符号集合互不相交这样递归下降程序看到当前 token 就能唯一决定走哪条产生式不需要回溯。2.1 消除左递归的具体改写与产生式对照把表达式三层拆成 E/E/T/T/F 是标准做法。改写后的产生式如下这份表建议直接抄进实验报告后面写代码时逐条对照非终结符产生式说明A{ M N }函数体花括号为终结符Mε | P M声明语句块可空PD i ;单条声明语句Dt | f数据类型t 代表 intf 代表 floatNε | Q N可执行语句块可空Qi E ;赋值语句ET E表达式入口E T E | - T E | ε加减层左递归已消除TF T项T* F T | / F T | ε乘除层F( E ) | i | d因子i 为标识符d 为整数改写时有两个容易忽略的点。第一M → ε | P M里的 ε 分支必须保留否则空函数体{ }无法通过第二P → D i ;末尾的分号是终结符词法分析器必须把它作为独立 token 输出不能和标识符粘连。我一般会在改写完成后先手推两个短串比如{ int a; }和{ }确认每条产生式都能对上再动代码。2.2 FIRST 集与 FOLLOW 集的推导过程FIRST 集从最底层往上推F 的 FIRST 是{(, i, d}T 继承 F 的 FIRSTE 继承 T 的 FIRSTE 的 FIRST 是{, -, ε}。FOLLOW 集从开始符号 A 出发A 的 FOLLOW 含#输入结束符因为 A →{ M N }所以 M 的 FOLLOW 含 N 的 FIRST 加上}N 的 FOLLOW 含}Q 在 N 的产生式里后面跟 N所以 Q 的 FOLLOW 含 N 的 FOLLOW 即}E 在 Q →i E ;里后面跟分号所以 E 的 FOLLOW 含;同时 E 出现在 F →( E )里所以还含)。验证 LL(1) 的判据是对同一非终结符的任意两条产生式其右部 FIRST 集不相交若某产生式可推出 ε则其 FIRST 集与 FOLLOW 集不相交。以 E 为例 T E的 FIRST 是{}- T E的 FIRST 是{-}ε 分支的 FIRST 是{ε}三者互斥且 ε 与 E 的 FOLLOW 集{;, ), #}也不相交所以 E 满足 LL(1)。逐条检查完这张表实验报告里「验证其为 LL(1) 文法」这一问才算有据可依而不是一句「显然成立」。提示FOLLOW 集里最容易漏的是#和)。前者来自开始符号的约定后者来自括号嵌套场景漏掉任何一个后面错误用例的判定就会失准。3. 词法分析器补强关键字 float 的种别编码与 token 流生成递归下降程序吃的是一串已经分类好的 token所以词法分析器必须先跑通。原始实验一的词法分析器通常只识别 int这次要补上 float并给它一个明确的种别编码 26。注意这里的编码是实验约定不是编译器标准报告里写清楚「按实验要求设定」即可。3.1 关键字识别与种别映射的实现下面这段 Java 是词法分析的核心逻辑保留了原实验的结构重点看isKey和analyze两个方法// 关键字表下标1 即为种别编码float 对应 2实验要求编码 26 时在此处映射 public static int isKey(String str) { String[] keyWord {int, float, if, void, main}; for (int i 0; i keyWord.length; i) { if (keyWord[i].equals(str)) { return i 1; // int-1, float-2 } } return -1; } // 词法分析主循环把字符流切成 token 并存入 list public static void analyze(char[] chars) { char ch; String arr ; for (int i 0; i chars.length - 1; i) { ch chars[i]; arr ; if (ch || ch \t || ch \n || ch \r) { continue; // 空白直接跳过 } else if (isLetter(ch)) { while (isLetter(ch) || isDigit(ch)) { // 标识符或关键字 arr ch; ch chars[i]; } i--; if (isKey(arr) 1) { list.add(t); // int } else if (isKey(arr) 2) { list.add(f); // float } else { list.add(i); // 普通标识符 } } else if (isDigit(ch)) { while (isDigit(ch)) { // 整数 arr arr ch; ch chars[i]; } i--; list.add(d); } else { switch (ch) { // 单字符终结符 case (: case ): case {: case }: case : case : case -: case *: case /: case ;: case !: list.add(String.valueOf(ch)); break; default: System.out.println(存在无法识别的字符); System.exit(0); } } } }这段代码的关键在于「最长匹配」遇到字母就一路吃到非字母非数字为止再回头判断整个串是关键字还是标识符。float之所以能被正确识别靠的就是先拼完整串再查关键字表而不是逐字符判断。如果实验要求把 float 的种别编码写成 26只需在isKey返回 2 之后、list.add之前做一次映射或者在关键字表里直接维护编码值报告里注明映射关系即可。3.2 token 序列的调试与验证方法词法分析跑完后list里存的是一串形如{ t i ; }的种别序列。我一般会在进入语法分析前先打印这串序列用两个短用例对照{ int a; }应输出{ t i ; }{ float b; b 1 2; }应输出{ f i ; i d d ; }。如果这里就出现i和f混淆说明关键字表或匹配顺序有问题不必往下查语法分析。这一步是后面所有调试的地基token 流错了递归下降程序再对也白搭。注意文件读取时new char[length 1]多留一位是为了容纳可能的结尾但循环条件写成i chars.length - 1会丢掉最后一个有效字符。测试用例末尾务必留一个换行或空格否则最后一个 token 可能被截断这是血泪经验里最常见的一类「玄学失败」。4. 递归下降分析程序九个函数如何对应产生式并处理空产生式递归下降的写法很直白一个非终结符对应一个函数函数体按产生式右部的顺序依次匹配 token 或调用其他函数。难点不在「写」而在「空产生式怎么退出」和「匹配失败怎么回退」。4.1 函数与产生式的映射结构按第 2 章的改写表A、M、P、D、N、Q、E、E代码里叫 G、T、T代码里叫 H、F 各对应一个静态方法。以 A 和 Q 为例static void A() { // A - { M N } if (list.get(index).equals({)) { index; M(); flag 1; N(); if (list.get(index).equals(})) { index; } } } static void Q() { // Q - i E ; if (list.get(index).equals(i)) { index; if (list.get(index).equals()) { index; E(); } } else { flag 0; // 不匹配标记失败 } }index是全局游标指向当前待匹配的 token每匹配一个终结符就index。E、T、F 三个函数负责表达式递归E 调 T 再调 G即 ET 调 F 再调 H即 TF 遇到(就递归回 E形成括号嵌套。这套映射关系写对之后整个分析器的骨架就立住了。4.2 空产生式与 flag 标志位的配合原实验里踩过的坑是 M、P、D 三个函数互相调用导致死循环。原因在于M → ε | P M中如果 P 匹配失败M 仍然会再次调用自己游标不动栈越压越深。解决办法是引入flag初始为 1某次匹配成功后置 0M 和 N 只在flag 1时递归调用自身否则直接返回。这样空产生式分支就有了明确的退出条件不会无限展开。static void M() { // M - ε | P M P(); if (flag 1) { M(); // 仅在上一次匹配成功时继续 } } static void N() { // N - ε | Q N Q(); if (flag 1) { N(); } }这个写法本质上是把「是否还能继续展开」编码进一个共享状态牺牲了一点优雅换来了可控性。更规范的做法是让每个函数返回 boolean 表示匹配成败由调用方决定是否继续但实验环境下用 flag 足够交差报告里把「为什么加 flag」讲清楚反而是加分项。4.3 主流程与成功/失败判定主函数负责读文件、调词法、调语法、比对游标public static void main(String[] args) throws Exception { 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(); analyze(buf); // 词法分析填充 list A(); // 从开始符号进入语法分析 if (index list.size()) { System.out.println(文法分析成功); } else { System.out.println(文法分析失败); } }判定条件index list.size()的含义是所有 token 都被消费完且没有中途失败。如果中途某处flag被置 0 但游标恰好也走到末尾仍可能误判成功所以更稳妥的写法是同时检查 flag 状态。正确用例{ int a; a 1 2; }应输出成功错误用例比如{ int a a 1; }缺分号或{ float ; }缺标识符应输出失败两组截图对照放进报告才算把「正确与错误测试用例」这一问答完整。5. 避坑与排查递归下降实验里最容易翻车的五个点5.1 现象程序卡死或栈溢出 → 原因左递归未彻底消除 → 解决逐条核对产生式右部首符号最典型的是表达式层没拆干净E 直接调 E游标不动递归无限深入。排查方法是把每个函数的首行打印出来看哪个函数在重复出现且 index 不变。解决就是回到第 2 章的表确认 E 只调 T、T 只调 F左递归全部转成了 E、T 的尾递归形式。5.2 现象正确用例被判失败 → 原因文件末尾字符被截断或分号未入 token 流 → 解决补结尾空白并检查 switch 分支i chars.length - 1这个循环边界会吃掉最后一个字符如果测试文件最后一行没有换行最后一个}或;就丢了。另外 switch 里漏写;分支也会导致分号被当成非法字符直接退出。排查时先打印 token 流看末尾是否完整再对照 switch 的 case 列表逐个核对。5.3 现象float 被识别成普通标识符 → 原因关键字表未更新或匹配顺序错误 → 解决先拼串再查表如果代码里先判断首字符再决定是不是关键字float的首字符f可能被当成标识符开头直接走标识符分支。正确顺序是先把连续字母数字拼成完整串再拿整串去关键字表里查。改完后用{ float x; }单独验证一次 token 流是否为{ f i ; }。5.4 现象空函数体{ }分析失败 → 原因M、N 的 ε 分支没有正确退出 → 解决确认 flag 初值与递归条件{ }进入 A 后调 MM 调 PP 调 DD 发现当前是}不匹配flag 置 0此时 M 不应再递归。如果 flag 初值没在 A 里重置为 1或者 M 的递归条件写成了无条件调用就会在}处反复尝试。排查时在 M、N 入口打印 flag 和 index看是否在}处停止。5.5 现象错误用例也显示成功 → 原因只比对游标未检查 flag → 解决成功判定加 flag 条件某些错误输入恰好让游标走到末尾但中途已经发生过不匹配。比如缺分号的语句Q 里匹配完和 E 后没检查;就返回游标可能刚好停在末尾。解决是把判定改成index list.size() flag 1并在每个终结符匹配失败处显式置 flag 为 0。6. 验收与答辩用三组用例和一张对照表把实验讲清楚验收时评委看的不是你代码多长而是你能不能证明「这套分析器确实按 LL(1) 规则工作」。我一般会准备三组用例一组全正确含 int 和 float 声明、加减乘除、括号嵌套一组词法错误出现非法字符一组语法错误缺分号、缺标识符、括号不配对。每组跑完把 token 流、分析结果、失败位置三样东西并排展示对照表如下用例输入片段预期 token 流开头预期结果失败定位正确 1{ int a; a 1 2; }{ t i ; i d d ; }成功无正确 2{ float b; b (1 2) * 3; }{ f i ; i ( d d ) * d ; }成功无语法错误{ int a a 1; }{ t i i d ; }失败第二个 i 处期望;词法错误{ int a; }遇中断失败非法字符答辩时被问得最多的是「你怎么证明它是 LL(1)」和「flag 到底解决了什么问题」。前者拿第 2 章的 FIRST/FOLLOW 表逐条指重点说 E 和 T 的 ε 分支与 FOLLOW 集不相交后者用 M 的死循环场景现场推一遍说明 flag 是把「能否继续展开」显式化。还有一个常被追问的点是「为什么不用预测分析表」回答清楚递归下降是 LL(1) 的一种实现形式、用函数调用栈替代了显式栈即可不必展开成教科书。从那以后我每次做这类实验都强制自己先把 token 流打印出来再写语法函数词法没过关绝不往下走——这个习惯帮我省掉了至少一半的「玄学调试」。希望帮到你。本文还有配套的精品资源点击获取