简介：这份资源面向学习编译原理、需要完成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 又依赖 C，C 可能绕回来依赖 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(Xi+1 ... 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 脚本，或者在程序里直接把结果输出到文件，然后用文本对比工具看差异。

如果输出和预期不一致，优先检查 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) 预测分析表这块硬骨头啃下来。

本文还有配套的精品资源，点击获取