简介面向编译原理课程“语法分析”实验的C实现方案主要适用对象是计算机专业本科生以及正在完成递归子程序法作业、需要对照参考实现的学习者。程序基于上次词法分析产出的单词序列按给定文法规则识别常量说明、变量说明、语句等各类语法成分同时解决预读、输出顺序等实验常见难点。资源包为zip压缩格式共2个文件其中1份cpp源码完整实现递归下降分析逻辑1份doc文档详细说明问题描述、输入输出要求并明确了源文件与结果文件的统一命名方式方便自动评测场景直接替换使用整体仅17KB轻量易用。目前已有六千余人学习说明该实现获得了较多开发者认可。源码在CG实验平台满分通过代码结构与实验文档高度对应运行后可对照输出结果逐行检查语法成分名字与单词信息既能帮助理解递归子程序法的调用框架也可用于排查预读处理、文件读写格式等细节问题适合作为实验参考或二次开发起点。语法分析实验到底在做什么不管你是正在被编译原理折磨的本科生还是想补一补基础的自学党“语法分析”这四个字大概率都让你头疼过。最近我又翻出了当年用C实现的语法分析实验代码重新整理了一遍发现这个实验其实没有想象中那么玄乎——说白了就是让程序能看懂“一串符号是否符合语法规则”就像你写英语作文时老师帮你检查主谓宾是否齐全一样。这个实验的经典做法是手写递归下降分析器更硬核一点的做法是构造LL(1)预测分析表。我当时选择用C实现主要看重它贴近底层、能直观体现数据结构设计而且C的STL容器处理文法符号集合特别顺手。这篇博文就把完整的实现思路、核心代码逻辑、以及我踩过的坑全部拆开讲清楚无论你是第一次做实验还是想查缺补漏都能找到能直接拿去用的东西。1. 实验前的思路定调自顶向下还是自底向上1.1 为什么我选择了LL(1)预测分析语法分析的主流实现路线有两条递归下降分析和LL(1)预测分析表都是自顶向下的思路。自底向上的代表是LR家族但那是编译器生产环境的常用选择课程实验用LR纯属给自己找麻烦。我最终选了LL(1)预测分析理由有三个。第一LL(1)分析表构造流程极具教学价值——你需要真正理解First集、Follow集、预测分析表三件套每个知识点都能在代码里找到对应实现。第二预测分析表的查表过程非常直观一个二维表加上一个栈就能跑起来不会有递归调用带来的隐蔽栈溢出风险。第三这玩意儿的错误检测能力很强输入串不合法时能第一时间定位到具体符号。这里需要说明的是LL(1)不是万能的。如果文法里有左递归或者公共左因子直接套LL(1)会直接翻车后面我会详细讲怎么处理。课程实验阶段你要做的第一步是把文法改写成符合LL(1)条件的形式这本身就是实验的重要考核点。1.2 一个足以跑通的示例文法我写实验时用的文法来自经典的表达式求值场景覆盖了赋值语句、加减乘除和括号足够展示所有核心机制1. program - statement 2. statement - id assign expr 3. expr - term expr_tail 4. expr_tail - add_op term expr_tail | epsilon 5. term - factor term_tail 6. term_tail - mul_op factor term_tail | epsilon 7. factor - left_paren expr right_paren | id | number这个文法包含的关键要素有终结符id、assign、add_op、mul_op、left_paren等、非终结符program、statement、expr等、以及神秘的epsilon空串。epsilon表示“这个非终结符可以什么也不产生”比如expr_tail在遇到右括号或分号时就会选择epsilon产生式乖乖闭嘴。选这个文法的原因在于它足够检验算法的正确性。id assign expr支持类似“x 1 2 * 3”的赋值语句括号让优先级处理变得清晰epsilon产生式则专门用来检验你First集和Follow集计算是否正确。这个文法是推导“x 1 2 * 3”语法树的完整路径能跑通它实验的核心部分就算拿下了。2. 核心数据结构设计与代码骨架2.1 文法符号的表示方式C实现的第一步是想清楚“终结符”和“非终结符”在代码里长什么样。我见过不少同学的代码用char类型硬编码比如把直接当终结符这种方案局限很大——一旦终结符变成“关键字if”或者“标识符ID”char就完全不够用了。我推荐用一个简单的结构体来表示符号enum class SymbolType { TERMINAL, // 终结符 NON_TERMINAL, // 非终结符 EPSILON, // 空串 END_MARKER, // 结束符 # }; struct Symbol { SymbolType type; std::string name; bool operator(const Symbol other) const { return type other.type name other.name; } bool operator(const Symbol other) const { if (type ! other.type) return type other.type; return name other.name; } };注意我重载了运算符这是因为后面要用std::map来存储First集和Follow集map要求键类型必须支持严格弱排序。这一步看起来不起眼但能省掉后面一大堆编译报错的麻烦。2.2 产生式的存储与First集计算产生式的存储方式直接决定后续代码的复杂度。文法中的产生式形如“expr - term expr_tail”这其实是一个非终结符对应一个右侧符号序列。我用两个结构体来组织struct Production { Symbol lhs; // 左部非终结符 std::vectorSymbol rhs; // 右部符号序列 }; // 文法的完整表示 using Grammar std::multimapSymbol, std::vectorSymbol;multimap的选择是有考量的同一个左部可以有多个产生式比如expr_tail - add_op term expr_tail和expr_tail - epsilon用multimap可以很方便地遍历某个非终结符的所有候选产生式。First集的计算规则可以用简单的话概括一个非终结符的First集就是它能推导出的所有串的开头终结符的集合。具体计算分三步std::mapSymbol, std::setSymbol firstSet; // 初始化终结符的First集就是它自己 for (auto [sym, prods] : grammar) { if (sym.type SymbolType::NON_TERMINAL) { firstSet[sym] {}; } } // 不断迭代直到集合不再变化 bool changed true; while (changed) { changed false; for (auto [lhs, rhs] : allProductions) { auto targetSet firstSet[lhs]; size_t oldSize targetSet.size(); for (auto symbol : rhs) { if (symbol.type SymbolType::TERMINAL) { targetSet.insert(symbol); break; } else if (symbol.type SymbolType::NON_TERMINAL) { // 把该非终结符的First集加入目标集合 for (auto fs : firstSet[symbol]) { if (fs.type ! SymbolType::EPSILON) { targetSet.insert(fs); } } // 如果该非终结符的First集不含epsilon则终止 if (firstSet[symbol].find(Symbol{SymbolType::EPSILON, epsilon}) firstSet[symbol].end()) { break; } } } if (targetSet.size() ! oldSize) changed true; } }这个代码是完整的核心逻辑是在while循环里反复扫描所有产生式直到所有First集都不再变化。这里特别要注意非终结符的处理如果某个非终结符的First集包含了epsilon这意味着它可能“产生空”此时我们必须继续看产生式右部的下一个符号。2.3 从First到Follow的推进Follow集的定义是在推导过程中某些句型中紧跟在某个非终结符后面的终结符集合。直白点说就是一个非终结符后面可能跟着什么符号。计算Follow集比First集麻烦一些规则有这么几条一是开始符号的Follow集必然包含结束符#。二是在产生式A - αBβ中B后面的符号是First(β)所以First(β)中除epsilon以外的所有符号都要加入Follow(B)。三是如果A - αB或者A - αBβ且First(β)包含epsilon则Follow(A)中的所有元素都要加入Follow(B)。这里最容易搞混的是第二条和第三条的先后关系。我的建议是先处理所有“右部最后一个符号”的情况再处理“中间符号且后面跟的First集含epsilon”的情况。实际代码用的是类似的迭代直到收敛的套路std::mapSymbol, std::setSymbol followSet; followSet[programStartSymbol].insert(endMarker); // 开始符号的Follow集含# bool changed true; while (changed) { changed false; for (auto [lhs, rhs] : allProductions) { for (size_t i 0; i rhs.size(); i) { Symbol B rhs[i]; if (B.type ! SymbolType::NON_TERMINAL) continue; auto followB followSet[B]; size_t oldSize followB.size(); if (i 1 rhs.size()) { // B是产生式右部最后一个符号 for (auto s : followSet[lhs]) followB.insert(s); } else { // 计算beta rhs[i1..]的First集 bool betaCanBeEmpty true; for (size_t j i 1; j rhs.size(); j) { Symbol c rhs[j]; if (c.type SymbolType::TERMINAL) { followB.insert(c); betaCanBeEmpty false; break; } else { for (auto fs : firstSet[c]) { if (fs.type ! SymbolType::EPSILON) followB.insert(fs); } if (firstSet[c].find(emptySymbol) firstSet[c].end()) { betaCanBeEmpty false; break; } } } if (betaCanBeEmpty) { for (auto s : followSet[lhs]) followB.insert(s); } } if (followB.size() ! oldSize) changed true; } } }这里有一个我踩过的坑在计算Follow(B)时如果B后面紧跟的符号是非终结符且它的First集包含epsilon你必须继续往后看直到找到一个终结符或一个First集不含epsilon的非终结符。最极端的情况是B后面所有符号的First集都包含epsilon那就要把Left-hand side产生式左部符号的Follow集全部搬过来。3. 预测分析表的构造与核心算法3.1 向量化存储预测分析表有了First集和Follow集我们就可以构造预测分析表。这张表是一个二维矩阵行对应非终结符列对应终结符加上结束符#表项存储的是应该选用的产生式序号。我的实现用了一个最简单的线性结构// 存储每个产生式的索引 std::vectorProduction productionList; // 预测分析表键是 (非终结符, 终结符)值是对应产生式在productionList中的下标 std::mapstd::pairSymbol, Symbol, int predictTable; // 构造预测分析表 void buildPredictTable() { for (size_t idx 0; idx productionList.size(); idx) { auto prod productionList[idx]; auto lhs prod.lhs; auto rhs prod.rhs; // 情况1rhs第一个符号是终结符 if (!rhs.empty() rhs[0].type SymbolType::TERMINAL) { predictTable[{lhs, rhs[0]}] (int)idx; } // 情况2rhs第一个符号是非终结符 else if (!rhs.empty() rhs[0].type SymbolType::NON_TERMINAL) { for (auto ts : firstSet[rhs[0]]) { if (ts.type ! SymbolType::EPSILON) { predictTable[{lhs, ts}] (int)idx; } } } // 情况3rhs可以推导出epsilon if (canDeriveEpsilon(rhs)) { for (auto ts : followSet[lhs]) { predictTable[{lhs, ts}] (int)idx; } } } }核心逻辑分三种情况处理对应了LL(1)文法构建预测分析表的经典规则。如果某个格子被填写了多个产生式那么这个文法就不是LL(1)文法——这时候你的程序应该输出对应的冲突报告而不是静默地让后写的覆盖先写的。3.2 驱动输入串的完整过程预测分析表构建完毕下面的语法分析过程其实就是一个表驱动的自动机栈里放的是文法符号输入缓冲区放的是待分析的终结符序列。bool parse(const std::vectorSymbol inputTokens) { std::stackSymbol parseStack; parseStack.push(endMarker); // 栈底压入# parseStack.push(startSymbol); // 栈顶压入开始符号 size_t index 0; while (!parseStack.empty()) { Symbol top parseStack.top(); Symbol currentInput inputTokens[index]; if (top.type SymbolType::TERMINAL) { if (top currentInput) { parseStack.pop(); // 栈顶终结符和当前输入匹配弹栈并消费输入 index; } else { // 栈顶终结符与输入不匹配语法错误 reportError(Terminal mismatch, top, currentInput, index); return false; } } else if (top.type SymbolType::END_MARKER) { if (currentInput.type SymbolType::END_MARKER) { parseStack.pop(); // 同时消耗输入中的# } else { reportError(Unexpected input after end, top, currentInput, index); return false; } } else { // 查预测分析表 auto key std::make_pair(top, currentInput); auto it predictTable.find(key); if (it predictTable.end()) { reportError(No production found, top, currentInput, index); return false; } // 弹出左部非终结符逆序压入产生式右部符号 parseStack.pop(); auto rhs productionList[it-second].rhs; if (!(rhs.size() 1 rhs[0].type SymbolType::EPSILON)) { for (auto it2 rhs.rbegin(); it2 ! rhs.rend(); it2) { parseStack.push(*it2); } } } } return true; }这里的逆序压入是算法核心栈的特性是后进先出为了让产生式右部的符号按照从左到右的顺序被展开我们必须从右往左依次压栈。我第一次写的时候没注意到这个细节结果表达式顺序完全乱掉。3.3 语法树与错误处理的衔接单一的bool返回值只能告诉你“对不对”但实验报告通常要求你“错误在哪”。我的做法是维护一个简易语法树节点栈在每次弹出栈顶非终结符并选择产生式时创建一个新的语法树节点把右部符号对应的节点挂到它的子节点列表中。struct ParseTreeNode { Symbol symbol; std::vectorParseTreeNode* children; std::string leafValue; // 如果是终结符叶子节点这里存储词法值 }; // 在parse过程中维护一个栈树节点栈 std::stackParseTreeNode* nodeStack;更实用的做法是同时输出完整推导过程。每走一步就把当前栈的内容快照输出为文本这样在实验报告里可以直接粘贴展示分析器的推导序列第1步栈# program输入id assign number ...动作选择产生式1第2步栈# statement输入id assign number ...动作选择产生式2这个推导序列在课堂演示和答辩环节非常加分同时也能帮你定位错误如果输入串不合法你手上会有一份完整的“决策轨迹”可以手动检查是哪一步出错了。4. 实验中的那些坑与排查实录4.1 词法分析输出的模糊尾随空格我实际运行时踩到过不少坑逐一整理出来供参考。第一个坑是词法分析器的输出格式问题。语法分析器的输入是一串终结符但这个串不是理想的字符串数组而是带有位置信息和字面值。我的词法器输出“id assign number id”这样的序列时尾随空格和处理不干净的分隔符很容易让终结符匹配变得不可靠。特别是加上字符串解析环节后一个未被预料的换行符会让错误定位从第3个token直接跳到最后。我的解决办法是做一个严格的终结符规则表把“可接受的输入模式”定义成白名单。每个合法终结符对应一个正则表达式任何不符合白名单的内容直接丢弃并记录错误。id- 标识符首字母是字母后续是字母或数字assign- 等于号“”add_op- “”或“-”mul_op- “*”或“/”number- 一位或多位数字4.2 左递归让程序直接栈溢出第二个坑也是最有代表性的坑是左递归导致的无限循环。刚开始我实验用的文法肯定是类似expr - expr term这样的写法因为它最贴近数学直觉。但这样的文法一旦拿到预测分析算法里程序会立刻陷入无限循环。为什么因为当遇到expr时你会去分析expr又要去分析expr……永远没完没了。这就是左递归的破坏力。解决办法是文法的等价改写。把expr - expr term | term改写为expr - term expr_tail expr_tail - term expr_tail | epsilon这样改写之后程序的递归深度受限于输入串的长度不会再出现无限递归。这是做LL(1)实验绕不开的步骤也是你最可能丢分的考点。别忘了每一个非终结符的epsilon产生式里都包含伏笔——它相当于给递归下降留出了“出口”。4.3 First集和Follow集计算的全集校验第三个常见问题是程序跑起来后预测分析表里有重复项。这个问题的根源要么是First集算错要么是Follow集算错。我的校验办法比较土但非常有效把First集、Follow集全部打印出来和课本例题手动推导的结果逐项比对。我推荐大家写一个额外的调试函数专门打印所有非终结符的First集和Follow集。这一招在答辩时也特别好用老师一问“你验证过哪些测试用例”你可以理直气壮地把输出端给老师看。void printFirstFollowSets() { for (auto [sym, firstSet] : firstSet) { std::cout First( sym.name ) { ; for (auto ts : firstSet) std::cout ts.name ; std::cout }\n; } for (auto [sym, followSet] : followSet) { std::cout Follow( sym.name ) { ; for (auto ts : followSet) std::cout ts.name ; std::cout }\n; } }4.4 终结符定义混乱导致表项缺失最后一个坑是终结符的定义方式混乱。如果终结符同时用字符串名称和枚举类型表示而这两者之间没有统一的映射关系很容易在构建预测分析表时出现表项“查得到但Id不匹配”的问题。我最终把所有终结符定义成常量Symbol对象放在一个全局字典里每次比较时只比对Symbol的name字段彻底杜绝了这一问题。5. 学习路线与工具配置建议5.1 一个经实战验证的完整程序流程如果你是从零开始写这个实验我建议按照下面几条路线推进。第一步设计文法和符号表。先手动构造LL(1)文法确认没有左递归和公共左因子。第二步实现符号类和产生式类用map或multimap组织。第三步实现First集和Follow集每做完一个都要打印验证。第四步构建预测分析表检查是否每个格子最多只有一个产生式。第五步实现词法器或者从实验一复用输出终结符序列。第六步实现表驱动分析器并输出推导过程。每一步之间有明确的依赖关系前一步的错误如果不及时发现后面查错难度呈指数级上升。5.2 环境选型的小建议热词里大家对“vscode配置c/c环境”和“dev c官网”的搜索频率很高我说下实测体验。Dev-C调试功能弱语法分析程序大量使用STL容器一旦运行出错日志输出比断点好用很多。Visual Studio Code配合MinGW或MSVC可以随时运行错误提示信息完整功能齐全推荐优先选这个组合。如果是老设备配置不高也总要优先选带CLI的编辑器方便在命令行快速测试和重定向输入输出。6. 一个实用的中途验收技巧实验经常有中期验收环节你得现场演示某个测试输入串的分析过程。这里分享一个实用技巧提前把打印推导过程的调试开关写成一个宏或flag这样答辩时切换动态ShowParseDetail现场展示比拿代码逐行解释直观得多。我自己的代码里加了一个-v命令行参数让程序可以选择“仅输出结果”或“输出完整分析过程”再配合几个精心挑选的测试用例一个正常表达式、一个含括号的嵌套表达式、一个缺失等号的错误表达式、一个缺少右括号的错误表达式。这四个用例可以全面检验你的分析器在正确路径和错误路径上的表现同时不会超出课堂答辩的时间限制。如果你觉得只有布尔判定太平淡还可以把分析过程同时写进一个.dot文件利用Graphviz等工具生成语法树的图片答辩时把图片贴到PPT里视觉效果会好很多。学习曲线稍微陡一些但对于分项目展示是很有价值的投资。这招我没有在整理代码时直接用因为会引入额外依赖但如果你时间充裕强烈建议试试。本文还有配套的精品资源点击获取