预测分析表自动生成：FIRST/FOLLOW集迭代计算与课设实战)
简介这份资源面向学习编译原理、需要完成LL(1)语法分析实验的高校学生与自学者核心解决给定文法后自动构造预测分析表的问题。内容围绕FIRST集与FOLLOW集的迭代计算、分析表数据结构设计展开并附带多组测试用例与对应输出结果便于对照验证程序正确性。压缩包共12个文件以11个txt文本和1个c源码为主txt承担文法输入、测试数据与结果输出等用途c文件为完整实现代码整体约15KB体积轻便。目前已有967人学习下载说明其在课程实验场景中具备一定参考价值。读者可借此理解LL(1)分析法的完整流程掌握集合迭代求解与预测分析表构造思路并通过多组测试样例排查逻辑错误适合作为课程实验的借鉴与排错参考。1. 从一份 C 语言课设说起LL(1) 预测分析表自动生成到底能解决什么如果你正在做编译原理课设大概率会遇到这样一道题给定一个文法要求程序自动输出它的 LL(1) 预测分析表。手工算 FIRST 集、FOLLOW 集、再填一张二维表文法稍微复杂一点就容易出错而且改一个产生式就得全部重算。这份「实现预测分析表的自动生成.zip」就是冲着这个痛点来的——用 C 语言把整个流程自动化输入文法输出分析表附带多组测试文件和对应的结果文件可以直接对照验证。它适合三类人正在做编译原理实验、需要一份可运行参考实现的学生想快速理解 FIRST/FOLLOW 迭代计算和预测分析表数据结构的自学者以及需要一个小型语法分析原型、不想从零搭框架的开发者。代码基于 C 语言在 Win10 VS2019 环境下编译通过参考教材是胡元义的《编译教程第四版》。需要说明的是这份资源定位是借鉴学习不是拿来直接交差的模板——你得看懂它怎么迭代、怎么建表才能应对答辩时的追问。2. 拆解核心算法FIRST 集、FOLLOW 集与预测分析表的构造逻辑2.1 为什么 FIRST 和 FOLLOW 必须迭代计算FIRST 集的定义看起来简单一个符号串能推导出的所有可能的开头终结符集合。但问题在于当产生式右部以非终结符开头而这个非终结符又能推导出空串 ε 时你就得继续往后看下一个符号。这就形成了一个依赖链——A 的 FIRST 集可能依赖 B 的 FIRST 集B 又依赖 CC 可能绕回来依赖 A。所以不能用一次遍历搞定必须反复扫描所有产生式直到所有集合都不再变化为止。FOLLOW 集更绕。它的计算规则里有一条如果 A → αBβ那么 FIRST(β) 中除 ε 外的所有符号都属于 FOLLOW(B)。如果 β 能推导出 ε那么 FOLLOW(A) 的所有符号也要加入 FOLLOW(B)。这意味着 FOLLOW 集的计算依赖 FIRST 集的结果而且同样存在循环依赖。我一般会先把 FIRST 集算到收敛再算 FOLLOW 集这样逻辑清晰也方便调试。常见做法是用一个changed标志位控制外层循环每轮遍历所有产生式只要有任何一个集合新增了元素就把changed置为 1继续下一轮直到某一轮没有任何变化说明所有集合已经收敛。这个思路在代码里体现得很直接下面结合资源中的实现方式来说明。2.2 数据结构怎么设计才不容易翻车预测分析表本质上是一个二维表行是非终结符列是终结符包括结束符#单元格里存放的是产生式编号或者产生式本身。在 C 语言里最直观的做法是用一个二维数组但非终结符和终结符的数量在运行时才知道所以要么用固定大小的数组加计数器要么动态分配。这份资源里采用的是固定上限的数组方案配合字符串存储符号。每个非终结符对应一个char*或char[]FIRST 集和 FOLLOW 集用字符数组加长度标记来表示。这种方案的好处是不用管内存释放调试时直接打印数组就能看到内容缺点是文法规模大了会浪费空间但对于课设级别的文法通常不超过 20 个产生式完全够用。另一个关键点是产生式的存储。每条产生式需要记录左部非终结符、右部符号串、以及产生式编号。右部符号串里可能包含 ε通常用特殊字符比如~或表示或者单独用一个标志位标记。资源中的测试文件test.txt到test4.txt应该就是不同文法的输入对应的testout.txt到testout4.txt是预期输出可以用来验证你的实现是否正确。2.3 从文法输入到分析表输出的完整步骤下面按资源中的实现思路把整个流程拆成可复现的步骤。假设你已经拿到了源码文件在 VS2019 里新建一个空项目把.c文件添加进去编译运行即可。但如果你想理解每一步在做什么或者需要自己改代码适配不同的文法格式这部分就是关键。第一步读取文法。输入文件里每一行是一条产生式格式通常是A - α | β | γ用|分隔同一左部的多个候选式。读取时需要把每个候选式拆成独立的产生式统一编号。注意处理空格和换行Windows 下的换行是\r\n如果直接用fgets读取字符串末尾会带\r需要手动去掉否则后续字符串比较会出问题。// 读取一行产生式并解析 while (fgets(line, MAX_LINE, fp) ! NULL) { // 去掉行尾的 \r 和 \n line[strcspn(line, \r\n)] \0; // 跳过空行 if (strlen(line) 0) continue; // 解析左部非终结符 char left line[0]; // 找到 - 的位置 char *arrow strstr(line, -); if (arrow NULL) continue; // 从箭头后面开始解析右部按 | 分割 char *rhs arrow 2; char *token strtok(rhs, |); while (token ! NULL) { // 去掉前导空格 while (*token ) token; // 存入产生式数组记录左部和右部 productions[prod_count].left left; strcpy(productions[prod_count].right, token); prod_count; token strtok(NULL, |); } }这段代码的逻辑说明strcspn用来定位\r或\n并截断避免行尾空白干扰。strstr找到-后右部按|用strtok分割。每次分割出一个候选式就存一条产生式编号自增。参数方面MAX_LINE需要根据文法规模设定一般 256 够用productions数组的大小也要预留足够空间课设级别 100 条足够。第二步计算 FIRST 集。用一个循环反复扫描所有产生式直到没有集合发生变化。对于每条产生式A - X1 X2 ... Xn依次处理每个 Xi如果 Xi 是终结符直接加入 FIRST(A) 并停止如果 Xi 是非终结符把 FIRST(Xi) 中除 ε 外的元素加入 FIRST(A)如果 Xi 不能推导出 ε则停止否则继续看下一个符号。如果所有符号都能推导出 ε则把 ε 也加入 FIRST(A)。// 迭代计算 FIRST 集 int changed 1; while (changed) { changed 0; for (int i 0; i prod_count; i) { char A productions[i].left; char *rhs productions[i].right; int all_nullable 1; // 标记右部是否全部可推导出 ε for (int j 0; rhs[j] ! \0; j) { char X rhs[j]; if (is_terminal(X)) { // 终结符直接加入 FIRST(A) if (add_to_first(A, X)) changed 1; all_nullable 0; break; } else { // 非终结符加入其 FIRST 集中除 ε 外的元素 for (int k 0; k first_len[X]; k) { if (first_set[X][k] ! ~) { if (add_to_first(A, first_set[X][k])) changed 1; } } // 如果 X 不能推导出 ε停止 if (!can_derive_null(X)) { all_nullable 0; break; } } } // 如果右部所有符号都能推导出 ε则 ε 也属于 FIRST(A) if (all_nullable) { if (add_to_first(A, ~)) changed 1; } } }逻辑说明外层while(changed)控制迭代只要有一轮有新增元素就继续。内层遍历每条产生式的右部all_nullable标记是否所有符号都可空。遇到终结符直接加入并跳出遇到非终结符先加入其 FIRST 集去掉 ε再判断它是否可空不可空就停止。如果整个右部都可空最后把 ε 加入。add_to_first函数负责去重添加返回 1 表示新增了元素。第三步计算 FOLLOW 集。先把结束符#加入开始符号的 FOLLOW 集。然后反复扫描每条产生式A - X1 X2 ... Xn对于每个非终结符 Xi看它后面的符号串把 FIRST(Xi1 ... Xn) 中除 ε 外的元素加入 FOLLOW(Xi)如果后面的符号串能推导出 ε或者 Xi 就是最后一个符号则把 FOLLOW(A) 加入 FOLLOW(Xi)。// 初始化开始符号的 FOLLOW 集加入 # add_to_follow(start_symbol, #); changed 1; while (changed) { changed 0; for (int i 0; i prod_count; i) { char A productions[i].left; char *rhs productions[i].right; int len strlen(rhs); for (int j 0; j len; j) { char B rhs[j]; if (is_terminal(B)) continue; // 看 B 后面的符号串 int all_nullable 1; for (int k j 1; k len; k) { char X rhs[k]; if (is_terminal(X)) { if (add_to_follow(B, X)) changed 1; all_nullable 0; break; } else { for (int m 0; m first_len[X]; m) { if (first_set[X][m] ! ~) { if (add_to_follow(B, first_set[X][m])) changed 1; } } if (!can_derive_null(X)) { all_nullable 0; break; } } } // 如果 B 后面所有符号都可空或 B 是最后一个符号 if (all_nullable) { for (int m 0; m follow_len[A]; m) { if (add_to_follow(B, follow_set[A][m])) changed 1; } } } } }逻辑说明外层同样是迭代到收敛。内层遍历右部每个符号只处理非终结符。对于当前非终结符 B向后扫描把后面符号的 FIRST 集去 ε加入 FOLLOW(B)遇到不可空的就停止。如果后面全部可空或者 B 就是最后一个符号则把 FOLLOW(A) 加入 FOLLOW(B)。add_to_follow同样负责去重。第四步构造预测分析表。遍历每条产生式A - α计算 FIRST(α)。对于 FIRST(α) 中的每个终结符 a不包括 ε把A - α填入M[A][a]。如果 ε 在 FIRST(α) 中则对于 FOLLOW(A) 中的每个终结符 b把A - α填入M[A][b]。如果某个单元格被填了两次说明文法不是 LL(1) 的需要报错。// 构造预测分析表 for (int i 0; i prod_count; i) { char A productions[i].left; char *rhs productions[i].right; // 计算右部符号串的 FIRST 集 char first_alpha[MAX_SYMS]; int first_alpha_len 0; compute_first_of_string(rhs, first_alpha, first_alpha_len); for (int j 0; j first_alpha_len; j) { char a first_alpha[j]; if (a ~) { // ε 在 FIRST(α) 中用 FOLLOW(A) 填充 for (int k 0; k follow_len[A]; k) { char b follow_set[A][k]; if (table[A][b] ! 0) { printf(冲突M[%c][%c] 已被填充\n, A, b); } table[A][b] i 1; // 产生式编号从 1 开始 } } else { if (table[A][a] ! 0) { printf(冲突M[%c][%c] 已被填充\n, A, a); } table[A][a] i 1; } } }逻辑说明compute_first_of_string计算右部符号串的 FIRST 集逻辑和单个非终结符类似但要注意整个串可空时 ε 才加入。然后遍历 FIRST(α)非 ε 的直接填表ε 的用 FOLLOW(A) 填。每次填表前检查是否已有值有则说明冲突文法不满足 LL(1) 条件。table二维数组的行列索引需要提前建立非终结符和终结符到索引的映射。2.4 测试文件怎么用对照验证你的输出资源里附带了test.txt到test4.txt五组输入以及对应的testout.txt到testout4.txt五组输出。建议的使用方式是先用test.txt跑一遍把程序输出和testout.txt逐行对比。如果一致再换test2.txt逐步增加文法复杂度。常见做法是写一个简单的 diff 脚本或者在程序里直接把结果输出到文件然后用文本对比工具看差异。文件用途建议用法test.txt基础文法产生式少首次运行验证流程是否跑通test2.txt ~ test4.txt逐步复杂的文法验证迭代计算是否正确处理嵌套依赖testout.txt ~ testout4.txt预期输出与程序输出逐行对比定位差异readme.txt说明文件先读一遍了解编译和运行方式如果输出和预期不一致优先检查 FIRST 集和 FOLLOW 集的打印结果。大部分错误都出在迭代没有收敛、ε 的处理遗漏、或者字符串比较时大小写和空格没处理好。把中间结果打印出来和手工计算的结果对照很快就能定位。3. 避坑与排查编译、运行、结果不对时先看这几条3.1 编译报错C4996或fopen不安全现象在 VS2019 里编译时提示fopen、strcpy、strtok等函数不安全建议使用_s版本。原因VS 默认开启了 SDL 检查把传统 C 函数标记为不安全。解决在项目属性 → C/C → 预处理器 → 预处理器定义中添加_CRT_SECURE_NO_WARNINGS。或者在文件最开头加#define _CRT_SECURE_NO_WARNINGS注意必须放在所有#include之前。3.2 读取文法时第一行丢失或最后一行重复现象程序读到的产生式数量比文件里少一行或者最后一条产生式被处理了两次。原因fgets在读到文件末尾时返回NULL但如果循环条件写成了while (!feof(fp))最后一次读取会重复处理缓冲区里的旧数据。解决直接用while (fgets(line, MAX_LINE, fp) ! NULL)不要用feof判断。另外检查文件末尾是否有空行空行会被跳过不影响结果。3.3 FIRST 集计算结果少了 ε 或者多了不该有的符号现象某个非终结符的 FIRST 集里没有 ε但手工计算应该有或者某个终结符不该出现却出现了。原因ε 的判断逻辑写错了。常见错误是把can_derive_null写成了只检查直接产生式A - ~没有递归检查A - B、B - ~这种情况。解决can_derive_null也需要迭代计算或者直接在 FIRST 集收敛后检查 ε 是否在 FIRST(A) 中。另一个原因是字符串比较时没去掉空格 ~和~被当成不同的符号。3.4 预测分析表出现冲突但文法明明是 LL(1) 的现象程序报某个单元格被填充两次但你手工验证文法满足 LL(1) 条件。原因大概率是 FOLLOW 集算错了导致 ε 产生式填到了不该填的列。重点检查 FOLLOW 集的计算当右部某个非终结符后面跟的是可空非终结符时有没有继续往后看有没有把 FOLLOW(A) 传下去。解决把每个非终结符的 FIRST 和 FOLLOW 集打印出来和手工计算的结果逐项对比。如果 FOLLOW 集对了表冲突通常也会消失。3.5 输出格式和预期文件对不上但内容是对的现象程序输出的分析表内容正确但空格、对齐、行序和testout.txt不一致diff 工具报大量差异。原因输出格式没有严格对齐预期文件的格式。解决先确认内容是否一致如果只是格式差异可以调整printf的格式串。常见做法是用%-10s这样的宽度控制对齐或者直接按预期文件的格式逐字符对照。如果预期文件是用制表符分隔的你的输出也要用制表符不能换成空格。4. 进阶用法把这份代码改成能处理任意文法的通用工具资源里的实现已经能跑通课设级别的文法但如果你想把它变成一个更通用的工具有几个方向可以动手。第一个方向是支持多字符非终结符。现在的代码大概率用单个字符表示非终结符遇到Expr、Term这种就歇了。改法是把所有符号统一用字符串存储FIRST 集和 FOLLOW 集用字符串数组比较用strcmp。工作量不大但能让你的工具处理更真实的文法。第二个方向是自动判断文法是否为 LL(1)。现在的冲突检测是在填表时被动发现的可以提前做一个检查对于同一非终结符的任意两条产生式A - α和A - β如果 FIRST(α) ∩ FIRST(β) 非空或者 ε 在 FIRST(α) 中且 FIRST(β) ∩ FOLLOW(A) 非空则文法不是 LL(1) 的。把这个检查加进去能在构造表之前就给出明确提示。第三个方向是加一个简单的分析过程模拟。给定输入串用生成的预测分析表模拟分析栈的操作输出每一步的栈内容、剩余输入和动作。这个功能对理解 LL(1) 分析过程非常有帮助也是很多课设的加分项。实现思路是初始化栈里放#和开始符号然后循环读取输入符号查表决定是推导还是匹配直到栈空或报错。// 模拟 LL(1) 分析过程 void parse_input(char *input) { char stack[MAX_STACK]; int top 0; stack[top] #; stack[top] start_symbol; int pos 0; printf(%-20s %-20s %-20s\n, 栈, 剩余输入, 动作); while (top 0) { char X stack[--top]; char a input[pos]; printf(%-20s %-20s , stack_to_string(stack, top), input pos); if (X #) { if (a #) { printf(接受\n); return; } else { printf(错误输入未结束\n); return; } } else if (is_terminal(X)) { if (X a) { printf(匹配 %c\n, a); pos; } else { printf(错误期望 %c实际 %c\n, X, a); return; } } else { int prod table[X][a]; if (prod 0) { printf(错误M[%c][%c] 为空\n, X, a); return; } printf(用产生式 %d 推导\n, prod); // 把产生式右部逆序压栈 char *rhs productions[prod - 1].right; for (int i strlen(rhs) - 1; i 0; i--) { if (rhs[i] ! ~) { stack[top] rhs[i]; } } } } }逻辑说明栈用数组模拟初始压入#和开始符号。每次取栈顶符号 X 和当前输入符号 a。如果 X 是#且 a 也是#接受如果 X 是终结符匹配则输入指针后移如果 X 是非终结符查表得到产生式编号把右部逆序压栈ε 不压。每一步打印栈内容、剩余输入和动作。参数方面MAX_STACK要足够大避免栈溢出输入串末尾要加#作为结束符。我自己的习惯是每次改完代码先用test.txt跑一遍确认输出和testout.txt完全一致再动其他文件。如果改了数据结构或者算法逻辑五组测试全部重跑一遍一个都不能少。编译原理的实验错一个符号后面全错后悔药没得吃。从那以后我每次改完核心逻辑都强制走一遍全量测试确认没有回归才继续。希望这份拆解能帮你把 LL(1) 预测分析表这块硬骨头啃下来。本文还有配套的精品资源点击获取
