简介：编译原理课程中的LL(1)语法分析器实验，往往需要同时完成文法设计、预测分析表构造与输入串判别等多个环节。这套资源面向正在学习自顶向下语法分析的本科生，围绕实验二提供了一个完整方案，内含源代码、可执行程序、实验报告、程序设计思想及讲解视频。压缩包共13个文件，大小约24.81MB，其中cpp与dev文件用于查看和重新编译工程，exe可直接运行验证，doc与docx文档涵盖实验报告与设计思路，mp4视频演示关键实现步骤，便于对照学习。内容覆盖了从读入LL(1)文法、构造预测分析表，到判断输入串是否为文法句子的完整流程，可帮助读者理解语法分析程序的实现方式并直接用于实验参考。目前已有3101人学习下载，适合编译原理实验课内练习或复习巩固。

1. LL(1)语法分析器：把编译原理实验二从“会画表”推进到“能跑通”

做编译原理实验二时，真正卡人的往往不是预测分析表怎么画，而是“程序如何自动判断输入串是不是该文法的句子”。LL(1)语法分析器这份资源，恰好把这条链路完整打包了：源码、可执行程序、讲解视频、实验报告和程序设计思想文档都在同一个包里。它的价值很直接——输入一个LL(1)文法，程序构造预测分析表，然后从键盘读入输入串，是句子就通过，不是就报错。适合正在赶实验、想先对照源码看懂再动手改代码的学生，也适合工作多年后需要快速回顾自顶向下分析机制的从业者。如果你接受一个前提：程序要能按文法自动填表，这份资源就是实打实的落地参考。

2. 预测分析表怎么构造：FIRST、FOLLOW 集与冲突判定

LL(1)名称里的两个“1”分别指“从左到右扫描、最左推导、向前看一个符号”。这里的核心前置是FIRST集、FOLLOW集和利用它们填出来的预测分析表。很多同学手算表没问题，但一到程序就不知道这些集合该用什么结构存、怎么迭代算。这一章把三个步骤拆开，重点放在“程序视角”。

2.1 FIRST 集：迭代求解比递归更适合写程序

FIRST集描述的是一个文法符号串能推导出的所有可能开头终结符。求它的规则不复杂：终结符的FIRST就是自身；非终结符A若有产生式A→α，则把FIRST(α)里的终结符都并入FIRST(A)；如果α能推导出空串，空串也属于FIRST(A)。手算时人脑能一眼看出推导路径，程序不能，所以程序里一般用迭代：每一轮把所有产生式扫一遍，只要有集合新增了元素就再扫一轮，直到所有集合大小都不再变化为止。

// 求解 FIRST 集的迭代框架 // 符号约定：eps 表示空串 ε，在程序里常用 "@" 或 "&" 代替 // first[x] 表示符号 x 的 FIRST 集合，用 bool 数组标记是否包含某个终结符 vector<bool> first[MAX_SYM]; bool changed = true; while (changed) { changed = false; for (每条产生式 A -> X1 X2 ... Xn) { int before = first[A].count(); if (X1 是终结符) { first[A].add(X1); // 首符号是终结符，直接并入 } else { first[A].addAll(first[X1]); // 并入首符号的 FIRST // 若 X1 可空，继续看 X2；用 i 记录当前扫到第几个符号 int i = 0; while (i < n && X_i 可空) { first[A].addAll(first[X_{i+1}]); i++; } if (i == n) first[A].add(eps); // 整个右部可空，空串加入 } if (first[A].count() > before) changed = true; } }

这段逻辑里最容易错的是“右部全可空”的判断。比如产生式 A→BC，B 和 C 都能推出空串，那么 A 的 FIRST 里必须有 eps，否则后面 FOLLOW 集的计算会全部错位。程序里判断“符号是否可空”通常是查该符号的 FIRST 里有没有 eps，所以求 FIRST 时先处理“直接产生空串的产生式”会让迭代收敛更快。另一个实践细节是空串的表示：源码里一般不会直接用字符 ε，常见有“@”、“&”或字符串“EPS”，如果你把输入文法里的 ε 写成中文输入法的“ε”，程序多半识别不了。

