编译原理实验：递归下降分析器消除左递归与避坑指南-北京尧图网络

简介编译原理实验资源聚焦自上而下的语法分析以递归下降分析法为主线完整解决从文法改造到分析程序实现的闭环问题。资源面向编译原理课程学习者尤其适合正在完成语法分析实验、需要参考完整代码与运行结果的学生。内容先对给定文法消除左递归求出各非终结符的 FIRST 集与 FOLLOW 集验证其满足 LL(1) 文法再结合可识别 float 关键字单词种别编码 26的词法分析器给出递归下降分析程序的 Java 实现并附运行结果。全包共 1 个文件格式为 doc约 80KB代码、表格与说明集中在一份文档内便于阅读、打印或对照实验报告整理。目前已有 531 人学习下载。借助其中的文法改造推导、预测分析表判断、函数级解析代码与排错细节读者能快速理解递归下降分析的结构并可直接改用于同类语法分析实验。1. 编译原理实验递归下降分析器为什么卡在“消除左递归”这一步做过编译原理实验的人都懂词法分析还能靠正则硬写一到语法分析、特别是自上而下的递归下降分析很多人第一反应是“文法改造完了照着产生式写函数不就行了”但真动手才发现代码写了一百多行跑起来不是栈溢出就是死循环最后卡在了一个看似不起眼的问题上文法里明明消除了左递归程序还是会无限递归。这份实验资源给的是一整套可复现的 Java 实现——文法改造、FIRST/FOLLOW 集计算、词法分析器扩展、递归下降分析程序、正确与错误用例的分析结果全都有。适合正在做编译原理课程设计、或想弄明白递归下降分析到底怎么落地的人。它不是一份只有代码的压缩包而是把“为什么这么写、踩了哪些坑、flag 标志怎么救场”都讲清楚了。2. 从原始文法到 LL(1)消除左递归与 FIRST/FOLLOW 集的验证逻辑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代表intf代表floati代表标志符d代表整数常量。注意看E和T的产生式E → E T是典型的直接左递归。如果你照着这个文法直接写递归下降分析函数E()开头就调用E()永远没机会消费输入 token栈直接爆掉。所以实验第一步必须是消除左递归。另一个问题藏在M → ε | P M这条产生式里它不是左递归它是右递归。右递归在递归下降分析里是合法的但和P → D i ;、D → t | f结合起来后如果D()匹配失败M()会不断递归调用P()产生死循环。这就是实验报告里“遇到的问题”部分提到的三条语句无限重复调用。后面第 5 章会专门讲这个坑。2.2 消除左递归的标准做法直接左递归的标准消法是引入一个新非终结符。以E为例原始E → E T | E - T | T 改造 E → T E E → T E | - T E | εT同理原始T → T * F | T / F | F 改造 T → F T T → * F T | / F T | εM和N本身是右递归不需要消除但要注意它们有ε产生式。改造后的完整文法如下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 E和- T E之间没有公共前缀不会产生 FIRST 集冲突这也为后面验证 LL(1) 打好了基础。2.3 FIRST 集和 FOLLOW 集怎么算、怎么验证 LL(1)LL(1) 的验证核心是两条每个产生式右部的 FIRST 集两两不相交每个非终结符的 FOLLOW 集与候选首符不冲突。计算 FIRST 集时从终结符往上推F的三个候选首符分别是(、i、d所以FIRST(F) { (, i, d }。T → F T的 FIRST 等于FIRST(F)E → T E的 FIRST 也同样是{ (, i, d }。带ε的产生式要单独记FIRST(E) { , -, ε }FIRST(T) { *, /, ε }FIRST(M) FIRST(P) ∪ { ε }。FOLLOW 集的计算顺序是从开始符号往下。A是开始符号FOLLOW(A) { # }# 表示输入结束。看产生式A → { M N }M后面跟着NFIRST(N)里有ε所以FOLLOW(M)还要并上FOLLOW(A)最终是FIRST(N) - { ε } ∪ FOLLOW(A) { i, } }。原文给的完整 FIRST/FOLLOW 集表格如下非终结符FIRST 集FOLLOW 集A{#Mε, t, fi, }Pt, fiDt, fiNε, i}Qii, }E(, i, d#, i, }, )E, -, ε#, i, }, )T(, i, d, -, #, i, }, )T*, /, ε, -, #, i, }, )F(, i, d, -, *, /, #, i, }, )逐条检查E的候选 T E、- T E、ε首符分别是、-、ε互不冲突且FOLLOW(E)里的#, i, }, )不包含或-所以 E 的候选互不干扰。M的候选是ε和P MFIRST(P M) { t, f }和FOLLOW(M) { i, } }也不相交。整体满足 LL(1) 条件。提示算 FOLLOW 集时最容易漏掉ε传递的情况。比如A → { M N }中N可以推导出ε那么M的 FOLLOW 就要把FOLLOW(A)也并进来。原文表格里FOLLOW(M) { i, } }就是同时包含了FIRST(N)和FOLLOW(A)的结果别只取前者。3. 词法分析器扩展把 float 塞进已有识别流程而不破坏 token 序列3.1 为什么 float 不能按普通标志符处理实验要求里有一条很关键词法分析器除了识别实验一的单词外要加入对关键字float的识别单词种别编码设为 26。如果float被当成普通标志符i送进语法分析器那D → t | f这条产生式就永远匹配不到float声明语句float i;直接报错。原文里的处理方式比较巧妙词法分析器不输出种别编码数字而是直接把关键字映射成语义字。int映射成tfloat映射成f普通标志符映射成i整数常量映射成d。这样语法分析器的D()只需要判断当前 token 是不是t或f就行不需要关心编码值。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; } } return -1; }这段代码返回的是关键字在数组里的下标加 1int返回 1float返回 2。调用处判断isKey(arr) 1就 add 一个t 2就 add 一个f。这里把种别编码 26 的概念内化成了语义字映射虽然不直接输出 26但效果等价——语法分析时只认t和f。3.2 标志符与数字的识别边界词法分析的核心在analyze(char[] chars)方法里逻辑分三路字母开头走标志符/关键字识别数字开头走常量识别其他字符走符号匹配。关键代码片段else if (isLetter(ch)) { while (isLetter(ch) || isDigit(ch)) { arr ch; ch chars[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)) { arr arr ch; ch chars[i]; } i--; list.add(d); }逻辑说明isLetter(ch)为真后进入循环持续吞掉后续字母和数字直到遇到非字母数字字符然后i--把多读的那个字符“退回去”。这个回退很重要——比如输入是float;循环读掉float后ch指向;此时i已经指向;的下标i--后外层 for 循环的i会恰好让ch重新读到;否则分号会被漏掉。isKey(arr)的返回值决定是t、f还是i。数字识别同理只吞数字不吞字母所以12abc会被切分成d和i两个 token这在小型语言里是常见且合理的处理。符号匹配部分是一个大 switch(、)、{、}、、、-、*、/、;都直接按字符入列。注意!也被加入了但文法里并没有用到。默认分支遇到无法识别的字符会打印提示并System.exit(0)这在调试时能快速暴露输入文件里的非法字符比如中文标点或全角空格。提示buf new char[length 1]这是为了让末尾多一个空字符位置。文件读取时如果最后一个字符不是换行循环访问chars[length]就会越界。加 1 后即使读到边界访问到的也是默认初始化的\u0000不会被识别成任何 token。4. 递归下降分析程序的结构与实现细节4.1 核心函数与文法产生式的一一映射整个分析程序的核心是一个全局ArrayListString list存 token 序列index指向当前读取位置flag是分析成功标志。每个非终结符对应一个静态方法方法体直接照抄产生式右部static void A() { // A → { M N } if (list.get(index).equals({)) { index; M(); flag 1; N(); if (list.get(index).equals(})) { index; } } }A()是入口先匹配{再依次调用M()和N()最后匹配}。这段代码有一个值得注意的细节M()调用完以后手动把flag重置为 1然后再调用N()。因为M()内部可能因为声明语句的ε选项把flag置成 0如果不重置N()会在flag 0时直接跳过Q()的执行。static void M() { // M → ε | P M P(); if (flag 1) M(); } static void P() { // P → D i ; D(); if (list.get(index).equals(i)) { index; } } static void D() { // D → t | f if (list.get(index).equals(t) || list.get(index).equals(f)) { index; } else { flag 0; index--; } }逻辑说明D()匹配到t或f则消费 token 并保持flag 1匹配失败时flag 0且index--回退一格。这里index--的目的是让下一个分析函数能重新看到当前 token。M()里先调P()如果D()失败导致flag 0M()就不会再递归调用自身而是直接返回。这就是用flag模拟ε产生式选择的机制——当M → ε时P()整体分析失败则M()退化为空。4.2 表达式部分的左递归消解与优先级保持表达式链E → T E、E → T E | - T E | ε、T → F T、T → * F T | / F T | ε用递归实现static void E() { // E → T E T(); G(); } static void G() { // G → T G | - T G | ε if (list.get(index).equals() || list.get(index).equals(-)) { index; T(); G(); } } static void T() { // T → F T F(); H(); } static void H() { // H → * F H | / F H | ε 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()和H()分别对应E和T它们用if判断当前 token 是/-或*//是则消费并继续递归否则直接返回相当于走了ε分支。这就是消除左递归后“表达结合性”的实现方式——E → T E中T先被分析E再处理后面的运算所以i i i会被分析成T (T T)的右结合结构。虽然递归下降分析不显式建 AST但函数调用过程本身就隐含了推导顺序。F()是递归下降的“叶子”它只接受标志符、整型常量和括号表达式。注意括号分支里E()返回后必须检查)是否存在缺失时会继续往下执行并最终在main()里报错。F()失败时只置flag 0不做index--因为调用者T()和H()不会再试图消费 token不回退也没问题。4.3 主控与结果判定public static void main(String[] args) throws Exception { File file new File(D:\\JAVA EE 源代码\\Recursive descent analyzer\\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); System.out.println(词法分析后程序转化为); for (int i 0; i list.size(); i) { System.out.print(list.get(i)); } System.out.println(); A(); if (index list.size()) { System.out.println(文法分析成功); } else { System.out.println(文法分析失败); } }判定条件是index list.size()也就是所有 token 都被消费干净才算成功。这个条件比flag 1更严格——如果输入是{ int i; }后面还跟着垃圾 tokenA()分析完}后index会停在list.size()之前直接判定失败。D()里index--回退的设计在这里有个副作用如果失败发生在A()的第一个{匹配之后的任何位置index可能回退到某个非末尾位置但最终index list.size()的判定依然可靠因为这个等式只有在完全消费所有 token 时成立。5. 避坑记录这份实验里我见过的五个真实问题5.1 死循环或栈溢出flag 没按预期退出递归现象程序运行时卡住不动控制台没有任何新输出强制停止后报StackOverflowError。这通常不是运行时偶发而是每次跑到M()或N()就无限递归。原因M → ε | P M这条产生式里P()调用D()匹配t或f。如果输入文件里声明语句的 token 不是t或fD()会置flag 0并index--但M()里写的是P(); if (flag 1) M();这本来没问题。常见做法是误写成while (flag 1)或者把flag判断放在P()之前导致P()和flag状态错位flag始终为 1M()一直在递归。原文用全局flag并在每个非终结符入口处配合判断是一个很隐蔽但有效的方案改代码时千万别动flag的重置位置。解决保持原文结构——M()里先调P()根据P()执行后的flag状态决定是否递归。不要在M()开头人为把flag置 1那样会覆盖D()失败的标志。5.2 float 被识别成标志符 iD() 匹配失败现象输入{ float x; }输出 token 序列里不是{ f i ; }而是{ i i ; }语法分析在D()处失败。原因isKey()方法里关键字数组顺序是{int, float, if, void, main}调用处用isKey(arr) 2判断 float。如果有人把数组改成了{float, int, ...}或者把返回逻辑改成return i不是i 1判断条件就全错位了。另一种情况是词法分析循环里先判断了isKey(arr) 1且没加else那么 float 匹配到 int 的兜底分支直接 add 成i。解决保持isKey返回“下标加一”调用处用两个独立else if分支别用if ... if ...串联。调试时先打印词法分析后的 token 序列看到f再往下查。5.3 输入文件末尾没有换行导致数组越界现象程序报ArrayIndexOutOfBoundsException堆栈指向analyze()方法里的chars[i]。原因buf长度是length 1但reader.read(buf)实际读入的字符数可能恰好等于length。如果源文件最后一行没有换行符while (isLetter(ch) || isDigit(ch))循环在读到缓冲区最后一个真实字符后会继续执行i此时i变成length访问chars[length]越界chars的有效下标只到length。加 1 后chars[length]是可访问的\u0000循环在该处停下。解决把文件读取部分改为int realLen reader.read(buf);循环只用realLen个字符更稳妥。或者保留length 1的写法但要确保analyze()里所有循环都限制在chars.length - 1以内。5.4 错误用例报“文法分析成功”因为 flag 被提前重置现象输入明显违反文法的代码比如{ int 3; }程序却输出“文法分析成功”。原因问题出在A()里M();后紧跟着flag 1;。如果M()内部因为D()匹配失败把flag置 0但M()是ε分支此时整体退化成空是合法的A()重置flag也是合理的。问题在于N()内部。如果N()的Q()失败flag为 0但N()是ε分支A()在调用完N()后没有再次检查flag就继续匹配}导致本应失败的输入被接受。解决最直接的改法是在A()匹配完}后额外检查index是否到达list.size()同时检查flag 1。但要注意M()和N()都可能走ε分支并把flag置 0所以检查点要放在每个非终结符返回后而不是只放在A()末尾。5.5 修改文法后 FIRST/FOLLOW 集对不上程序行为诡异现象把M → ε | P M改成M → P M | ε调换顺序或者给E增加了一个ε之外的新产生式程序在特定输入下行为异常但不是每次必现。原因LL(1) 文法的产生式顺序不重要但候选集合不能有 FIRST 冲突。M → P M | ε和M → ε | P M的 FIRST 集相同、不冲突行为应该一致。真正的问题通常是把E → T E | ε的ε去掉或者给F()增加了一个F → i导致FIRST(F)变成{ (, i, d }不变但 FOLLOW 集传播发生变化。原文的表格是严格计算过的少算一个ε传递或漏算一个 FOLLOW 元素LL(1) 判定就会失效。解决改文法前先按第 2 章的表格重新算 FIRST 和 FOLLOW重点检查带ε的产生式是否引发“首符”和“后随”冲突。用表格逐条对照别凭感觉改。6. 进阶验证自己构造测试用例来确认分析器行为拿到这份实验代码后不要急着交作业先用几组精心构造的输入跑一遍确认它真的符合 LL(1) 文法的行为预期。我一般会准备三类测试第一类是标准正确用例{ int i; i 3; } { float f; f i 2 * (3 - 1); } { int a; int b; a b; }这三条覆盖了声明、赋值、表达式四则运算、括号嵌套、多次声明。跑完输出应该是“文法分析成功”且词的 token 序列分别是{ t i ; i d ; }、{ f i ; i i d * ( d - d ) ; }。第二类是边界用例专门验证ε分支是否正常工作——声明语句块为空、可执行语句块为空{ } { int i; }{ }这条很关键它要求M()直接走εN()也直接走εA()匹配{后立即匹配}。如果程序在这条输入上报失败说明flag处理有问题。{ int i; }验证M走P M分支后能正确退出M的递归。第三类是错误用例专挑 LL(1) 分析最容易漏掉的地方{ i 3; } // 缺少声明D() 处失败 { int 3; } // 声明类型后跟数字P() 处失败 { int i; i ; } // 赋值表达式为空E() 处失败 { int i; i 3 } // 缺少分号index 无法对齐跑完再看输出是不是“文法分析失败”如果失败用例输出成功就按第 5 章的排查思路去查flag重置位置。除了跑实验还有个值得做的进阶验证是把 token 序列打印出来人工比对确认float被正确映射成f。从那以后我每次拿到类似的递归下降实验代码都会强制走一遍这三类测试——先正确用例确认主流程再边界用例确认ε分支最后错误用例确认失败判定可靠顺序固定不再跳步。希望帮到你。本文还有配套的精品资源点击获取

编译原理实验：递归下降分析器消除左递归与避坑指南

相关推荐

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

45个经典Linux面试题：从命令到网络排障的完整考点解析

三兴化工的技术实力如何

更多资讯

PC上安装Claude Code：从Node.js到环境变量的完整配置指南

Winform界面美化利器：AntdUI Table控件从入门到实战

Electron多窗口与Pinia状态同步：三种方案对比与实战避坑

从零构建AI工程体系：LLM应用开发核心实践与落地复盘

C-语言词法语法分析器实现指南：从LL(1)文法到可调试递归下降

深入理解链式前向星：数组模拟邻接表的原理、实现与应用

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？