手写递归下降分析器：Java实现LL(1)语法分析实战

简介本资源是一份面向计算机专业本科生与编译原理初学者的实验教学材料聚焦自上而下的语法分析核心技能——递归下降分析器的设计与实现。内容涵盖LL(1)文法改造含左递归消除、FIRST/FOLLOW集手工推导、词法分析器扩展新增float关键字识别种别码26及完整Java版递归下降分析程序源码配套详尽实验步骤、文法转换过程与解析函数映射说明。压缩包为单个80KB的Word文档.doc内含实验目的、原始与改造后文法、集合计算表格、代码逐函数注释及关键语法树构建逻辑结构清晰、推导严谨便于课堂复现与课后自学。已有534人学习下载适合课程实验报告撰写、期末复习巩固及编译器原理实践能力提升。1. 一个能跑通的递归下降分析器不是教科书伪代码是真能读文件、报错、画出语法结构的 Java 实战项目你写完词法分析器拿到一串t i ; f i ; i d i ;这样的 token 流接下来该干啥不是背定义不是抄 PPT而是让程序自己“看懂”这串符号——它是不是合法的函数体有没有漏掉右括号赋值号右边是不是真能算出个表达式这个项目就是干这个的它把编译原理课上抽象的“LL(1) 文法”“FIRST/FOLLOW 集”全落地成可调试、可断点、可改、可加日志的 Java 代码。它不依赖任何第三方 parser generator比如 ANTLR纯手写递归函数每个A()E()F()都对应一条文法规则每行if (list.get(index).equals(i))都是你和语法树之间的直接对话。适合刚学完词法分析、正对着《龙书》第 2 章发懵的本科生也适合想补全编译器前端实战链路的初级开发——它不讲“为什么需要语法分析”它只做一件事给你一个.txt文件你放进去它告诉你“成功”或“失败”失败时还准确定位到哪个 token 卡住了。没有黑匣子没有魔法只有index和flag0的血泪经验。2. 文法改造与 LL(1) 验证从原始规则到可驱动递归函数的产生式递归下降分析器不是拿原始文法就能硬上的。原始文法里声明语句块 → Ɛ | 声明语句 声明语句块是典型的直接左递归如果直接翻译成void M() { P(); M(); }调用栈瞬间爆满JVM 直接抛StackOverflowError。这不是 bug是设计缺陷。我们必须先对文法动刀把它变成无左递归、无公共前缀、满足 LL(1) 条件的形态才能让每个非终结符的解析函数只靠“看下一个 token”就决定走哪条路。2.1 消除左递归把无限递归变成可控循环原始规则声明语句块 → Ɛ | 声明语句 声明语句块这是标准的 A → αA | β 形式这里 α 是声明语句β 是 Ɛ。消除方法是引入新非终结符M将规则重写为声明语句块 → 声明语句 声明语句块 | Ɛ 声明语句块 → 声明语句 声明语句块 | Ɛ但这样仍有冗余。更简洁的标准做法是M → P M M → P M | ε对照实验文档里的改造结果M → ε | P M // 原始有问题 → M → P M | ε M → P M | ε // 消除后正确但实际代码里没出现M函数为什么因为作者做了工程化简化用flag标志位模拟了M的循环逻辑。我们看M()函数static void M() { //M →ε| PM if(flag1) M(); // 这行是关键不是无条件递归而是受 flag 控制 }这行if(flag1) M();就是M → P M | ε的 Java 实现只有上层P()成功flag仍为 1才继续调用M()否则跳过。这是一种用状态变量替代新非终结符的务实做法牺牲了一点理论纯粹性换来了代码简洁和调试友好。如果你要严格按教材实现应该拆出MPrime()函数但如果你要快速验证语法结构这个flag方案更直给。2.2 FIRST 集与 FOLLOW 集不是数学作业是预测表的底层依据FIRST 和 FOLLOW 集不是为了考试而是为了回答一个问题“当我在解析E时看到下一个 token 是我该不该进E → T E这条路” 答案藏在FIRST(E)里——如果 ∈ FIRST(E)那就进如果 ∉ FIRST(E)但 ∈ FOLLOW(E)且E → ε存在那也要进因为E可能推导出空得把让给E的后续部分。实验文档给出了完整表格我们挑最关键的E和T看非终结符产生式FIRST 集FOLLOW 集ETE | -TE | ε,-,ε#,i,},)T*FT | /FT | ε*,/,ε,-,#,i,},)注意FOLLOW(E)包含}和)这意味着当E解析完下一个 token 是}函数体结束或)表达式结束时E必须选择ε分支退出否则整个分析就卡死。这个逻辑在E对应的G()函数里体现为static void G() { //G→ TG | -TG | Ɛ if(list.get(index).equals() || list.get(index).equals(-)) { index; T(); G(); // 继续匹配更多 T 或 -T } // 如果不是 或 -函数自然返回相当于选择了 ε 分支 }这里没有显式判断index是否指向}或)因为G()的调用者E()已经保证了上下文E()解析的是{ ... }或( ... )内部的表达式所以当G()看不到/-时它就该安静退出把控制权交还给外层。这就是 FOLLOW 集在代码中的隐式体现——它约束了函数的调用边界而不是写在if条件里。2.3 改造后文法与代码函数的逐行映射最终可用的文法实验文档已给出和 Java 函数是一一对应的。理解这个映射是读懂整个项目的钥匙文法产生式Java 函数关键逻辑说明A → { M N }A()先匹配{再调M()再调N()最后匹配}M → ε | P MM()flag1时才递归调自身模拟M循环P → D i ;P()先调D()匹配t或f再匹配字面量i最后匹配;D → t | fD()直接检查list.get(index)是否为t或f匹配则index否则flag0N → ε | Q NN()同M()flag1才递归Q → i EQ()先匹配i再匹配再调E()E → T EE()调T()再调G()E的实现E → TE | -TE | εG()匹配或-后调T()并递归G()否则静默返回εT → F TT()调F()再调H()T的实现T → *FT | /FT | εH()匹配*或/后调F()并递归H()否则静默返回εF → ( E ) | i | dF()匹配(则递归调E()并匹配)否则匹配i或d提示G()和H()是E和T的实现不是笔误。作者用单字母命名保持简洁符合递归下降常见风格。G代表EE-primeH代表TT-prime。这个映射表就是你的调试地图。当你发现N()总是提前退出就去查Q()里i E的E()是否失败当F()在(后卡住就去确认E()的入口T()是否被正确调用。一切问题都回归到这条映射链上。3. 词法分析器深度解析从字符流到 token 列表的完整流水线递归下降分析器不吃源代码它只吃 token。int a;必须变成[t, i, ;]t表示inti表示标识符float b 3.14;必须变成[f, i, , d, ;]。这个转换工作由analyze(char[] chars)完成。它不是简单的字符串分割而是一个状态机驱动的扫描器处理空格、字母、数字、运算符、分隔符还要识别关键字。3.1 关键字识别float的种别码 26 如何落地实验要求“在词法分析器中加入识别关键字float的部分设置其单词种别编码为 26”。但代码里没看到数字26。为什么因为作者做了种别码到 token 字符串的映射简化。看isKey(String str)函数public static int isKey(String str){ String keyWord[] {int,float,if,void,main}; for(int i0;ikeyWord.length;i){ if(keyWord[i].equals(str)) { return i1; // int - 1, float - 2, if - 3... } } return -1; }然后在analyze主循环里if(isKey(arr)1){ // int list.add(t); // 用 t 代表 int } else if(isKey(arr)2){ // float list.add(f); // 用 f 代表 float } else{ list.add(i); // 其他标识符 }所以“种别码 26”在这里被抽象为字符f。f就是float的 token 表示。这完全合理递归下降分析器只关心 token 类型是类型声明是标识符不关心具体数值。t和f在语法层面地位等同都是数据类型用单字符表示既节省内存又方便if(list.get(index).equals(t))这样的字符串比较。如果你要扩展支持double只需在keyWord数组末尾加double在isKey返回3时list.add(d)注意别和整数字面量d冲突需改用D或b。3.2 标识符与字面量的分离i和d的判定逻辑analyze函数如何区分a标识符和123整数字面量核心在两个 while 循环// 处理标识符以字母开头后跟字母或数字 else if(isLetter(ch)){ while(isLetter(ch)||isDigit(ch)){ // 持续读取直到非字母数字 arrch; chchars[i]; // 提前读下一个字符 } i--; // 回退一步因为上面多读了一个 if(isKey(arr)1){ list.add(t); } else if(isKey(arr)2){ list.add(f); } else{ list.add(i); } // 非关键字就是普通标识符 } // 处理数字以数字开头只读数字 else if(isDigit(ch)){ while(isDigit(ch)){ // 只读数字不读字母 arrarrch; chchars[i]; } i--; list.add(d); // 统一用 d 表示整数字面量 }关键点在于i--。假设输入是a123;ch初始为a进入isLetter分支。while循环读取a、1、2、3当ch变成;时退出循环。此时i已指向;的索引。i--把i拉回3的索引这样外层for循环的i才会让下一次迭代从;开始。没有这行i--;就会被跳过导致语法分析器永远等不到分号。3.3 运算符与分隔符的硬编码为什么!也被收录analyze函数末尾有个switch罗列了所有要识别的单字符符号case (: case ): case {: case }: case : case : case -: case *: case /: case ;: case !: list.add(String.valueOf(ch)); break;!出现在这里很奇怪——原始文法里没有逻辑非运算符。这是预留扩展位。当前文法只支持 - * / 但!的 token 已被生成只是Q()、E()等函数里没写处理它的分支。如果你想加if (!a) {...}只需在Q()或新增的Condition()函数里加if(list.get(index).equals(!)) { index; F(); }。这种“token 先生成语法后支持”的做法是词法/语法分离的经典实践。注意default分支遇到未识别字符会System.exit(0)。这是粗暴但有效的错误处理——宁可崩不给错误结果。生产环境应改为抛异常并打印位置。4. 递归下降分析器执行链从main()到A()的完整调用栈与状态流转main()是入口但它只做三件事读文件、调analyze()、调A()。真正的解析逻辑全在A()及其调用链里。理解这个链的状态如何传递、错误如何传播、成功如何确认是运行和调试的核心。4.1 全局状态变量index和flag的真实含义整个分析器只靠两个全局变量驱动static int index 0;指向list中下一个待匹配的 token 索引。list.get(index)是当前要吃的 token。static int flag 1;匹配成功标志。初始为 1表示“上一步匹配成功可以继续”一旦某个函数发现 token 不匹配如D()看到i却期望t就设flag 0并index--回退避免跳过错误 token。flag不是布尔值是整数这很关键。M()和N()的递归条件是if(flag1)意味着只有上层调用成功本层才继续。如果P()失败flag0M()就不会再次调用自己从而打破左递归循环。flag是控制流开关也是错误传播信标。4.2A()函数语法树根节点的构建者A()对应函数体 → { 声明语句块 可执行语句块 }是整个分析的起点和终点static void A(){ //A→{ M N } if (list.get(index).equals({)) { // 必须以 { 开头 index; // 吃掉 { M(); // 解析声明块 flag1; // 重置 flag这是关键 N(); // 解析可执行块 if (list.get(index).equals(})) { // 必须以 } 结尾 index; // 吃掉 } } } else { flag 0; // 第一个 token 不是 {直接失败 } }注意flag1;这行。M()执行完flag可能是 0如果M里某次P()失败但N()必须在flag1时才执行。所以M()结束后必须重置flag否则N()永远不会启动。这是作者修复的一个隐蔽 bug原始设计可能让M()的失败污染N()的执行。flag1是M和N之间的隔离墙。4.3 错误定位与恢复为什么index--出现在D()和F()里看D()static void D() { //D→ t | f if(list.get(index).equals(t)||list.get(index).equals(f)) { index; // 匹配成功前进 } else { flag0; // 匹配失败 index--; // 回退让上层知道这里卡住了 } }F()同理。index--的目的是让错误暴露在最外层。假设输入是{ t a ; }A()调M()M()调P()P()调D()。D()看到t成功index指向a。P()接着匹配a期望i失败设flag0但P()里没index--。M()检查flag1失败退出。A()最后检查list.get(index)此时是a是否为}不是于是报“失败”。但用户不知道错在哪——是t后面缺了i还是}缺了index--在D()里确保当D()成功后index指向P()期望的i如果i不在那儿P()的失败会让index停在错误 token 上A()的最终检查就能看到它。5. 常见问题排查5 个真实踩坑记录与血泪解决方案写递归下降分析器80% 的时间花在 debug。下面这些坑是我当年在实验室熬通宵时记下的每一个都附带现象、原因和一行解决代码。5.1 现象程序一运行就IndexOutOfBoundsException堆栈指向list.get(index)原因index超出了list的长度。常见于F()函数里list.get(index).equals(()之前index已经等于list.size()。这是因为某次flag0后函数没做index--导致index一直递增到越界。解决在所有list.get(index)调用前加安全检查if (index list.size()) { flag 0; return; }把这个检查放在A(),M(),P(),D(),N(),Q(),E(),G(),T(),H(),F()的开头。一劳永逸。5.2 现象int a; float b;被判为成功但int a float b;缺分号也被判成功原因P()函数只检查了D()和i没检查结尾的;。看原文P → D i ;分号是终结符必须匹配。解决修改P()static void P() { //P → D i ; D(); if(list.get(index).equals(i)) { index; if(list.get(index).equals(;)) { // 新增必须有分号 index; } else { flag 0; } } else { flag 0; } }5.3 现象a (b c) * d;解析失败卡在*原因F()函数处理(E)时匹配完)后index指向*但T()调用H()时H()看到*就匹配却忘了H()之后T()还要返回。问题在T()的结构static void T(){ //T→ F H F(); H(); // 这里 H() 匹配 * 后index 指向 d但 T() 没返回控制权回到谁 }T()本身没有返回值它只是顺序执行。H()匹配*后index指向dH()返回T()也返回控制权回到G()G()再返回最终E()结束。这逻辑是对的但H()里缺少对*后F()的调用看H()原代码static void H(){ //H→ *FH | /FH | Ɛ if(list.get(index).equals(*)||list.get(index).equals(/)) { index; // 吃掉 * 或 / F(); // 必须调 F()原文漏了这一行 H(); // 再递归 } }原文H()里只有index没调F()所以*后的d永远不被F()吃掉导致后续失败。5.4 现象int a 1 2 * 3;解析成功但int a 1 * 2 3;失败原因运算符优先级没体现。E → T E和T → F T的设计本意是E处理 -T处理* /但F()只处理i、d、(E)不处理1 * 2这种乘法表达式。F()应该能处理原子项而T()负责把它们连成乘除链。解决F()本身没错错在T()的调用时机。E()调T()T()调F()和H()H()处理*F和/F。所以1 * 2应该由T()启动T()调F()吃1H()看到*吃*调F()吃2H()再看下一个是不属于* /H()返回T()返回。E()的G()看到吃调T()…… 这个逻辑是通的。失败是因为F()没正确处理1。检查analyze()1被识别为dF()里有if(list.get(index).equals(d)) { index; }所以F()能吃d。问题可能在H()的index--缺失。在H()的else分支加else { // ε 分支什么也不做但确保 index 不越界 if (index list.size()) { flag 0; return; } }5.5 现象int a; int b;中第二个int被忽略N()不解析第二个Q()原因N()的递归条件if(flag1) N();依赖Q()的成功。但第一个Q()a;成功后flag1N()再调自己第二个Q()b;如果因;后没有i而失败flag0N()就停止不再尝试第三个Q()。但文法N → ε | Q N允许Q后跟ε即Q可以失败N仍可选ε分支。解决N()不能只依赖flag它必须主动尝试Q()失败了就走ε。修改N()static void N() { //N→ε|QN int savedIndex index; // 保存当前位置 int savedFlag flag; Q(); if (flag 1) { // Q() 成功继续 N() N(); } else { // Q() 失败回退走 ε 分支 index savedIndex; flag savedFlag; // 什么都不做相当于选择了 ε } }这实现了“试探性匹配”是递归下降处理A → B | C的标准手法。6. 二次开发实战从支持float到添加if语句的完整改造路径这个项目最宝贵的价值不是它现在能做什么而是它极低的改造门槛。我带过几届学生做课程设计从零开始加if语句、while循环、甚至简单函数调用平均耗时不超过 4 小时。核心就三点扩文法、加 token、写函数。下面以添加if语句为例走一遍真实开发流。6.1 步骤一扩展文法计算 FIRST/FOLLOW原始文法没有控制流。我们加一条可执行语句块 → Ɛ | 表达式语句 可执行语句块 | 条件语句 可执行语句块 条件语句 → if ( 表达式 ) 函数体函数体就是已有的A。所以if语句的结构是if (E) { ... }。计算FIRST(条件语句) { if }FOLLOW(条件语句) FOLLOW(可执行语句块) { }, ; }。if是关键字种别码应为3keyWord[2]token 设为k避免和i冲突。6.2 步骤二修改词法分析器支持if关键字在keyWord数组加if在isKey()返回3时list.add(k)String keyWord[] {int,float,if,void,main}; // 加了 if // ... else if(isKey(arr)3){ // if list.add(k); // 用 k 表示 if }6.3 步骤三编写if解析函数并集成到N()新增函数K()Kforifstatic void K() { // K → k ( E ) A if(list.get(index).equals(k)) { // 匹配 if index; if(list.get(index).equals(()) { index; E(); // 解析条件表达式 if(list.get(index).equals())) { index; A(); // 解析 then 分支的函数体即 { ... } } else { flag 0; } } else { flag 0; } } else { flag 0; } }修改N()让它能选择Q()赋值或K()ifstatic void N() { //N→ε|QN|KN int savedIndex index; int savedFlag flag; // 先试 Q() Q(); if (flag 1) { N(); return; // 成功退出 } // Q 失败回退试 K() index savedIndex; flag savedFlag; K(); if (flag 1) { N(); return; } // Q 和 K 都失败走 ε 分支 index savedIndex; flag savedFlag; }6.4 步骤四测试与验证写测试文件test_if.txt{ int a; if (a) { int b; } }词法分析后应为[{, t, i, ;, k, (, i, ), {, t, i, ;, }]运行A()→M()→P()int a;→N()→K()if→E()a→A(){ int b; }。全程flag保持1最终index list.size()输出“文法分析成功”。从那以后我每次加新语法都强制走一遍这四步1) 白板上画文法和 FIRST/FOLLOW2)grep -n keyWord *.java找词法入口3)vim RecurDesAnalyzer.java新建函数并粘贴骨架4) 写三行测试用例正确、少括号、错关键字。这套流程让我在编译原理期末答辩时现场给老师演示了 5 分钟内加完while循环。希望帮到你。本文还有配套的精品资源点击获取