简介用于编译原理课程中LL(1)预测分析表的自动生成面向计算机专业本科生以及需要掌握FIRST集、FOLLOW集迭代计算与预测分析表构造原理的学习者。压缩包内代码使用C语言编写适配Win10VS2019环境对应胡元义《编译教程第四版》的实验要求。压缩包共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返回 1changed就会被置 1下一轮继续。EPSILON用 ASCII 码 1ENDMARK用 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; // 规则 2A - α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; } // 规则 3B 在右部末尾或 β 可空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]; // 存产生式下标 10 表示无表项 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); // 规则 1FIRST(α) 中的终结符入表 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 看。类别文件名作用测试代码test4.c主程序包含 FIRST、FOLLOW、建表全部逻辑测试文法test1.txt、test2.txt、test3.txt、test4.txt4 个不同文法难度递增结果文件testout.txt、testout1.txt、testout2.txt、testout3.txt、testout4.txt运行后生成的分析表输出说明文档readme.txt运行方法、环境要求、注意事项压缩包里的 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 按 CtrlF5 编译运行。如果用命令行方式开发者命令行里执行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.txtfc是 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) 形式。原始文法消除左递归后E - E T | TE - T ET - T * F | FT - F TF - ( E ) | idF - ( E ) | id改完之后重新跑一遍冲突消失分析表每个格子只剩一个产生式编号。5.4 现象VS2019 编译报错 C4996fopen 被标记不安全在 VS2019 里直接编译 test4.c报错error C4996: fopen was declared deprecated。VS 默认对 C 标准库的fopen、scanf等函数给出安全告警要求改用带_s后缀的版本。嫌改代码麻烦的话在项目属性里找到预处理器定义加上_CRT_SECURE_NO_WARNINGS再重新编译即可。如果不想动项目配置也可以把文件操作改成fopen_sFILE* 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 集三轮以内收敛才会去看最终的分析表。这套习惯帮我省掉了大量无意义的查错时间希望也能帮到你。本文还有配套的精品资源点击获取