FIRST 集合的存储结构看文法规模。实验文法的符号个数通常不超过 30 个，用二维布尔数组或者 vector 都行。我一般习惯用布尔数组，因为后续填预测分析表时要频繁做“某个终结符在不在集合里”的查询，布尔数组的 O(1) 查询在循环里最省心。如果你要支持更复杂的文法，再把 bool 换成 set ，代价是每次插入要判断重复，性能慢一点，但思路完全一致。

2.2 FOLLOW 集：从“开头”倒推“后继”的三条规则

FOLLOW集描述的是一个非终结符在推导过程中右边可能出现的终结符集合。它解决的是预测分析表里“空串分支”的问题：当某产生式右部能推出空串时，当前非终结符后面跟着什么，决定了该不该用这个产生式。手算 FOLLOW 是从开始符号出发一遍推导就出来了，程序里同样得用迭代，因为 FOLLOW 的定义互相依赖。

// FOLLOW 集求解的三条规则，对应程序实现 // 初始化：follow[start].add(#)，# 是输入结束符 // 循环扫描所有产生式，直到没有集合变化 for (每条产生式 A -> X1 X2 ... Xn) { for (int i = 0; i < n; i++) { if (X_i 是非终结符) { // 规则 2：A -> α B β，把 FIRST(β) 里除 eps 外的终结符并入 FOLLOW(B) for (int j = i + 1; j < n; j++) { follow[X_i].addAll(first[X_j] 去掉 eps); if (X_j 不可空) break; // β 不能推出空串就停止后看 } // 规则 3：A -> α B 或 β 可空，把 FOLLOW(A) 并入 FOLLOW(B) if (i 右边的所有符号都可空) { follow[X_i].addAll(follow[A]); } // 规则 1：开始符号的 FOLLOW 里要有 # follow[start].add(#); } } }

这三条规则里，规则 3 是最容易被忽略的。每一轮迭代里 FOLLOW(A) 可能还没算完，就把它并入 FOLLOW(B)，那么下一轮循环必须再来一遍，直到 FOLLOW(A) 本身不再增长，所以外层用 while(changed) 包住这个 for 循环。这个“变化驱动继续迭代”的思路在 FIRST、FOLLOW、闭包类算法里都是同一个套路，建议直接背下来。

程序实现还有一个细节：规则 2 里“FIRST(β) 去掉 eps”和“β 可空”的判断，依赖的是 FIRST 集是否包含 eps。所以 FIRST 没求对，FOLLOW 一定跟着错。调试时如果发现 FOLLOW 结果和手算不一致，先回头查 FIRST 里 eps 的位置，不要急着改 FOLLOW 的逻辑。

2.3 预测分析表：一张表把所有冲突暴露出来

预测分析表是个二维表，行标是非终结符，列标是终结符（加上 #），每个格子存放一个产生式右部。填表规则：

// 填表核心逻辑 for (每条产生式 A -> α) { for (终结符 t ∈ FIRST(α)) { 表[A][t] = α; // 直接把可用的产生式放进去 } if (eps ∈ FIRST(α)) { for (终结符 t ∈ FOLLOW(A)) { 表[A][t] = α; // α 可空时，FOLLOW 中的终结符也触发 } } }

第 7 行和第 10 行可能同时往同一个格子填内容，这就是 LL(1) 冲突。常规做法是填入前先查格子是否已有值，如果有就把文法判定为“非 LL(1) 文法”，输出冲突的产生式对。手算表时你对冲突的判断多半是“发现同一个格子里有两条产生式”，程序里就是一次 if 判断的事，但很多初版代码直接写赋值语句，后写覆盖先写，冲突被静默吞掉，这是最危险的坑，第五章会专门展开。

判断文法是否为 LL(1) 除了看表冲突，还可以用两个硬性条件快速筛选：第一，不能有左递归；第二，对每个非终结符 A，FIRST(A) 与 FOLLOW(A) 不能有交集。这两个条件满足后再填表，冲突几乎不会出现。程序里放一个 checkConflict() 函数，在填表结束时遍历一次表，把所有冲突输出，会让你实验报告里“如何判断 LL(1) 文法”这一小节非常有话写。

3. 拿到源码先读这三块：数据结构、驱动循环、报错链路

实验资源里的 LL(1) 语法分析器.cpp 是主体实现。面对一个几百行的 C++ 实验源码，从头一行行读效率低，正确方式是先找三类东西：数据结构定义、主循环、错误处理。把它们读明白，程序等于看懂了一半。这一章按读源码的顺序来讲。

