C语言实现LL(1)预测分析表自动生成：从FIRST/FOLLOW集到分析器

简介这份资源面向学习编译原理、需要完成LL(1)语法分析实验的高校学生与自学者核心解决给定文法后自动构造预测分析表的问题。内容围绕FIRST集、FOLLOW集的迭代计算以及分析表数据结构设计展开可配合《编译原理教程》第四版胡元义教材中的例题进行对照练习帮助理解自顶向下语法分析的整体流程。压缩包共12个文件以11个txt文本和1个c源码为主txt多为测试输入与结果输出样例c文件为完整实现代码整体约15KB轻量便于直接编译运行。目前已有967人学习下载说明该实验在课程中具有较高参考价值。读者可借助源码理清集合迭代求解与表结构构建思路通过多组测试样例验证输出结果并在此基础上自行替换文法进行扩展实验适合作为课程实验的借鉴与排错参考。1. 从一份 C 语言课设说起LL(1) 预测分析表到底怎么自动生成如果你正在做编译原理课设大概率绕不开这个场景老师给一个文法要求你手写出 FIRST 集、FOLLOW 集再填一张预测分析表最后用程序验证。手写一遍能过但文法稍微复杂一点集合迭代就算错表也跟着崩。这份「实现预测分析表的自动生成.zip」就是冲着这个痛点来的——它用 C 语言把从文法读入到分析表输出的整条链路跑通配套了多组测试输入和结果文件可以直接对照验证自己的实现。适合正在啃 LL(1) 文法、需要一份可运行参考的在校生和自学者。它不替你写实验报告但能让你看清每一步的数据结构长什么样、迭代什么时候收敛、表项冲突长在哪。2. 拆开压缩包文件结构、数据结构与 FIRST/FOLLOW 迭代逻辑2.1 测试文件与结果文件的对应关系拿到压缩包先别急着编译把文件按用途分一下类后面调试会省很多事。从目录看输入侧是test.txt、test1.txt到test4.txt输出侧是testout.txt、testout1.txt到testout4.txt外加一份readme.txt和源码test4.c。这种命名方式很典型testN.txt是第 N 组文法输入testoutN.txt是对应的预测分析表输出testout.txt通常是无编号的默认用例结果。文件角色用途test.txt / test1~4.txt输入存放产生式文法每行一条testout.txt / testout1~4.txt输出对应文法的 LL(1) 分析表test4.c源码主程序含集合计算与表构造readme.txt说明编译与运行提示我一般会先打开test.txt和testout.txt对读一遍确认输入文法的格式约定——终结符和非终结符怎么区分、产生式用什么符号分隔、空串 ε 怎么表示。这一步不做后面改代码就是盲改。2.2 文法在内存里怎么存产生式表与符号集LL(1) 自动生成的第一道坎不是算法是数据结构。产生式如果用字符串硬解析每算一次 FIRST 都要重新扫一遍效率低还容易出错。常见做法是先把文法读进一个结构体数组每条产生式拆成「左部非终结符」和「右部符号序列」两部分。// 产生式结构左部一个非终结符右部一串符号 typedef struct { char left; // 左部非终结符如 E char right[32][8]; // 右部符号序列每个符号最多 8 字符 int len; // 右部符号个数 } Production; Production grammar[64]; // 最多 64 条产生式 int prodCount 0; // 实际产生式数量这里right用二维字符数组而不是单个字符串是为了处理E-T E这种右部有多个符号的情况。len记录右部长度遍历时直接按长度走不用每次找结束符。参数上64和32是经验值课设级别的文法够用如果你的文法产生式超过 64 条把数组开大即可但要注意栈上大数组可能溢出必要时改成static或动态分配。符号集这边终结符和非终结符各维护一个字符数组加计数读文法时顺便收集避免后面反复扫描。2.3 FIRST 集迭代什么时候算收敛FIRST 集的本质是「一个符号串能推导出的首终结符集合」。对单个符号规则很直接终结符的 FIRST 就是它自己非终结符要看它所有产生式的右部首符号。真正麻烦的是右部首符号也是非终结符甚至整个右部都能推出 ε这时候要把下一个符号的 FIRST 并进来。// 迭代计算 FIRST 集直到某一轮没有任何集合发生变化 int changed 1; while (changed) { changed 0; for (int i 0; i prodCount; i) { char A grammar[i].left; int k 0; // 逐个符号处理遇到不能推空串的符号就停 while (k grammar[i].len) { char X grammar[i].right[k][0]; int before firstSet[A].count; addFirstSet(A, X); // 把 FIRST(X) 并入 FIRST(A) if (firstSet[A].count ! before) changed 1; if (!canDeriveEpsilon(X)) break; // X 不能推 ε后续符号不再并入 k; } if (k grammar[i].len) { // 右部所有符号都能推 ε则 ε 属于 FIRST(A) addEpsilonToFirst(A); } } }逻辑说明外层while(changed)是迭代到不动点这是 FIRST 集计算的标准做法因为非终结符之间可能相互依赖一轮算不完。canDeriveEpsilon(X)判断某个符号能否推出空串终结符恒为假非终结符查它是否已有 ε 在 FIRST 里。参数上addFirstSet要做去重否则集合计数永远在变迭代不收敛——这是新手最容易翻车的地方。2.4 FOLLOW 集与预测分析表的填表规则FOLLOW 集比 FIRST 多一层「上下文」它描述某个非终结符后面可能紧跟哪些终结符。规则有三条——开始符号的 FOLLOW 含$若A-αBβ则 FIRST(β) 去掉 ε 并入 FOLLOW(B)若 β 能推 ε 或不存在则 FOLLOW(A) 并入 FOLLOW(B)。这三条同样要迭代到收敛。表构造是最后一步规则一句话对每条产生式A-α对 FIRST(α) 里每个终结符 a把A-α填进M[A][a]如果 α 能推 ε则对 FOLLOW(A) 里每个符号 b把A-ε填进M[A][b]。填表时如果目标格子已经有内容且不是同一条产生式就是 LL(1) 冲突说明这个文法不是 LL(1) 的。// 填预测分析表 M[非终结符][终结符] for (int i 0; i prodCount; i) { char A grammar[i].left; // 情况一右部首符号的 FIRST 集 for (int t 0; t firstSetOfRight[i].count; t) { char a firstSetOfRight[i].terms[t]; if (a ! EPSILON) setTable(A, a, i); // 冲突检测在 setTable 内 } // 情况二右部能推 ε用 FOLLOW(A) 填 if (rightCanDeriveEpsilon(i)) { for (int t 0; t followSet[A].count; t) { setTable(A, followSet[A].terms[t], i); } } }setTable里要做冲突判断如果M[A][a]已有值且不等于当前产生式编号打印冲突位置并标记该文法非 LL(1)。这一步别省课设里老师往往就看你有没有处理冲突。3. 编译运行与结果验证从 test.txt 到 testout.txt 的完整走查3.1 在 VS2019 下编译这份 C 代码源码是test4.c单文件没有额外依赖VS2019 下新建空项目把文件加进去即可。注意两点一是文件编码如果test.txt里有中文注释或特殊符号用 UTF-8 保存否则读进来会乱码二是工作目录程序用相对路径读test.txt默认工作目录是项目目录不是exe所在目录跑之前确认test.txt在正确位置。# 如果不想开 VS用 gcc 命令行也能编 gcc test4.c -o ll1.exe -Wall ./ll1.exe-Wall打开全部警告集合数组越界、未初始化变量这类问题会直接报出来比运行时崩溃好查。常见做法是先在命令行跑通再挪进 VS 调试因为 VS 的默认工作目录和命令行不一致容易读不到输入文件。3.2 用 test.txt 跑一遍并对照 testout.txt跑通之后程序会读test.txt里的文法输出 FIRST、FOLLOW 和预测分析表。验证方法很直接打开testout.txt逐行对照。重点看三处——FIRST 集里有没有漏掉 ε、FOLLOW 集里$有没有加、分析表里空串产生式填的位置对不对。如果输出和testout.txt不一致先别改算法按这个顺序排查文法读入的符号切分对不对、canDeriveEpsilon的判断有没有漏、迭代终止条件是不是提前退出。我一般会在每轮迭代后打印一次集合内容看它是第几轮稳定的和手算的轮数对一下很快能定位。3.3 换 test1~4.txt 验证通用性单组用例跑通不代表程序对。test1.txt到test4.txt大概率覆盖了不同情况有的文法含 ε 产生式有的右部多符号有的可能存在 LL(1) 冲突。逐个跑对照testout1~4.txt。如果某组结果对不上先判断是程序 bug 还是这组文法本身不是 LL(1)——后者的话testoutN.txt里应该有冲突提示程序输出冲突位置也算正确行为。提示验证时优先看集合的「元素个数」而不是「顺序」集合输出顺序依赖遍历顺序不同实现可能不一样但元素集合必须一致。4. 避坑与排查集合不收敛、表项冲突、文件读入乱码4.1 FIRST 集迭代不收敛程序卡死现象程序跑起来一直不退出CPU 占满。原因addFirstSet没有去重每次并入都让count变化changed永远为 1。解决并入前先查目标集合里是否已有该符号有就跳过只有真正新增元素时才把changed置 1。4.2 预测分析表出现冲突却当成正常输出现象某个M[A][a]被填了两次程序没报错直接覆盖。原因setTable里没做冲突检测后填的覆盖了先填的。解决填表前判断该格是否已有产生式编号有且不同就打印Conflict at M[A][a]并标记文法非 LL(1)。这是课设的得分点别漏。4.3 读 test.txt 时符号切分错误现象产生式右部T E被当成一个符号或者E被拆成E和。原因按空格切分时没考虑带撇的非终结符或者分隔符约定和文件实际格式不符。解决先打印读入的每条产生式确认切分结果再调整切分逻辑带撇符号建议整体作为一个 token 处理。4.4 输出文件乱码或覆盖原结果现象testout.txt打开是乱码或者跑一次就被覆盖。原因写文件时用了文本模式但编码不一致或者输出文件名硬编码成同一个。解决输出文件按输入文件名派生比如test1.txt对应testout1.txt编码统一用 UTF-8VS 里在「高级保存选项」确认。4.5 FOLLOW 集漏掉开始符号的$现象分析表里$列全空遇到输入结束符无法分析。原因初始化 FOLLOW 集时忘了给开始符号加$。解决在读文法确定开始符号后第一件事就是把$加进它的 FOLLOW 集再进入迭代。5. 进阶技巧把分析表变成可执行的分析器集合和表都对了其实离一个能跑的分析器只差一个栈。LL(1) 分析过程就是「栈顶符号 vs 当前输入符号」查表栈顶是非终结符就查M查到产生式就把栈顶替换成右部逆序栈顶是终结符就和输入符号比对相同则双双弹出。这一步做完你的课设就不只是「生成表」而是「用表分析句子」。// LL(1) 分析主循环简化版 stack[top] $; stack[top] startSymbol; // 开始符号入栈 int ip 0; // 输入串指针 while (top 0) { char X stack[top]; char a input[ip]; if (X $ a $) { printf(Accept\n); break; } if (isTerminal(X) || X $) { if (X a) { top--; ip; } // 匹配双双前进 else { printf(Error at %c\n, a); break; } } else { int p table[X][a]; // 查预测分析表 if (p -1) { printf(Error: no rule for M[%c][%c]\n, X, a); break; } top--; // 弹出栈顶非终结符 for (int k grammar[p].len - 1; k 0; k--) stack[top] grammar[p].right[k][0]; // 右部逆序入栈 } }参数说明table[X][a]存产生式编号-1表示无规则右部逆序入栈是为了让第一个符号先被处理。跑的时候拿test.txt里的文法生成表再随便写个句子当输入看能不能走到Accept。如果中途报错回头查表里对应格子是不是空的——多半是 FOLLOW 集算漏了。从那以后我每次做完集合计算都会强制拿一个最短句子走一遍分析栈因为表对不对跑一个句子比盯十遍输出都管用。希望帮到你。本文还有配套的精品资源点击获取