尧图网站建设 文法分析器：FIRST/FOLLOW集计算与预测分析表生成)
简介这份资源是面向计算机专业学生与编译原理学习者的C课程设计项目围绕根据文法自动生成LL(1)分析器展开帮助理解自左向右扫描、仅查看一个输入符号的预测分析流程。包内共11个文件以8个cpp源文件为核心配合1个头文件与1个说明文档另有许可证文件压缩包约12KB结构紧凑便于直接编译运行与二次修改。内容覆盖文法解析、FIRST集与FOLLOW集构造、冲突检测、分析表生成、分析器实现及错误处理等关键环节并借助STL容器与面向对象方式组织文法规则和分析表。已有406人学习下载适合作为课程设计参考或编译器前端入门练手读者可据此掌握从文法输入到自动生成分析表的完整思路并借鉴其中的数据结构设计与排错方法。1. 从一份 C 课设说起LL(1) 分析器到底能帮你省下多少手工推导如果你正在做编译原理课程设计大概率绕不开一个经典题目给定一组文法产生式判断它是不是 LL(1) 文法然后自动生成分析表并跑通一个输入串。手工推导 FIRST 集、FOLLOW 集、SELECT 集再画预测分析表文法稍微复杂一点就容易出错改一个产生式就得从头再来一遍。这份基于 C 实现的 LL(1) 文法分析器解决的正是这个重复劳动问题——你把文法规则写成文本喂进去它自动完成预处理、FIRST/FOLLOW 集计算、冲突检测、分析表生成和输入串分析全流程。它适合两类人一类是正在赶编译原理课设、需要一份能跑通且结构清晰的参考实现另一类是想搞明白 LL(1) 分析器内部数据流怎么组织的 C 学习者。整个项目按功能拆成了 preprocess、get_first、get_follow、generator、analyze 等独立源文件不是一坨代码堆在 main 里读起来能看清每一步在干什么。下面我从文法输入格式开始把这份资源怎么用、参数怎么设、容易在哪翻车按实操顺序拆一遍。2. 文法预处理与数据结构产生式怎么存、符号怎么分类2.1 文法文本的输入格式与解析逻辑这份实现里文法通常以产生式文本形式输入每条规则形如E - T E多个候选式用|分隔空产生式用ε或特定标记表示。preprocess.cpp 负责把原始文本切成一个个符号区分终结符和非终结符。常见做法是大写字母开头的标识符视为非终结符其余小写字母、运算符、数字、括号等视为终结符ε单独处理为空串标记。解析时最容易翻车的地方是分隔符处理。比如E-T|E和E - T | E必须都能正确切分否则后续 FIRST 集计算会拿到带空格的符号名导致集合匹配失败。我一般会在预处理阶段统一做一次 trim 和符号规范化把箭头统一成-把连续空白压成一个空格再按|拆分候选式。// preprocess.cpp 中产生式解析的核心逻辑示意 struct Production { std::string lhs; // 左部非终结符 std::vectorstd::string rhs; // 右部符号序列空串用 ε 表示 }; std::vectorProduction parseGrammar(const std::string raw) { std::vectorProduction grammar; std::istringstream iss(raw); std::string line; while (std::getline(iss, line)) { // 去掉首尾空白和回车 trim(line); if (line.empty()) continue; // 按 - 切分左右部 auto pos line.find(-); std::string lhs trim(line.substr(0, pos)); std::string rhsPart trim(line.substr(pos 2)); // 按 | 拆分候选式 std::vectorstd::string alts split(rhsPart, |); for (auto alt : alts) { Production p; p.lhs lhs; p.rhs tokenize(trim(alt)); // 按空格切符号ε 单独识别 grammar.push_back(p); } } return grammar; }这段代码的关键点有三个trim保证左右部没有多余空白split按|拆候选式每个候选式独立成一条 Productiontokenize把右部切成符号序列遇到ε时存成单个标记而不是空 vector这样后续 FIRST 集计算时能明确知道这是一条空产生式。参数上lhs必须是非终结符rhs里每个元素要么是终结符要么是非终结符不能混入箭头或竖线残留。2.2 符号表与集合容器的选型符号分类完成后需要建立非终结符集合和终结符集合。常见做法是用std::setstd::string存符号保证去重和有序遍历FIRST 集和 FOLLOW 集用std::mapstd::string, std::setstd::string键是非终结符值是该非终结符对应的符号集合。选std::set而不是std::vector的原因是集合运算求并、求交、判断包含用 set 自带的insert、count、set_intersection更直接不用手写去重。// common_header.h 中集合类型的定义 using SymbolSet std::setstd::string; using FirstMap std::mapstd::string, SymbolSet; using FollowMap std::mapstd::string, SymbolSet; // 全局符号分类 SymbolSet nonTerminals; // 非终结符集合 SymbolSet terminals; // 终结符集合 std::string startSymbol; // 文法开始符号通常是第一条产生式的左部这里有个细节开始符号的确定。一般取第一条产生式的左部作为开始符号但有些文法会显式指定。如果你的课设要求支持显式指定可以在输入格式里加一行START: E预处理时单独解析。FOLLOW 集计算时开始符号的 FOLLOW 集里必须加入结束符通常用$或#表示否则分析表在输入串末尾会查不到动作。注意符号命名不要用ε作为普通终结符否则和空串标记冲突。如果文法里确实需要表示空串统一用ε并在 tokenize 阶段单独识别。3. FIRST 与 FOLLOW 集计算递归不动点怎么收敛3.1 FIRST 集的计算规则与迭代实现FIRST 集的定义是对任意符号串 αFIRST(α) 是 α 能推导出的所有可能的开头终结符集合如果 α 能推导出空串则 ε 也在 FIRST(α) 中。对单个非终结符 A如果存在产生式A - X1 X2 ... Xn则 FIRST(X1) 中所有非 ε 符号加入 FIRST(A)如果 X1 能推出 ε则继续看 X2以此类推如果所有 Xi 都能推出 ε则 ε 加入 FIRST(A)。直接递归容易死循环因为文法里可能有左递归或相互依赖。常见做法是迭代到不动点反复遍历所有产生式每次根据当前 FIRST 集更新直到某一轮没有任何集合发生变化为止。// get_first.cpp 中 FIRST 集迭代计算 void computeFirst(const std::vectorProduction grammar, FirstMap first) { bool changed true; while (changed) { changed false; for (const auto p : grammar) { const std::string A p.lhs; // 处理空产生式 A - ε if (p.rhs.size() 1 p.rhs[0] ε) { if (first[A].insert(ε).second) changed true; continue; } bool allNullable true; // 当前候选式是否所有符号都可空 for (const auto sym : p.rhs) { if (terminals.count(sym)) { // 终结符直接加入 FIRST(A) if (first[A].insert(sym).second) changed true; allNullable false; break; } else { // 非终结符把 FIRST(sym) 中非 ε 部分加入 FIRST(A) for (const auto s : first[sym]) { if (s ! ε) { if (first[A].insert(s).second) changed true; } } // 如果该非终结符不能推出 ε则停止 if (!first[sym].count(ε)) { allNullable false; break; } } } // 所有符号都可空则 ε 加入 FIRST(A) if (allNullable) { if (first[A].insert(ε).second) changed true; } } } }参数说明grammar是预处理后的产生式列表first是输出参数键为非终结符。changed标志控制迭代终止每轮只要有新符号加入就继续。allNullable用来判断当前候选式是否整体可空。这段代码的时间复杂度在最坏情况下是 O(迭代轮数 × 产生式数量 × 符号集大小)对于课设规模的文法几十条产生式完全够用。3.2 FOLLOW 集的依赖关系与计算顺序FOLLOW 集的定义是对非终结符 AFOLLOW(A) 是所有可能出现在 A 后面的终结符集合。计算规则有三条开始符号的 FOLLOW 集包含结束符$对产生式A - α B βFIRST(β) 中非 ε 符号加入 FOLLOW(B)如果 β 能推出 ε 或 β 为空则 FOLLOW(A) 加入 FOLLOW(B)。FOLLOW 集的计算依赖 FIRST 集所以必须在 FIRST 集收敛之后再算。同样用迭代到不动点的方式因为 FOLLOW 集之间也可能相互依赖。// get_follow.cpp 中 FOLLOW 集迭代计算 void computeFollow(const std::vectorProduction grammar, const FirstMap first, FollowMap follow, const std::string start) { follow[start].insert($); // 开始符号加入结束符 bool changed true; while (changed) { changed false; for (const auto p : grammar) { const std::string A p.lhs; for (size_t i 0; i p.rhs.size(); i) { const std::string B p.rhs[i]; if (!nonTerminals.count(B)) continue; // 只看非终结符 // 计算 β p.rhs[i1 ...] bool betaNullable true; for (size_t j i 1; j p.rhs.size(); j) { const std::string sym p.rhs[j]; if (terminals.count(sym)) { if (follow[B].insert(sym).second) changed true; betaNullable false; break; } else { for (const auto s : first.at(sym)) { if (s ! ε) { if (follow[B].insert(s).second) changed true; } } if (!first.at(sym).count(ε)) { betaNullable false; break; } } } // β 可空或为空把 FOLLOW(A) 加入 FOLLOW(B) if (betaNullable) { for (const auto s : follow[A]) { if (follow[B].insert(s).second) changed true; } } } } } }这里有个容易忽略的点follow[A]在迭代过程中可能还没算完但因为整体是迭代到不动点后续轮次会继续传播最终结果正确。参数start是文法开始符号必须和预处理阶段确定的一致。如果开始符号搞错FOLLOW 集里$会加错位置分析表在末尾符号处直接查不到动作。提示调试 FIRST 和 FOLLOW 集时先把结果打印出来和手工推导对一遍。常见错误是空产生式处理遗漏导致 ε 没进 FIRST 集进而 FOLLOW 集少算一批符号。4. 分析表构造与冲突检测什么时候文法不是 LL(1)4.1 SELECT 集与预测分析表生成LL(1) 分析表的核心是 SELECT 集。对产生式A - α如果 α 不能推出 ε则 SELECT(A - α) FIRST(α)如果 α 能推出 ε则 SELECT(A - α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。分析表的行是非终结符列是终结符加结束符$单元格填产生式编号或动作。构造时遍历所有产生式对每条产生式计算 SELECT 集然后把产生式填入对应单元格。如果某个单元格已经有产生式说明冲突——同一个非终结符在同一输入符号下有两个候选动作这个文法就不是 LL(1) 的。// generator.cpp 中分析表构造与冲突检测 struct TableEntry { int prodIndex; // 产生式编号-1 表示空 bool isError; // 是否冲突 }; std::mapstd::string, std::mapstd::string, TableEntry buildTable( const std::vectorProduction grammar, const FirstMap first, const FollowMap follow) { std::mapstd::string, std::mapstd::string, TableEntry table; for (size_t idx 0; idx grammar.size(); idx) { const auto p grammar[idx]; SymbolSet select; // 计算 FIRST(α) bool nullable true; for (const auto sym : p.rhs) { if (sym ε) continue; if (terminals.count(sym)) { select.insert(sym); nullable false; break; } else { for (const auto s : first.at(sym)) { if (s ! ε) select.insert(s); } if (!first.at(sym).count(ε)) { nullable false; break; } } } // α 可空加入 FOLLOW(A) if (nullable) { for (const auto s : follow.at(p.lhs)) { select.insert(s); } } // 填入分析表 for (const auto term : select) { auto cell table[p.lhs][term]; if (cell.prodIndex ! 0) { // 已有产生式冲突 cell.isError true; } else { cell.prodIndex static_castint(idx); } } } return table; }参数说明prodIndex从 0 开始编号0 表示空单元格实际使用时可以用 -1 表示空、-2 表示冲突。isError标记冲突单元格。冲突检测的逻辑是如果同一个单元格被两条产生式写入就标记为冲突。实际课设里冲突信息要打印出来告诉用户是哪两条产生式在哪个符号上冲突方便调整文法。4.2 冲突类型与文法调整方向LL(1) 冲突常见有两种FIRST/FIRST 冲突和 FIRST/FOLLOW 冲突。FIRST/FIRST 冲突是指同一个非终结符的两条产生式右部 FIRST 集有交集FIRST/FOLLOW 冲突是指一条产生式右部可空其 FIRST 集和该非终结符的 FOLLOW 集有交集。检测到冲突后调整方向通常是提取左公因子或消除左递归。提取左公因子如果A - αβ | αγ改成A - αAA - β | γ。消除左递归如果A - Aα | β改成A - βAA - αA | ε。这两步做完再重新跑一遍 FIRST/FOLLOW/分析表直到无冲突。注意消除左递归和提取左公因子会改变文法结构产生新的非终结符。新非终结符的命名要避免和原有符号冲突常见做法是加后缀或数字编号。5. 避坑与排查课设里最容易翻车的五个点5.1 空产生式写成空字符串导致 FIRST 集漏算现象FIRST 集里没有 εFOLLOW 集少算一批符号分析表在可空产生式处查不到动作。原因预处理时把A -或A - ε解析成了空 rhs后续判断p.rhs.size() 1 p.rhs[0] ε不成立。解决在 tokenize 阶段统一把空右部或ε转成单个ε标记保证每条产生式的 rhs 至少有一个元素。5.2 开始符号的 FOLLOW 集忘记加结束符现象输入串分析到最后一个符号时分析表查不到动作报错退出。原因FOLLOW(startSymbol) 里没有$分析表最后一列是空的。解决在 computeFollow 开头显式执行follow[start].insert($)并确保 start 和预处理阶段确定的开始符号一致。5.3 迭代计算不收敛或提前退出现象FIRST 或 FOLLOW 集结果不全或者程序卡死。原因changed标志更新逻辑写错比如只在插入成功时更新但漏了某些分支或者迭代终止条件写成固定轮数而不是集合变化。解决每轮遍历所有产生式任何集合插入成功都置changed true循环条件用while (changed)不要用固定轮数。5.4 分析表冲突检测漏报现象文法明明有冲突程序却认为无冲突生成的分析表在运行时选错产生式。原因冲突检测只在单元格已有产生式时标记但初始值判断写错比如用prodIndex ! -1判断已有值而初始值恰好是 -1。解决明确初始值比如 0 表示空冲突时单独标记isError不要依赖 prodIndex 的数值判断。5.5 输入串符号切分与文法符号不一致现象分析器读入输入串后符号匹配失败明明文法里有这个终结符却查不到。原因输入串按字符切分而文法里终结符可能是多字符如id、num导致id被切成i和d。解决输入串也按空格或逗号分隔的 token 切分保证和文法里的终结符粒度一致。如果输入串是连续字符需要先做词法分析切成 token。6. 从能跑到好用分析过程追踪与文法调试技巧把分析表跑通只是第一步真正做课设时老师往往会要求你展示分析过程——每一步栈里有什么、当前输入符号是什么、选了哪条产生式。这份实现里 analyze.cpp 负责驱动分析常见做法是用一个栈存符号初始压入$和开始符号然后循环读输入符号查分析表决定展开或匹配。// analyze.cpp 中带追踪输出的分析驱动 void analyze(const std::string input, const std::mapstd::string, std::mapstd::string, TableEntry table, const std::vectorProduction grammar) { std::vectorstd::string stack; stack.push_back($); stack.push_back(startSymbol); std::vectorstd::string tokens tokenizeInput(input); // 按 token 切分 tokens.push_back($); size_t pos 0; int step 0; while (!stack.empty()) { std::string top stack.back(); std::string cur tokens[pos]; printf(Step %d: stack top %s, input %s\n, step, top.c_str(), cur.c_str()); if (top $ cur $) { printf(Accept!\n); return; } if (terminals.count(top) || top $) { if (top cur) { stack.pop_back(); pos; } else { printf(Error: expected %s, got %s\n, top.c_str(), cur.c_str()); return; } } else { auto it table.find(top); if (it table.end() || !it-second.count(cur)) { printf(Error: no action for %s on %s\n, top.c_str(), cur.c_str()); return; } const TableEntry entry it-second.at(cur); if (entry.isError) { printf(Error: conflict at %s on %s\n, top.c_str(), cur.c_str()); return; } const Production p grammar[entry.prodIndex]; printf( apply: %s - , p.lhs.c_str()); for (const auto s : p.rhs) printf(%s , s.c_str()); printf(\n); stack.pop_back(); // 逆序压栈保证左部符号先处理 for (auto rit p.rhs.rbegin(); rit ! p.rhs.rend(); rit) { if (*rit ! ε) stack.push_back(*rit); } } } }这段代码的关键在于栈顶是终结符时直接匹配输入栈顶是非终结符时查分析表找到产生式后弹栈并把右部逆序压入。逆序压栈是为了让最左符号在栈顶下一步优先处理。追踪输出把每一步的栈顶和当前输入符号打出来方便和手工推导对照。参数上tokens末尾必须加$和 FOLLOW 集里的结束符一致。调试文法时我习惯先把 FIRST 和 FOLLOW 集打印出来和手工推导逐行对再打印分析表看每个非终结符行是否完整最后跑几个典型输入串包括正确串和错误串确认错误处理能给出有意义的位置信息。如果分析表某一行大量为空通常是 FOLLOW 集算漏了如果某一列冲突回去检查是否有左递归或左公因子没处理。从那以后我每次拿到新的文法都强制先跑一遍 FIRST/FOLLOW 打印再手工验证两三个非终结符确认集合没问题再往下走分析表。这个习惯帮我省掉了大量“分析表莫名其妙查不到动作”的排查时间。希望这份拆解能帮你把课设顺利跑通。本文还有配套的精品资源点击获取 C++实现LL(1)文法分析器：FIRST/FOLLOW集计算与预测分析表生成
简介这份资源是面向计算机专业学生与编译原理学习者的C课程设计项目围绕根据文法自动生成LL(1)分析器展开帮助理解自左向右扫描、仅查看一个输入符号的预测分析流程。包内共11个文件以8个cpp源文件为核心配合1个头文件与1个说明文档另有许可证文件压缩包约12KB结构紧凑便于直接编译运行与二次修改。内容覆盖文法解析、FIRST集与FOLLOW集构造、冲突检测、分析表生成、分析器实现及错误处理等关键环节并借助STL容器与面向对象方式组织文法规则和分析表。已有406人学习下载适合作为课程设计参考或编译器前端入门练手读者可据此掌握从文法输入到自动生成分析表的完整思路并借鉴其中的数据结构设计与排错方法。1. 从一份 C 课设说起LL(1) 分析器到底能帮你省下多少手工推导如果你正在做编译原理课程设计大概率绕不开一个经典题目给定一组文法产生式判断它是不是 LL(1) 文法然后自动生成分析表并跑通一个输入串。手工推导 FIRST 集、FOLLOW 集、SELECT 集再画预测分析表文法稍微复杂一点就容易出错改一个产生式就得从头再来一遍。这份基于 C 实现的 LL(1) 文法分析器解决的正是这个重复劳动问题——你把文法规则写成文本喂进去它自动完成预处理、FIRST/FOLLOW 集计算、冲突检测、分析表生成和输入串分析全流程。它适合两类人一类是正在赶编译原理课设、需要一份能跑通且结构清晰的参考实现另一类是想搞明白 LL(1) 分析器内部数据流怎么组织的 C 学习者。整个项目按功能拆成了 preprocess、get_first、get_follow、generator、analyze 等独立源文件不是一坨代码堆在 main 里读起来能看清每一步在干什么。下面我从文法输入格式开始把这份资源怎么用、参数怎么设、容易在哪翻车按实操顺序拆一遍。2. 文法预处理与数据结构产生式怎么存、符号怎么分类2.1 文法文本的输入格式与解析逻辑这份实现里文法通常以产生式文本形式输入每条规则形如E - T E多个候选式用|分隔空产生式用ε或特定标记表示。preprocess.cpp 负责把原始文本切成一个个符号区分终结符和非终结符。常见做法是大写字母开头的标识符视为非终结符其余小写字母、运算符、数字、括号等视为终结符ε单独处理为空串标记。解析时最容易翻车的地方是分隔符处理。比如E-T|E和E - T | E必须都能正确切分否则后续 FIRST 集计算会拿到带空格的符号名导致集合匹配失败。我一般会在预处理阶段统一做一次 trim 和符号规范化把箭头统一成-把连续空白压成一个空格再按|拆分候选式。// preprocess.cpp 中产生式解析的核心逻辑示意 struct Production { std::string lhs; // 左部非终结符 std::vectorstd::string rhs; // 右部符号序列空串用 ε 表示 }; std::vectorProduction parseGrammar(const std::string raw) { std::vectorProduction grammar; std::istringstream iss(raw); std::string line; while (std::getline(iss, line)) { // 去掉首尾空白和回车 trim(line); if (line.empty()) continue; // 按 - 切分左右部 auto pos line.find(-); std::string lhs trim(line.substr(0, pos)); std::string rhsPart trim(line.substr(pos 2)); // 按 | 拆分候选式 std::vectorstd::string alts split(rhsPart, |); for (auto alt : alts) { Production p; p.lhs lhs; p.rhs tokenize(trim(alt)); // 按空格切符号ε 单独识别 grammar.push_back(p); } } return grammar; }这段代码的关键点有三个trim保证左右部没有多余空白split按|拆候选式每个候选式独立成一条 Productiontokenize把右部切成符号序列遇到ε时存成单个标记而不是空 vector这样后续 FIRST 集计算时能明确知道这是一条空产生式。参数上lhs必须是非终结符rhs里每个元素要么是终结符要么是非终结符不能混入箭头或竖线残留。2.2 符号表与集合容器的选型符号分类完成后需要建立非终结符集合和终结符集合。常见做法是用std::setstd::string存符号保证去重和有序遍历FIRST 集和 FOLLOW 集用std::mapstd::string, std::setstd::string键是非终结符值是该非终结符对应的符号集合。选std::set而不是std::vector的原因是集合运算求并、求交、判断包含用 set 自带的insert、count、set_intersection更直接不用手写去重。// common_header.h 中集合类型的定义 using SymbolSet std::setstd::string; using FirstMap std::mapstd::string, SymbolSet; using FollowMap std::mapstd::string, SymbolSet; // 全局符号分类 SymbolSet nonTerminals; // 非终结符集合 SymbolSet terminals; // 终结符集合 std::string startSymbol; // 文法开始符号通常是第一条产生式的左部这里有个细节开始符号的确定。一般取第一条产生式的左部作为开始符号但有些文法会显式指定。如果你的课设要求支持显式指定可以在输入格式里加一行START: E预处理时单独解析。FOLLOW 集计算时开始符号的 FOLLOW 集里必须加入结束符通常用$或#表示否则分析表在输入串末尾会查不到动作。注意符号命名不要用ε作为普通终结符否则和空串标记冲突。如果文法里确实需要表示空串统一用ε并在 tokenize 阶段单独识别。3. FIRST 与 FOLLOW 集计算递归不动点怎么收敛3.1 FIRST 集的计算规则与迭代实现FIRST 集的定义是对任意符号串 αFIRST(α) 是 α 能推导出的所有可能的开头终结符集合如果 α 能推导出空串则 ε 也在 FIRST(α) 中。对单个非终结符 A如果存在产生式A - X1 X2 ... Xn则 FIRST(X1) 中所有非 ε 符号加入 FIRST(A)如果 X1 能推出 ε则继续看 X2以此类推如果所有 Xi 都能推出 ε则 ε 加入 FIRST(A)。直接递归容易死循环因为文法里可能有左递归或相互依赖。常见做法是迭代到不动点反复遍历所有产生式每次根据当前 FIRST 集更新直到某一轮没有任何集合发生变化为止。// get_first.cpp 中 FIRST 集迭代计算 void computeFirst(const std::vectorProduction grammar, FirstMap first) { bool changed true; while (changed) { changed false; for (const auto p : grammar) { const std::string A p.lhs; // 处理空产生式 A - ε if (p.rhs.size() 1 p.rhs[0] ε) { if (first[A].insert(ε).second) changed true; continue; } bool allNullable true; // 当前候选式是否所有符号都可空 for (const auto sym : p.rhs) { if (terminals.count(sym)) { // 终结符直接加入 FIRST(A) if (first[A].insert(sym).second) changed true; allNullable false; break; } else { // 非终结符把 FIRST(sym) 中非 ε 部分加入 FIRST(A) for (const auto s : first[sym]) { if (s ! ε) { if (first[A].insert(s).second) changed true; } } // 如果该非终结符不能推出 ε则停止 if (!first[sym].count(ε)) { allNullable false; break; } } } // 所有符号都可空则 ε 加入 FIRST(A) if (allNullable) { if (first[A].insert(ε).second) changed true; } } } }参数说明grammar是预处理后的产生式列表first是输出参数键为非终结符。changed标志控制迭代终止每轮只要有新符号加入就继续。allNullable用来判断当前候选式是否整体可空。这段代码的时间复杂度在最坏情况下是 O(迭代轮数 × 产生式数量 × 符号集大小)对于课设规模的文法几十条产生式完全够用。3.2 FOLLOW 集的依赖关系与计算顺序FOLLOW 集的定义是对非终结符 AFOLLOW(A) 是所有可能出现在 A 后面的终结符集合。计算规则有三条开始符号的 FOLLOW 集包含结束符$对产生式A - α B βFIRST(β) 中非 ε 符号加入 FOLLOW(B)如果 β 能推出 ε 或 β 为空则 FOLLOW(A) 加入 FOLLOW(B)。FOLLOW 集的计算依赖 FIRST 集所以必须在 FIRST 集收敛之后再算。同样用迭代到不动点的方式因为 FOLLOW 集之间也可能相互依赖。// get_follow.cpp 中 FOLLOW 集迭代计算 void computeFollow(const std::vectorProduction grammar, const FirstMap first, FollowMap follow, const std::string start) { follow[start].insert($); // 开始符号加入结束符 bool changed true; while (changed) { changed false; for (const auto p : grammar) { const std::string A p.lhs; for (size_t i 0; i p.rhs.size(); i) { const std::string B p.rhs[i]; if (!nonTerminals.count(B)) continue; // 只看非终结符 // 计算 β p.rhs[i1 ...] bool betaNullable true; for (size_t j i 1; j p.rhs.size(); j) { const std::string sym p.rhs[j]; if (terminals.count(sym)) { if (follow[B].insert(sym).second) changed true; betaNullable false; break; } else { for (const auto s : first.at(sym)) { if (s ! ε) { if (follow[B].insert(s).second) changed true; } } if (!first.at(sym).count(ε)) { betaNullable false; break; } } } // β 可空或为空把 FOLLOW(A) 加入 FOLLOW(B) if (betaNullable) { for (const auto s : follow[A]) { if (follow[B].insert(s).second) changed true; } } } } } }这里有个容易忽略的点follow[A]在迭代过程中可能还没算完但因为整体是迭代到不动点后续轮次会继续传播最终结果正确。参数start是文法开始符号必须和预处理阶段确定的一致。如果开始符号搞错FOLLOW 集里$会加错位置分析表在末尾符号处直接查不到动作。提示调试 FIRST 和 FOLLOW 集时先把结果打印出来和手工推导对一遍。常见错误是空产生式处理遗漏导致 ε 没进 FIRST 集进而 FOLLOW 集少算一批符号。4. 分析表构造与冲突检测什么时候文法不是 LL(1)4.1 SELECT 集与预测分析表生成LL(1) 分析表的核心是 SELECT 集。对产生式A - α如果 α 不能推出 ε则 SELECT(A - α) FIRST(α)如果 α 能推出 ε则 SELECT(A - α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。分析表的行是非终结符列是终结符加结束符$单元格填产生式编号或动作。构造时遍历所有产生式对每条产生式计算 SELECT 集然后把产生式填入对应单元格。如果某个单元格已经有产生式说明冲突——同一个非终结符在同一输入符号下有两个候选动作这个文法就不是 LL(1) 的。// generator.cpp 中分析表构造与冲突检测 struct TableEntry { int prodIndex; // 产生式编号-1 表示空 bool isError; // 是否冲突 }; std::mapstd::string, std::mapstd::string, TableEntry buildTable( const std::vectorProduction grammar, const FirstMap first, const FollowMap follow) { std::mapstd::string, std::mapstd::string, TableEntry table; for (size_t idx 0; idx grammar.size(); idx) { const auto p grammar[idx]; SymbolSet select; // 计算 FIRST(α) bool nullable true; for (const auto sym : p.rhs) { if (sym ε) continue; if (terminals.count(sym)) { select.insert(sym); nullable false; break; } else { for (const auto s : first.at(sym)) { if (s ! ε) select.insert(s); } if (!first.at(sym).count(ε)) { nullable false; break; } } } // α 可空加入 FOLLOW(A) if (nullable) { for (const auto s : follow.at(p.lhs)) { select.insert(s); } } // 填入分析表 for (const auto term : select) { auto cell table[p.lhs][term]; if (cell.prodIndex ! 0) { // 已有产生式冲突 cell.isError true; } else { cell.prodIndex static_castint(idx); } } } return table; }参数说明prodIndex从 0 开始编号0 表示空单元格实际使用时可以用 -1 表示空、-2 表示冲突。isError标记冲突单元格。冲突检测的逻辑是如果同一个单元格被两条产生式写入就标记为冲突。实际课设里冲突信息要打印出来告诉用户是哪两条产生式在哪个符号上冲突方便调整文法。4.2 冲突类型与文法调整方向LL(1) 冲突常见有两种FIRST/FIRST 冲突和 FIRST/FOLLOW 冲突。FIRST/FIRST 冲突是指同一个非终结符的两条产生式右部 FIRST 集有交集FIRST/FOLLOW 冲突是指一条产生式右部可空其 FIRST 集和该非终结符的 FOLLOW 集有交集。检测到冲突后调整方向通常是提取左公因子或消除左递归。提取左公因子如果A - αβ | αγ改成A - αAA - β | γ。消除左递归如果A - Aα | β改成A - βAA - αA | ε。这两步做完再重新跑一遍 FIRST/FOLLOW/分析表直到无冲突。注意消除左递归和提取左公因子会改变文法结构产生新的非终结符。新非终结符的命名要避免和原有符号冲突常见做法是加后缀或数字编号。5. 避坑与排查课设里最容易翻车的五个点5.1 空产生式写成空字符串导致 FIRST 集漏算现象FIRST 集里没有 εFOLLOW 集少算一批符号分析表在可空产生式处查不到动作。原因预处理时把A -或A - ε解析成了空 rhs后续判断p.rhs.size() 1 p.rhs[0] ε不成立。解决在 tokenize 阶段统一把空右部或ε转成单个ε标记保证每条产生式的 rhs 至少有一个元素。5.2 开始符号的 FOLLOW 集忘记加结束符现象输入串分析到最后一个符号时分析表查不到动作报错退出。原因FOLLOW(startSymbol) 里没有$分析表最后一列是空的。解决在 computeFollow 开头显式执行follow[start].insert($)并确保 start 和预处理阶段确定的开始符号一致。5.3 迭代计算不收敛或提前退出现象FIRST 或 FOLLOW 集结果不全或者程序卡死。原因changed标志更新逻辑写错比如只在插入成功时更新但漏了某些分支或者迭代终止条件写成固定轮数而不是集合变化。解决每轮遍历所有产生式任何集合插入成功都置changed true循环条件用while (changed)不要用固定轮数。5.4 分析表冲突检测漏报现象文法明明有冲突程序却认为无冲突生成的分析表在运行时选错产生式。原因冲突检测只在单元格已有产生式时标记但初始值判断写错比如用prodIndex ! -1判断已有值而初始值恰好是 -1。解决明确初始值比如 0 表示空冲突时单独标记isError不要依赖 prodIndex 的数值判断。5.5 输入串符号切分与文法符号不一致现象分析器读入输入串后符号匹配失败明明文法里有这个终结符却查不到。原因输入串按字符切分而文法里终结符可能是多字符如id、num导致id被切成i和d。解决输入串也按空格或逗号分隔的 token 切分保证和文法里的终结符粒度一致。如果输入串是连续字符需要先做词法分析切成 token。6. 从能跑到好用分析过程追踪与文法调试技巧把分析表跑通只是第一步真正做课设时老师往往会要求你展示分析过程——每一步栈里有什么、当前输入符号是什么、选了哪条产生式。这份实现里 analyze.cpp 负责驱动分析常见做法是用一个栈存符号初始压入$和开始符号然后循环读输入符号查分析表决定展开或匹配。// analyze.cpp 中带追踪输出的分析驱动 void analyze(const std::string input, const std::mapstd::string, std::mapstd::string, TableEntry table, const std::vectorProduction grammar) { std::vectorstd::string stack; stack.push_back($); stack.push_back(startSymbol); std::vectorstd::string tokens tokenizeInput(input); // 按 token 切分 tokens.push_back($); size_t pos 0; int step 0; while (!stack.empty()) { std::string top stack.back(); std::string cur tokens[pos]; printf(Step %d: stack top %s, input %s\n, step, top.c_str(), cur.c_str()); if (top $ cur $) { printf(Accept!\n); return; } if (terminals.count(top) || top $) { if (top cur) { stack.pop_back(); pos; } else { printf(Error: expected %s, got %s\n, top.c_str(), cur.c_str()); return; } } else { auto it table.find(top); if (it table.end() || !it-second.count(cur)) { printf(Error: no action for %s on %s\n, top.c_str(), cur.c_str()); return; } const TableEntry entry it-second.at(cur); if (entry.isError) { printf(Error: conflict at %s on %s\n, top.c_str(), cur.c_str()); return; } const Production p grammar[entry.prodIndex]; printf( apply: %s - , p.lhs.c_str()); for (const auto s : p.rhs) printf(%s , s.c_str()); printf(\n); stack.pop_back(); // 逆序压栈保证左部符号先处理 for (auto rit p.rhs.rbegin(); rit ! p.rhs.rend(); rit) { if (*rit ! ε) stack.push_back(*rit); } } } }这段代码的关键在于栈顶是终结符时直接匹配输入栈顶是非终结符时查分析表找到产生式后弹栈并把右部逆序压入。逆序压栈是为了让最左符号在栈顶下一步优先处理。追踪输出把每一步的栈顶和当前输入符号打出来方便和手工推导对照。参数上tokens末尾必须加$和 FOLLOW 集里的结束符一致。调试文法时我习惯先把 FIRST 和 FOLLOW 集打印出来和手工推导逐行对再打印分析表看每个非终结符行是否完整最后跑几个典型输入串包括正确串和错误串确认错误处理能给出有意义的位置信息。如果分析表某一行大量为空通常是 FOLLOW 集算漏了如果某一列冲突回去检查是否有左递归或左公因子没处理。从那以后我每次拿到新的文法都强制先跑一遍 FIRST/FOLLOW 打印再手工验证两三个非终结符确认集合没问题再往下走分析表。这个习惯帮我省掉了大量“分析表莫名其妙查不到动作”的排查时间。希望这份拆解能帮你把课设顺利跑通。本文还有配套的精品资源点击获取