3.1 三个核心结构：产生式表、预测表与符号栈

实验性质的分析器，数据结构一般不会用复杂封装，最常见的是定长数组。先找这几个声明：

// 典型的数据结构声明（各实验源码命名略有差异） #define MAX_SYM 50 // 支持的最大符号数 #define MAX_PROD 100 // 支持的最大产生式数 struct Production { char left; // 产生式左部，一个非终结符 char right[MAX_SYM]; // 产生式右部字符串，如 "T*F" }; Production prods[MAX_PROD]; // 产生式表 char nonTerminals[MAX_SYM]; // 非终结符集合 char terminals[MAX_SYM]; // 终结符集合 int predictTable[MAX_SYM][MAX_SYM]; // 预测分析表，值为产生式下标，-1 表示错误

predictTable 的行列不是直接用字符下标，而是用符号在 nonTerminals、terminals 数组里的下标。所以程序里会有两个查下标的函数，比如 getNTIndex(char c)。做实验时如果要往程序里填文法，改的就是这几个数组的初始化部分，而不是主循环。预测表用 int 型二维数组存产生式下标是实验标准写法，好处是判断“格子是否为空”只要比较是否为 -1，比存字符串省事得多。

符号栈在源码里要么用 std::stack，要么自己写个 int 数组加栈顶指针。实验程序用数组栈更常见，因为要输出每一步的栈内容，数组遍历起来比 stack 方便。栈里存的是符号的 ASCII 码，末尾用 # 标记结束。看清楚栈的初始化位置：通常在分析开始前压入 # 和开始符号，顺序是先 # 后开始符号，这样栈顶才是开始符号。

3.2 驱动主循环：查表、压栈、匹配、推进

主循环是整个程序的核心，通常长这样：

// LL(1) 分析主循环框架 int top = 0; // 栈顶指针 char stack[MAX_SYM]; // 分析栈 stack[0] = '#'; // 栈底 stack[1] = startSymbol; // 开始符号 top = 1; int ip = 0; // 输入串指针 char input[MAX_SYM]; // 待分析的输入串 while (stack[top] != '#') { // 栈底 # 说明分析结束 char X = stack[top]; // X 是当前栈顶 char a = input[ip]; // a 是当前输入符号 if (X == a && X == '#') break; // 成功：栈和输入同时到结尾 if (X 是终结符 || X == '#') { if (X == a) { top--; ip++; continue; } // 匹配，双双推进 else reportError("栈顶终结符与输入不匹配"); } else { int row = getNTIndex(X); int col = getTerminalIndex(a); int prodIdx = predictTable[row][col]; if (prodIdx == -1) { reportError("预测表为空，输入串不是句子的推导结果"); } else { // 弹出栈顶，把产生式右部逆序压栈 top--; char* right = prods[prodIdx].right; if (right 不是 eps) { for (int k = strlen(right) - 1; k >= 0; k--) { stack[++top] = right[k]; } } } } } if (stack[top] == '#' && input[ip] == '#') printf("分析成功\n");

看这段代码你基本能理解 LL(1) 的“预测”到底发生在哪：第 20 行查表。栈顶非终结符对应当前输入符号，查预测分析表确定唯一产生式。压栈时注意是逆序压入，右部第一个符号最后压，所以它最先弹出、最先匹配。如果产生式右部是空串，就直接弹掉栈顶，不往里压任何东西，相当于“消耗掉”这个非终结符。

这个循环里最容易被忽略的是栈底判断。有的程序用 stack[top] == '#' 做退出条件，但没有同时判断 input[ip] 是否也等于 '#'，导致输入串提前读完后栈里还有东西，程序会拿栈顶非终结符去查表，列下标对到 '#' 上，表项通常是空的，于是报错。如果你实验时发现“合法句子被报错”，先看是不是输入串末尾没有补 #。

3.3 错误处理：三种报错出口和一种静默错误

实验要求里明确写了“若正确就通过，若错误就报错”，所以程序的报错会集中在这几个出口：栈顶终结符与输入符号不一致；预测表对应格子为空；输入串扫描完了但栈没空。每一种都对应一个错误码或错误信息，实验报告里要把这几条列出来。

