企业官网建设流程全解析

简介：用于编译原理课程中LL(1)预测分析表的自动生成，面向计算机专业本科生以及需要掌握FIRST集、FOLLOW集迭代计算与预测分析表构造原理的学习者。压缩包内代码使用C语言编写，适配Win10+VS2019环境，对应胡元义《编译教程（第四版）》的实验要求。压缩包共12个文件，主要为1个C源文件和11个txt文本；C源码承担文法读入、非终结符与终结符处理、FIRST/FOLLOW集合求解及分析表生成等核心逻辑，txt文件则提供多组测试文法、输入样例和输出结果，便于对照验证。目前已有967人学习下载。资源完整呈现了预测分析表的程序化构建过程，对迭代计算中的难点、产生式处理及分析表对应的数据结构设计均有可运行代码支撑；随附的测试文件覆盖多种文法情形，结果文件中包含测试输出，可辅助排查空串、左递归等易错点，适合课程实验参考、算法理解与二次开发借鉴。

1. 预测分析表自动生成的C语言实现：LL(1)文法分析从哪里落地

用递归下降写解析器的人，十个里有八个被左递归坑过。我当时被E -> E + T这种产生式整到栈溢出，才回头换成 LL(1) 预测分析表——先把 FIRST 集和 FOLLOW 集算清楚，再填出那张以非终结符为行、以终结符为列的二维表。这个 zip 包解决的问题，就是在给定文法后自动生成预测分析表：C 语言工程，Win10 下的 VS2019 直接编译运行，输入是几行产生式文本，输出就是可供语法驱动程序查询的 LL(1) 分析表，同时把 FIRST、FOLLOW 集合一并打印出来。适合正在做编译原理实验、需要自己实现 FIRST 和 FOLLOW 迭代逻辑的人，也适合想借鉴现成代码但不想盲目复制的人。提前说清楚：这份材料定位是借鉴模板，不是交作业替身，直接一字不改上交的风险自己掂量。

2. FIRST 与 FOLLOW 的迭代计算：文法的C语言建模与集合闭包

2.1 文法读入与内部存储结构

先解决文法怎么放进内存。拿到 test1.txt，里面是产生式文本，常见格式是E -> E + T | T，空产生式写成ε或@。程序第一步要把字符流解析成能反复遍历的内部结构，而不是每次重新读文件，因为后面 FIRST、FOLLOW、填表都要多次扫描产生式。

我一般定义这样的三个结构：

#define MAX_PROD 100 #define MAX_LEN 50 #define SYM_CNT 128 typedef struct { char lhs; // 产生式左部，非终结符 char rhs[MAX_LEN]; // 右部符号串，符号间用空格分隔 int len; // 右部符号个数 } Production; typedef struct { Production prods[MAX_PROD]; int prod_count; char non_terminals[SYM_CNT]; // 非终结符集合 char terminals[SYM_CNT]; // 终结符集合，不含 '#' 和 'ε' } Grammar;

lhs只存一个字符，因为文法非终结符一般就是单个大写字母；rhs用定长数组，避免动态内存释放的麻烦。MAX_PROD给 100 是保守值，实验文法一般不超过 20 条产生式，但数组开大一点不会出错。SYM_CNT为 128，对应 ASCII 字符全集，后面集合运算直接用字符编码做数组下标，省去哈希表。

解析产生式的核心函数长这样：

