企业官网建设流程全解析

编译原理课程实验里，预测分析器往往是被卡住时间最长的一个环节。很多同学做词法分析的时候还挺顺利，一到语法分析，面对 FIRST 集、FOLLOW 集、预测分析表这一连串概念就开始发懵。其实预测分析器这东西并没有想象中那么高不可攀，它的核心就是一张二维表和一台“栈 + 输入串”的模拟器，本文把从文法到分析器的完整链路展开，配上可跑的代码，照着一步步做就能把实验拿下。

这套内容同时也是一份独立的小型 LL(1) 分析器实现手册，不管是课程实验、考研复试，还是想自己写一个精简的表达式解析器，都可以直接参考。本文里的代码风格偏向教学，不会刻意追求花哨的优化，重点是逻辑完整、看得懂、能改。

1. 整体设计与思路拆解

1.1 预测分析器到底在做什么

语法分析的任务，通俗讲就是检查一段输入串能不能由给定文法推导出来。预测分析器采用的是“自顶向下”的推导思路：从文法的开始符号出发，每一步根据当前看到的输入符号，决定接下来应该用哪条产生式继续推导。整个过程不需要回溯，所以叫“预测”。

实验里通常会要求在给定文法的前提下，分析一串由终结符组成的句子，输出推导过程或者构造语法树。我这次实现的核心模块是：

• 文法预处理：提取产生式，区分终结符与非终结符
• 计算每个非终结符的 FIRST 集和 FOLLOW 集
• 根据这两个集合生成预测分析表 M[A][a]
• 用栈模拟预测分析过程，对输入串做出接受或报错判断

这里有一个常见误区：很多同学一上来就写分析栈的代码，结果分析表是手工算好写死在程序里的。这样不能说错，但实验的意义就丢了。因为一旦遇到多个产生式的文法，手工算表极易出错，而且老师通常要求程序自动完成整个流程。

1.2 为什么选择表驱动而非递归下降

预测分析器有两种主流实现路线：递归下降子程序和表驱动预测分析。前者写起来直观，每个非终结符对应一个函数；后者本质是前者的“数据驱动版”，用一个栈和一张表替代了函数调用。实验题目既然明确写“预测分析器”，通常默认就是表驱动实现。表驱动的优势是分析逻辑与文法解耦，换一条文法只改数据不换框架，这也是工程上更值得掌握的思路。

整个程序我建议按数据流组织：文法读入 → FIRST 集 → FOLLOW 集 → 分析表 → 驱动分析，前一模块的输出就是后一模块的输入，调试时也可以逐模块打印验证。

2. FIRST 集、FOLLOW 集与 LL(1) 判定

2.1 FIRST 集的计算逻辑

FIRST(α) 指的是从 α 出发能推导出的所有终结符的集合，如果 α 能推导出空串（ε），那么 ε 也在 FIRST(α) 里。计算产生式右部候选式的 FIRST 集时，需要逐符号扫描：

• 如果当前符号是终结符，直接加入该终结符，停止扫描
• 如果当前符号是非终结符，把它的 FIRST 集（除 ε 外）全部加入；若它的 FIRST 集不含 ε，停止扫描；否则继续看下一个符号
• 如果扫完候选式中的所有符号都没有停止，说明该候选式整体可以推导出 ε，把 ε 加入

计算非终结符的 FIRST 集是一个迭代过程：初始时每个非终结符的 FIRST 集为空，然后反复扫描所有产生式，把新得到的符号加入集合，直到所有集合不再变化。这个“不动点迭代”的写法在实验里是最不容易出错的，哪怕文法有几十条产生式也能稳定算完。

我用 C++ 实现的 FIRST 集计算逻辑：

vector<string> grammar; // 产生式，格式为 "A->α" map<char, vector<string>> productions; // 非终结符 -> 候选式列表 set<char> nonTerminals, terminals; map<char, set<char>> firstSet; map<char, set<char>> followSet; bool isTerminal(char c) { return !(c >= 'A' && c <= 'Z'); } // 供内部使用的函数：计算符号串的 FIRST 集合 set<char> getFirstOfString(const string& s) { set<char> result; for (char c : s) { if (isTerminal(c)) { result.insert(c); break; } bool hasEpsilon = false; for (char x : firstSet[c]) { if (x == '#') hasEpsilon = true; // 用 # 表示 ε else result.insert(x); } if (!hasEpsilon) break; } return result; } void computeFirstSets() { // 初始化：终结符的 FIRST 集是自己 for (char c : nonTerminals) firstSet[c] = {}; bool changed = true; while (changed) { changed = false; for (char A : nonTerminals) { for (string& alpha : productions[A]) { // 求候选式 α 的 FIRST 集 set<char> alphaFirst; bool allEpsilon = true; for (char c : alpha) { if (isTerminal(c)) { if (alphaFirst.find(c) == alphaFirst.end()) { alphaFirst.insert(c); } allEpsilon = false; break; } else { bool hasEps = false; for (char x : firstSet[c]) { if (x == '#') hasEps = true; else alphaFirst.insert(x); } if (!hasEps) { allEpsilon = false; break; } } } if (allEpsilon || alpha.empty()) alphaFirst.insert('#'); // 合并进 firstSet[A] for (char x : alphaFirst) { if (firstSet[A].find(x) == firstSet[A].end()) { firstSet[A].insert(x); changed = true; } } } } } }