真正的麻烦是静默错误——程序不报错，但结果是错的。最常见的是两种：一是预测表冲突被覆盖，导致合法句子被错误接受；二是 FIRST/FOLLOW 算错但表恰好没冲突，分析过程看着不报错，推导步骤却和文法的实际推导不一致。这类问题在输出“分析成功”时尤其有迷惑性，所以拿到源码第一件事不是跑例子，而是构造一个“必须报错”的输入串，确认程序真的会报错。如果连明显的非法串都被判定成功，先检查填表逻辑而不是检查分析主循环。

4. 跑起来再说：工具链、复现步骤与自定义文法替换

4.1 包里文件怎么分工，用哪个工具打开

解压这个 zip 包后，文件比想象中齐全。.dev 和 .layout 是 Dev-C++ 的工程文件和窗口布局文件，Makefile.win 是配套的 make 脚本，说明这份源码是在 Dev-C++ 环境下开发的；.o 和 .exe 是编译中间产物和编译好的程序；讲解视频.mp4 是配套讲解；程序设计思想.docx 是根据源码写的设计说明；编译原理实验二.docx 和《编译原理》实验二-2020.doc 是实验报告模板和题目要求。文件分工如下表。

工具链选择上，最省事的是装一个 Dev-C++，直接双击 LL(1)语法分析程序.dev 打开工程，点编译运行。如果你不喜欢 Dev-C++ 的老界面，用 VS Code 加 MinGW 也可以，手动按 Makefile.win 的内容执行 make 即可。注意 .o 和 .exe 是别人机器上编译出来的，能跑不代表你能改，修改源码后一定要重新编译生成新的 exe，否则你改的代码不会生效。

4.2 第一次运行：输入文法、输入串，看分析过程

程序的交互流程遵循实验二的标准要求：先构造预测分析表，再读入输入串。运行后按提示依次输入终结符、非终结符、产生式列表，最后输入要判断的串。下面是一次典型的会话示意：

