简介这份资源面向计算机专业学生与编译原理学习者提供一套基于C实现的LL(1)文法分析器课程设计代码解决从文法规则自动生成分析表并完成语法分析的问题。压缩包共11个文件以8个cpp源文件为核心配合1个头文件与说明文档整体约12KB涵盖文法预处理、FIRST集与FOLLOW集计算、分析表生成及主流程分析等模块结构清晰便于按功能阅读。已有406人学习下载适合作为课程设计参考或编译原理实验练手。读者可从中掌握文法解析、集合递归计算、冲突检测与错误处理等关键环节理解如何用STL容器与面向对象方式封装文法规则和分析表并借助异常机制优雅处理非法输入从而把LL(1)分析理论落到可运行的C工程实践中。1. 从文法到分析表为什么手写 LL(1) 分析器比调库更值得做编译原理课上讲 LL(1) 的时候很多人第一反应是“这不就是算 FIRST 集、FOLLOW 集、画个预测分析表吗”然后考试一过就全忘了。真到工作里遇到需要解析自定义配置语言、DSL 脚本、协议报文格式的时候才发现手头没有趁手的工具——用正则硬怼复杂嵌套结构迟早翻车上 ANTLR 又觉得为了一个小语法引入整套代码生成框架太重。这时候“基于 C 实现根据文法自动生成 LL(1) 文法分析器”这个方向就变得很实在你给一段产生式描述程序自动算出 FIRST、FOLLOW、SELECT 集判断是不是 LL(1) 文法是就生成预测分析表再拿这张表去驱动一个下推自动机完成句子识别。整个过程不依赖外部工具一个可执行文件就能跑嵌到自己的项目里也方便。适合有 C 基础、想真正搞懂自顶向下语法分析落地细节的人也适合需要给自家小语言快速搭解析器的一线开发者。下面我按自己实现过的一版思路把选型、数据结构、核心算法和踩过的坑讲清楚。2. 文法表示与数据结构选型产生式怎么存才不别扭2.1 用结构体还是用类来建模文法符号文法里有两类符号终结符和非终结符。最省事的做法是统一用字符串表示再用一个std::setstd::string存非终结符集合终结符集合从产生式右部里减掉非终结符得到。但字符串比较在分析表构建阶段会被调用得非常频繁如果文法规模上百条产生式性能会有点难受。我一般会做一层映射先把所有符号收集起来分配一个整型 id非终结符 id 从 0 开始终结符 id 从某个偏移开始最后加一个特殊的结束符$。这样后续 FIRST、FOLLOW 集合都可以用std::bitset或者std::vectorbool来表示求并集、判断包含都是位运算快很多。产生式本身用一个结构体存struct Production { int lhs; // 左部非终结符 id std::vectorint rhs; // 右部符号 id 序列 int index; // 产生式编号用于分析表填表 };用std::vectorProduction保存所有产生式顺序就是它们在文法里出现的顺序。这个顺序很重要因为 SELECT 集冲突时LL(1) 要求同一非终结符的任意两条产生式 SELECT 集不相交一旦相交就说明不是 LL(1) 文法需要报错并指出是哪两条冲突。2.2 终结符、非终结符和空串的表示约定空产生式用右部为空 vector 表示不要用特殊字符串ε混在符号表里否则后面算 FIRST 集时还要额外判断容易漏。约定rhs.empty()即代表该产生式推导出空串。结束符$单独分配一个 id不参与非终结符集合只在 FOLLOW 集初始化和分析表驱动时使用。符号表可以用两个std::unordered_map做双向映射std::unordered_mapstd::string, int sym2id; std::vectorstd::string id2sym;读文法的时候每遇到一个新符号就查表没有就分配新 id 并压入id2sym。这样打印分析表、报错信息时都能还原成人类可读的名字。2.3 从文本文法到内存结构的解析步骤文法文本格式我习惯用每行一条产生式左部和右部用-分隔右部符号用空格分开例如E - T E E - T E | ε T - F T同一左部有多条产生式时用|分隔。解析时按行读先按-切出左部再按|切出多个右部候选每个候选再按空格切分成符号序列。遇到ε就生成空右部。这里有个细节左部符号第一次出现时要登记为非终结符右部里出现的符号如果不在已知非终结符集合里先当作候选终结符等所有产生式读完后再统一确定——因为可能存在右部先出现、左部后定义的情况。// 伪代码示意解析流程 for each line: split by - into lhs_str, rhs_str lhs_id get_or_create_nonterminal(lhs_str) for each alternative in split(rhs_str, |): Production p; p.lhs lhs_id; for each token in split(alternative, ): if token ε: continue; p.rhs.push_back(get_or_create_symbol(token)); productions.push_back(p);参数说明get_or_create_nonterminal只查非终结符表get_or_create_symbol先查非终结符表再查终结符表都没有就暂存到待定集合。全部读完后待定集合里的符号就是终结符。3. FIRST、FOLLOW、SELECT 三集合的迭代算法与收敛判断3.1 FIRST 集的不动点迭代怎么写才不漏FIRST 集的定义是从某个符号出发能推导出的所有可能的开头终结符集合如果该符号能推导出空串则空串也属于 FIRST 集。对非终结符 X规则是对每条 X - Y1 Y2 ... Yk先把 FIRST(Y1) 中除空串外的元素加入 FIRST(X)如果 Y1 能推出空串继续看 Y2以此类推如果所有 Yi 都能推出空串则空串加入 FIRST(X)。实现上用迭代到不动点的方式最稳bool changed true; while (changed) { changed false; for (auto p : productions) { bool all_nullable true; for (int sym : p.rhs) { if (isTerminal(sym)) { if (first[p.lhs].insert(sym)) changed true; all_nullable false; break; } else { for (int t : first[sym]) { if (t ! EMPTY first[p.lhs].insert(t)) changed true; } if (!first[sym].count(EMPTY)) { all_nullable false; break; } } } if (all_nullable) { if (first[p.lhs].insert(EMPTY)) changed true; } } }这里first用std::vectorstd::setint或位集都行。关键点是每轮遍历所有产生式只要有新元素加入就继续下一轮直到某一轮没有任何变化。收敛性由集合单调递增且有上界保证最坏情况轮数是符号数乘以集合大小实际文法规模下几轮就稳定。3.2 FOLLOW 集的初始化与传播规则FOLLOW 集只对非终结符有意义。初始化时把开始符号的 FOLLOW 集加入结束符$。传播规则有三条对于产生式 A - αBβ把 FIRST(β) 中除空串外的元素加入 FOLLOW(B)如果 β 能推出空串把 FOLLOW(A) 加入 FOLLOW(B)如果 B 是产生式最后一个符号同样把 FOLLOW(A) 加入 FOLLOW(B)。实现时同样用不动点迭代外层循环所有产生式内层从右往左扫描右部维护一个“当前后缀的 FIRST 集”和“后缀是否可空”两个变量这样一趟就能处理完一条产生式的所有非终结符。bool changed true; while (changed) { changed false; for (auto p : productions) { std::setint suffix_first; bool suffix_nullable true; for (int i p.rhs.size() - 1; i 0; --i) { int sym p.rhs[i]; if (!isTerminal(sym)) { for (int t : suffix_first) { if (follow[sym].insert(t)) changed true; } if (suffix_nullable) { for (int t : follow[p.lhs]) { if (follow[sym].insert(t)) changed true; } } } // 更新 suffix_first 和 suffix_nullable if (isTerminal(sym)) { suffix_first.clear(); suffix_first.insert(sym); suffix_nullable false; } else { std::setint new_first; for (int t : first[sym]) if (t ! EMPTY) new_first.insert(t); suffix_first new_first; suffix_nullable first[sym].count(EMPTY) 0; } } } }参数说明suffix_first表示当前扫描位置右侧所有符号的 FIRST 集去掉空串suffix_nullable表示右侧是否可全部推出空串。从右往左扫描是为了复用后缀信息避免对每个非终结符都重新算一遍右侧 FIRST。3.3 SELECT 集与 LL(1) 判定条件SELECT 集是给产生式用的不是给符号用的。对产生式 A - α如果 α 不能推出空串SELECT 就是 FIRST(α)如果 α 能推出空串SELECT 是 FIRST(α) 去掉空串再并上 FOLLOW(A)。判定 LL(1) 的条件是对同一个非终结符的所有产生式它们的 SELECT 集两两不相交。实现时按左部把产生式分组组内两两求交集非空就报冲突。for (auto group : productions_by_lhs) { for (int i 0; i group.size(); i) { for (int j i 1; j group.size(); j) { std::setint inter; std::set_intersection(select[group[i]].begin(), select[group[i]].end(), select[group[j]].begin(), select[group[j]].end(), std::inserter(inter, inter.begin())); if (!inter.empty()) { // 报错产生式 i 和 j 冲突文法不是 LL(1) } } } }冲突时最好把冲突的终结符也打印出来方便定位是哪个 token 导致二义性。常见原因是左递归没消除干净或者公共左因子没提取。4. 预测分析表构建与下推自动机驱动4.1 分析表的数据结构与填表逻辑分析表是一个二维表行是非终结符列是终结符含$单元格存产生式编号空表示出错。用std::vectorstd::vectorint存行索引是非终结符 id列索引是终结符 id 映射到 0..n-1。填表时遍历每条产生式对 SELECT 集中每个终结符 t把table[lhs][t]设为该产生式编号。如果发现单元格已经被填过且编号不同说明有冲突直接报错。std::vectorstd::vectorint table(num_nonterminals, std::vectorint(num_terminals, -1)); for (auto p : productions) { for (int t : select[p.index]) { int col terminal_to_col[t]; if (table[p.lhs][col] ! -1) { // 冲突table[p.lhs][col] 和 p.index 都想填 } table[p.lhs][col] p.index; } }参数说明-1表示空单元格terminal_to_col把终结符 id 映射到列下标$也要占一列。4.2 用栈驱动分析过程的完整代码下推自动机的驱动逻辑很固定栈里初始放$和开始符号输入串末尾补$。每步看栈顶和当前输入符号如果栈顶是终结符匹配就弹出并前进不匹配就报错如果栈顶是非终结符查分析表有产生式就把栈顶弹出并把右部逆序压栈空产生式就只弹出如果栈顶是$且输入也是$接受。bool parse(const std::vectorint input) { std::vectorint stack; stack.push_back(DOLLAR); stack.push_back(start_symbol); size_t pos 0; while (!stack.empty()) { int top stack.back(); int cur (pos input.size()) ? input[pos] : DOLLAR; if (isTerminal(top) || top DOLLAR) { if (top cur) { stack.pop_back(); pos; } else { return false; // 终结符不匹配 } } else { int col terminal_to_col[cur]; int prod_idx table[top][col]; if (prod_idx -1) return false; // 查表出错 stack.pop_back(); const auto rhs productions[prod_idx].rhs; for (auto it rhs.rbegin(); it ! rhs.rend(); it) { stack.push_back(*it); } } } return pos input.size(); }参数说明input是词法分析后的终结符 id 序列不含末尾$函数内部用DOLLAR补齐。stack用std::vector模拟back()是栈顶。压栈时逆序是为了让右部第一个符号先被处理。4.3 错误恢复的两种实用策略实际用的时候不可能一报错就退出至少要有两种恢复手段。第一种是恐慌模式发现查表为空时不断弹出栈顶直到遇到能跟当前输入符号匹配的终结符或者栈顶是$为止然后继续。第二种是短语级恢复在分析表里预埋一些同步记号比如把 FOLLOW 集里的符号作为该非终结符的同步点遇到错误时跳到同步记号继续。我一般先实现恐慌模式够用且简单等真有需求再加同步记号。// 恐慌模式恢复示意 while (!stack.empty() !can_sync(stack.back(), cur)) { stack.pop_back(); } if (stack.empty()) return false;can_sync判断栈顶符号是否能与当前输入符号配合继续分析具体逻辑可以简单点栈顶是终结符且等于 cur或者栈顶是非终结符且table[top][cur] ! -1。5. 避坑与排查那些让分析器跑不起来的小问题5.1 左递归没消除导致 FIRST 集算不出来现象FIRST 集迭代很多轮都不收敛或者分析表大量冲突。原因文法里有直接左递归比如E - E T | T算 FIRST(E) 时会不断把 FIRST(E) 自己加进去虽然集合本身不会无限增长但 SELECT 集冲突严重LL(1) 判定必然失败。解决先做左递归消除把E - E T | T改写成E - T E、E - T E | ε。间接左递归要先代入再消除步骤稍多但套路固定。5.2 空产生式处理不当让 FOLLOW 集偏小现象某些该被接受的句子在分析表里查不到产生式。原因算 FIRST 集时忘了把空串传播下去导致 FOLLOW 集没拿到应有的元素。解决检查 FIRST 集迭代里all_nullable的判断确保只有右部所有符号都可空时才把空串加入左部 FIRST 集。另外 FOLLOW 传播时suffix_nullable的更新要在处理完当前符号之后再做顺序反了会漏。5.3 终结符和非终结符 id 空间混用现象分析表填表时行列对不上或者运行时栈里符号判断错乱。原因终结符和非终结符用了同一套 id 空间isTerminal判断依赖 id 范围一旦分配顺序变了就出错。解决严格分开两段 id 空间非终结符从 0 开始终结符从num_nonterminals开始isTerminal就是id num_nonterminals。结束符单独给一个最大 id不参与列映射时特殊处理。5.4 输入串末尾忘记补结束符现象分析到最后一个符号时栈里还剩$没匹配或者越界访问。原因驱动循环里取当前输入符号时没处理pos input.size()的情况。解决取符号时用pos input.size() ? input[pos] : DOLLAR并且接受条件写成pos input.size() stack.empty()。栈里初始的$会在最后一步跟输入的$匹配掉。5.5 分析表冲突信息不够定位不到具体产生式现象报“不是 LL(1) 文法”但不知道哪两条产生式冲突。原因冲突检测只报了布尔结果没记录冲突的产生式编号和终结符。解决在填表冲突分支里把table[p.lhs][col]和p.index都打印出来同时打印对应的终结符名字最好再把两条产生式的文本也输出这样一眼就能看出是公共左因子还是左递归残留。6. 进阶技巧把分析器做成可复用的库真要把这个东西用起来别只写成一个main.cpp里跑完就完。我一般会拆成三个模块文法解析模块负责读文本建结构集合计算模块负责 FIRST/FOLLOW/SELECT 和分析表驱动模块负责跑输入串。对外暴露一个LL1Parser类构造函数接收文法文本提供bool isLL1()和bool parse(const std::vectorstd::string tokens)两个接口。这样嵌到别的项目里只需要包含头文件不用改源码。验证方法上除了拿课本上的算术表达式文法跑我还会构造几个边界用例空串输入、只有单个终结符的输入、含嵌套括号的输入、故意写一个非 LL(1) 文法看报错信息是否清晰。另外可以写一个简单的词法分析器把输入字符串切成 token 序列这样整个链路从字符串到语法树就通了。一个具体技巧分析表可以用std::mapstd::pairint,int, int存稀疏表文法大的时候比二维数组省内存查表用find判断是否存在。如果追求速度再换回二维数组两者接口一致切换成本很低。class LL1Parser { public: explicit LL1Parser(const std::string grammar_text); bool isLL1() const; bool parse(const std::vectorstd::string tokens); private: // 内部数据结构 };参数说明grammar_text是完整文法文本tokens是词法分析后的终结符字符串序列。isLL1在构造时就算好parse每次调用重置栈和输入位置可重入。我自己踩过最深的坑是早期把 FIRST 集和 FOLLOW 集算完就以为万事大吉结果分析表填的时候发现同一单元格被填了两次查了半天才发现是文法里有个隐藏的公共左因子没提取。从那以后我养成了一个习惯任何文法先跑一遍冲突检测把冲突的产生式打印出来再动手改比盲猜快得多。希望帮到你。本文还有配套的精品资源点击获取