LL(1)语法分析器实验详解：First集、Follow集与预测分析表构建-北京尧图网络

简介面向编译原理课程 LL(1) 语法分析器实验的完整资源包适合计算机专业本科生完成课程设计、实验报告撰写或考前复习。资源围绕输入 LL(1) 文法后构造预测分析表、判定输入串是否为文法句子这一核心任务提供了从语法分析程序设计思想、源代码编写到可执行程序运行的完整闭环。压缩包共13个文件包含可直接运行的exe、可修改的C源码、实验报告、程序设计思想文档及讲解视频等整体约24.81MB既能快速观察分析结果也能对照资料理解预测分析表的构造与冲突处理方法。目前已有3101人学习使用内容还附带了另一版实现及对应Dev-C工程便于对比不同写法、排查实验中的常见错误。对于需要系统掌握自上而下语法分析的读者这套资料既能辅助理解算法流程也能直接支撑实验验收与报告整理。1. LL(1)语法分析器实验二这门实验到底在逼你做什么很多同学做到编译原理实验二的LL(1)语法分析器时第一反应是去网上下一个源码包改两行交差。与其这样不如想清楚这门课为什么把它放在词法分析之后。LL(1)语法分析器要你在一个很小的工程模型里同时处理集合推导、表驱动匹配和错误恢复这三点恰好是编译器前端最核心的工作方式。你花一个周末把它的逻辑缝起来后面的递归下降、符号表、甚至中间代码生成看起来都会顺很多——因为它们本质上都是同一套「表驱动」的思维。这篇文章按我自己做完后沉淀的顺序来讲先算什么集合、再怎么建表、最后怎么驱动以及那些让我翻过车的细节。写实验二之前把这篇过一遍能少走不少弯路。2. First集与Follow集的计算顺序比深度更值得较劲2.1 为什么要先算这两个集合分析表生成的唯一依据LL(1)分析器本质上是查表给定栈顶的非终结符A和当前输入符a查预测分析表M[A][a]决定用哪条产生式展开。这张表不是人肉拍出来的而是由两套集合算出来的——First集和Follow集。First(A)表示A能推导出的所有串的首终结符集合Follow(A)表示在规范推导中可能紧跟A之后的终结符集合。你写驱动器可能只花两小时但如果不把这两个集合算明白后面分析表出现大片空白你还是不知道为什么合法句子被判非法。很多同学把这两个集合当成纯理论考点实际上它们是整个实验的数据源头算错一步后面全错。2.2 First集的迭代计算一个能跑的最小实现常见做法是用不动点迭代而不是递归因为文法里有间接推导链递归容易陷入环。我一般习惯先把文法读成dictkey是非终结符value是产生式右侧的符号列表。下面这段代码是按教科书的定义做的def first_set(grammar, nonterm): first {nt: set() for nt in grammar} changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for sym in prod: if sym.islower() or sym in #()-*/: # 终结符 if sym not in first[nt]: first[nt].add(sym) changed True break else: # 非终结符 before len(first[nt]) first[nt] | (first[sym] - {}) if len(first[nt]) ! before: changed True if not in first[sym]: # 该符号不能推出空串 break else: if not in first[nt]: # 整条产生式都能推空 first[nt].add() changed True return first逻辑说明对每条产生式从左到右扫遇到终结符就直接收进First集并停止本产生式遇到非终结符时把它自己的First集搬过来注意要临时去掉空串如果该非终结符可以推出空串就继续看下一个符号整条产生式的所有符号都能推空才把空串加入First集。那个for-else是Python里容易被忽略的写法for循环正常跑完没breakelse才执行正好用于「整条产生式都能推空」的情况。参数说明islower()是简易终结符判定只适合小写终结符的文法如果你的终结符是大写或像digit这样的词建议改成显式的终结符集合判断——在first函数外面先收集一遍文法里的所有终结符再传进来。空字符串表示ε。用了一个单独的字符串而不是None是为了后面集合运算和打印方便这个约定在全文要一以贯之。while changed驱动不动点迭代最坏情况下迭代轮数也不会超过非终结符的数量别用递归去算First集存在间接左递归时递归栈会直接炸掉。2.3 Follow集的三个边界条件开始符号、产生式末尾、空串传播Follow集很容易在三个边界上踩坑。第一开始符号的Follow必须包含结束符#或$你选哪个符号就要在全文用哪个不要中途换。第二对形如A → αB的产生式B在末尾时Follow(A)要全部并入Follow(B)。第三对A → αBβ这样的产生式要处理“β恰好能推空”的情形先把First(β)中除了ε之外的符号全部并入Follow(B)如果ε在First(β)里还得把Follow(A)并入Follow(B)。第三个条件最容易被漏因为很多人把它写成else分支而不是独立判断一出错就是黑匣子问题。def nullable_seq(symbols, first): for sym in symbols: if sym in grammar and not in first[sym]: return False if sym not in grammar: # 终结符 return False return True def follow_set(grammar, first, start): follow {nt: set() for nt in grammar} follow[start].add(#) changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: for i, sym in enumerate(prod): if sym not in grammar: # 终结符跳过 continue beta prod[i1:] before len(follow[sym]) if not beta: follow[sym] | follow[nt] else: for b in beta: if b in grammar: follow[sym] | (first[b] - {}) else: follow[sym].add(b) if nullable_seq(beta, first): follow[sym] | follow[nt] if len(follow[sym]) ! before: changed True return follow逻辑说明它对每条产生式的每个符号位置逐一处理。符号是非终结符时先看它后面有没有剩余符号beta。没有剩余符号说明该非终结符位于产生式末尾直接把Follow(nt)并入有剩余符号时先把First(beta)里的终结符全部并入Follow(sym)再单独判断beta整体能否推空——能推空则说明紧跟在该非终结符后的可能还包括Follow(nt)。参数说明nullable_seq是我单独抽出来的工具函数给定一串符号只有当所有符号都是非终结符、且它们的First集都包含空串时才返回True。别把它写进follow计算的if条件里那样代码会绕到你自己都看不懂。before变量用来记录合并前的集合大小有变化才把changed置True否则迭代会提前终止Follow集算出一半就停下来。这个循环每一轮都会遍历所有产生式直到不再发生变化。和First集一样迭代次数有限但如果你在某个集合里忘记了加changed标记程序会陷入死循环——这两个函数是同步工作的一个卡住后面全卡住。3. 预测分析表的生成从集合到M[A][a]的映射规则3.1 表中的冲突为什么是文法问题而不是程序问题First和Follow算完之后建表本身非常机械。对每个A → α把First(α)中所有终结符去掉ε对应的M[A][a]填上这条产生式如果ε在First(α)里就对Follow(A)中每个终结符也填上这条产生式。到这里你会遇到一个关键概念如果某个格子被两条不同的产生式同时抢占说明文法不是LL(1)的程序没法判断该用谁。这通常不是代码bug而是文法没做提取左公因子或者消除左递归这种冲突必须回到文法层面解决靠编码技巧是压不下去的——不同学校实验二的验收重点往往就在这里建议提前确认。3.2 构建分析表的完整实现留空白表项作为错误检测点def first_of_seq(first, seq, grammar): result set() for sym in seq: if sym in grammar: result | (first[sym] - {}) if not in first[sym]: return result else: result.add(sym) return result result.add() return result def build_table(grammar, first, follow): terminals set(#) for prods in grammar.values(): for prod in prods: for sym in prod: if sym not in grammar: terminals.add(sym) table {nt: {t: None for t in terminals} for nt in grammar} for nt, prods in grammar.items(): for prod in prods: fset first_of_seq(first, prod, grammar) for a in fset: if a ! : if table[nt][a] is not None: print(f冲突! {nt} 在 {a} 上: {table[nt][a]} vs {prod}) table[nt][a] prod if in fset: for b in follow[nt]: if table[nt][b] is not None: print(f冲突! {nt} 在 {b} 上: {table[nt][b]} vs {prod}) table[nt][b] prod return table逻辑说明build_table遍历所有产生式对每个产生式的First集合逐个终结符填表再单独处理ε在First中的情况把Follow集合的终结符也填上。数据结构选用dict嵌套dict用None表示空白项。空白项不报错等驱动器访问到时再报语法错误——这是比较常见的设计把错误检测推迟到驱动阶段而不是建表阶段。参数说明first_of_seq是前面First函数的序列版本对一串符号计算可推导的首集合。规则与单个非终结符一样符号能推空才继续检查后续符号不能推空就立刻返回。terminals集合是从文法里自动收集出来的不要手写。手写终结符集总会在某个边界漏掉#或)这是最让人头大的问题来源之一。检测到冲突时用print直接打出来比静默覆盖好。实验二如果书面要求你提交一张无冲突的分析表这段打印就是你判断文法是否为LL(1)的依据。3.3 一个可复现的算数表达式文法从文法到表的全链路为了方便复现我给出一个消除了左递归的文法这也是很多实验模板会直接提供的E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | i右侧符号用i表示标识符 * ( )都是终结符。在Python里这个文法用dict表示就是花一点时间把上面的规则按标准写法录入。用前面三份代码依次跑First、Follow和建表得到的表里有几个特殊项可以用来对拍E行在列是E→ T E在#列和)列是E→εT行在*列是T→* F T在、)、#列是T→ε。如果哪一列是空的就往上面的集合计算里查——不是First就是Follow出了问题。4. 驱动器主循环用栈把分析表变成句子的成功匹配4.1 分析栈是什么已推导部分与未推导部分的界面预测分析器在运行时维护一个栈栈里装的是文法符号。栈底是#栈顶是当前最优先处理的非终结符输入串指针指向当前待分析的字符。每次循环只看两样东西栈顶符号X和输入头a。如果X是终结符且等于a就弹出X、推进输入指针这相当于两个符号对上了号如果X是非终结符就查表table[X][a]把X弹出把产生式右侧符号从右往左压栈如果表项是None就报语法错误。栈里剩余的符号序列就是理论上还没推导完的未来你每次记录的栈快照其实就是整个推导过程的轨迹。4.2 主循环的实现匹配、展开、报错、接受四种动作def parse(table, grammar, start_symbol, tokens): tokens tokens [#] stack [#, start_symbol] pos 0 while stack: top stack.pop() a tokens[pos] if top a and top #: return True if top a: pos 1 continue if top in grammar: # 非终结符查表展开 prod table[top][a] if prod is None: return False if prod []: # 空产生式不压任何东西 continue for sym in reversed(prod): stack.append(sym) else: return False # 栈顶是不可匹配的终结符 return False逻辑说明主循环把情况分成四类。第一类是栈顶和输入都到了#说明两边同时耗尽句子被接受。第二类是栈顶终结符与输入相等正常匹配输入指针后移一位。第三类是栈顶是非终结符去查表查到产生式就把右侧倒序压栈若产生式是ε则什么都不压。第四类是栈顶是不可匹配的终结符直接判非法。这个版本没有错误恢复返回真假适合先把逻辑跑通验证前面三个函数的输出是否正确。参数说明入栈顺序一定要用reversed(prod)否则产生式最左侧符号会在栈顶下方推导顺序就反了这是我第一次写时翻车的点。空产生式用[]表示压栈时什么都不做。直接把[]当普通产生式压栈栈里会多出一个永远匹配不上的ε符号后续步骤全部错位。返回True/False太粗糙了。实验报告如果要展示推导过程建议每次stack.pop()之前把当前栈内容、剩余输入、待用产生式记录下来最后输出一张分析步骤表这能直接写进实验报告亲测加分有效。4.3 语法错误定位一个能说人话的报错策略判断非法只是第一步实验要求的通常是能报错、能定位。常见的做法是panic-mode错误恢复当查表失败时如果是栈顶终结符与输入不匹配就丢弃输入符号直到出现一个能与栈顶匹配的符号如果是非终结符查表为空则直接把栈顶非终结符弹出宣称这里期望某些终结符但遇到了a。前者靠输入指针前移后者靠栈变化两者都不会导致死循环代码也简单。def parse_with_recovery(table, grammar, start_symbol, tokens): tokens tokens [#] stack [#, start_symbol] pos 0 while stack: if pos len(tokens): return False top stack[-1] a tokens[pos] if top a and top #: return True if top a: stack.pop() pos 1 elif top in grammar and table[top].get(a) is not None: stack.pop() prod table[top][a] if prod ! []: for sym in reversed(prod): stack.append(sym) elif top in grammar: expected [t for t, v in table[top].items() if v is not None] print(f第 {pos} 个符号 {a} 无法匹配 {top}期望 {expected}) stack.pop() else: print(f第 {pos} 个符号 {a} 与栈顶 {top} 不匹配跳过) pos 1 return False逻辑说明区别在最后两个分支栈顶是非终结符但表项为空时弹掉栈顶并打印期望集合栈顶终结符与输入不匹配时直接把输入指针往后挪把当前字符丢进跳过区。这种策略不会一次报出一百条错误每条真实错误基本只报一次比较像真实编译器的表现。注意这里用stack[-1]而不是pop是为了在报错时保留栈内容方便调试。参数说明期望集合直接用table[top]字典里非None项对应的键生成这个打印信息读起来是期望遇到、)或#但遇到了*比语法错误四个字有用得多。跳过策略有个边界如果输入从头到尾都匹配不上pos会一路跑到len(tokens)所以while条件里必须加上pos len(tokens)的短路保护否则越界取到None整个程序异常退出。5. 高频翻车点从现象反推文法与代码问题5.1 现象1First和Follow循环引用导致死循环现象程序能跑但卡在计算First集CPU占用暴涨等了五分钟没结果。原因最常见是把不动点迭代写成了直接递归。对A → B C、B → A D这类间接左递归文法递归算First时A等着B的结果B又等着A的结果递归栈就挂住了。解决改成while changed形式的迭代每轮把集合变化合并后再重新扫描直到没有任何集合变化。迭代轮数不会超过非终结符链的长度上限通常十轮内必然收敛。如果你在递归里加了visited标记说明方向对了但你绕远了。5.2 现象2分析表大片空白合法句子被判非法现象用i i * i这样教科书级的句子去测parse返回False但手推明明能导出来。原因这个黑匣子问题往往是Follow集漏了beta为空串可推空的分支或者终结符集合手写漏了)和#。表里空白的M[T][]就是这么来的。解决先把终结符收集自动化再去把2.3里的三个边界条件逐行对一遍。建议在build_table里加一个自检循环检查每个非终结符在终结符加#上是否都有表项没有就打印缺失项——这个自检能救很多次我后来每个版本都保留着这段检查代码。5.3 现象3左递归文法导致分析栈无限增长现象运行时栈里元素越来越多最终MemoryError中断。原因文法没有消除左递归比如原始表达式文法E → E T直接喂给建表程序。查表会让E在遇到i时用E → E T展开栈里永远有一个E输入指针却几乎不动。解决先手工消除左递归再喂程序或者写一个自动消除左递归的函数把A → A α | β转换成A → β A、A → α A | ε。这个转换在实验报告里要单独写一节体现很多老师会专门看这个步骤——它算是对「为什么LL(1)不接受左递归」的直接回答。5.4 现象4空串ε的表示混用现象代码里有的地方用表示空串有的地方用ε有的地方用None。查表时prod []和prod is None的判断在交替使用中出错或者打印步骤表时显示一片混乱。原因字符串和None混用后空产生式被压栈后永远无法被消掉输入匹配经常差一步。解决全程序统一用。如果实验报告要求展示ε只在输出格式化时把翻译成ε来显示数据结构内部不换表示。老代码里同时出现过None和ε那几天排查得昏天黑地这个建议是血泪换来的。5.5 现象5错误恢复后死循环或越界现象加上了错误恢复功能之后程序要么在报错过的地方原地打转要么直接IndexError越界退出。原因panic-mode的两个分支里弹栈分支和跳过分支没有配合好。当栈顶非终结符查表为空时你弹栈是对的但如果输入串里恰好没有能匹配新栈顶的字符pos不推进while会一直转反过来跳过分支也一样。解决两条规则同时应用就安全了——报错时非终结符表项为空就弹栈终结符不匹配就前进pos一次报错至少让「栈状态」或「输入位置」二者之一前进一步。另外一个保险是在while循环顶部加pos len(tokens)判断保底不越界。6. 从能跑通到能答辩三个验证技巧与一个土办法6.1 用三条句子把四类行为全部覆盖验证一个LL(1)分析器要测三类句子而不是一条第一类是能完全匹配的合法串如i i * i第二类是开头合法但中途出错的串如i * i第三类是首符号就不在First集里的串如* i。前两类分别验证错误恢复的两个分支第三类验证起始判断。我建议把这三类句子和预期行为写成一个简单的对比表第一类必须返回True且无报错第二类返回False且报错位置在第3个符号左右第三类返回False且报错位置在第1个符号。把这张表放进实验报告的测试章节比截图一张终端输出要严谨。6.2 输出分析步骤表然后逐行对拍把每次栈变化按「步骤号、栈、剩余输入、所用产生式或动作」格式化输出。对拍方法很土但有效拿一个长度不超过5个token的句子让程序跑出来的步骤表和你自己用铅笔在草稿纸上手动推导的步骤表逐行对比。第一次做这个实验时我偷懒只对拍了最终结果结果栈里压了一个多余的T导致结论恰好正确步骤却错得离谱。从那以后我只相信步骤表对拍一行一行地看别嫌慢。6.3 把分析表结构化保存方便调试和答辩展示分析表生成后保存成CSV行是非终结符列是终结符单元格是产生式。这个文件既能用来快速查看哪里有空白项也是实验报告里可以直接当作成果展示的素材。答辩时被问「你的表怎么建的」直接打开CSV指出E行在#列是ε产生式、T行在)列是ε产生式比在终端里翻代码有说服力得多。这三步做完实验二就不只是「能跑」而是能讲清楚每个细节。后续做语法分析树构建、中间代码生成本质上还是这套表驱动框架。希望帮到你。本文还有配套的精品资源点击获取

LL(1)语法分析器实验详解：First集、Follow集与预测分析表构建

相关推荐

FastAPI实现软删除：从字段设计到查询过滤的完整实践

豆瓣影评情感分析：朴素贝叶斯文本分类实战

操作系统T1考题解析：进程状态迁移与上下文切换双线推演

更多资讯

计算机网络实验全链路：从Boson Netsim拓扑到SOCKET编程实战

基于Python的微博舆情分析可视化系统：爬虫、情感分析与展示全流程

近红外光谱回归建模：物理约束驱动的深度学习方法

开题报告写作新思路：千笔与灵感风暴AI的分工协作指南

网红罗盘时钟：物理+代码+光影的时间装置入门指南

Advanced Installer 20.7.1：打造干净可复现的MSI安装包与升级链路

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

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

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

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

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