编译原理语法分析实验：LL(1)递归下降与FIRST/FOLLOW集实现

简介这份资源面向正在学习编译原理、需要完成语法分析实验的高校学生聚焦「自上而下的语法分析」这一编译器前端关键环节帮助读者理解递归下降分析程序的构造思路与实现过程。内容围绕消除左递归、改写文法、计算各非终结符的 FIRST 集与 FOLLOW 集并验证 LL(1) 性展开同时要求在词法分析器中加入 float 关键字识别、将其种别编码设为 26再据此编写递归下降分析程序覆盖声明语句块、表达式、赋值语句等产生式对应的递归函数设计与解析失败标记处理。资源包共 1 个 doc 文档约 80KB以实验报告形式整理实验目的、文法改造过程、FIRST/FOLLOW 集表格、Java 代码片段与运行结果便于对照自查与复现实验。目前已有 534 人学习适合作为语法分析实验的参考范例与排错对照材料。1. 从{ int a; a b c * d; }说起这份实验包能跑出什么编译原理的语法分析实验十个人里有八个卡在两件事上文法规约写不出来程序跑起来在 M、P、D 三个函数里原地打转。这份自上而下语法分析的实验包把「编译原理 词法分析器」和「递归下降分析」拼成了一条能跑通的链路先把一段带花括号的函数体扫成 t / f / i / d 加运算符的 token 序列再由九个互相递归的函数做预测分析最后打印「文法分析成功」或「文法分析失败」。它适合正在做语法分析实验、需要一份 Java 参考实现的人也适合代码写完了但结果判不对、想对着 FIRST 集和 FOLLOW 集找差异的人。文法改造、集合推导、词法改造、递归函数、错误用例五件事一件不少。2. 文法改造从E → E T到 LL(1)消除左递归与两个集合怎么手算这一章是整个实验的地基。很多人上来就抄代码结果函数里写了一堆if却说不清为什么这个位置要判断而不是(。原因很简单递归下降本质上是一张 LL(1) 预测分析表的代码化你写在if里的每个条件都应该能在 FIRST 集和 FOLLOW 集里找到出处。所以先把文法改对再把集合算对代码只是誊写。2.1 原始文法的三处病灶题目给的文法用符号写出来是这样一组产生式t代表 intf代表 floati代表标识符d代表整数常量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这份文法有三处需要处理的地方处理方式完全不同混为一谈就会翻车。第一处是E → E T | E - T | T和T → T * F | T / F | F这是标准的直接左递归。递归下降分析是从左到右扫、按最左推导展开的遇到E()函数第一件事就是调用E()递归立刻套娃栈直接爆掉。左递归必须消除没有商量余地。第二处是M → ε | P M和N → ε | Q N这两个是右递归。右递归在递归下降里是安全的M()调用完P()再调M()游标一直在前进不会原地打转。但它们带 ε 分支判定顺序有讲究必须先用 FIRST 集判断「当前 token 是不是 P 的开头」是才进P()不是就直接当 ε 返回。顺序写反了就会出现原文里那个「三条语句不断重复调用」的现象。第三处是D → t | f这类多候选产生式。它没有递归但要求你在进入D()之前确认当前 token 落在{t, f}里否则就是语法错误。这一步的判断依据同样来自 FIRST 集。提示消除左递归只针对E和T。有些同学图省事把M、N也一起改写结果改出来的文法和代码对不上反而更难调。2.2 消除左递归的改写步骤与改写后的文法直接左递归的通用消除公式是A → Aα | β改写成A → βA、A → αA | ε。代入E → E T | E - T | T其中 α 是 T和- Tβ 是T得到E → T E、E → T E | - T E | ε。T同理α 是* F和/ Fβ 是F得到T → F T、T → * F T | / F T | ε。把改写结果和原文法逐条对照方便检查有没有漏项原产生式改写后产生式改写手法E → E T | E - T | TE → T EE → T E | - T E | ε消除直接左递归引入新非终结符ET → T * F | T / F | FT → F TT → * F T | / F T | ε同上引入TF → ( E ) | i | d不变无递归候选首符号两两不同M → ε | P M不变右递归无需改写N → ε | Q N不变右递归无需改写改写之后E和T这两个新符号在代码里通常直接写成G()和H()因为 Java 方法名不接受撇号。原文代码里的G()就是EH()就是T看代码时别被这两个名字绕晕。2.3 FIRST / FOLLOW 集逐条推导与 LL(1) 判定集合推导是这份实验里最容易糊弄过去、也最容易在答辩时被问穿的部分。按定义老老实实推一遍不难。FIRST 集从最底层的F、D往上算FIRST(D) {t, f}FIRST(F) {(, i, d}FIRST(Q) {i}FIRST(P) FIRST(D) {t, f}。带 ε 的要单独标出来FIRST(M) FIRST(P) ∪ {ε} {t, f, ε}FIRST(N) {i, ε}FIRST(E) {, -, ε}FIRST(T) {*, /, ε}。E和T因为候选首符号都落到F所以FIRST(E) FIRST(T) FIRST(F) {(, i, d}。A的第一个符号是终结符{所以FIRST(A) {{}。FOLLOW 集从开始符号A出发FOLLOW(A) {#}#是输入结束标记。然后沿产生式右部往右传A → { M N }M后面紧跟NFIRST(N) {i, ε}先加i因为N可空再加FOLLOW(A)得FOLLOW(M) {i, #}N后面是}得FOLLOW(N) {}}。M → P MP后跟MFIRST(M) {t, f, ε}加{t, f}再因为M可空加FOLLOW(M)得FOLLOW(P) {t, f, i, #}。P → D i ;D后是i得FOLLOW(D) {i}。Q → i E ;给出FOLLOW(E)里的;F → ( E )给出)合起来FOLLOW(E) {), ;}。E位于E末尾FOLLOW(E) FOLLOW(E) {), ;}。T后跟E得FOLLOW(T) {, -, ), ;}。T位于T末尾继承FOLLOW(T)F后跟TFIRST(T)贡献*和/最终FOLLOW(F) {*, /, , -, ), ;}。整理成表非终结符FIRST 集FOLLOW 集A{{#}Mt, f, εi, #Pt, ft, f, i, #Dt, fiNi, ε}Qii, }E(, i, d), ;E, -, ε), ;T(, i, d, -, ), ;T*, /, ε, -, ), ;F(, i, d*, /, , -, ), ;LL(1) 的判定条件有两条同一个非终结符的任意两个候选产生式FIRST 集不相交如果某个候选能推出 ε那么它的 FIRST 集除 ε 外要和该非终结符的 FOLLOW 集不相交。逐条查M → ε | P MFIRST(P) {t, f}与FOLLOW(M) {i, #}不相交通过N → ε | Q N{i}与{}}不相交通过E → T E | - T E | ε{}、{-}互斥且{, -}与{), ;}不相交通过T同理{*, /}与{, -, ), ;}不相交通过D → t | f、F → ( E ) | i | d的首符号两两不同通过。所以这份改写后的文法是 LL(1) 的可以放心用单符号向前看做递归下降。这份推导最直接的用处是把集合翻译成代码里的判断条件。M()里判断「当前 token 是不是t或f」依据就是FIRST(P) {t, f}E对应的G()里判断「是不是或-」依据就是FIRST(E)里的两个终结符。写代码时养成「先看集合再写 if」的习惯函数就不会写歪。3. 词法分析器改造把 float 接进种别编码还要让语法层认得出来实验要求里有一条容易被忽略在词法分析器中加入识别关键字float的部分单词种别编码设为 26。这句话有两个落点——词法层要能扫出float语法层要能把它当成声明语句的数据类型。只做前一半程序会在D()里报错。3.1 为什么代码里用t/f/i/d而不是数字编码原文代码里有一处看起来「不合要求」的地方种别编码明明要求设成 26代码里却把int映射成字符串tfloat映射成f。这不是偷懒是有意为之的设计取舍。递归下降分析和词法分析器之间靠 token 序列通信。如果 token 用整数编码语法层的判断会写成if (cur 26)可读性极差排查时对着一串数字根本看不出是哪个单词。用单字符占位符的好处是list打印出来是{ t i ; i i i ; }一眼就能看出 token 流对不对语法函数里的if条件也和文法产生式里的符号一一对应。原文用isKey()返回1给int、2给float、3给if、4给void、5给main再在外层转成t/f这个中间层就是留给编码映射的位置。注意如果实验验收按种别编码逐个核对就得把中间层改成真正的数字编码比如int记 25、float记 26语法层的比较跟着改成数字常量。两种写法都能跑通关键是词法侧和语法侧必须约定同一套符号不能一边用f一边用26。3.2 关键字表的改法与前缀陷阱关键字识别的核心是一张表加一次查表。原文的写法是先把连续的字母数字拼成完整单词再拿去和关键字数组比对比对命中就返回编号不命中就当普通标识符i处理。这个「先拼完整再查表」的顺序很关键。// 关键字表顺序决定 isKey 的返回值新增关键字只能往后追加 private static final String[] KEY_WORD {int, float, if, void, main}; // 返回 1 表示 int2 表示 float-1 表示不是关键字 public static int isKey(String str) { for (int i 0; i KEY_WORD.length; i) { if (KEY_WORD[i].equals(str)) { return i 1; // 下标从 0 开始编号从 1 开始 } } return -1; }这里有两个参数要盯住。一个是数组顺序isKey的返回值直接由下标决定如果把float插到int前面int的编号就从 1 变成 2下面analyze()里所有isKey(arr) 1的判断全部失效。新增关键字只能追加到末尾或者干脆改成switch按字符串分派把编号和顺序解耦。另一个是匹配方式用equals而不是startsWith否则intValue这种标识符会被误判成关键字int。这个前缀陷阱在扩充词法分析器时特别常见。有人为了「支持更长的关键字」把判断改成str.startsWith(KEY_WORD[i])结果所有以i开头的标识符全被吃成intD()里判断数据类型时一路绿灯最后报「文法分析成功」但语义完全错乱。查这类问题最快的办法是把 token 列表打出来看i和t混了立刻现形。3.3 从字符流到 token 列表回退、越界与非法字符analyze()是词法分析器的主循环逐字符读、按类别分流。这段代码有几个边界必须处理好否则后面语法层会因为 token 流不对而误报。public static void analyze(char[] chars) { String arr; for (int i 0; i chars.length - 1; i) { // 末尾留一位防止 i 越界 char ch chars[i]; arr ; if (ch || ch \t || ch \n || ch \r) { continue; // 空白直接跳过不产生 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 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); // 直接退出不抛异常 } } } }三个参数值得说明。循环上界写chars.length - 1是因为内层while里用了i预读下一个字符如果最后一个字符恰好是字母或数字预读会踩到数组边界。原文用new char[length 1]多申请一位本质上也是给预读留缓冲。i--是配套的回退动作内层while退出时i已经指向当前单词之后的第一个字符外层for还会再i一次不回退就会跳过一个字符——这个 bug 的表现是「int a;里的分号莫名消失」语法层报缺;。非法字符分支用System.exit(0)直接终止好处是错误立刻暴露坏处是退出码 0 在脚本里会被当成正常结束做自动化测试时判断不了成败。我一般改成打印行号和字符后return让上层拿到一个不完整的 token 列表再看语法层怎么报错定位信息更全。4. 递归下降分析程序九个函数对应九条产生式游标和失败标志怎么管文法改对了、token 流对了剩下的事就是把产生式誊成函数。这部分看着机械实际上全局状态的设计决定了程序是「跑通」还是「跑飞」。4.1 全局游标与失败标志的设计递归下降只需要两个全局状态一个指向 token 列表当前位置的游标index一个表示「已经出错」的标志。原文用private static int index 0和private static int flag 1思路是对的问题出在flag的语义被用混了——它一会儿表示「当前分支匹配成功」一会儿表示「整体分析失败」两个含义搅在一起才有了后面index--这种补丁式写法。我习惯把这两件事拆开游标只管前进和回退失败用布尔返回值沿调用链往上抛。这样每个函数的返回值为true表示「这个非终结符匹配成功」false表示失败调用方用if (!X()) return false;短路代码结构和产生式一一对应不需要在函数之间靠全局标志传话。private static int index 0; // 游标当前待匹配 token 的下标 // 安全取当前 token越界返回 null避免 IndexOutOfBoundsException private static String cur() { return index list.size() ? list.get(index) : null; } // 匹配一个终结符相同则游标前移否则记失败 private static boolean match(String t) { if (t.equals(cur())) { index; return true; } return false; }cur()里的越界保护不是可有可无的装饰。递归下降在分析到输入末尾时函数仍然会去问「下一个 token 是不是}」如果直接list.get(index)index list.size()时立刻抛异常。原文代码没有这层保护正确用例能跑错误用例比如少一个右花括号直接崩在异常栈里看起来像程序 bug 而不是语法错误。4.2 按产生式誊写函数以A、M、P、D四个为例誊写的规则只有一条产生式右部有什么函数体里就按顺序写什么终结符用match非终结符调函数遇到|就用 FIRST 集判断走哪支。先看函数体这一层static boolean A() { // A → { M N } if (!match({)) return false; if (!M()) return false; if (!N()) return false; return match(}); } static boolean M() { // M → ε | P M if (t.equals(cur()) || f.equals(cur())) { // FIRST(P) {t, f} if (!P()) return false; return M(); // 右递归游标已前进不会死循环 } return true; // 当前 token 不在 FIRST(P)走 ε 分支 } static boolean P() { // P → D i ; if (!D()) return false; if (!match(i)) return false; return match(;); } static boolean D() { // D → t | f if (t.equals(cur()) || f.equals(cur())) { index; return true; } return false; }M()是整个程序的关键点值得单独说。它的两个候选是ε和P M判定依据是FIRST(P) {t, f}当前 token 是t或f说明后面确实跟着一条声明语句进P()否则只能是空声明块直接返回true。这个「先判 FIRST再决定是否吃入」的顺序就是 LL(1) 预测分析的全部精髓和查表法是同一件事的两种写法。M()的递归调用return M()是尾递归形式每次调用前P()已经消耗掉至少两个 tokenD一个、i一个游标严格前进不会出现原文里那个反复调用的问题。原文用flag打断循环本质上是手动模拟了「游标是否前进」这件事改成返回值之后前进由match和index保证flag就不需要了。同层的N、Q、E、G、T、H、F照同样套路写E和T因为消除了左递归函数体变成「先调下一层再看有没有/-或*//」static boolean E() { // E → T E if (!T()) return false; return G(); } static boolean G() { // E → T E | - T E | ε if (.equals(cur()) || -.equals(cur())) { index; if (!T()) return false; return G(); } return true; // FIRST(E) 里没有 /-走 ε }G()和M()的结构完全同构都是「判断首符号集合命中就吃入并递归否则当 ε」。把这两个函数放在一起看会发现递归下降的代码量其实和产生式条数成正比写顺了之后剩下的只是体力活。4.3 用 flag 打断死循环一段值得保留的经验原文那段「三条语句不断重复调用」的排查记录是这份实验包里最有价值的部分之一因为它记录了一个真实的现象和真实的解法。现象是M()、P()、D()三个函数互相调用停不下来后面的语句永远分析不到原因是D()匹配失败时没有正确终止外层误以为「还能继续」继续调M()游标不前进形成活锁。原文的解法是引入flag初值 1匹配成功置 0只有flag回到 1 时才允许再次进入分析函数同时配合index--回退。这个解法能跑通但它把「匹配失败」和「分支结束」两件事压在了同一个变量上所以D()里出现了else { flag 0; index--; }这种写法——index--是没有必要的因为在进入D()之前游标根本没动过回退反而把游标拖回了上一个 token。我后来写这类分析器习惯把回退这件事从函数里彻底拿掉游标只由match和显式的index推动任何失败都通过返回值上报调用方要么短路返回要么在确定的分支点做一次有限回退。这样每个函数的副作用只有一个——消耗 token调试时在match里打一行日志就能看到整个分析过程不用再去猜flag现在是几。顺带说一句index--这种写法在带回溯的算法里是必要的但递归下降是预测分析不做回溯出现回退代码基本意味着分支条件写错了。看到自己的分析器里有index--第一反应应该是回去检查 FIRST 集判断而不是加更多回退。5. 避坑清单五个真实翻车点现象、成因与改法调这类程序最耗时的不是写代码是明明写完了却不知道为什么结果不对。下面五条是我和身边同学在这份实验上真实踩过的按现象、成因、改法写方便对着排查。5.1 词法层的两个坑关键字粘连与编码对不上第一条float识别了但语法层不认。现象是正确用例{ float x; }报「文法分析失败」把float换成int就成功。成因是词法层把float映射成了f但语法层的D()里只判断了t或者isKey数组里float的位置被改过、返回值变了。改法是先在analyze()之后把list整个打印出来确认float x;扫出来是f i ;三段再检查D()的if条件里有没有f。这一步能省掉一半的排查时间——问题出在词法还是语法一眼就能分清。第二条标识符被误判成关键字。现象是{ int intx; }这种写法不报错或者{ inta; }被当成一条合法声明。成因是关键字比对用了前缀匹配或者比对发生在拼串完成之前。改法是严格用equals做整词比对并且确保while (isLetter(ch) || isDigit(ch))这个循环把整个单词吃完之后才调用isKey(arr)。顺序反了int后面的字母就永远进不了arr。5.2 语法层的两个坑越界与多余回退第三条错误用例直接抛异常而不是报失败。现象是跑错误用例时控制台甩出一串IndexOutOfBoundsException看不到「文法分析失败」。成因是所有list.get(index)都没有越界判断输入提前结束时函数还在问「下一个 token 是不是;」。改法是统一走cur()这层封装越界返回nullmatch拿null去比较自然不相等失败沿返回值往上抛最后在main里打印失败而不是崩栈。第四条index--把游标拖回去。现象是某些用例里分号被跳过、或者同一个 token 被匹配两次。成因是D()失败分支里写了index--而进入D()之前游标并没有前进过这一减等于凭空回退一格。改法是把D()改成只读判断加返回布尔值匹配成功才index失败直接return false不在函数内部做任何回退。5.3 判定层的坑list复用与「成功」的假象第五条连续跑多个用例时结果互相污染。现象是第一个用例成功、第二个用例明明有错也报成功或者反过来。成因是list是静态成员analyze()只往里add不清空第二次分析时上一次的 token 还留在前面同时index也没重置为 0。改法是在每次分析开始前执行list.clear(); index 0;这一行不加所有多用例测试都是假的。public static void main(String[] args) throws Exception { for (String path : testFiles) { list.clear(); // 清空上一轮的 token index 0; // 游标归零 char[] buf readFile(path); analyze(buf); boolean ok A() index list.size(); // 两个条件都满足才算成功 System.out.println(path - (ok ? 文法分析成功 : 文法分析失败)); } }判定条件里index list.size()这一半经常被漏掉。只判断A()返回true输入末尾多出来的垃圾 token 不会被发现程序照样报成功。两个条件缺一不可函数链走完且游标正好停在末尾。6. 加餐把用例做成可回归的测试集再补一句错误定位代码能跑通只是及格线真正省心的是把用例固定下来每次改完文法或词法跑一遍就知道有没有改坏。这份实验的价值也在这里——它自带的正确用例和错误用例稍微整理就是一张回归表。用例编号输入内容预期结果主要考察点C1{ int a; a b c * d; }成功声明块 赋值 乘加优先级C2{ float x; x ( a b ) / 2; }成功float 识别、括号嵌套、除法C3{ int a; a b ; }失败表达式缺右操作数C4{ int a; a b c }失败缺分号游标提前停在}C5{ }成功两个 ε 分支同时走通C6{ int a a b; }失败声明语句缺分号C5 值得单独说一下。空函数体同时触发M → ε和N → ε是两个 ε 分支的联合测试很多实现在这里翻车——M()里判断FIRST(P)时如果写成「当前 token 不是}就进P()」空函数体会误入声明分支然后在D()里失败。正确的判断永远是「当前 token 在不在FIRST(P)里」而不是「在不在某个结束符里」前者是白名单后者是黑名单黑名单在文法扩展时一定会漏。错误定位的信息量也值得加一点。原文失败时只打印一句「文法分析失败」调的时候完全不知道错在哪。我习惯在match失败时把位置和期望符号一起打出来private static boolean match(String t) { if (t.equals(cur())) { index; return true; } // 失败时输出期望符号、实际符号和下标方便定位 System.out.printf(匹配失败期望 [%s]实际 [%s]位置 %d%n, t, cur(), index); return false; }这一行日志的成本几乎为零收益是把「哪条产生式、第几个 token 出错」直接摆到眼前。C4 那种缺分号的用例日志会告诉你期望;、实际是}、位置在下标 8对着 token 列表一数就知道是赋值语句没闭合。从那以后我每次写递归下降都会先把 FIRST 集列成一张表贴在旁边对着表写if条件写完再拿三组用例过一遍全对的、缺一个符号的、多一个括号的。三组都过了这份分析器才算真的能用。希望帮到你。本文还有配套的精品资源点击获取