C++实现LL(1)语法分析器：FIRST/FOLLOW集与预测分析表详解

简介这份资源面向正在学习编译原理、需要完成语法分析实验的高校学生与自学者核心是提供一个可直接参考的递归子程序法语法分析实现方案。它基于词法分析程序识别出的单词按给定文法对各类语法成分进行识别并按顺序输出单词信息与语法成分名称帮助读者理解从词法到语法的完整分析流程。压缩包共2个文件包含1个cpp源码与1个doc说明文档整体约17KB源码对应实验平台上的完整实现文档则给出问题描述与输入输出要求便于对照理解设计思路。目前已有6106人学习下载说明该方案在同类实验中具有较高的参考价值。读者可借此掌握递归下降分析的基本框架、预读处理与结果输出格式并对照自身实验查漏补缺适合作为课程作业与实验评测的参考范例。1. 语法分析实验到底在做什么从一段报错代码说起很多人第一次做编译原理语法分析实验拿到题目就懵了——给一个文法要求写个 C 程序判断输入串是否合法输出分析过程。看起来简单真动手才发现FIRST 集算不对、FOLLOW 集漏了 ε、预测分析表填错一格整个程序就跑飞了。更崩溃的是你明明按教材上的算法写的结果和参考答案对不上debug 两小时发现是文法里一个候选式的顺序搞反了。这个实验的核心就一件事给定上下文无关文法用 C 实现一个语法分析器能对任意输入串给出「合法/非法」的判断并输出推导过程或语法树。常见做法有两种——递归下降和 LL(1) 预测分析。递归下降写起来直观但遇到左递归直接死循环LL(1) 需要构造预测分析表前期计算量大但跑起来稳定适合实验课交作业。适合谁看正在上编译原理课、被实验报告卡住的人想用 C 把理论落地、但不知道从哪下手的人以及已经写完但结果不对、想找排查思路的人。下面按「理论先立住 → 代码能复现 → 坑在哪」的顺序推一遍你跟着走就能跑通。2. 文法预处理与 FIRST/FOLLOW 集手算和代码怎么对齐2.1 为什么必须先消左递归和提取左公因子教材上的文法往往是「好看但不好用」的。比如E → E T | T直接写递归下降parseE()第一件事就是调parseE()栈直接溢出。LL(1) 更严格——有左递归连预测分析表都构造不出来因为 FIRST 集里永远包含不了终结符。所以动手写代码之前先做两步预处理消除左递归。对于A → Aα | β改成A → βA A → αA | ε提取左公因子。对于A → αβ1 | αβ2改成A → αA A → β1 | β2这两步是机械操作但手算容易漏。我一般会写个小脚本先跑一遍确认没有直接左递归和公共前缀再进入下一步。2.2 FIRST 集和 FOLLOW 集的 C 实现FIRST 集的规则不复杂终结符的 FIRST 就是它自己非终结符看所有候选式第一个符号的 FIRST 并进来如果第一个符号能推出 ε继续看第二个。FOLLOW 集稍微绕一点起始符号的 FOLLOW 包含$对于A → αBβFIRST(β) 去掉 ε 加入 FOLLOW(B)如果 β 能推出 εFOLLOW(A) 加入 FOLLOW(B)。用 C 实现时数据结构选mapstring, setstring最顺手。下面是我常用的框架#include bits/stdc.h using namespace std; mapstring, vectorvectorstring grammar; // 文法产生式 mapstring, setstring FIRST, FOLLOW; setstring nonTerminals, terminals; // 判断是否为终结符不在非终结符集合里就是终结符 bool isTerminal(const string s) { return nonTerminals.find(s) nonTerminals.end(); } // 计算 FIRST 集 void computeFIRST() { bool changed true; while (changed) { changed false; for (auto [lhs, prods] : grammar) { for (auto prod : prods) { // 空产生式 if (prod.size() 1 prod[0] ε) { if (FIRST[lhs].insert(ε).second) changed true; continue; } for (size_t i 0; i prod.size(); i) { string sym prod[i]; if (isTerminal(sym)) { if (FIRST[lhs].insert(sym).second) changed true; break; } else { // 把 FIRST(sym) 中非 ε 的加入 FIRST(lhs) for (auto f : FIRST[sym]) { if (f ! ε) { if (FIRST[lhs].insert(f).second) changed true; } } // 如果 sym 不能推出 ε停止 if (FIRST[sym].find(ε) FIRST[sym].end()) break; // 如果所有符号都能推出 ε加入 ε if (i prod.size() - 1) { if (FIRST[lhs].insert(ε).second) changed true; } } } } } } }这段代码的逻辑是反复扫描所有产生式直到 FIRST 集不再变化。外层while(changed)是必须的因为一个非终结符的 FIRST 可能依赖另一个非终结符而那个又依赖回来需要迭代到不动点。参数说明grammar的 key 是产生式左部value 是右部符号序列的列表ε用字符串ε表示。注意prod.size() 1 prod[0] ε这个判断空产生式要单独处理。FOLLOW 集的代码类似但依赖 FIRST 的结果所以必须先算完 FIRST 再算 FOLLOWvoid computeFOLLOW(const string startSymbol) { FOLLOW[startSymbol].insert($); // 起始符号加入结束符 bool changed true; while (changed) { changed false; for (auto [lhs, prods] : grammar) { for (auto prod : prods) { for (size_t i 0; i prod.size(); i) { string B prod[i]; if (isTerminal(B)) continue; // 情况1B 后面有符号 bool allEpsilon true; for (size_t j i 1; j prod.size(); j) { string beta prod[j]; if (isTerminal(beta)) { if (FOLLOW[B].insert(beta).second) changed true; allEpsilon false; break; } else { for (auto f : FIRST[beta]) { if (f ! ε) { if (FOLLOW[B].insert(f).second) changed true; } } if (FIRST[beta].find(ε) FIRST[beta].end()) { allEpsilon false; break; } } } // 情况2B 后面所有符号都能推出 ε或 B 在末尾 if (allEpsilon) { for (auto f : FOLLOW[lhs]) { if (FOLLOW[B].insert(f).second) changed true; } } } } } } }这里有个容易翻车的点allEpsilon的初始值是true但如果 B 后面有终结符要立刻置false并break。很多人写的时候忘了在终结符分支里改这个标志导致 FOLLOW 集多算了一堆不该有的符号。2.3 手算验证拿一个具体文法对一遍光看代码没感觉拿经典文法走一遍E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id手算 FIRST(E) FIRST(T) FIRST(F) { (, id }。FIRST(E) { , ε }。FOLLOW(E) { $, ) }因为 E 出现在( E )里右括号跟在后面E 是起始符号所以 $ 也在。FOLLOW(E) FOLLOW(E) { $, ) }。跑一遍代码输出对得上说明 FIRST/FOLLOW 计算没问题。对不上就回去查产生式有没有写错、ε 有没有漏。3. LL(1) 预测分析表构造与 C 实现从表到分析器3.1 预测分析表的填充规则有了 FIRST 和 FOLLOW预测分析表 M 的填充规则很直接对于每个产生式A → α遍历 FIRST(α) 中的每个终结符 a把A → α填入 M[A][a]如果 ε 在 FIRST(α) 里遍历 FOLLOW(A) 中的每个符号 b把A → ε填入 M[A][b]。冲突检测也在这里做如果 M[A][a] 已经有值了说明文法不是 LL(1) 的需要回去改文法或者换分析方法。用 C 存预测分析表mapstring, mapstring, vectorstring比较直观mapstring, mapstring, vectorstring parsingTable; void buildTable() { for (auto [lhs, prods] : grammar) { for (auto prod : prods) { setstring firstAlpha; bool hasEpsilon false; // 计算 FIRST(α) if (prod.size() 1 prod[0] ε) { hasEpsilon true; } else { for (size_t i 0; i prod.size(); i) { string sym prod[i]; if (isTerminal(sym)) { firstAlpha.insert(sym); break; } else { for (auto f : FIRST[sym]) { if (f ! ε) firstAlpha.insert(f); } if (FIRST[sym].find(ε) FIRST[sym].end()) break; if (i prod.size() - 1) hasEpsilon true; } } } // 填入表中 for (auto a : firstAlpha) { if (parsingTable[lhs].count(a)) { cerr 冲突M[ lhs ][ a ] endl; } parsingTable[lhs][a] prod; } if (hasEpsilon) { for (auto b : FOLLOW[lhs]) { if (parsingTable[lhs].count(b)) { cerr 冲突M[ lhs ][ b ] endl; } parsingTable[lhs][b] prod; } } } } }关键参数parsingTable[lhs][a]存的是产生式右部符号序列。冲突检测用count判断是否已存在有冲突就打印出来方便定位问题。3.2 用栈驱动的分析过程LL(1) 分析器的主循环就是一个栈加一个输入指针void parse(const vectorstring tokens) { stackstring stk; stk.push($); stk.push(E); // 起始符号 size_t pos 0; vectorstring input tokens; input.push_back($); while (!stk.empty()) { string top stk.top(); string cur input[pos]; if (top $ cur $) { cout 分析成功 endl; return; } if (isTerminal(top) || top $) { if (top cur) { stk.pop(); pos; } else { cout 错误期望 top 实际 cur endl; return; } } else { if (parsingTable[top].count(cur)) { stk.pop(); vectorstring prod parsingTable[top][cur]; // 逆序入栈 for (int i prod.size() - 1; i 0; i--) { if (prod[i] ! ε) stk.push(prod[i]); } } else { cout 错误M[ top ][ cur ] 无产生式 endl; return; } } } }逻辑说明栈里存的是「还需要匹配的符号」输入串末尾加$作为结束标记。每次看栈顶和当前输入符号——栈顶是终结符就匹配匹配成功双双前进栈顶是非终结符就查表把产生式右部逆序压栈因为栈是后进先出逆序压才能保证从左到右匹配。参数说明tokens是词法分析输出的 token 序列每个 token 用字符串表示。input.push_back($)是加结束符别忘了。3.3 输出分析过程让实验报告有东西可写实验报告通常要求输出每一步的栈内容、剩余输入串和所用产生式。在循环里加一行打印就行cout 栈: ; // 打印栈内容需要辅助函数因为 stack 不支持遍历 printStack(stk); cout 输入: ; for (size_t i pos; i input.size(); i) cout input[i] ; cout 动作: ;printStack可以用递归或者临时栈实现。这一步不难但输出格式要对齐不然报告看起来乱。4. 递归下降版本什么时候选它怎么写不翻车4.1 递归下降和 LL(1) 的选型对比维度递归下降LL(1) 预测分析代码量少每个非终结符一个函数多需要建表可读性高直接对应文法低表驱动左递归必须消除必须消除回溯可能需要不需要适合场景文法简单、实验要求不高文法规范、要求输出分析过程如果实验只要求判断合法性递归下降够用。如果要求输出完整推导过程或者文法比较复杂LL(1) 更稳。4.2 递归下降的 C 骨架以之前的表达式文法为例string input; size_t pos 0; void match(const string expected) { if (pos input.size() input.substr(pos, expected.size()) expected) { pos expected.size(); } else { throw runtime_error(期望 expected 位置 to_string(pos)); } } void parseE(); // 前向声明 void parseT(); void parseE() { parseT(); parseEPrime(); } void parseEPrime() { if (pos input.size() input[pos] ) { match(); parseT(); parseEPrime(); } // ε 产生式什么都不做 } void parseT() { parseF(); parseTPrime(); } void parseTPrime() { if (pos input.size() input[pos] *) { match(*); parseF(); parseTPrime(); } } void parseF() { if (pos input.size() input[pos] () { match((); parseE(); match()); } else if (pos input.size() isalpha(input[pos])) { // 简化处理 id pos; } else { throw runtime_error(语法错误位置 to_string(pos)); } }注意parseEPrime和parseTPrime里的 ε 分支——直接返回不做任何操作。这是递归下降处理空产生式的方式。4.3 递归下降的三个常见翻车点翻车一忘了消除左递归。E → E T直接写成parseE()调parseE()栈溢出。必须改成E → T E。翻车二回溯没处理好。如果文法有公共前缀比如A → ab | ac递归下降需要试探。我一般会先提取左公因子避免回溯。翻车三错误恢复太粗糙。抛异常直接退出实验报告里看不出哪一步出错。建议在match失败时打印当前位置和期望符号方便定位。5. 避坑与排查语法分析实验里最容易翻车的 5 个地方5.1 现象FIRST 集算出来少了符号原因迭代没到不动点就退出了。FIRST 集的计算是单调递增的但一个非终结符的 FIRST 可能依赖另一个而那个又依赖回来需要反复扫描直到不再变化。解决外层用while(changed)包住每次插入成功就置changed true。别用固定轮数轮数不好估。5.2 现象FOLLOW 集多出了不该有的符号原因allEpsilon标志没在终结符分支里置false。比如A → B cB 后面是终结符 c应该把 c 加入 FOLLOW(B) 然后停止但如果忘了改标志会继续走到「B 在末尾」的逻辑把 FOLLOW(A) 也加进去。解决在遇到终结符时立刻allEpsilon false; break;。这个血泪经验来自我当年实验报告被扣分。5.3 现象预测分析表有冲突程序跑不起来原因文法不是 LL(1) 的。常见于公共前缀没提取干净或者 ε 产生式的位置不对。解决先检查有没有提取左公因子。如果文法本身不是 LL(1)考虑换 SLR 或者 LR(1)但实验课一般不会要求这么复杂大概率是预处理没做干净。5.4 现象分析过程中栈顶和输入不匹配但文法没问题原因产生式右部入栈顺序搞反了。栈是后进先出如果正序压栈匹配顺序就反了。解决逆序压栈。for (int i prod.size() - 1; i 0; i--)这个循环方向别写错。5.5 现象输入串末尾忘了加结束符死循环原因分析器在等$但输入串里没有栈永远清不空。解决input.push_back($)这行别忘了。另外栈底也要先压$两个$相遇才算成功。6. 进阶技巧用语法树输出把实验报告拉满基础版只输出「合法/非法」但实验报告想拿高分通常要求输出语法树或者推导过程。这里给一个把 LL(1) 分析过程转成语法树的思路。在分析循环里每次用产生式展开时创建一个树节点把产生式右部的符号作为子节点。但栈驱动的分析是线性的直接建树需要额外记录父子关系。我一般用「节点栈」配合符号栈struct TreeNode { string symbol; vectorTreeNode* children; TreeNode(string s) : symbol(s) {} }; // 在 parse 函数里维护一个节点栈 stackTreeNode* nodeStack; nodeStack.push(new TreeNode($)); nodeStack.push(new TreeNode(E)); // 当用产生式 A → α 展开时 TreeNode* parent nodeStack.top(); nodeStack.pop(); for (int i prod.size() - 1; i 0; i--) { if (prod[i] ε) continue; TreeNode* child new TreeNode(prod[i]); parent-children.insert(parent-children.begin(), child); nodeStack.push(child); }逻辑说明节点栈和符号栈同步操作。符号栈弹出非终结符时节点栈也弹出对应节点然后为产生式右部每个符号创建子节点逆序插入children保证从左到右的顺序。参数说明children.insert(begin, child)是头插因为循环是逆序的头插之后顺序就正过来了。也可以用push_back配合正序循环看个人习惯。最后打印树的时候用递归先序遍历每层缩进两个空格void printTree(TreeNode* root, int depth 0) { if (!root) return; for (int i 0; i depth; i) cout ; cout root-symbol endl; for (auto* child : root-children) { printTree(child, depth 1); } }这样输出的语法树直接贴进实验报告比纯文本的分析过程好看得多。验证方法拿几个合法输入串和非法输入串各跑一遍合法串应该输出完整树非法串应该在错误位置报错并停止。如果树的结构和手推的不一样回去检查产生式入栈顺序和节点插入顺序。我自己的习惯是先用手算把一个小文法的完整分析过程写出来再拿代码跑同样的输入逐步对比栈内容和输出。对不上就单步调试看是哪一步的查表结果和手算不一致。这个笨办法帮我省了很多返工时间。希望帮到你。本文还有配套的精品资源点击获取