LL(1)语法分析器实现指南：从FIRST集与FOLLOW集到预测分析表

简介编译原理课程中的LL(1)语法分析器实验往往需要同时完成文法设计、预测分析表构造与输入串判别等多个环节。这套资源面向正在学习自顶向下语法分析的本科生围绕实验二提供了一个完整方案内含源代码、可执行程序、实验报告、程序设计思想及讲解视频。压缩包共13个文件大小约24.81MB其中cpp与dev文件用于查看和重新编译工程exe可直接运行验证doc与docx文档涵盖实验报告与设计思路mp4视频演示关键实现步骤便于对照学习。内容覆盖了从读入LL(1)文法、构造预测分析表到判断输入串是否为文法句子的完整流程可帮助读者理解语法分析程序的实现方式并直接用于实验参考。目前已有3101人学习下载适合编译原理实验课内练习或复习巩固。1. LL(1)语法分析器把编译原理实验二从“会画表”推进到“能跑通”做编译原理实验二时真正卡人的往往不是预测分析表怎么画而是“程序如何自动判断输入串是不是该文法的句子”。LL(1)语法分析器这份资源恰好把这条链路完整打包了源码、可执行程序、讲解视频、实验报告和程序设计思想文档都在同一个包里。它的价值很直接——输入一个LL(1)文法程序构造预测分析表然后从键盘读入输入串是句子就通过不是就报错。适合正在赶实验、想先对照源码看懂再动手改代码的学生也适合工作多年后需要快速回顾自顶向下分析机制的从业者。如果你接受一个前提程序要能按文法自动填表这份资源就是实打实的落地参考。2. 预测分析表怎么构造FIRST、FOLLOW 集与冲突判定LL(1)名称里的两个“1”分别指“从左到右扫描、最左推导、向前看一个符号”。这里的核心前置是FIRST集、FOLLOW集和利用它们填出来的预测分析表。很多同学手算表没问题但一到程序就不知道这些集合该用什么结构存、怎么迭代算。这一章把三个步骤拆开重点放在“程序视角”。2.1 FIRST 集迭代求解比递归更适合写程序FIRST集描述的是一个文法符号串能推导出的所有可能开头终结符。求它的规则不复杂终结符的FIRST就是自身非终结符A若有产生式A→α则把FIRST(α)里的终结符都并入FIRST(A)如果α能推导出空串空串也属于FIRST(A)。手算时人脑能一眼看出推导路径程序不能所以程序里一般用迭代每一轮把所有产生式扫一遍只要有集合新增了元素就再扫一轮直到所有集合大小都不再变化为止。// 求解 FIRST 集的迭代框架 // 符号约定eps 表示空串 ε在程序里常用 或 代替 // first[x] 表示符号 x 的 FIRST 集合用 bool 数组标记是否包含某个终结符 vectorbool first[MAX_SYM]; bool changed true; while (changed) { changed false; for (每条产生式 A - X1 X2 ... Xn) { int before first[A].count(); if (X1 是终结符) { first[A].add(X1); // 首符号是终结符直接并入 } else { first[A].addAll(first[X1]); // 并入首符号的 FIRST // 若 X1 可空继续看 X2用 i 记录当前扫到第几个符号 int i 0; while (i n X_i 可空) { first[A].addAll(first[X_{i1}]); i; } if (i n) first[A].add(eps); // 整个右部可空空串加入 } if (first[A].count() before) changed true; } }这段逻辑里最容易错的是“右部全可空”的判断。比如产生式 A→BCB 和 C 都能推出空串那么 A 的 FIRST 里必须有 eps否则后面 FOLLOW 集的计算会全部错位。程序里判断“符号是否可空”通常是查该符号的 FIRST 里有没有 eps所以求 FIRST 时先处理“直接产生空串的产生式”会让迭代收敛更快。另一个实践细节是空串的表示源码里一般不会直接用字符 ε常见有“”、“”或字符串“EPS”如果你把输入文法里的 ε 写成中文输入法的“ε”程序多半识别不了。FIRST 集合的存储结构看文法规模。实验文法的符号个数通常不超过 30 个用二维布尔数组或者 vector 都行。我一般习惯用布尔数组因为后续填预测分析表时要频繁做“某个终结符在不在集合里”的查询布尔数组的 O(1) 查询在循环里最省心。如果你要支持更复杂的文法再把 bool 换成 set 代价是每次插入要判断重复性能慢一点但思路完全一致。2.2 FOLLOW 集从“开头”倒推“后继”的三条规则FOLLOW集描述的是一个非终结符在推导过程中右边可能出现的终结符集合。它解决的是预测分析表里“空串分支”的问题当某产生式右部能推出空串时当前非终结符后面跟着什么决定了该不该用这个产生式。手算 FOLLOW 是从开始符号出发一遍推导就出来了程序里同样得用迭代因为 FOLLOW 的定义互相依赖。// FOLLOW 集求解的三条规则对应程序实现 // 初始化follow[start].add(#)# 是输入结束符 // 循环扫描所有产生式直到没有集合变化 for (每条产生式 A - X1 X2 ... Xn) { for (int i 0; i n; i) { if (X_i 是非终结符) { // 规则 2A - α B β把 FIRST(β) 里除 eps 外的终结符并入 FOLLOW(B) for (int j i 1; j n; j) { follow[X_i].addAll(first[X_j] 去掉 eps); if (X_j 不可空) break; // β 不能推出空串就停止后看 } // 规则 3A - α B 或 β 可空把 FOLLOW(A) 并入 FOLLOW(B) if (i 右边的所有符号都可空) { follow[X_i].addAll(follow[A]); } // 规则 1开始符号的 FOLLOW 里要有 # follow[start].add(#); } } }这三条规则里规则 3 是最容易被忽略的。每一轮迭代里 FOLLOW(A) 可能还没算完就把它并入 FOLLOW(B)那么下一轮循环必须再来一遍直到 FOLLOW(A) 本身不再增长所以外层用 while(changed) 包住这个 for 循环。这个“变化驱动继续迭代”的思路在 FIRST、FOLLOW、闭包类算法里都是同一个套路建议直接背下来。程序实现还有一个细节规则 2 里“FIRST(β) 去掉 eps”和“β 可空”的判断依赖的是 FIRST 集是否包含 eps。所以 FIRST 没求对FOLLOW 一定跟着错。调试时如果发现 FOLLOW 结果和手算不一致先回头查 FIRST 里 eps 的位置不要急着改 FOLLOW 的逻辑。2.3 预测分析表一张表把所有冲突暴露出来预测分析表是个二维表行标是非终结符列标是终结符加上 #每个格子存放一个产生式右部。填表规则// 填表核心逻辑 for (每条产生式 A - α) { for (终结符 t ∈ FIRST(α)) { 表[A][t] α; // 直接把可用的产生式放进去 } if (eps ∈ FIRST(α)) { for (终结符 t ∈ FOLLOW(A)) { 表[A][t] α; // α 可空时FOLLOW 中的终结符也触发 } } }第 7 行和第 10 行可能同时往同一个格子填内容这就是 LL(1) 冲突。常规做法是填入前先查格子是否已有值如果有就把文法判定为“非 LL(1) 文法”输出冲突的产生式对。手算表时你对冲突的判断多半是“发现同一个格子里有两条产生式”程序里就是一次 if 判断的事但很多初版代码直接写赋值语句后写覆盖先写冲突被静默吞掉这是最危险的坑第五章会专门展开。判断文法是否为 LL(1) 除了看表冲突还可以用两个硬性条件快速筛选第一不能有左递归第二对每个非终结符 AFIRST(A) 与 FOLLOW(A) 不能有交集。这两个条件满足后再填表冲突几乎不会出现。程序里放一个 checkConflict() 函数在填表结束时遍历一次表把所有冲突输出会让你实验报告里“如何判断 LL(1) 文法”这一小节非常有话写。3. 拿到源码先读这三块数据结构、驱动循环、报错链路实验资源里的 LL(1) 语法分析器.cpp 是主体实现。面对一个几百行的 C 实验源码从头一行行读效率低正确方式是先找三类东西数据结构定义、主循环、错误处理。把它们读明白程序等于看懂了一半。这一章按读源码的顺序来讲。3.1 三个核心结构产生式表、预测表与符号栈实验性质的分析器数据结构一般不会用复杂封装最常见的是定长数组。先找这几个声明// 典型的数据结构声明各实验源码命名略有差异 #define MAX_SYM 50 // 支持的最大符号数 #define MAX_PROD 100 // 支持的最大产生式数 struct Production { char left; // 产生式左部一个非终结符 char right[MAX_SYM]; // 产生式右部字符串如 T*F }; Production prods[MAX_PROD]; // 产生式表 char nonTerminals[MAX_SYM]; // 非终结符集合 char terminals[MAX_SYM]; // 终结符集合 int predictTable[MAX_SYM][MAX_SYM]; // 预测分析表值为产生式下标-1 表示错误predictTable 的行列不是直接用字符下标而是用符号在 nonTerminals、terminals 数组里的下标。所以程序里会有两个查下标的函数比如 getNTIndex(char c)。做实验时如果要往程序里填文法改的就是这几个数组的初始化部分而不是主循环。预测表用 int 型二维数组存产生式下标是实验标准写法好处是判断“格子是否为空”只要比较是否为 -1比存字符串省事得多。符号栈在源码里要么用 std::stack要么自己写个 int 数组加栈顶指针。实验程序用数组栈更常见因为要输出每一步的栈内容数组遍历起来比 stack 方便。栈里存的是符号的 ASCII 码末尾用 # 标记结束。看清楚栈的初始化位置通常在分析开始前压入 # 和开始符号顺序是先 # 后开始符号这样栈顶才是开始符号。3.2 驱动主循环查表、压栈、匹配、推进主循环是整个程序的核心通常长这样// LL(1) 分析主循环框架 int top 0; // 栈顶指针 char stack[MAX_SYM]; // 分析栈 stack[0] #; // 栈底 stack[1] startSymbol; // 开始符号 top 1; int ip 0; // 输入串指针 char input[MAX_SYM]; // 待分析的输入串 while (stack[top] ! #) { // 栈底 # 说明分析结束 char X stack[top]; // X 是当前栈顶 char a input[ip]; // a 是当前输入符号 if (X a X #) break; // 成功栈和输入同时到结尾 if (X 是终结符 || X #) { if (X a) { top--; ip; continue; } // 匹配双双推进 else reportError(栈顶终结符与输入不匹配); } else { int row getNTIndex(X); int col getTerminalIndex(a); int prodIdx predictTable[row][col]; if (prodIdx -1) { reportError(预测表为空输入串不是句子的推导结果); } else { // 弹出栈顶把产生式右部逆序压栈 top--; char* right prods[prodIdx].right; if (right 不是 eps) { for (int k strlen(right) - 1; k 0; k--) { stack[top] right[k]; } } } } } if (stack[top] # input[ip] #) printf(分析成功\n);看这段代码你基本能理解 LL(1) 的“预测”到底发生在哪第 20 行查表。栈顶非终结符对应当前输入符号查预测分析表确定唯一产生式。压栈时注意是逆序压入右部第一个符号最后压所以它最先弹出、最先匹配。如果产生式右部是空串就直接弹掉栈顶不往里压任何东西相当于“消耗掉”这个非终结符。这个循环里最容易被忽略的是栈底判断。有的程序用 stack[top] # 做退出条件但没有同时判断 input[ip] 是否也等于 #导致输入串提前读完后栈里还有东西程序会拿栈顶非终结符去查表列下标对到 # 上表项通常是空的于是报错。如果你实验时发现“合法句子被报错”先看是不是输入串末尾没有补 #。3.3 错误处理三种报错出口和一种静默错误实验要求里明确写了“若正确就通过若错误就报错”所以程序的报错会集中在这几个出口栈顶终结符与输入符号不一致预测表对应格子为空输入串扫描完了但栈没空。每一种都对应一个错误码或错误信息实验报告里要把这几条列出来。真正的麻烦是静默错误——程序不报错但结果是错的。最常见的是两种一是预测表冲突被覆盖导致合法句子被错误接受二是 FIRST/FOLLOW 算错但表恰好没冲突分析过程看着不报错推导步骤却和文法的实际推导不一致。这类问题在输出“分析成功”时尤其有迷惑性所以拿到源码第一件事不是跑例子而是构造一个“必须报错”的输入串确认程序真的会报错。如果连明显的非法串都被判定成功先检查填表逻辑而不是检查分析主循环。4. 跑起来再说工具链、复现步骤与自定义文法替换4.1 包里文件怎么分工用哪个工具打开解压这个 zip 包后文件比想象中齐全。.dev 和 .layout 是 Dev-C 的工程文件和窗口布局文件Makefile.win 是配套的 make 脚本说明这份源码是在 Dev-C 环境下开发的.o 和 .exe 是编译中间产物和编译好的程序讲解视频.mp4 是配套讲解程序设计思想.docx 是根据源码写的设计说明编译原理实验二.docx 和《编译原理》实验二-2020.doc 是实验报告模板和题目要求。文件分工如下表。文件类型用途LL(1)语法分析器.cpp源码主实现实验报告的核心依据法二.cpp / 法二.exe源码 / 程序另一套实现思路可用于对比写法LL(1)语法分析程序.dev工程文件用 Dev-C 直接打开编译Makefile.win构建脚本Dev-C / MinGW 环境下的编译入口LL(1)语法分析器.o中间产物运行无关可忽略讲解视频.mp4视频对照源码看运行流程程序设计思想.docx文档写实验报告时可参考的设计思路编译原理实验二.docx / 实验二-2020.doc文档实验题目与报告模板工具链选择上最省事的是装一个 Dev-C直接双击 LL(1)语法分析程序.dev 打开工程点编译运行。如果你不喜欢 Dev-C 的老界面用 VS Code 加 MinGW 也可以手动按 Makefile.win 的内容执行 make 即可。注意 .o 和 .exe 是别人机器上编译出来的能跑不代表你能改修改源码后一定要重新编译生成新的 exe否则你改的代码不会生效。4.2 第一次运行输入文法、输入串看分析过程程序的交互流程遵循实验二的标准要求先构造预测分析表再读入输入串。运行后按提示依次输入终结符、非终结符、产生式列表最后输入要判断的串。下面是一次典型的会话示意请输入终结符个数: 4 请输入终结符(不含#): i * ( ) 请输入非终结符个数: 3 请输入非终结符: E T F 请输入产生式个数: 6 请输入产生式(格式 A-B C): E-T E E- T E | T-F T T-* F T | F-( E ) | i 请输入要分析的输入串: i i * i # 分析成功注意上面这段是典型实验程序的输入格式示意你拿到的源码提示语可能有差异比如用“输入文法规则”或“按行输入产生式”。以实际程序为准但输入顺序基本逃不开“先符号表、后产生式、最后输入串”。这个流程要能跑通有个前提你输入的产生式必须是 LL(1) 文法。上面示例里的 E 和 T 是消除左递归后的写法如果你直接把课本里的 E→ET 输进去程序大概率会卡死或者表冲突详见第五章。验证程序是否正常建议第一次先用题目自带的例子跑一遍第二次再换自己的文法。一个容易被忽视的点是输入串末尾的 #。实验程序几乎都要在输入串末尾加 # 表示结束漏掉会触发“输入串提前读完”的报错。产生式里的空串也要用程序规定的符号通常是 不是希腊字母 ε这个约定要看源码或程序设计思想.docx 里的说明。4.3 换成你自己的文法四个必须同步改的位置实验二的要求通常是“给定一个文法构造预测分析表并分析句子”。如果你要把程序从示例文法换成题目文法必须同步改四个地方少一个都会出诡异结果。// 需要自定义时改动的初始化部分 // 位置 1终结符集合 char terminals[] {i, , *, (, )}; // 按题目要求改注意不含 # // 位置 2非终结符集合 char nonTerminals[] {E, T, F, E_, T_}; // 用 E_ 代替 E 是常见做法 // 位置 3产生式列表重点确认空串符号是 还是别的 struct Production prods[] { {E, T E_}, {E_, T E_}, // 右部为 时注意程序约定的空串符号 {E_, }, {T, F T_}, {T_, * F T_}, {T_, }, {F, ( E )}, {F, i}, }; // 位置 4默认输入串 char input[] i i * i #; // 需要判定的句子改完后一定重新编译。替换时容易犯一个错非终结符 E 在字符数组里写不下很多源码直接用原字符 E 再加一个特殊标记或者干脆不区分 E 和 E导致同一行出现两个不同产生式、列下标冲突。我在实验里通常会把 E 改写为 H 或 _避免和原符号冲突这是最容易翻车也最好规避的位置。如果源码把文法写死在文件里而不是从键盘输入替换逻辑一样只是改动点从“输入产生式”变成“改文件内容”。少数实验源码会从外部 .txt 读文法这种情况你的自定义文法要按文件里已有的格式排版一行一条产生式左右部之间用箭头或空格分隔具体分隔符看文件的样例行。4.4 用报告模板对照验证程序输出与实验二要求对得上吗实验报告里经常要求贴“分析过程”——也就是每个步骤的栈、剩余输入和所用产生式。但很多实验程序的输出只有“分析成功”四个字。先运行一遍看输出如果有步骤输出直接可用如果没有用第六章的扩展方法补一个。另外讲解视频.mp4 里一般会演示默认文法的完整运行你先照着视频把输入串敲一遍能复现视频里的输出再确认工具链没问题之后才谈改文法。这里啰嗦一句包里同时有编译原理实验二.docx 和《编译原理》实验二-2020.doc两个模板内容可能不完全一致以老师发的实验要求为准别直接拿 2020 版填今年的报告年份对不上会被打回。5. 避坑合集LL(1)实验里五个高频翻车现场5.1 左递归文法让程序死循环栈永远降不下去现象程序运行后不报错但输出疯狂滚动或者界面直接卡死强制结束后发现输出里的栈顶永远是同一个非终结符栈内容越来越长。原因LL(1) 文法必须是无左递归的。你把 E→ET 这样的产生式直接输进程序后预测分析表里 E 在遇到 时反复选择 E→ET每次压栈都把 E 放在栈顶下一轮查表还是它形成死循环。程序没有做“左递归检测”所以不报错只是永远跑不完。解决先把文法消除左递归再输入。E→ET 改成 E→TE、E→TE|T 同理。消完后如果程序还卡检查有没有间接左递归比如 A→B CB→A d 这种。判断方法把非终结符按任意顺序编号检查是否存在“推导两步又回到自己”的产生式链有就继续消除。5.2 预测表冲突被静默覆盖格子里的产生式“后写盖先写”现象一个明显非法的输入串被判定“分析成功”或者一个合法串被报错两种情况看起来相互矛盾但都出自同一原因。原因程序填表时没有冲突检测直接执行 predictTable[row][col] prodIdx。一个格子先填了 E→T E后填了 E→ 的判断结果后写的把先写的覆盖了表看起来完整实际是错误的。解决在填表循环里加查重。每填一个格子先判断是否已有内容有就输出“冲突”并打印两个产生式让程序拒绝继续。代码很简单// 填表时的冲突检测 int cell predictTable[row][col]; if (cell ! -1 cell ! prodIdx) { printf(LL(1)冲突: 产生式%d与%d在同一格\n, cell, prodIdx); printf(该文法不是LL(1)文法\n); return 1; } predictTable[row][col] prodIdx;注意 cell ! prodIdx 这个条件。同一条产生式在 FIRST 和 FOLLOW 分支里可能被填两次到同一个格子那是正常的重复赋值不算冲突。真正冲突是两个不同产生式抢同一个格子。5.3 空串符号不一致手写 ε 与程序内置符号对不上现象你按课本的 ε 输入产生式FIRST、FOLLOW 怎么算都不对程序输出要么是空表要么分析结果完全错误。但与你手算结果对比推导逻辑没问题。原因程序源码里空串符号可能是 、 或字符串 eps而你输入的是 ε 这个字符。程序把 ε 当成普通终结符处理产生式和终结符表全部错位。字符集不支持直接输入 ε也是很多实验源码故意用 的原因。解决先看源码里表示空串的常量定义通常在文件头有 #define EPS 这样的宏。把你写产生式时的 ε 统一替换成该符号。注意输入串里不要带 ε因为输入串对应的是终结符序列ε 不出现在输入串中。5.4 输入串里的空格被当成终结符现象输入串写成 i i * i带空格后程序报“栈顶终结符与输入不匹配”你检查了无数遍文法都没问题。原因输入串从键盘读入时带着空格字符程序逐字符处理时把空格当作输入符号去查预测表表项自然是空。如果程序是自写的可以在读取时过滤如果运行现成 exe直接不带空格输入。解决最稳妥的输入格式是不带空格的串如 ii*i#。题目要求展示空格时在源码输入处加过滤// 过滤输入串中的空白字符 char filtered[MAX_SYM]; int j 0; for (int i 0; input[i] ! \0; i) { if (input[i] ! input[i] ! \t) filtered[j] input[i]; } filtered[j] \0;这一步过滤也要在文法产生式的读取处做特别是从文本文件读文法的程序文件里为了排版加的空格全会被当成符号。5.5 改了源码但双击的还是旧 exe现象你在源码里改了半天重新运行程序发现行为没任何变化报错内容还是老样子。原因你运行的是包里自带的 LL(1)语法分析器.exe那是原作者编译好的二进制你的源码改动根本没参与编译。很多同学在这上面浪费半小时。解决在 Dev-C 里打开 .dev 工程后用“编译并运行”而不是直接去文件管理器双击 exe。如果你手动用 make执行 make 后会生成新的 exe 并覆盖旧的确认编译输出里没有 error。改源码后看文件修改时间exe 的修改时间必须晚于 .cpp 的修改时间这是最直观的验证。另外补一条经验不要拿 .o 文件判断程序状态.o 是编译中间产物源码改了但 make 没执行时旧的 .o 还在那里很容易误以为编译过了。我一般写完代码直接看 exe 时间戳比 .o 可靠。6. 把分析过程打出来栈与剩余输入的每步跟踪很多实验程序的输出只有“分析成功”四个字但实验报告偏偏要求贴推导过程。与其手敲过程不如在源码主循环里加一步栈跟踪。这个扩展改动极小、效果直观几乎对所有 LL(1) 实验源码通用。// 主循环每步输出栈与剩余输入 // 假设栈用数组 stack[0..top]输入串从 ip 开始 int currentProd -1; // 全局变量填表分支里赋值 currentProd prodIdx; void printTrace(char stack[], int top, char input[], int ip) { printf(栈: ); for (int i 0; i top; i) printf(%c, stack[i]); printf( 剩余输入: ); for (int i ip; input[i] ! \0; i) printf(%c, input[i]); printf( 所用产生式: %d\n, currentProd); }把 printTrace 放在 3.2 节主循环的每次查表之前调用每一步的分析就有据可查。注意如果源码用的是 std::stack直接遍历会从栈顶往栈底输出顺序是反的先把元素弹到临时数组再倒序输出即可。如果程序本来就在边分析边打印只需要在打印语句里补上剩余输入串。验证效果输入 iii#你会看到栈从 #E 开始匹配到 i 后变成 #ET接着 E 查表选择 TE输出逐行显示“栈: #ET 剩余输入: ii# 所用产生式: 1”整条推导链和课本上的最左推导完全对应实验报告直接截图就能用。这段跟踪对排错还有个额外价值当输入串开头的终结符导致查表失败时printTrace 能让你立刻看出栈顶符号和当前输入到底差在哪。我调 FIRST/FOLLOW 的 bug 时经常靠这行输出定位到“该用产生式 3 却用了产生式 1”再回头查集合要素就快得多。从那以后我拿到任何语法分析器实验资源第一件事就是加这行栈跟踪把“分析成功”这个黑匣子打开先让每一步推导可见再谈正确性和报告撰写。这个习惯帮我省掉了大量不明不白的排错时间希望帮到你。本文还有配套的精品资源点击获取