请输入终结符个数: 4 请输入终结符(不含#): i + * ( ) 请输入非终结符个数: 3 请输入非终结符: E T F 请输入产生式个数: 6 请输入产生式(格式 A->B C): E->T E' E'->+ T E' | @ T->F T' T'->* F T' | @ F->( E ) | i 请输入要分析的输入串: i + i * i # 分析成功

注意：上面这段是典型实验程序的输入格式示意，你拿到的源码提示语可能有差异，比如用“输入文法规则”或“按行输入产生式”。以实际程序为准，但输入顺序基本逃不开“先符号表、后产生式、最后输入串”。

这个流程要能跑通，有个前提：你输入的产生式必须是 LL(1) 文法。上面示例里的 E' 和 T' 是消除左递归后的写法，如果你直接把课本里的 E→E+T 输进去，程序大概率会卡死或者表冲突，详见第五章。验证程序是否正常，建议第一次先用题目自带的例子跑一遍，第二次再换自己的文法。

一个容易被忽视的点是输入串末尾的 #。实验程序几乎都要在输入串末尾加 # 表示结束，漏掉会触发“输入串提前读完”的报错。产生式里的空串也要用程序规定的符号，通常是 @，不是希腊字母 ε，这个约定要看源码或程序设计思想.docx 里的说明。

4.3 换成你自己的文法：四个必须同步改的位置

实验二的要求通常是“给定一个文法，构造预测分析表并分析句子”。如果你要把程序从示例文法换成题目文法，必须同步改四个地方，少一个都会出诡异结果。

// 需要自定义时改动的初始化部分 // 位置 1：终结符集合 char terminals[] = {'i', '+', '*', '(', ')'}; // 按题目要求改，注意不含 '#' // 位置 2：非终结符集合 char nonTerminals[] = {'E', 'T', 'F', 'E_', 'T_'}; // 用 'E_' 代替 E' 是常见做法 // 位置 3：产生式列表（重点确认空串符号是 @ 还是别的） struct Production prods[] = { {'E', "T E_"}, {'E_', "+ T E_"}, // 右部为 @ 时，注意程序约定的空串符号 {'E_', "@"}, {'T', "F T_"}, {'T_', "* F T_"}, {'T_', "@"}, {'F', "( E )"}, {'F', "i"}, }; // 位置 4：默认输入串 char input[] = "i + i * i #"; // 需要判定的句子

改完后一定重新编译。替换时容易犯一个错：非终结符 E' 在字符数组里写不下，很多源码直接用原字符 'E' 再加一个特殊标记，或者干脆不区分 E 和 E'，导致同一行出现两个不同产生式、列下标冲突。我在实验里通常会把 E' 改写为 'H' 或 '_'，避免和原符号冲突，这是最容易翻车也最好规避的位置。

如果源码把文法写死在文件里而不是从键盘输入，替换逻辑一样，只是改动点从“输入产生式”变成“改文件内容”。少数实验源码会从外部 .txt 读文法，这种情况你的自定义文法要按文件里已有的格式排版，一行一条产生式，左右部之间用箭头或空格分隔，具体分隔符看文件的样例行。

4.4 用报告模板对照验证：程序输出与实验二要求对得上吗

实验报告里经常要求贴“分析过程”——也就是每个步骤的栈、剩余输入和所用产生式。但很多实验程序的输出只有“分析成功”四个字。先运行一遍看输出，如果有步骤输出直接可用；如果没有，用第六章的扩展方法补一个。另外，讲解视频.mp4 里一般会演示默认文法的完整运行，你先照着视频把输入串敲一遍，能复现视频里的输出，再确认工具链没问题，之后才谈改文法。这里啰嗦一句：包里同时有编译原理实验二.docx 和《编译原理》实验二-2020.doc，两个模板内容可能不完全一致，以老师发的实验要求为准，别直接拿 2020 版填今年的报告，年份对不上会被打回。

5. 避坑合集：LL(1)实验里五个高频翻车现场

5.1 左递归文法让程序死循环：栈永远降不下去

现象：程序运行后不报错，但输出疯狂滚动，或者界面直接卡死；强制结束后发现输出里的栈顶永远是同一个非终结符，栈内容越来越长。

原因：LL(1) 文法必须是无左递归的。你把 E→E+T 这样的产生式直接输进程序后，预测分析表里 E 在遇到 '+' 时反复选择 E→E+T，每次压栈都把 E 放在栈顶，下一轮查表还是它，形成死循环。程序没有做“左递归检测”，所以不报错，只是永远跑不完。

解决：先把文法消除左递归再输入。E→E+T 改成 E→TE'、E'→+TE'|@，T 同理。消完后如果程序还卡，检查有没有间接左递归，比如 A→B C，B→A d 这种。判断方法：把非终结符按任意顺序编号，检查是否存在“推导两步又回到自己”的产生式链，有就继续消除。

5.2 预测表冲突被静默覆盖：格子里的产生式“后写盖先写”

现象：一个明显非法的输入串被判定“分析成功”，或者一个合法串被报错，两种情况看起来相互矛盾，但都出自同一原因。

原因：程序填表时没有冲突检测，直接执行 predictTable[row][col] = prodIdx。一个格子先填了 E→T E'，后填了 E'→@ 的判断结果，后写的把先写的覆盖了，表看起来完整，实际是错误的。

解决：在填表循环里加查重。每填一个格子先判断是否已有内容，有就输出“冲突”并打印两个产生式，让程序拒绝继续。代码很简单：

// 填表时的冲突检测 int cell = predictTable[row][col]; if (cell != -1 && cell != prodIdx) { printf("LL(1)冲突: 产生式%d与%d在同一格\n", cell, prodIdx); printf("该文法不是LL(1)文法\n"); return 1; } predictTable[row][col] = prodIdx;

注意 cell != prodIdx 这个条件。同一条产生式在 FIRST 和 FOLLOW 分支里可能被填两次到同一个格子，那是正常的重复赋值，不算冲突。真正冲突是两个不同产生式抢同一个格子。

5.3 空串符号不一致：手写 ε 与程序内置符号对不上

现象：你按课本的 ε 输入产生式，FIRST、FOLLOW 怎么算都不对，程序输出要么是空表，要么分析结果完全错误。但与你手算结果对比，推导逻辑没问题。

原因：程序源码里空串符号可能是 @、& 或字符串 "eps"，而你输入的是 ε 这个字符。程序把 ε 当成普通终结符处理，产生式和终结符表全部错位。字符集不支持直接输入 ε，也是很多实验源码故意用 @ 的原因。

解决：先看源码里表示空串的常量定义，通常在文件头有 #define EPS '@' 这样的宏。把你写产生式时的 ε 统一替换成该符号。注意输入串里不要带 ε，因为输入串对应的是终结符序列，ε 不出现在输入串中。

5.4 输入串里的空格被当成终结符

现象：输入串写成 i + i * i（带空格）后，程序报“栈顶终结符与输入不匹配”，你检查了无数遍文法都没问题。

原因：输入串从键盘读入时带着空格字符，程序逐字符处理时把空格当作输入符号去查预测表，表项自然是空。如果程序是自写的，可以在读取时过滤；如果运行现成 exe，直接不带空格输入。

解决：最稳妥的输入格式是不带空格的串，如 i+i*i#。题目要求展示空格时，在源码输入处加过滤：

// 过滤输入串中的空白字符 char filtered[MAX_SYM]; int j = 0; for (int i = 0; input[i] != '\0'; i++) { if (input[i] != ' ' && input[i] != '\t') filtered[j++] = input[i]; } filtered[j] = '\0';

这一步过滤也要在文法产生式的读取处做，特别是从文本文件读文法的程序，文件里为了排版加的空格全会被当成符号。

5.5 改了源码但双击的还是旧 exe

现象：你在源码里改了半天，重新运行程序发现行为没任何变化，报错内容还是老样子。

原因：你运行的是包里自带的 LL(1)语法分析器.exe，那是原作者编译好的二进制，你的源码改动根本没参与编译。很多同学在这上面浪费半小时。

解决：在 Dev-C++ 里打开 .dev 工程后，用“编译并运行”而不是直接去文件管理器双击 exe。如果你手动用 make，执行 make 后会生成新的 exe 并覆盖旧的，确认编译输出里没有 error。改源码后看文件修改时间：exe 的修改时间必须晚于 .cpp 的修改时间，这是最直观的验证。

另外补一条经验：不要拿 .o 文件判断程序状态，.o 是编译中间产物，源码改了但 make 没执行时旧的 .o 还在那里，很容易误以为编译过了。我一般写完代码直接看 exe 时间戳，比 .o 可靠。

6. 把分析过程打出来：栈与剩余输入的每步跟踪

很多实验程序的输出只有“分析成功”四个字，但实验报告偏偏要求贴推导过程。与其手敲过程，不如在源码主循环里加一步栈跟踪。这个扩展改动极小、效果直观，几乎对所有 LL(1) 实验源码通用。

// 主循环每步输出栈与剩余输入 // 假设栈用数组 stack[0..top]，输入串从 ip 开始 int currentProd = -1; // 全局变量，填表分支里赋值 currentProd = prodIdx; void printTrace(char stack[], int top, char input[], int ip) { printf("栈: "); for (int i = 0; i <= top; i++) printf("%c", stack[i]); printf(" 剩余输入: "); for (int i = ip; input[i] != '\0'; i++) printf("%c", input[i]); printf(" 所用产生式: %d\n", currentProd); }

把 printTrace 放在 3.2 节主循环的每次查表之前调用，每一步的分析就有据可查。注意如果源码用的是 std::stack，直接遍历会从栈顶往栈底输出，顺序是反的，先把元素弹到临时数组再倒序输出即可。如果程序本来就在边分析边打印，只需要在打印语句里补上剩余输入串。

验证效果：输入 i+ii#，你会看到栈从 #E 开始，匹配到 i 后变成 #E'T，接着 E' 查表选择 +TE'，输出逐行显示“栈: #E'T 剩余输入: +ii# 所用产生式: 1”，整条推导链和课本上的最左推导完全对应，实验报告直接截图就能用。

这段跟踪对排错还有个额外价值：当输入串开头的终结符导致查表失败时，printTrace 能让你立刻看出栈顶符号和当前输入到底差在哪。我调 FIRST/FOLLOW 的 bug 时经常靠这行输出定位到“该用产生式 3 却用了产生式 1”，再回头查集合要素就快得多。从那以后，我拿到任何语法分析器实验资源，第一件事就是加这行栈跟踪，把“分析成功”这个黑匣子打开，先让每一步推导可见，再谈正确性和报告撰写。这个习惯帮我省掉了大量不明不白的排错时间，希望帮到你。

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