编译原理LL1语法分析：FIRST集与FOLLOW集计算及预测分析表实现-北京尧图网络

简介这份资源是山东科技大学2022年编译原理课程的实验配套材料聚焦语法分析中的LL(1)分析法实现面向正在学习编译原理、需要完成课程实验或准备相关考试的高校学生。实验要求对给定文法含E、G、T、M、F等非终结符及、-、*、/、(、)、i等符号构造LL(1)分析表并对任意输入符号串进行语法分析资源提供了可直接运行的完整代码与实验报告帮助读者理解FIRST集、FOLLOW集、预测分析表的构建流程。压缩包为zip格式大小约1.08MB内含源码与文档等文件便于在CodeBlocks等环境中直接编译运行。目前已有915人学习下载适合需要快速获取可运行实验方案、对照报告梳理分析步骤或排查代码问题的读者参考使用。1. 语法分析之LL1分析法从FIRST集到预测分析表的完整落地很多同学做编译原理实验时词法分析写得挺顺一到语法分析就卡住了。尤其是LL1分析法课本上把FIRST集、FOLLOW集、预测分析表讲得云里雾里真到动手写代码发现连输入串怎么被“吃掉”的都看不明白。这个实验的核心其实就三件事给定一个文法算出FIRST集和FOLLOW集构造预测分析表然后用一个栈去模拟最左推导过程。听起来简单但每一步都有细节能把人卡半天。这篇文章面向正在做编译原理实验的本科生也适合想重新捡起语法分析底层逻辑的开发者。我会用一个具体的算术表达式文法做例子把每个步骤的代码和参数都写清楚你照着改改就能跑自己的文法。LL1分析法虽然能力有限但它是理解自顶向下语法分析最好的入口搞懂它后面的LR系列才不会觉得是玄学。2. 文法预处理与FIRST/FOLLOW集计算手算和代码怎么对齐2.1 为什么LL1要求文法无左递归且提取左公因子LL1分析法的第一个硬性条件就是文法不能有左递归。左递归分两种直接左递归比如E - E T间接左递归比如A - BcB - Ad。为什么不能有因为LL1是自顶向下分析从左到右扫描输入每次只看一个终结符就要决定用哪条产生式。如果存在左递归递归下降时会无限调用自己栈永远压不完。消除直接左递归有固定套路。假设产生式是A - Aα | β其中α和β是符号串β不以A开头。改写成A - βA A - αA | ε间接左递归要先通过代入法把间接变成直接再消除。提取左公因子则是为了解决另一个问题当两条产生式有共同前缀时LL1分析表的一个格子会出现两个候选产生式这就冲突了。比如S - if E then S和S - if E then S else S前看一个token是if根本分不清该选哪条。提取左公因子后变成S - if E then S S S - else S | ε这一步做完文法才具备LL1分析的基本资格。我一般会先手算一遍确认没有左递归和公共前缀再写代码不然代码跑出来的表全是冲突排查起来很痛苦。2.2 FIRST集和FOLLOW集的递推算法与代码实现FIRST集的定义是一个符号串能推导出的所有可能的开头终结符集合。如果这个符号串能推导出空串ε那ε也在FIRST集里。FOLLOW集则是在某个句型中紧跟在非终结符后面的终结符集合。对于开始符号要把结束符$加入它的FOLLOW集。计算FIRST集用递推法。对每条产生式X - Y1Y2...Yk先把FIRST(Y1)中除ε外的符号加入FIRST(X)。如果Y1能推出ε就继续看Y2以此类推。如果所有Yi都能推出ε那ε也加入FIRST(X)。FOLLOW集的计算稍微绕一点对每条产生式A - αBβ把FIRST(β)中除ε外的符号加入FOLLOW(B)如果β能推出ε或者β不存在就把FOLLOW(A)加入FOLLOW(B)。下面是用Python实现的代码输入是文法产生式输出FIRST和FOLLOW集# 文法定义字典的key是非终结符value是产生式右部列表 # 每个产生式右部用空格分隔的符号串表示空串用 ε 表示 grammar { E: [T E\], E\: [ T E\, ε], T: [F T\], T\: [* F T\, ε], F: [( E ), id] } # 终结符集合手动指定也可以从文法中自动提取 terminals {, *, (, ), id, $} non_terminals set(grammar.keys()) start_symbol E # 初始化FIRST集 FIRST {nt: set() for nt in non_terminals} # 终结符的FIRST集就是它自己 for t in terminals: FIRST[t] {t} def compute_first(): changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: symbols prod.split() if symbols [ε]: if ε not in FIRST[nt]: FIRST[nt].add(ε) changed True continue # 遍历产生式右部每个符号 all_nullable True for sym in symbols: if sym not in FIRST: FIRST[sym] {sym} # 把FIRST(sym)中除ε外的加入FIRST(nt) for f in FIRST[sym] - {ε}: if f not in FIRST[nt]: FIRST[nt].add(f) changed True # 如果sym不能推出ε停止 if ε not in FIRST[sym]: all_nullable False break if all_nullable: if ε not in FIRST[nt]: FIRST[nt].add(ε) changed True compute_first() print(FIRST集) for nt in non_terminals: print(f FIRST({nt}) {FIRST[nt]})这段代码的核心逻辑是不断迭代直到集合不再变化。all_nullable变量用来判断当前产生式右部是否所有符号都能推出ε。注意FIRST[sym]对于终结符就是它自己对于非终结符则依赖之前的计算结果所以必须用while循环反复扫描。FOLLOW集的代码类似但要注意开始符号的$FOLLOW {nt: set() for nt in non_terminals} FOLLOW[start_symbol].add($) def compute_follow(): changed True while changed: changed False for nt, productions in grammar.items(): for prod in productions: symbols prod.split() for i, sym in enumerate(symbols): if sym not in non_terminals: continue # 看sym后面的符号 rest symbols[i1:] if not rest: # 后面没东西了把FOLLOW(nt)加进来 for f in FOLLOW[nt]: if f not in FOLLOW[sym]: FOLLOW[sym].add(f) changed True else: all_nullable True for r in rest: if r not in FIRST: FIRST[r] {r} for f in FIRST[r] - {ε}: if f not in FOLLOW[sym]: FOLLOW[sym].add(f) changed True if ε not in FIRST[r]: all_nullable False break if all_nullable: for f in FOLLOW[nt]: if f not in FOLLOW[sym]: FOLLOW[sym].add(f) changed True compute_follow() print(\nFOLLOW集) for nt in non_terminals: print(f FOLLOW({nt}) {FOLLOW[nt]})参数说明grammar字典的key必须是非终结符value是产生式右部列表每个产生式用空格分隔符号空串统一写成ε。terminals集合要包含所有终结符和结束符$。运行后你会得到每个非终结符的FIRST和FOLLOW集拿手算结果对一下如果对不上大概率是某个产生式的ε处理漏了。2.3 预测分析表的构造规则与冲突检测有了FIRST和FOLLOW集构造预测分析表就水到渠成了。表的行是非终结符列是终结符包括$。对每条产生式A - α对FIRST(α)中的每个终结符a把A - α填入M[A][a]。如果ε在FIRST(α)中则对FOLLOW(A)中的每个终结符b把A - α填入M[A][b]。如果某个格子被填了两次说明有冲突这个文法就不是LL1文法。冲突检测很重要我见过不少同学的表填完了跑不通就是因为没检查冲突硬着头皮往下写结果分析栈的行为完全不可预测。# 构造预测分析表 table {nt: {} for nt in non_terminals} conflicts [] for nt, productions in grammar.items(): for prod in productions: symbols prod.split() first_set set() if symbols [ε]: first_set {ε} else: all_nullable True for sym in symbols: if sym not in FIRST: FIRST[sym] {sym} first_set | (FIRST[sym] - {ε}) if ε not in FIRST[sym]: all_nullable False break if all_nullable: first_set.add(ε) for a in first_set - {ε}: if a in table[nt]: conflicts.append((nt, a, table[nt][a], prod)) table[nt][a] prod if ε in first_set: for b in FOLLOW[nt]: if b in table[nt]: conflicts.append((nt, b, table[nt][b], prod)) table[nt][b] prod if conflicts: print(\n发现冲突) for c in conflicts: print(f M[{c[0]}][{c[1]}] 同时有 {c[2]} 和 {c[3]}) else: print(\n预测分析表构造成功无冲突) # 打印表格 all_terminals sorted(terminals) header .join(f{t:8} for t in all_terminals) print(header) for nt in non_terminals: row f{nt:5} for t in all_terminals: val table[nt].get(t, ) row f{val:8} print(row)这段代码里conflicts列表记录了所有冲突位置。如果输出为空恭喜你文法通过LL1检验。否则需要回到文法层面修改通常是提取左公因子或消除左递归没做干净。3. 用栈驱动LL1分析从输入串到推导树的完整模拟3.1 分析栈的初始状态与动作定义LL1分析器本质上是一个下推自动机。它维护一个栈初始时栈里只有开始符号和结束符$栈底是$栈顶是开始符号。输入缓冲区里是待分析的token序列末尾也加上$。然后循环执行看栈顶符号X和当前输入符号a。如果X是终结符且X a弹出栈顶输入指针后移。如果X是终结符且X ! a报错。如果X是非终结符查预测分析表M[X][a]如果表项为空报错否则用产生式右部替换栈顶的X右部符号逆序压栈保证最左符号在栈顶。如果X $且a $分析成功。这个过程中栈里存的是符号输入指针指向当前token。每次替换栈顶非终结符就相当于在推导树上展开一个节点。我建议在代码里把每一步的栈内容和剩余输入都打印出来这样能直观看到最左推导的过程调试时特别有用。3.2 完整分析器代码与逐步输出下面是一个完整的LL1分析器实现接上面的预测分析表def ll1_parse(input_tokens): input_tokens: 输入的token列表例如 [id, , id, *, id] # 栈初始化栈底是$然后是开始符号 stack [$, start_symbol] # 输入末尾加$ tokens input_tokens [$] pos 0 # 输入指针 print(f\n{步骤:6}{栈内容:30}{当前输入:15}{动作}) print(- * 80) step 0 while stack: step 1 top stack[-1] current tokens[pos] stack_str .join(reversed(stack)) remaining .join(tokens[pos:]) if top $ and current $: print(f{step:6}{stack_str:30}{remaining:15}分析成功) return True if top in terminals: if top current: print(f{step:6}{stack_str:30}{remaining:15}匹配 {top}) stack.pop() pos 1 else: print(f{step:6}{stack_str:30}{remaining:15}错误期望 {top}实际 {current}) return False else: # 非终结符查表 if current in table.get(top, {}): prod table[top][current] print(f{step:6}{stack_str:30}{remaining:15}用 {top} - {prod}) stack.pop() if prod ! ε: # 逆序压栈 symbols prod.split() for sym in reversed(symbols): stack.append(sym) else: print(f{step:6}{stack_str:30}{remaining:15}错误M[{top}][{current}] 为空) return False return False # 测试 test_input [id, , id, *, id] print(f\n输入串{ .join(test_input)}) result ll1_parse(test_input) print(f\n分析结果{接受 if result else 拒绝})运行这段代码你会看到每一步的栈变化。比如第一步栈是$ E当前输入是id查表得E - T E于是弹出E压入E和T逆序栈变成$ E T。接着栈顶是T继续展开。整个过程就是最左推导的逆过程。参数说明input_tokens是词法分析输出的token列表每个token必须是终结符集合里的符号。如果你的词法分析器输出的是(type, value)二元组需要先提取type字段。table就是上一步构造的预测分析表。stack用列表模拟append和pop都在尾部操作所以栈顶是列表末尾。3.3 错误恢复的两种实用策略实际实验中输入串不一定完全合法错误恢复能力是加分项。LL1分析器的错误恢复有两种常用策略第一种是恐慌模式。当查表发现M[X][a]为空时从栈顶开始弹出符号直到栈顶是终结符且能跟当前输入匹配或者栈顶的FOLLOW集包含当前输入符号。然后跳过输入中的一些token直到找到一个能继续的同步符号。这种策略实现简单但可能跳过大量输入。第二种是短语层恢复。在预测分析表里预先填入同步记号比如用synch标记。当遇到错误时如果表项是synch就弹出栈顶非终结符不消耗输入相当于假装这个非终结符已经正确推导完了。这种策略更精细但需要手动指定同步集合。我一般会在实验里加一个简单的恐慌模式恢复至少让程序不会一遇到错误就崩溃而是能报告错误位置并继续检查后面的内容。具体做法是在查表失败时打印错误信息然后弹出栈顶符号直到栈顶是$或者当前输入符号在栈顶非终结符的FOLLOW集里。4. 避坑指南LL1实验里最容易翻车的五个地方4.1 文法左递归没消干净程序直接栈溢出现象程序运行后卡死或者报递归深度超限。原因文法里存在间接左递归手算时没发现。比如A - BcB - Ad看起来没有直接左递归但代入后A - Adc还是左递归。解决写一个检测函数对每个非终结符看它能否经过若干步推导回到自己。更简单的办法是先把所有产生式代入展开再检查是否有A - A...的形式。我一般会在代码里加一个check_left_recursion函数跑一遍再往下做。4.2 FIRST集计算时漏掉ε的传递现象预测分析表某些格子为空但手算明明有产生式。原因计算FIRST集时某个符号能推出ε但代码里没有继续看后面的符号。比如A - B CB能推出εC能推出ε那A也能推出ε。如果代码在B推出ε后就停了就会漏掉。解决用all_nullable标志只有当前面所有符号都能推出ε时才继续看下一个符号。这个逻辑在2.2节的代码里已经体现了但手写时很容易漏。4.3 预测分析表冲突被忽略运行时行为诡异现象程序有时能跑通有时报错换个输入串结果完全不对。原因表里有冲突同一个格子被覆盖了两次后填的产生式覆盖了前面的。解决在填表时用conflicts列表记录所有重复填充一旦发现冲突就打印出来。如果冲突无法通过修改文法消除说明这个文法不是LL1文法需要考虑用LL1以外的分析方法或者继续提取左公因子。4.4 栈的压入顺序搞反推导顺序全乱现象分析过程看起来在走但匹配的token顺序不对很快就报错。原因用产生式右部替换栈顶时应该逆序压栈保证最左符号在栈顶。如果顺序压栈最右符号在栈顶就变成了最右推导跟LL1的最左推导矛盾。解决压栈前用reversed(symbols)或者用stack.extend(reversed(symbols))。这个细节课本上往往一笔带过但写代码时错一次就够你查半天。4.5 输入串末尾忘记加结束符现象分析到最后栈里还剩$输入已经空了程序报索引越界。原因输入token列表末尾没有加$导致tokens[pos]在pos超出范围时崩溃。解决在ll1_parse函数开头就执行tokens input_tokens [$]并且循环条件里检查pos len(tokens)。另外栈底也要先压入$这样最后才能匹配上。5. 从LL1到实际编译器一个可复用的分析器骨架LL1分析法虽然只能处理一小类文法但它的代码骨架可以复用到更复杂的场景。我习惯把整个分析器拆成三个模块文法加载模块、集合计算模块、分析驱动模块。文法加载模块负责读入产生式支持从文本文件读取每行一条产生式用-分隔左右部。集合计算模块就是第2章的代码封装成类对外暴露get_first()、get_follow()、get_table()三个方法。分析驱动模块接收token流返回推导步骤列表或语法树。如果你想让这个实验更有含金量可以加两个进阶功能。第一个是自动生成推导树。在分析过程中每次用产生式展开非终结符时就在树结构里加一个节点记录父节点和子节点关系。分析结束后用递归方式打印树形结构或者导出成DOT格式用Graphviz可视化。第二个是支持多条产生式合并。有些文法里同一个非终结符有多条产生式右部首符号不同可以合并成一条带|的产生式加载时自动拆分。这样文法文件写起来更紧凑。验证方法很简单准备三组测试输入。第一组是合法输入比如id id * id应该接受。第二组是缺少右括号的输入比如( id id应该在某个位置报错并指出期望的符号。第三组是多余运算符的输入比如id * id应该在*处报错。如果三组都能正确处理说明分析器基本可靠。最后说个我自己的习惯每次写完集合计算代码我都会先拿一个只有两三条产生式的小文法手算一遍把FIRST和FOLLOW集写在纸上再跟代码输出对比。这一步花不了五分钟但能省下后面几小时的调试时间。LL1分析法的坑大多不在算法本身而在这些边边角角的细节处理上。希望帮到你。本文还有配套的精品资源点击获取

编译原理LL1语法分析：FIRST集与FOLLOW集计算及预测分析表实现

相关推荐

pstack-claude：用LLM增强Linux进程栈分析的轻量级调试方案

生成式AI消费级应用Top 100——第六版：用TaoToken统一Key复现榜单数据管道

从零手写Java动态数组：理解扩容原理与ArrayList核心机制

更多资讯

考勤管理系统源码包解析：数据库设计与部署避坑指南

长尾效应与肥尾效应：从选品到风控的决策指南

8086机器语言解码实战：手写指令解码器与反汇编入门

抽象代数核心：群环域与伽罗瓦理论考点解析

Python base64 编码为什么带 b‘xxx‘？彻底搞懂 bytes 与 str 的边界

视觉骨干网络演进：VIT、Swin、MAE、CLIP四篇论文精读与实战

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

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

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

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

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