2.2 FOLLOW 集的计算与两个易错点

FOLLOW(A) 是可能在句型中紧跟在 A 后面的终结符集合，规则并不复杂：

• 开始符号的 FOLLOW 集加入 $
• 看产生式 A → αBβ（B 是非终结符），把 FIRST(β) 中除 ε 外的符号加入 FOLLOW(B)
• 若 β 能推导出 ε，或者 β 根本不存在（即 A → αB），把 FOLLOW(A) 加入 FOLLOW(B)

迭代过程跟 FIRST 集一样，直到集合不再变大。注意 FOLLOW 集不需要考虑产生式右部开头是终结符的情况，因为 FOLLOW 关心的是“跟在某个非终结符后面”的符号，而不是推导的开头。

两个高频易错点：

1. FOLLOW 集迭代时，必须使用当前一轮已经更新过的 FOLLOW(A) 值来传播给 FOLLOW(B)，否则某些文法会少算。稳妥的办法是：在每一轮循环里对所有产生式统一扫描，扫描过程中如果发现 FOLLOW(B) 里有新增符号，就把当前轮次的 changed 标记为 true，但继续基于更新后的集合进行计算；下一轮若不再有变化才退出。
2. 对形如 A → αBβ 且 β 为单个非终结符 C 的产生式，要记得 FIRST(C) 可能也含 ε；处理时先把 FIRST(C) 中除 ε 外的符号加入 FOLLOW(B)，再判断 C 是否能推导出 ε，若是则把 FOLLOW(A) 也加入。

实现片段：