void parse_production(Grammar* g, char* line) { Production* p = &g->prods[g->prod_count]; p->lhs = line[0]; int i = 0, j = 0; while (line[i] != '\0' && line[i] != '\n') { if (line[i] == '-' && line[i + 1] == '>') { i += 2; continue; } if (line[i] == '|') { // 遇到候选分隔符，结束当前产生式，开启新的 p->len = j; g->prod_count++; p = &g->prods[g->prod_count]; p->lhs = line[0]; j = 0; } else if (line[i] != ' ') { p->rhs[j++] = line[i]; } i++; } p->len = j; g->prod_count++; }

这段逻辑的关键在|的处理：E -> E + T | T这一行会被拆成两条产生式，左部都是E，右部分别是E + T和T。len记录右部符号个数，空格直接跳过，符号以单个字符为单位压入rhs。注意prod_count在|分支里先自增再取新结构体，最后循环外还要再自增一次，这里漏掉会导致最后一条产生式被覆盖。

2.2 FIRST 集的迭代计算：直到集合不再变化

FIRST 集的定义不复杂：一个符号串能推导出的所有可能开头终结符。但实现时有个很容易翻车的地方——文法可能间接推导，比如A -> B、B -> C、C -> a，必须循环迭代到所有集合都不再变化，才算达到不动点。

我用二维布尔数组存集合：

#define EPSILON 1 // 用 ASCII 码 1 代表 ε，避免和 '\0' 冲突 #define ENDMARK 2 // 用 ASCII 码 2 代表 #，输入结束符 int first[SYM_CNT][SYM_CNT]; // first[非终结符][符号] = 1 表示属于 int nullable[SYM_CNT]; // nullable[符号] = 1 表示可推导出 ε int add_to_set(int* set, int sym) { if (!set[sym]) { set[sym] = 1; return 1; // 集合真的变了 } return 0; // 集合没变 } void compute_first(Grammar* g) { int changed = 1; while (changed) { changed = 0; for (int i = 0; i < g->prod_count; i++) { Production* p = &g->prods[i]; int A = (unsigned char)p->lhs; int j = 0; while (j < p->len) { int X = (unsigned char)p->rhs[j]; if (is_terminal(X)) { changed |= add_to_set(first[A], X); break; // 遇到终结符，FIRST(A) 加入 X，结束 } else { // 非终结符：把 FIRST(X) 中除 ε 外全部加入 FIRST(A) for (int s = 0; s < SYM_CNT; s++) { if (first[X][s] && s != EPSILON) { changed |= add_to_set(first[A], s); } } // X 不可空，停止扫描后续符号 if (!nullable[X]) break; } j++; // 右部所有符号都可空，ε 进入 FIRST(A) if (j == p->len) { changed |= add_to_set(first[A], EPSILON); } } } } }

这里changed是外层循环唯一依据，任何一个add_to_set返回 1，changed就会被置 1，下一轮继续。EPSILON用 ASCII 码 1，ENDMARK用 2，刻意避开'\0'、' '、'\n'这些在字符串处理里容易混淆的字符。is_terminal的判断标准是：符号存在于g->terminals数组，且不是EPSILON和ENDMARK。

2.3 FOLLOW 集的迭代计算：三条规则与依赖逆推

FOLLOW 集比 FIRST 集更容易漏，因为它依赖关系是反向的：A -> αBβ时，FOLLOW(B) 要接收 FIRST(β) 的内容，而 FOLLOW(A) 的内容也要传递到 FOLLOW(B)。如果 β 可空，这条传递链路还会更长。

三条规则对应到代码里是这样的：

int follow[SYM_CNT][SYM_CNT]; void compute_follow(Grammar* g, int start_symbol) { // 规则 1：开始符号的 FOLLOW 集合包含 # add_to_set(follow[start_symbol], ENDMARK); int changed = 1; while (changed) { changed = 0; for (int i = 0; i < g->prod_count; i++) { Production* p = &g->prods[i]; int A = (unsigned char)p->lhs; for (int j = 0; j < p->len; j++) { int B = (unsigned char)p->rhs[j]; if (is_terminal(B)) continue; // 规则 2：A -> αBβ，FIRST(β) 除 ε 加入 FOLLOW(B) int k = j + 1; int beta_all_nullable = 1; while (k < p->len) { int beta_sym = (unsigned char)p->rhs[k]; if (is_terminal(beta_sym)) { changed |= add_to_set(follow[B], beta_sym); beta_all_nullable = 0; break; } for (int s = 0; s < SYM_CNT; s++) { if (first[beta_sym][s] && s != EPSILON) { changed |= add_to_set(follow[B], s); } } if (!nullable[beta_sym]) { beta_all_nullable = 0; break; } k++; } // 规则 3：B 在右部末尾，或 β 可空，FOLLOW(A) 加入 FOLLOW(B) if (k >= p->len || beta_all_nullable) { for (int s = 0; s < SYM_CNT; s++) { if (follow[A][s]) { changed |= add_to_set(follow[B], s); } } } } } } }

规则 2 里的内层while是很多人写错的地方：A -> B C且C可空时，需要继续看C后面的符号；如果只处理一个后续符号，FOLLOW(B)就会漏掉本应继承的内容。规则 3 的触发条件有两个，一是B就是产生式最后一个符号，二是B后面的符号串整体可空，两种情况都要把FOLLOW(A)并入FOLLOW(B)。

2.4 为什么不直接写递归

教科书上常用递归方式描述 FIRST 集和 FOLLOW 集，直观好理解，但实际编码时我建议用迭代。原因有两点：第一，间接左递归的文法如A -> B、B -> A，递归实现需要额外处理访问标记，一不小心就栈溢出；第二，迭代到不动点的写法，循环条件就是changed标志，逻辑透明，调试时打印每一轮的集合变化也很方便。这套思路在后面填预测分析表时同样适用。

3. 构造LL(1)预测分析表：表项填充与冲突判定

3.1 数据结构选型：定长二维数组，别一开始就用哈希

预测分析表本质是[非终结符][终结符] -> 产生式编号的映射。实验文法符号数量有限，直接用二维 int 数组最省事，输出也直观：

#define MAX_NONTERM 64 #define MAX_TERM 64 int parse_table[MAX_NONTERM][MAX_TERM]; // 存产生式下标 + 1，0 表示无表项 int nonterm_index[SYM_CNT]; // 非终结符字符 -> 行号（从 1 开始） int term_index[SYM_CNT]; // 终结符字符 -> 列号（从 1 开始）

行号和列号从 1 开始，把 0 留给空表项，这样打印时扫到 0 就输出-，语义清晰。索引映射在填表前先建好：

int row_count = 0, col_count = 0; for (int i = 0; i < g->prod_count; i++) { int lhs = (unsigned char)g->prods[i].lhs; if (nonterm_index[lhs] == 0) { nonterm_index[lhs] = ++row_count; } } for (int s = 0; s < SYM_CNT; s++) { if (is_terminal(s) || s == ENDMARK) { term_index[s] = ++col_count; } }

term_index要把ENDMARK也就是#也映射为一列，因为 LL(1) 分析表的列头是终结符加#。很多人在这一步漏掉#列，导致后面FOLLOW集合里的#无处安放。

3.2 填表规则：FIRST 驱动、FOLLOW 兜底

填表的核心规则只有两条：对每个产生式A -> α，把FIRST(α)中的每个终结符a对应的表项填成该产生式；如果α可推导出ε，再把FOLLOW(A)中的每个终结符b（含#）对应的表项也填成该产生式。

void build_table(Grammar* g) { for (int i = 0; i < g->prod_count; i++) { Production* p = &g->prods[i]; int A = nonterm_index[(unsigned char)p->lhs]; int alpha_first[SYM_CNT] = {0}; compute_first_of_rhs(g, p, alpha_first); // 规则 1：FIRST(α) 中的终结符入表 for (int s = 0; s < SYM_CNT; s++) { if (alpha_first[s] && is_terminal(s)) { int col = term_index[s]; if (parse_table[A][col] != 0) { printf("冲突: 符号 %c 位置已有产生式 %d\n", s, parse_table[A][col]); } else { parse_table[A][col] = i + 1; } } } // 规则 2：α 可空时，FOLLOW(A) 中的终结符入表 if (alpha_first[EPSILON]) { for (int s = 0; s < SYM_CNT; s++) { if (follow[(unsigned char)p->lhs][s] && (is_terminal(s) || s == ENDMARK)) { int col = term_index[s]; if (parse_table[A][col] != 0) { printf("冲突: 符号 %c 位置已有产生式 %d\n", s, parse_table[A][col]); } else { parse_table[A][col] = i + 1; } } } } } }

这段代码的关键是alpha_first[EPSILON]的判定：它表示α整个符号串可空。注意和FIRST(A)包含ε是两码事，A -> B C时B可空但C不可空，FIRST(α)就不该含ε。所以compute_first_of_rhs必须独立实现，不能直接拿first[A]用。

void compute_first_of_rhs(Grammar* g, Production* p, int* result) { int j = 0; while (j < p->len) { int X = (unsigned char)p->rhs[j]; if (is_terminal(X)) { result[X] = 1; return; // 首符号就是终结符，FIRST(α) 到此为止 } for (int s = 0; s < SYM_CNT; s++) { if (first[X][s] && s != EPSILON) { result[s] = 1; } } if (!nullable[X]) { return; // 遇到不可空符号，停止传播 } j++; } result[EPSILON] = 1; // 全部符号可空，ε 进入集合 }

这里有个细节：result数组的索引是 ASCII 码，EPSILON的值为 1，不会和任何真实文法符号的 ASCII 码冲突，所以result[EPSILON] = 1这个操作是安全的。is_terminal(X)为真时立刻return，因为第一个符号是终结符，后面符号不会再产生新的开头符号。

3.3 冲突判定：多重入口即宣告非 LL(1)

填表过程中打印冲突: 符号 %c 位置已有产生式 %d，这就说明文法不是 LL(1)。常见冲突来源有两类：左递归文法，比如E -> E + T | T，会让表[E][id]同时被两条产生式写入；公共左因子文法，比如if_stmt -> if (e) s | if (e) s else s，两个候选的 FIRST 集重合。遇到冲突，程序不会崩，但分析表是不可用的，需要回头改文法。

这类冲突检测是最有价值的输出之一——代码不只是生成一张表，还顺带给出了文法合法性的诊断信息。后续做实验报告时，把冲突日志截图放进去，老师一眼就能看出你理解了 LL(1) 的判定条件。

4. 测试文件与结果文件对照：test1~test4 在验证什么

4.1 zip 解压后的文件分配

下载的 zip 解压后，里面分三类文件：代码、测试输入、测试输出。先分清谁是谁，别上来就打开 testout 看。

压缩包里的 testout 系列文件是作者跑通的基准输出，不是给你直接交差的素材。正确用法是：自己编译运行 test4.c，生成新的 testout，再和包里原有的逐行对比，确认你的运行环境没有引入差异。

4.2 结果文件的内容格式与判读

testout 文件一般分三段：FIRST 集合表、FOLLOW 集合表、预测分析表。典型输出像这样：

FIRST(E) = { ( id } FIRST(E') = { + ε } FOLLOW(E) = { ) # } FOLLOW(E') = { ) # } 预测分析表: id + ( ) # E 1 - 1 - - E' - 2 - 3 3

行是非终结符，列是终结符加#，格子里的数字是产生式编号。从这张表可以直接判断是否满足 LL(1)：每个格子有且只有一个数字，没有2/3这种多重入口，就是合法预测分析表。ε在 FIRST 集合里可以看到，但不会出现在预测分析表的列头里，因为它不是输入符号。

4.3 运行流程与验证

在 Win10 的 VS2019 环境下，常规做法是直接从 IDE 里打开 test4.c 按 Ctrl+F5 编译运行。如果用命令行方式，开发者命令行里执行：

cl /W4 /Fe:test4.exe test4.c

生成 test4.exe 后，把文法文件作为输入重定向：

test4.exe < test1.txt > my_testout1.txt

<把 test1.txt 的内容喂给程序的 stdin，>把标准输出写入 my_testout1.txt。如果程序内部用fopen("test1.txt")固定读取，就不需要重定向，直接运行后会读取当前目录下的文本文件，注意把 test1.txt 放到 exe 同目录。

验证环节用fc命令逐字节对比：

fc my_testout1.txt testout1.txt

fc是 Windows 自带的文件比较命令，输出FC: 找不到差异就是完全一致。如果差异只在行尾空格或者换行符，通常不影响分析表内容，但建议用fc /W忽略空白差异再对比一次：

fc /W my_testout1.txt testout1.txt

/W参数压缩连续空白字符，能把因为编辑器换行风格不同造成的假差异过滤掉。顺手提醒一句：如果解压时提示文件损坏，先检查是不是 zip 伪加密标记——极少数下载站会给 zip 加伪加密头，文件能解压但会要求密码，用 7-Zip 打开看看加密标记位就能判断。

5. 避坑指南：迭代不收敛、#号缺失与 VS2019 的三类典型翻车点

5.1 现象：程序运行后一直不输出，CPU 占满

第一次跑 compute_first 时，程序卡死，任务管理器里进程 CPU 100%，等了几分钟也没反应。原因是迭代结束条件失效，changed变量被错误置 0，但add_to_set又不断返回 1，形成了死循环。更隐蔽的一种原因是 ε 符号占用了'\0'的 ASCII 码 0，导致p->rhs字符串在strlen或fgets处理时提前截断，后续产生式内容丢失，集合计算永远达不到不动点。解决办法是把EPSILON定义为 1、ENDMARK定义为 2，避开所有控制字符；同时把while (changed)改成do { changed = 0; ... } while (changed);结构，确保第一轮一定执行。

5.2 现象：FOLLOW 集合缺 # 号，分析表最后一列全空

用官方例题文法测试，生成的预测分析表#列全部是-，但根据理论，开始符号的 FOLLOW 集合必须包含#。原因是compute_follow里漏了规则 1 的初始化：没有对开始符号执行add_to_set(follow[start_symbol], ENDMARK)，导致#号在后续迭代里没有任何来源。这个问题的隐蔽之处在于程序能正常跑完，不报任何错，只有对照教科书手算 FOLLOW 集才能发现。解决是在compute_follow函数入口处无条件加这一行，同时确认ENDMARK和is_terminal的判断逻辑不冲突——#永远不应该被当成普通终结符加入 FIRST 集。

5.3 现象：左递归文法导致预测分析表出现多重入口

用E -> E + T | T作为输入，build_table 输出大量冲突：表[E][id]同时被产生式 1 和产生式 2 占用。这不是代码 bug，而是文法本身不满足 LL(1) 条件。左递归文法会让 FIRST 集发生循环依赖，产生的冲突无法通过修改代码来规避。解决思路是先消除左递归再从文法层面修正：把E -> E + T | T改写为E -> T E'、E' -> + T E' | ε，这也解释了为什么 test1.txt 里给出的文法通常都是改造过的 LL(1) 形式。

改完之后重新跑一遍，冲突消失，分析表每个格子只剩一个产生式编号。

5.4 现象：VS2019 编译报错 C4996，fopen 被标记不安全

在 VS2019 里直接编译 test4.c，报错error C4996: 'fopen' was declared deprecated。VS 默认对 C 标准库的fopen、scanf等函数给出安全告警，要求改用带_s后缀的版本。嫌改代码麻烦的话，在项目属性里找到预处理器定义，加上_CRT_SECURE_NO_WARNINGS，再重新编译即可。如果不想动项目配置，也可以把文件操作改成fopen_s：

FILE* fp = NULL; errno_t err = fopen_s(&fp, "test1.txt", "r"); if (err != 0) { printf("打开 test1.txt 失败，错误码 %d\n", err); return 1; }

fopen_s比fopen多返回一个错误码，文件不存在、路径错误、权限不足时都能拿到具体原因，这在调试时反而更有用。

5.5 现象：空产生式被当成普通符号，分析表多出一列ε

输入文法里有E' -> ε，结果预测分析表列头出现了ε，而且格子里的数字全是错位。原因是parse_production解析时把文本里的ε直接strcpy进rhs，而ε在 UTF-8 编码下是多字节字符，拆成单个 byte 后变成两个不可见字符，和EPSILON宏对不上。解决方法是解析阶段就做字符映射：读入文本后，凡遇到ε、@、#这些标记符号，统一替换成对应的EPSILON、ENDMARK宏值，后续所有逻辑只认宏不认文本。这个替换必须在 parse_production 的最前面完成，否则len统计会多算字节数，导致整条产生式解析错乱。

6. 进阶技巧：迭代日志追踪与文法预检

6.1 加一个迭代追踪开关

调试 FIRST 集和 FOLLOW 集不收敛时，最好的手段是在迭代循环里加追踪开关，把每轮的集合变化打印出来：

#define DEBUG_ITER 1 int iter = 0; do { changed = 0; iter++; #if DEBUG_ITER printf("=== 第 %d 轮迭代 ===\n", iter); for (int i = 0; i < g->prod_count; i++) { int A = (unsigned char)g->prods[i].lhs; printf("FIRST(%c) = {", A); for (int s = 0; s < SYM_CNT; s++) { if (first[A][s]) printf(" %c", s); } printf(" }\n"); } #endif // 原有的迭代逻辑 } while (changed);

如果某一轮的集合和上一轮完全相同，说明达到不动点；如果连续几十轮还在变，说明迭代条件写错了或者 ε 符号定义有冲突。这个开关在交付时注释掉即可，不要删，后面改文法还会用到。

6.2 建表前的左递归预检

在build_table之前加一个简单的左递归检测，能提前暴露问题：

int has_left_recursion(Grammar* g) { for (int i = 0; i < g->prod_count; i++) { Production* p = &g->prods[i]; if (p->rhs[0] == p->lhs) { printf("检测到直接左递归: %c -> %c...\n", p->lhs, p->rhs[0]); return 1; } } return 0; }

这个方法只查直接左递归，间接左递归如A -> B、B -> A需要借助可达性分析才能发现。实验文法则直接交给compute_first迭代去暴露，不收敛时再看追踪日志定位。

自从那次被左递归整到凌晨两点，我现在每拿到一个文法文件，都会先跑一遍预检函数，再决定要不要直接进建表流程。顺手把迭代追踪开关打开，确认 FIRST 集三轮以内收敛，才会去看最终的分析表。这套习惯帮我省掉了大量无意义的查错时间，希望也能帮到你。

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