简介这份资料面向计算机专业编译原理课程学习者围绕自上而下的语法分析实验提供递归下降分析法的完整实现参考。内容涵盖对给定简单语言文法消除直接与间接左递归、改写产生式逐一计算各非终结符的FIRST集和FOLLOW集并据此验证文法的LL(1)性质同时要求在词法分析器中补充float关键字识别、将其单词种别编码设为26再结合Java代码构造递归下降分析程序涉及函数体、声明语句块、表达式、赋值语句等递归函数及解析结果。压缩包内含1个doc文件约80KB便于集中查看实验报告、代码片段与运行记录。目前已有534人学习适合需要完成同类实验、梳理LL(1)判定流程和递归下降编码思路的读者参考。1. 递归下降分析为什么一个非终结符一个函数就能判对错编译原理里最容易被当成玄学的一步是语法分析。词法分析器把源码切成一串种别码之后递归下降要做的事听上去简单得不像话给每个非终结符写一个函数函数体照抄产生式右部遇到终结符就吃掉一个 token。可就是这样一套没有状态机、没有分析表、没有显式语法树的写法既能放行{ int a; a 1 2 * 3; }也能在{ int a a 1; }上停住。它凭什么凭两件事文法必须先改造成 LL(1) 可判定的形状以及调用栈本身就是那棵隐式的语法树。搞懂这两件事你才会明白消除左递归不是走过场ε 产生式为什么必须靠 FOLLOW 集决策代码跑飞时又该看哪儿。2. 消除左递归E → E T 为什么会让递归下降直接栈溢出2.1 左递归在递归下降里的真实表现先把实验给的原始文法摆出来。它描述的是一个函数体一对花括号里前面若干条声明语句后面若干条赋值语句。A → { M N } M → ε | P M P → D i ; D → t | f N → ε | Q N Q → i E ; E → E T | E - T | T T → T * F | T / F | F F → ( E ) | i | d其中 t 代表int、f 代表float、i 代表标识符、d 代表整数常量。如果你照着这套产生式一对一翻译成函数E()的第一行就是调用E()。程序一进E()就再进E()中间没有任何 token 被消费递归深度无限增长最后栈溢出。这不是 Java 的毛病换成任何语言都一样——递归下降的调用栈深度等于从开始符号到当前 token 所走的推导步数而左递归产生式E → E T会允许你在不推进输入的前提下无限次展开 E栈自然就撑爆了。这里有个容易被忽略的细节M → ε | P M和N → ε | Q N是右递归不会栈溢出但它会随语句条数线性增长调用深度一条语句一层。一百条声明的函数体就是一百层M()嵌套。这也解释了为什么实验代码里M()后面还要判断 flag 再递归——右递归本身合法只是不好收尾。2.2 消除左递归的机械变换与 E 的语义直接左递归的消除有固定套路把A → Aα | β改写成A → βA、A → αA | ε。对 E 和 T 动手得到E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | i | d实验中把 E 命名为 G、T 命名为 H代码里就是这么写的。改造后的 E 有个很值钱的语义它表示我已经解析完一个 T 了接下来还有没有加减法要接着做。1 2 * 3的解析过程是先T()吃掉 1G()看到再T()吃掉2 * 3G()再看下一个 token 是}或;走 ε 分支返回。加减法的左结合性就藏在这个先递归吃右边再回头算左边的调用顺序里。手写递归下降不需要真的建树但如果你要建 AST节点构造点就在G()消费的那一行。顺带说一句右递归的 M、N 其实也可以改写成迭代形式M → (P)*用 while 循环替代递归。实验代码没这么做代价是深函数体时的栈开销收益是代码和文法一一对应、好读。这是个典型的取舍不是错误。2.3 FIRST 集与 FOLLOW 集LL(1) 的入场券改造完文法还不够得证明它是 LL(1) 的——也就是对每个非终结符只看下一个 token 就能唯一确定走哪条产生式。判据是同一非终结符的各候选式FIRST 集两两不相交若某个候选式能推出 ε则它的 FIRST 集要与该非终结符的 FOLLOW 集不相交。实验里给出的 FIRST/FOLLOW 表核心几行是这样的产生式FIRST 集FOLLOW 集A → { M N }{#M → ε | P Mt, f}P → D i ;t, ft, fD → t | ft, fiN → ε | Q Ni}Q → i E ;ii, }E → T E(, i, d#, i, }, )E → TE | -TE | ε, -, ε#, i, }, )T → F T(, i, d, -, #, i, }, )T → *FT | /FT | ε*, /, ε, -, #, i, }, )F → ( E ) | i | d(, i, d, -, *, /, #, i, }, )拿 M 举例FIRST(M) {t, f}FOLLOW(M) {}}两者不相交所以看到t或f就走P M分支看到}就走 ε 分支。这个判定是纯静态的不需要试错。而这恰恰是实验代码没有利用的信息——它用了一个运行时 flag 去做同样的判断绕了远路。第 5 章会细说这个。手算容易出错我一般会用脚本对一遍。核心递推就两条FIRST 沿产生式右部往右扫遇到能推出 ε 的非终结符才继续往后看FOLLOW 从开始符号的#出发对每条A → αBβ把 FIRST(β){ε} 加进 FOLLOW(B)若 β 能推出 ε再把 FOLLOW(A) 加进 FOLLOW(B)。# 极简 FIRST/FOLLOW 计算骨架production 用 (lhs, rhs_list) 表示 prods { E: [[T, E]], E: [[, T, E], [-, T, E], []], # [] 代表 ε T: [[F, T]], T: [[*, F, T], [/, F, T], []], F: [[(, E, )], [i], [d]], } nonterm set(prods) nullable {k for k, v in prods.items() if [] in v} # 能推出 ε 的非终结符 def first_of_seq(seq): 求一个符号串的 FIRST 集遇 ε 继续看下一个符号 out set() for sym in seq: if sym in nonterm: out | first[sym] - {ε} if sym not in nullable: return out # 这个非终结符推不出 ε后面不用看了 else: return out | {sym} # 终结符直接返回 return out | {ε} # 全串都能推 ε first {k: set() for k in nonterm} changed True while changed: # 不动点迭代直到集合稳定 changed False for lhs, rhs_list in prods.items(): for rhs in rhs_list: add first_of_seq(rhs) if rhs else {ε} if not add first[lhs]: first[lhs] | add changed True print({k: sorted(v) for k, v in first.items()}) # 输出应为 E/T/F 均为 {(, d, i}E 含 ,-,εT 含 *,/,ε这段代码的关键在first_of_seq的提前返回只有当符号可空属于 nullable时才允许穿透到下一个符号继续收集。少了这个判断E → T E的 FIRST 会错误地把 E 的、-也算进去直接导致 LL(1) 判定失败。跑一遍和手算的表对上你就有了继续往下写解析器的底气。3. 词法分析器字符流是怎么被压成种别码序列的3.1 从字符流到种别码一个手写扫描器的结构递归下降吃的不是字符是 token 序列。实验里的词法分析器没有用正则引擎而是手写了一个字符级状态循环思路很朴素跳过空白遇到字母就一路吃字母和数字遇到数字就一路吃数字遇到单字符运算符就直接入表。产出的ArrayListString里每个元素就是一个种别码。public static void analyze(char[] chars) { char ch; String arr ; for (int i 0; i chars.length - 1; i) { // 注意上界见 5.2 的坑 ch chars[i]; arr ; if (ch || ch \t || ch \n || ch \r) { // 空白直接跳过不产生 token } 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 ;: list.add(String.valueOf(ch)); break; default: System.out.println(存在无法识别的字符); System.exit(0); // 硬退出不给恢复机会 } } }参数chars是文件内容读进内存后的字符数组list是全局 token 表。这里的核心机制是最长匹配读字母时不会读一个就停而是持续读到非字母非数字为止然后回退一格。i--那一行看起来不起眼但它是手写扫描器的标准动作——while循环退出时ch已经指向了下一个不属于当前 token 的字符指针必须还给for循环。3.2 关键字表与标识符的歧义消解int和float这两个字符串既是关键字也能被词法规则识别成标识符。消解办法只有一个先按标识符的规则完整读出来再拿整串去关键字表里查。不能一边读一边判否则intx会被误判成int后面跟一个x。isKey返回的是关键字在数组里的下标加一1 对应 int、2 对应 float其余返回 3 到 5。但代码只判了 1和 2if、void、main全都落进 else 分支变成i。这在本文法里勉强能跑因为文法根本不接受这几个词被当成标识符后会在语法分析阶段报错。可它埋了个隐患错误信息会说语法错误而真实原因是你识别了一个不该存在的关键字。词法层的错误被推迟到语法层暴露是调试困难的常见来源。3.3 种别码的设计为什么用 t/f 而不是数字 26实验要求里写设置 float 的单词种别编码为 26但代码里用的是字符串f。这不矛盾只是编码方式不同。种别码的本质是把无限多的单词映射到有限的整数集合上方便后续用数组或 switch 快速分派。用t、f、i、d这些单字符字符串本质是把种别码压缩成了可读的助记符只要词法端和语法端约定一致就不会出错。真要落地成编译器一般会定义成常量final int T_INT 1, T_FLOAT 26, T_ID 2, T_NUM 3;好处是种别码和错误信息、符号表索引可以共享一张表坏处是多一层数字到字符串的映射调试时不直观。实验阶段用助记符更省事这也是为什么原代码能写那么短。4. 递归下降的函数骨架index 游标、终结符匹配与 flag 状态位4.1 index 游标整个分析器只有一个读头递归下降的状态极简一个全局index指向当前待匹配的 token一个全局flag表示到目前为止还合法。匹配成功就index不匹配就flag 0。没有栈外状态没有分析表所有上下文都在函数调用栈里。private static ArrayListString list new ArrayListString(); private static int index 0; // 读头当前待匹配的 token 下标 private static int flag 1; // 全局合法性开关1 正常0 已出错 static void A() { // A → { M N } if (list.get(index).equals({)) { index; M(); flag 1; // M 段结束后强制复位让 N 段继续 N(); if (list.get(index).equals(})) { index; } } } static void M() { // M → ε | P M P(); if (flag 1) M(); // 只有 P 成功才继续递归吃下一条声明 } static void P() { // P → D i ; D(); if (list.get(index).equals(i)) { // 此处未判 flagD 失败时也会执行 index; } } static void D() { // D → t | f if (list.get(index).equals(t) || list.get(index).equals(f)) { index; } else { flag 0; index--; // 失败回退一格把读头还给调用者 } }A()里的flag 1是个非常有意思的设计它等于在说声明块解析失败不影响可执行语句块的解析。这个假设在测试用例里通常成立但严格讲是错的——如果 M 段失败是因为遇到了非法 token继续解析 N 段只会把一个清晰的错误变成一串莫名其妙的错误。D()里的index--更微妙。它做的是单步回溯匹配失败时把读头退回去让P()看到原始的 token。但注意P()在D()返回后并没有检查flag而是直接list.get(index).equals(i)——如果D()失败时index已经是 0这一减就变成 -1list.get(-1)直接抛异常。这个坑在第 5 章单独说。4.2 表达式的三层递归E/G/T/H/F 的调用链表达式部分是整个实验里结构最漂亮的地方。三层优先级每层一个函数层与层之间靠调用链自然形成优先级E 处理加减T 处理乘除F 处理括号和原子。static void E() { // E → T E T(); G(); } static void G() { // E → T E | - T E | ε if (list.get(index).equals() || list.get(index).equals(-)) { index; // 吃掉运算符 T(); // 递归解析右操作数含更高优先级 G(); // 继续看后面还有没有同级运算符 } // 否则什么都不做等价于走 ε 分支 } static void T() { // T → F T F(); H(); } static void H() { // T → * F T | / F T | ε if (list.get(index).equals(*) || list.get(index).equals(/)) { index; F(); H(); } } static void F() { // F → ( E ) | i | d if (list.get(index).equals(i) || list.get(index).equals(d)) { index; } else if (list.get(index).equals(()) { index; E(); // 括号内的表达式重新回到最高优先级 if (list.get(index).equals())) index; } else { flag 0; } }G()的递归位置是关键。它先吃运算符再调T()解析右操作数最后再调自己G()。这个顺序保证了1 - 2 - 3被解析成(1 - 2) - 3而不是1 - (2 - 3)——因为第一个G()会先把整个2 - 3的入口交给下一层等右侧递归返回后才回到自己这一层继续。左结合性是靠递归调用发生在消费运算符之后、返回之前这个位置关系实现的不是靠额外标记。同理*的优先级高于是因为T()在E()内部被调用F()又在T()内部被调用调用链深的那层先完成匹配。F()处理括号时重新调用E()等于把优先级重置回最低——这是递归下降处理嵌套结构的标准手法也是它能天然支持任意深度嵌套的原因。代价是每层括号多一层调用栈。4.3 成功判定为什么只看 index 是否走到末尾A(); if (index list.size()) System.out.println(文法分析成功); else System.out.println(文法分析失败);这个判定比 flag 可靠得多。index list.size()意味着所有 token 都被消费完了且没有在中间某处提前停下。flag 只反映有没有遇到不匹配不反映有没有吃完全部输入——如果文法在某个位置提前返回flag 可能还是 1但 index 停在中间。两个判据要一起用缺一个都会漏报。这也是为什么原代码里错误用例能报出来A 匹配{后如果后面结构不对index 走不到末尾。5. 排查清单递归下降实现里最容易翻车的五个点5.1 结构性陷阱递归不收口与全局状态污染现象一程序卡死或栈溢出M()无限自我调用。原因M → ε | P M的 ε 分支不消费任何 tokenP()失败后如果 flag 没及时置位M()会带着同一个 index 再调一次M()。原代码靠if (flag 1) M()挡住了这条路但 flag 是个全局变量任何一处失败都会污染后续所有判断。解决ε 分支的判定应该静态化。M 的 FIRST 是 {t, f}FOLLOW 是 {}}直接写成当前 token 是 t 或 f 才递归否则返回根本不需要 flagstatic void M() { while (list.get(index).equals(t) || list.get(index).equals(f)) { P(); // 迭代替代右递归栈深度从 O(n) 降到 O(1) } }现象二输入在中间某处出错但程序报告分析成功。原因A()里flag 1的强制复位。如果 M 段失败把 flag 置 0A 立刻复位成 1N 段接着跑最后 index 恰好走到末尾于是判成功。原代码的错误用例之所以能报错是因为错误 token 让 index 停在了中间属于运气好。解决把 flag 换成函数返回值。boolean M()返回是否匹配成功失败就一路往上抛不在中间复位。现象三D()的index--越界。原因D()在 index 为 0 时失败并执行index--变成 -1随后P()里list.get(index)直接抛ArrayIndexOutOfBoundsException: -1。空函数体{ }就是触发条件——M 第一次进来调 PP 调 DD 看到}不匹配回退到 -1。解决回退前判断if (index 0) index--。更彻底的做法是保存入口快照int mark index;失败时index mark;回退量永远精确。5.2 边界与词法陷阱少扫一个字符、多认一个关键字现象四文件最后一个 token 丢失明明正确的输入报语法错误。原因for (int i 0; i chars.length - 1; i)的上界少了一格。原代码用char buf[] new char[length 1]多申请一个字符来补偿靠数组末尾的\0兜底。这个补偿极其脆弱一旦文件读取长度和length()对不上比如文件里有中文或换行符差异末尾 token 就被吞掉。解决按实际读取到的字符数循环int n reader.read(buf); for (int i 0; i n; i)不依赖file.length()。这是血泪经验多字节字符场景下必翻车。现象五if、void被当成标识符错误定位跑到语法层。原因isKey返回 3 到 5 时analyze只判了 1 和 2其余全走 else 变成i。解决要么在词法层补全关键字表并给出明确种别码要么直接在这些词出现时抛词法错误别让它流到语法层。错误信息里带上行列号更好——递归下降本身不记位置这是它的短板得靠词法阶段补。6. 设计取舍手写递归下降和表驱动 LL(1) 该怎么选递归下降最诱人的地方是可读性等于文法本身。E()里三行代码对应三条产生式改文法就改函数不需要重新生成分析表。代价也明显文法一旦不是 LL(1)你得靠回溯或提取左公因子硬撑而回溯会带来指数级最坏复杂度。实验代码就卡在这个中间态——它半预测半回溯D()里那行index--是回溯M()里那个if (flag 1)是想模拟预测。真正落地时我会这样权衡维度手写递归下降表驱动 LL(1)文法改动成本改函数即可几分钟重算 FIRST/FOLLOW、重建表错误信息质量高能定位到具体函数和 token低只能报在状态 X 遇到 Y左递归处理必须手工消除同样必须消除栈深度随嵌套深度增长显式栈可控制适合场景语法相对稳定、要精细报错文法频繁变动、工具链生成还有一条容易被忽略的递归下降天然支持局部错误恢复。在M()里出错时你可以跳过 token 直到遇到;或}同步集然后继续解析后面的语句一次报出多个错误。表驱动的 LL(1) 要做得这么细得在分析表里塞同步符号复杂度立刻上去。这也是为什么主流手写编译器前端大多选递归下降——报错体验是用户能直接感知的东西。验证一个递归下降分析器有没有写对我习惯走三步。第一步手算 FIRST/FOLLOW确认文法确实是 LL(1)这是根本文法不对后面全白搭。第二步构造最小用例集空函数体、单条声明、单条赋值、括号嵌套、连续加减乘除各一组再各配一个故意错的版本缺分号、缺右括号、类型名后面直接跟。第三步在analyze()出口打印完整 token 流和预期序列逐项比对能在进入语法分析之前就把词法层的坑挖出来。从那以后我每次写这类分析器都会先强制走一遍打印 token 流 手算 FOLLOW 集这两步再动手写第一个函数。跳过这两步省下的十分钟后面要用两小时的断点调试来还。希望帮到你。本文还有配套的精品资源点击获取