void computeFollowSets() { for (char c : nonTerminals) followSet[c] = {}; followSet[startSymbol].insert('$'); bool changed = true; while (changed) { changed = false; for (auto& p : productions) { char A = p.first; for (string& alpha : p.second) { for (size_t i = 0; i < alpha.size(); i++) { char B = alpha[i]; if (isTerminal(B)) continue; // 只处理非终结符 // 找到 B 后面的符号串 beta string beta = alpha.substr(i + 1); set<char> betaFirst = getFirstOfString(beta); // 将 FIRST(beta) 除 ε 外的符号加入 FOLLOW(B) for (char x : betaFirst) { if (x != '#' && followSet[B].find(x) == followSet[B].end()) { followSet[B].insert(x); changed = true; } } // 如果 beta 可推导出 ε，或者 beta 为空，则传播 FOLLOW(A) bool betaHasEpsilon = betaFirst.find('#') != betaFirst.end(); if (beta.empty() || betaHasEpsilon) { for (char x : followSet[A]) { if (followSet[B].find(x) == followSet[B].end()) { followSet[B].insert(x); changed = true; } } } } } } } }

2.3 判断文法是否为 LL(1)

实验里可能会要求判断文法是不是 LL(1) 文法。核心条件很简单：

• 对每个非终结符 A 的任意两个不同候选式 A → α 和 A → β，要求 FIRST(α) 与 FIRST(β) 不相交
• 如果 FIRST(α) 含 ε，那么 FIRST(β) 不能与 FOLLOW(A) 相交；反之亦然

实际中我会通过预测分析表来判断：填表过程中某单元格 M[A][a] 被两个不同产生式竞争，就说明不是 LL(1)。这个方法直观，而且填入多个产生式时还能直接提示冲突位置，方便调试。注意下面要填表时的冲突检测，不只是在代码里做，也应该打印出冲突的产生式对，这样改文法的时候能很清楚哪里出了问题。

3. 预测分析表构建与驱动算法

3.1 填表规则与冲突检测

预测分析表是一个二维数组，行是非终结符，列是终结符和 $。对每个产生式 A → α 执行两步：

• 对 a ∈ FIRST(α) 且 a ≠ ε，把产生式填入 M[A][a]
• 若 ε ∈ FIRST(α)，则对 b ∈ FOLLOW(A)，把产生式填入 M[A][b]（包括 b = $）

填表时若目标格子已有条目，说明文法不是 LL(1)，我会记录冲突。

3.2 表驱动分析流程

分析栈初始状态：# 底面加开始符号。分析时不断看栈顶符号和输入串第一个符号：

• 栈顶是终结符且等于当前输入符号：弹出栈顶，输入指针后移
• 栈顶是终结符但不等于输入符号：报错
• 栈顶是非终结符 X：查表 M[X][当前输入符号]，若为空则报错；若存在产生式 X → Y1Y2...Yk，则弹出 X，把产生式右部逆序压栈（最后一个是 Yk，最先被弹出的将是 Y1，保证按产生式顺序推导）
• 栈顶是 $ 且输入也到 $：接受

这个流程建议在代码里把每一步的栈内容、剩余输入、所用产生式打印出来，实验报告加分不少，调试时也直观。

驱动代码我按课堂作业的经验写成下面这样：

vector<char> analyzeStack; // 模拟栈 int inputIndex = 0; string inputStr; // 输入串，最后追加 '$' void printStatus() { // 打印栈内容 cout << "栈:"; for (char c : analyzeStack) cout << " " << c; cout << " | 输入: " << inputStr.substr(inputIndex) << endl; } bool predictiveParse() { analyzeStack.clear(); analyzeStack.push_back('$'); analyzeStack.push_back(startSymbol); inputIndex = 0; while (true) { printStatus(); char top = analyzeStack.back(); char cur = inputStr[inputIndex]; if (top == '$' && cur == '$') { cout << "分析成功" << endl; return true; } if (isTerminal(top)) { if (top == cur) { analyzeStack.pop_back(); inputIndex++; } else { cout << "错误：栈顶终结符 " << top << " 与输入 " << cur << " 不匹配" << endl; return false; } } else { auto key = make_pair(top, cur); if (parsingTable.find(key) == parsingTable.end()) { cout << "错误：分析表中无 M[" << top << "][" << cur << "]" << endl; return false; } string prod = parsingTable[key]; // 形如 "A->α" cout << "选用产生式 " << prod << endl; analyzeStack.pop_back(); string rhs = prod.substr(3); // 右部 if (rhs == "#") continue; // 空产生式，无需压栈 // 逆序压栈 for (int i = rhs.size() - 1; i >= 0; i--) { analyzeStack.push_back(rhs[i]); } } } }

注意空产生式（A → ε）在表里也要有记录，代码里用 # 表示。实际填表时，如果候选式是 A → #，按规则会填入 FOLLOW(A) 中的每个符号位置。

4. 完整代码实现与环境搭建

4.1 文法输入与预处理

实验要求的文法输入格式要稳定。我常用如下格式，每行一条产生式，左部和右部用->分隔，多个候选式用|分开：

E->T E' E'->+ T E'|# T->F T' T'->* F T'|# F->( E )|i

预处理阶段要做的手工操作有：

• 把多条产生式按“|”拆分成独立候选式
• 从左部收集非终结符集合
• 从右部收集非终结符和终结符，注意->和|这些语法符号不属于文法符号
• 记录开始符号（第一条产生式的左部）

这里有个容易被忽略的坑：终结符里可能包含多字符符号，比如 expr 中的>=、==。课程实验的表达式文法里通常只用单个字符（i、+、*、括号）代表各类 token，所以直接按单字符处理没问题。如果实验要求多字符终结符，建议先把输入串做一次预处理，把多字符符号替换成单字符占位符，比如>=换成G，再交给分析器。这样处理保持分析器核心逻辑简单，不需要改动数据结构。

4.2 构建预测分析表

map<pair<char, char>, string> parsingTable; void buildParsingTable() { parsingTable.clear(); for (auto& prodPair : productions) { char A = prodPair.first; for (string& alpha : prodPair.second) { set<char> alphaFirst = getFirstOfString(alpha); for (char a : alphaFirst) { if (a != '#') { auto key = make_pair(A, a); if (parsingTable.find(key) != parsingTable.end()) { cout << "冲突：M[" << A << "][" << a << "] 已有 " << parsingTable[key] << "，待填入 " << A << "->" << alpha << endl; } else { parsingTable[key] = string(1, A) + "->" + alpha; } } } if (alphaFirst.find('#') != alphaFirst.end()) { for (char b : followSet[A]) { auto key = make_pair(A, b); if (parsingTable.find(key) != parsingTable.end()) { cout << "冲突：M[" << A << "][" << b << "] 已有 " << parsingTable[key] << "，待填入 " << A << "->" << alpha << endl; } else { parsingTable[key] = string(1, A) + "->" + alpha; } } } } } }

4.3 测试用例设计

测试文法我推荐用带左递归消解后的经典表达式文法。左递归在自顶向下分析里是死路，用 E → T E' 这种右递归形式替代。

输入串设计几组有代表性的：

• 带括号和多个运算符：i+i*i
• 嵌套括号：(i+i)*i
• 空串（如果文法允许）
• 错误串：i+*i、i(i)，用于验证报错路径

判断接受与否只看能否推到输入串结束且栈清到$。分析成功时不输出推导树也可以打印推导序列，即每一步选用的产生式编号，这就是一个最简的“最左推导”证据。

4.4 把代码拼起来跑通

主函数流程按顺序调用即可：

int main() { readGrammar(); computeFirstSets(); computeFollowSets(); buildParsingTable(); testLL1(); cout << "输入待分析的句子（末尾无需加$,程序自动补）: "; cin >> inputStr; inputStr += '$'; predictiveParse(); return 0; }

建议在 main 里先写一个打印 FIRST 和 FOLLOW 集的调试函数，跑任何文法前先确认集合计算正确，再去分析句子。我实验时吃过亏：以为分析表填错了，折腾很久才发现是 FIRST 集计算漏了迭代，最后打印集合一眼就看出问题。

5. 实操中常见的五个坑

5.1 空产生式的表示混乱

有的教材用 ε，有的用^，还有用null。建议统一用#存到集合和处理逻辑里。如果你在代码里混用符号，getFirstOfString 判断 epsilon 时会漏判，后续 FOLLOW 集传播也会出错。这个统一符号的事在工程里叫“规范”，虽然是小事，但能省掉大量无谓调试。

5.2 输入串中的空格和换行

从标准输入读取句子的时候，如果问句里有空格，比如i + i * i，直接cin >> inputStr只能读第一段。实验报告建议要么输入时要求不带空格，要么用getline()读取，然后手动过滤空白字符。我后来包装了一层cleanInput()：把空格、制表符、回车全删掉。这也是一个词法预处理的雏形，真实编译器中词法分析和语法分析本来就需要配合。

5.3 只做了产生式匹配，却没处理错误恢复

课程实验一般只要求报错，不需要恢复。但如果想往深做一点，可在报错后执行一个“同步符号”策略：当栈顶是非终结符 X 且输入符号不在 FOLLOW(X) 中时，跳过输入符号。这个思路叫做“恐慌模式恢复”，是很多真实编译器的兜底手段，可以作为实验报告里的进阶加分项。加代码也不麻烦，就是在查表失败后，不断推进 inputIndex，直到某个符号能匹配上栈顶或输入结束。

5.4 分析表中把 $ 当成终结符处理

在判断终结符时我用isTerminal(c)检测c >= 'A' && c <= 'Z'，但$和#都不属于大写字母，按这个函数会被当成终结符。这是天经地义的，但要注意 FIRST/FOLLOW 集合计算时不能把$和#混进普通终结符集合。我建议在去重和输出打印阶段统一处理：#只在 FIRST 集里出现，$只在 FOLLOW 集与分析栈底出现。如果你打印 FIRST 集时把#当成普通终结符显示，容易产生误导。

5.5 迭代法计算集合时忘了判断“是否变化”

这是一个很容易犯的错：把 while 循环写成了 for 循环的固定轮数，以为扫描三遍就一定能收敛。碰到复杂的间接左递归文法（比如 A → B，B → A a 这种构造），三遍可能不够。实验里我平时构造的表达式文法基本一遍就收敛了，但测试别人给的文法时翻过车。所以老老实实用 while + changed 标记，直到某轮结束时 changed 为 false 再退出。

6. 实验收尾与一点个人心得

把这套东西跑通之后，我对“自顶向下”分析的理解比看十遍教材都管用。尤其是那个栈模拟，第一次看到栈里真的按照产生式右部逆序压入符号，然后一步一步弹出终结符对应输入时，会有一种“原来语法分析是这么回事”的通透感。

最后还想分享两个可以让实验报告眼前一亮的小优化：

1. 在分析过程中记录每一步的“推导序号 + 栈状态 + 输入”并以表格形式输出，配合程序运行截图，实验报告的可读性会好很多。其实这就是编译器前端 debug 日志的简化版。
2. 测试不同文法时，让程序输出“该文法是否为 LL(1) 文法”的判断结论，如果非 LL(1) 就输出冲突的具体位置。这个能力在完成基本要求后加上去很快，却是很多同学容易忽略的功能点。

如果后续还有时间，可以把这个小项目扩展成支持多字符终结符、错误恢复、甚至直接输出一棵语法树的版本。一棵简单语法树的数据结构无非是树节点把产生式右部的符号按序挂到左部下，递归建树即可。但那是下一步的事了，先把预测分析器本身做到能稳定跑通、能讲清楚原理，这个实验就成了。