简介面向计算机专业编译原理课程实验的递归下降分析文档聚焦自上而下语法分析的作用、分析对象与处理结果。内容围绕一个简单语言文法展开先消除直接与间接左递归整理改造后的产生式逐个计算非终结符的FIRST集和FOLLOW集以验证LL(1)性质再说明词法分析器中增加float关键字识别、种别编码设为26的衔接方式并给出递归下降分析程序的Java实现、各非终结符对应递归函数及运行结果。资源包仅含1个doc文件约80KB篇幅紧凑却覆盖实验目的、文法改造、分析表、代码主体和结果记录适合课程实验报告撰写参考与考前复盘。已有534人学习读者可据此对照检查自己的集合推导、递归函数调用顺序、flag标志处理与词法接口设计快速定位文法改造或解析流程中的偏差。1. 递归下降的第一道坎文法改完为什么还在死循环很多人第一次写递归下降都会卡在同一个地方文法改过了FIRST/FOLLOW 也推了一遍函数照着产生式写完了一跑——卡住不动。栈在涨控制台没输出挂调试器一看M()在调P()P()在调D()D()什么都没消费就退回来了M()于是又把自己递归了一次。这份实验资源把这条链路完整暴露了出来。它不替你回避那个flag——相反那个看起来像随手加的全局整型恰恰是递归下降处理 ε 产生式时绕不开的机制。理解它比会写一百个if-else更有用因为它解释了「递归下降凭什么能工作、又在什么条件下会失效」。2. 左递归消除从 A→Aα|β 到 A→βA 这一刀到底切了什么递归下降最脆的环节不是写函数而是函数体里第一行写什么。如果产生式是E → E T | T那你翻译成代码时只有两种写法要么在E()里先调E()当场无限递归要么硬写个循环绕开——但那就不是「照着文法写」了。左递归消除就是把文法先改成「函数里读一个 token 再决定走哪条路」的形状。2.1 直接左递归怎么拆β 做头α 挂尾教科书给的变换规则只有一行A → Aα | β ⇒ A → βA A → αA | ε拆法含义很直白把「先递归再干活」翻成「先干活再递归」。β是不会以A开头的那个候选式所以可以安全地放在函数体开头原来跟在A后面的α挪到新非终结符A里用右递归消化掉。A的 ε 分支就是「尾巴到此为止」的出口。拿这份文法里的表达式部分走一遍。原始产生式是E → E T | E - T | T T → T * F | T / F | FE和T都是直接左递归。按上面的模板拆E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | i | d拆完之后E()拿到控制权时第一件事是调T()不是调自己/-的循环交给E()去消化。注意E里同时有/-和 ε 两条路所以E()必须能根据下一个 token 决定是「继续吃一个符号」还是「收手返回」。这一步看着简单但它是后面所有冲突的源头——能不能区分这两条路就是 LL(1) 判定要干的事。2.2 右递归不要动M → ε | PM 不是左递归很多人一看到文法里有递归就手痒想把M → ε | PM也拆一遍。千万别。这里的M出现在产生式最右边是右递归递归下降天然就能处理——M()里调一次P()再在尾部按条件调一次M()栈深度随输入长度线性增长不会在读到第一个 token 之前就爆掉。真正需要处理左递归的只有「产生式右部第一个符号等于左部」那一种也就是E和T。像M和N这种右递归 ε 组合原样搬进代码反而更清楚——代价是得用flag兜住 ε 的出口这就是第 4 章要拆的那段。2.3 改造后的完整文法与「ε 去哪了」把两处都处理完整份文法落到纸面上是这样A → { M N } M → ε | P M P → D i ; D → t | f N → ε | Q N Q → i E ; E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | i | d和原始版本对比E/T被拆成两截多出E/T两个非终结符其余产生式原样保留。这一步做完文法里已经不存在「函数第一行就要调自己」的情况但还差一步验证改造后的文法到底是不是 LL(1)也就是「给定一个非终结符和下一个 token能不能唯一确定走哪条产生式」。这件事只能靠 FIRST 和 FOLLOW 集来判。3. FIRST 与 FOLLOWLL(1) 判定到底在判什么LL(1) 里那个「1」不是随便写的它表示「向前看 1 个 token」。整个判定的核心问题只有一个对同一个非终结符的两条不同产生式它们在「第一个能出现的终结符」上有没有重叠。有重叠就意味着解析器站在那个位置时不知道该走哪条路——这就是冲突。FIRST 集负责回答「某条产生式能打头出现哪些终结符」FOLLOW 集负责回答「某个非终结符后面可能跟哪些终结符」是 ε 分支的判定依据。3.1 FIRST 集的递推ε 为什么要一路往下传FIRST 集的定义是「从某个符号串推导出来的所有可能的首终结符集合」空串用 ε 表示。计算规则分三条如果X是终结符FIRST(X) {X}。如果X → ε是一条产生式把 ε 加进FIRST(X)。如果X → Y1 Y2 ... Yn把FIRST(Y1) - {ε}加进FIRST(X)如果Y1能推导出 ε再把FIRST(Y2) - {ε}加进去依此类推如果Y1...Yn全都能推 ε把 ε 加进FIRST(X)。第三条的「依此类推」就是最容易被手算漏掉的地方。例如A → { M N }{是终结符所以FIRST(A) {直接就定了不用管后面。但E → T E不一样T本身是非终结符得先算FIRST(T)T又能推出 ε 吗不能因为T → F TF一定至少消费一个 token所以FIRST(E)就是FIRST(T)的全集不需要往下传更多。反过来看M → ε | P MFIRST(M) FIRST(P) ∪ {ε}FIRST(P) FIRST(D) {t, f}所以FIRST(M) {t, f, ε}。ε 在这里必须先「冒」出来否则算A的时候会漏掉M为空的情况。把这份文法的 FIRST 集完整列一遍非终结符FIRST 集A{Mt, f, εPt, fDt, fNi, εQiE(, i, dE, -, εT(, i, dT*, /, εF(, i, d注意E、T、F的 FIRST 集完全一致这不是巧合——它们本来就是同一套表达式语法在不同优先级上的别名第一个能出现的终结符都一样。这种一致在 LL(1) 判定里本身就是个信号如果某个非终结符的多个候选式 FIRST 集都长这样冲突立刻就会暴露。3.2 FOLLOW 集的来源谁在我后面谁就进了我的集合FOLLOW 集回答的是「某个非终结符在语法树的某个位置之后可能紧跟着什么终结符」。它是 ε 分支判定的关键——当一条产生式能推出空串解析器就需要用 FOLLOW 集判断「不吃任何 token 直接返回」是不是合法的下一步。计算规则也是三条把#输入结束符加进开始符号的 FOLLOW 集。对每条产生式A → α B β把FIRST(β) - {ε}加进FOLLOW(B)。上一条如果β能推出 ε或β为空把FOLLOW(A)整体加进FOLLOW(B)。回到这份文法A是开始符号所以FOLLOW(A) {#}。接着由A → { M N }推FOLLOW(M)和FOLLOW(N)M后面跟NFIRST(N) {i, ε}去掉 ε 剩{i}所以i进FOLLOW(M)又因为N能推出 εM后面可能直接是}所以}也进FOLLOW(M)。N后面是}所以}进FOLLOW(N)。E的 FOLLOW 集稍微绕一点。E → T EE在末尾所以FOLLOW(E)包含FOLLOW(E)而E又出现在F → ( E )里E后面是)所以)也进FOLLOW(E)Q → i E ;E后面是;所以;也进FOLLOW(E)。最终FOLLOW(E) {), ;, #, }这里}来自FOLLOW(E)的传递而FOLLOW(E)又从FOLLOW(A) {#}一路继承——这一长串传递链是手算最容易断的地方。整理成表非终结符FOLLOW 集A#Mt, f, i, }Pt, f, iDt, f, iNi, }Qi, }E#, i, }, )含;E#, i, }, )T,-, #, i, }, )T,-, #, i, }, )F,-,*,/,#,i,},)表格里E那行多写了;是因为Q → i E ;里E后面跟分号而这个分号在其它路径上没出现——补上才是完整的FOLLOW(E) {#, i, }, ), ;}。手算这种传递链血泪经验只有一条把所有「非终结符出现在末尾」的产生式先列出来再一条一条把 FOLLOW 往下传中途千万别跳步。3.3 LL(1) 判定的实战看 E 和 T 的冲突面判定规则有两种等价写法实质一样对非终结符A的任意两条不同产生式A → α | β要求FIRST(α) ∩ FIRST(β) ∅。如果其中一条能推出 ε比如A → α | ε还要求FIRST(α) ∩ FOLLOW(A) ∅。拿E和T来试。E → T E | - T E | ε前两条的 FIRST 分别是{}和{-}不相交第三条是 ε得看FIRST(TE) ∩ FOLLOW(E)和FIRST(-TE) ∩ FOLLOW(E)FOLLOW(E) {#, i, }, ), ;}和、-都不相交通过。T同理*//和,-,#,),;也互斥通过。所以改造后的文法是 LL(1) 的。这个结论看上去轻飘飘一句话但它是整个递归下降能写出来的前提——如果这里判不过后面写的每个函数都会在某条输入上翻车而且翻得毫无规律。4. 递归下降的代码骨架一个下标、一列函数再加一个 flag把 LL(1) 结论翻译成代码结构简单得不像话每个非终结符对应一个静态方法方法里按 FIRST 集决定走哪条产生式全局维护一个index指向当前 token再加一个flag用来在 ε 分支和失败路径之间做切换。代码短、可读性高但每一处判断都对应着第三章算出来的集合写错一个字符就会在某个边角输入上翻车。4.1 函数骨架index 是唯一的游标list 是词法分析的产物先看整体结构。RecurDesAnalyzer里只保留三个全局状态list存词法分析后的 token 序列index指向当前待匹配位置flag标记最近一次匹配是否成功。所有非终结符对应的函数都只操作这三个东西没有参数、没有返回值——这是手写递归下降最典型的状态共享写法优点是短缺点是任何一次越界或漏匹配都会直接污染全局状态。private static ArrayListString list new ArrayList(); private static int index 0; private static int flag 1; static void A() { // A → { M N } if (list.get(index).equals({)) { index; // 吃掉 { M(); // 声明语句块 flag 1; // 为 N 的 ε 判断重置标志 N(); // 可执行语句块 if (list.get(index).equals(})) { index; // 吃掉 } } } }A()里的flag 1重置很关键但不显眼。M()内部会把flag置 0 来表示「P 没匹配上、走了 ε 分支」如果不在N()之前重置N()里Q()的后续递归就会被上一轮的失败状态卡住。这种「状态污染」是手写解析器最隐蔽的坑之一靠肉眼读代码几乎看不出来只有跑测试用例才会暴露。E()和T()的结构稍微不同因为它们拆完以后都要先调一个非终结符、再调带撇的那个static void E() { // E → T E T(); // 先吃一个 T EPrime(); // 再交给 E } static void EPrime() { // E → T E | - T E | ε if (list.get(index).equals() || list.get(index).equals(-)) { index; // 吃掉 或 - T(); EPrime(); // 右递归消化剩余的 /- } // 没有 或 -走 ε直接返回 }注意EPrime()的 ε 分支没有显式写if而是靠「两个条件都不成立就返回」隐式完成的。这种写法在E和T上能成立因为它们的候选式除了 ε 都是单个符号开头换成M或N就不行了得靠flag来补——这正是第 4.2 节要拆的地方。4.2 无限递归的坑M → ε | PM 单靠函数调用跑不动M、P、D三个非终结符是整份代码里最容易翻车的一段因为它们的结构是 ε 在前、递归在后M → ε | P M P → D i ; D → t | f照字面翻译M()应该是「先试P()成功了再递归M()」P()调D()D()匹配t或f。问题出在「试P()」这一步如果当前 token 既不是t也不是fD()匹配不上P()什么都没消费就退回来了M()看到P()成功因为没报错就继续递归于是M()自己调自己栈一直涨程序卡死。这是 ε 产生式在递归下降里的经典失效模式ε 分支的判定不能靠「上一次调用有没有报错」必须靠一个显式的状态位。原始代码里没有这个状态位所以实验里出现了「三条语句不断重复调用」的现象——M、P、D三者来回互调index却不动。修复的办法就是那个flag但它的语义要写清楚才不违背直觉static void M() { // M → ε | P M P(); // 先试着吃一条声明语句 if (flag 1) M(); // 只有 P 成功消费了 token才继续递归 } static void P() { // P → D i ; D(); if (flag 1 list.get(index).equals(i)) { index; // 吃掉标志符 } // 注意这里还应补上分号匹配 index否则 A() 会卡在 ; } static void D() { // D → t | f if (list.get(index).equals(t) || list.get(index).equals(f)) { index; } else { flag 0; // 匹配失败通知上层走 ε index--; // 回退一格把位置还原 } }flag的语义只有两种状态1 表示「最近一次非终结符匹配成功」0 表示「失败应走 ε 分支」。D()匹配失败时flag 0M()因此不再递归直接返回——等价于走了M → ε。flag不是用来「防止循环」的它是 ε 分支的判定依据循环只是这个判定缺失时的外在症状。4.3 index-- 的回退原始版「回溯」的两面性D()里的index--值得单独说。它做的是「匹配失败后把游标退回一格」让上层函数可以从同一个位置重新尝试别的路径。这在功能上等价于最小粒度的回溯但它有两个隐患如果D()失败时index已经是 0index--会变成 -1下一次list.get(index)直接抛IndexOutOfBoundsException。D()失败后flag 0但P()里如果还有别的分支比如分号匹配它必须自己检查flag再决定要不要继续否则会在一个已经失败的状态上继续消费 token。实际写的时候更稳的做法是把「试探」和「提交」分开先在局部变量里试匹配成功再写回全局index失败就原地返回。这样不需要index--也不会污染全局游标。原版代码用index--是因为结构简单、没打算处理太复杂的回溯作为教学样例够用但移植到正经解析器里就是 bug 温床。4.4 词法入口float 的「种别 26」在代码里对应什么递归下降的输入不是原始字符是词法分析器吐出来的 token 序列。这份资源里的analyze()方法负责扫描字符串、识别关键字、把 token 按类别塞进listpublic 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; } return -1; }isKey返回的是关键字在数组里的位置加一int返回 1float返回 2。然后analyze()按返回值做映射1 对应ttype 的首字母2 对应ffloat 的首字母其余标识符统一记为i整数记为d。所以「float 的种别编码 26」在文法实验的约定里是一个数字标识analyze()内部用助记符f代替它——两者是同一件事的两层表示数字编码是对外的接口契约字符串标签是分析器内部方便写判断用的。新增float关键字时要改两处而不是一处isKey的数组里加上它analyze()的分支里也要加上对应的else if。只改数组不改分支float会掉进「不是关键字」的 else 里被当成普通标识符i然后M()在匹配P → D i时把float当成D后面的标志符整个解析就歪了——这也是第 5 章要列的头号踩坑。5. 常见问题排查递归下降里最容易翻车的五个地方递归下降的代码短但短不等于好调。它没有中间表示、没有错误恢复所有问题都表现为「最终判定失败」或「程序卡死」光看结果分不出是文法错了、词法错了还是游标越界。下面五条是按现象反推原因的路子每条都对应这份代码里实际踩过的坑。5.1 症状程序一直跑但控制台不输出现象输入一个合法程序进程 CPU 占满控制台不打印任何结果等久了可能栈溢出。原因M → ε | PM的 ε 分支没有终止条件M()调P()、P()调D()、D()匹配不上什么都没消费就返回M()于是无限递归。这是「ε 产生式缺少状态位」的典型症状。解决在D()失败时置flag 0M()递归前检查flag 1。更彻底的做法是把 ε 分支写成显式判断if (当前 token 不属于 FIRST(P)) return;直接不进入递归。5.2 症状正确输入被判「文法分析失败」现象输入{ int x; }这种一眼合法的程序最后打印「文法分析失败」。原因P()本文还有配套的精品资源点击获取