简介这份资源面向正在学习编译原理、需要完成语法分析实验的高校学生聚焦递归子程序法这一经典实现路径。内容围绕给定文法设计并实现语法分析程序展开要求基于词法分析识别出的单词进一步判定各类语法成分并按规则输出单词信息与语法成分标记适合作为课程实验的参考实现与对照样例。压缩包共2个文件包含1个cpp源码文件与1个doc实验说明文档整体约17KB源码可直接编译运行文档便于理解题目要求与输出格式。该实现在CG实验平台上满分通过已有6110人学习说明其思路经过实际评测验证。读者可从中获取完整的递归下降分析框架、各语法成分对应的子程序划分方式以及按序输出单词与语法成分标记的处理细节用于对照自己的实验代码排查偏差、理解文法到程序的映射关系也可作为课程设计阶段的起步参考。1. 语法分析到底在编译流程里站哪一格先看一张全景地图很多人学编译原理一上来就扎进 FIRST 集和 FOLLOW 集的推导里推着推着就迷路了——不是不会算而是不知道自己在算什么。语法分析这门实验课的核心其实就一句话把词法分析吐出来的 token 序列按文法规则还原成一棵语法树同时尽可能早、尽可能准地报出错误。它上游接词法分析下游接语义分析和中间代码生成是整个前端里承上启下的一环。这份 C 版语法分析实验资源覆盖的正是这条链路里最需要动手的一环词法接口对接、文法表示、递归下降与预测分析、LR 分析表构造、语法树输出和错误恢复。适合正在做课程实验、准备考试、或者想把「理论课听懂了但写不出来」这个断层补上的人。下面按知识地图、模块要点、易错点、复习清单的顺序梳理你可以当成一份可抄的复习底稿。2. 文法与词法接口实验真正的地基在哪2.1 文法怎么表示决定了后面所有代码的形状语法分析实验翻车的第一个高发区不在算法而在文法的存储方式。理论课上文法写在纸上产生式是E - E T | T这种形式到了代码里你得决定用数组、邻接表还是mapstring, vectorvectorstring来存。梳理下来会发现最省事的做法是非终结符用字符串或枚举产生式右部存成vectorstring左部做 key。这样既能顺序遍历也能按左部快速取候选式递归下降和 LL(1) 都能直接复用。// 产生式存储左部 - 多个候选右部 // 每个右部是一个符号序列空串用特殊标记 EPS 表示 using Symbol std::string; const Symbol EPS ε; struct Grammar { std::vectorSymbol nonTerminals; // 非终结符集合 std::vectorSymbol terminals; // 终结符集合 std::mapSymbol, std::vectorstd::vectorSymbol prods; // 左部 - 候选式列表 Symbol start; // 开始符号 };这段结构的含义很直白prods的 value 是「候选式列表」每个候选式又是符号序列天然对应A - α | β的写法。参数上唯一要留心的是空产生式——用EPS显式占位比用空 vector 更安全因为空 vector 在遍历时容易被误判成「没有候选式」。很多实验报告里 FIRST 集算错根子就在这里空产生式没被当成一个合法候选式参与计算。2.2 词法接口token 流对接的三个约定语法分析器不该自己去读字符它只认 token。所以实验里通常有一个词法分析模块输出(类型, 值)的序列。对接时有三个约定必须提前定死否则调试时会怀疑人生第一token 类型用什么表示字符串还是枚举两边必须一致第二标识符和常量的「值」要不要保留语法分析阶段通常只需要类型值留给语义分析第三文件结束符怎么表示建议单独定义一个EOF_TOKEN不要用空指针或特殊字符串糊弄。struct Token { std::string type; // 如 ID NUM PLUS EOF std::string value; // 原始字面量语法阶段可不用 }; // 语法分析器只依赖这个接口不关心词法怎么实现 class TokenStream { public: explicit TokenStream(std::vectorToken tokens) : toks_(std::move(tokens)), pos_(0) {} const Token peek() const { return toks_[pos_]; } Token next() { return toks_[pos_]; } bool atEnd() const { return toks_[pos_].type EOF; } private: std::vectorToken toks_; size_t pos_; };peek()看当前不消耗next()消耗并前进atEnd()判断结束——这三个方法足够支撑递归下降和预测分析。重点在于把词法接口抽象成TokenStream之后语法分析部分的代码可以脱离真实输入单独测试你手写一个 token 数组就能验证分析逻辑这在实验调试阶段能省掉大量「到底是词法错还是语法错」的扯皮。2.3 消除左递归与提取左公因子的实操顺序直接拿课本文法写递归下降十有八九会栈溢出因为左递归E - E T会让parseE()一进来就调parseE()。标准处理是先消除左递归再提取左公因子顺序不能反。消除左递归的公式是A - Aα | β改写成A - βA、A - αA | ε提取左公因子则是把公共前缀抽出来。这两步做完文法才适合 LL(1) 分析。处理步骤目的典型错误消除直接左递归避免递归下降无限递归只改了一条产生式漏了同组其他候选式消除间接左递归处理 ABA 的环代入顺序不对改完仍有环提取左公因子让 FIRST 集不相交提取后忘了补空产生式分支计算 FIRST/FOLLOW构造预测分析表空产生式的 FOLLOW 传播漏算梳理下来会发现这四步里最容易出错的是「消除间接左递归」——它需要按非终结符顺序逐个代入顺序错了环就消不干净。血泪经验是改完文法后拿几个典型句子手工推一遍最左推导能推通再写代码比写完代码再 debug 快得多。3. 两大分析路线递归下降与 LL(1) 预测分析3.1 递归下降把每条产生式写成一个函数递归下降的直觉极其简单一个非终结符对应一个函数函数体里按候选式依次匹配。它的优点是代码结构和文法几乎一一对应可读性极强缺点是对文法要求高左递归和回溯都是坑。写的时候有个固定套路先peek()看当前 token决定走哪条候选式然后逐个符号处理——遇到终结符就match()遇到非终结符就递归调用。// 对应文法E - T E E - T E | ε // T - F T T - * F T | ε // F - ( E ) | id void Parser::parseE() { parseT(); parseEPrime(); } void Parser::parseEPrime() { if (ts_.peek().type PLUS) { // 看当前 token 决定分支 ts_.next(); // 消耗 parseT(); parseEPrime(); // 尾递归可优化成循环 } // 否则走 ε 分支直接返回 } void Parser::parseF() { if (ts_.peek().type ID) { ts_.next(); } else if (ts_.peek().type LPAREN) { ts_.next(); parseE(); if (ts_.peek().type ! RPAREN) error(缺少右括号); ts_.next(); } else { error(期望 id 或 (); } }这段代码的关键点有三个parseEPrime里的分支判断依赖「当前 token 是否属于该候选式的 FIRST 集」这是预测的前提parseF里对右括号的检查是错误检测的典型位置尾递归的parseEPrime其实可以改写成while循环避免深表达式导致栈过深。参数上没什么可调的真正要盯的是error()的触发时机——报错时最好带上当前 token 和期望集合否则调试时只知道「错了」不知道「错在哪」。3.2 LL(1) 预测分析表FIRST、FOLLOW 与表的填法LL(1) 的核心是一张二维表行是非终结符列是终结符格子里填「用哪条产生式」。构造流程是固定的先算每个符号的 FIRST 集再算非终结符的 FOLLOW 集然后对每条产生式A - α把 α 的 FIRST 集里的终结符对应格子填上这条产生式如果 α 能推出 ε就把 FOLLOW(A) 里的终结符也填上。表填完如果某格有两个产生式说明文法不是 LL(1)得回去改文法。集合含义计算要点FIRST(α)α 能推出的首终结符集合逐符号扫描遇 ε 继续看下一个FOLLOW(A)A 后面可能紧跟的终结符集合开始符号先放$再按产生式传播SELECT(A-α)该产生式适用的向前看符号α 不推 ε 取 FIRST推 ε 取 FOLLOW最容易忽略的是 FOLLOW 的传播规则对产生式A - αBβFOLLOW(B) 要并上 FIRST(β) 去掉 ε如果 β 能推 ε还要并上 FOLLOW(A)。这条「β 推 ε 时继续传播」的规则是考试和实验里共同的失分点。用预测分析表驱动时维护一个栈栈顶是非终结符就查表压产生式右部逆序栈顶是终结符就与输入匹配这套流程写出来不到五十行但表填错一格就全盘皆输。3.3 两条路线的取舍什么时候别硬上递归下降递归下降适合文法规模小、结构清晰的场景实验课的教学文法用它最直观但一旦文法有大量公共前缀、或者需要处理运算符优先级层次很多的表达式手写递归下降的函数数量会爆炸。这时候 LL(1) 表驱动更省代码代价是要先做文法变换。梳理下来可以这样判断如果文法已经消除左递归且 FIRST 集基本不相交递归下降优先如果候选式多、前缀重叠严重先做 LL(1) 表用统一驱动循环处理。别为了「看起来高级」硬上表驱动实验报告里表填错比函数写错更难查。4. LR 分析从移进归约到分析表构造4.1 移进归约的直觉为什么 LR 比 LL 更强LL 分析在「看到非终结符时」就要决定用哪条产生式向前看只有一个符号所以对文法限制多。LR 分析反过来它把输入符号一个个移进栈等到栈顶形成某个产生式的右部时再归约决策时机更晚能利用的信息更多因此能处理的文法范围更大左递归也不用消除。理解 LR 的关键是那个「栈 输入」的格局栈里放的是已经识别完的符号输入是还没看的 token分析器根据「栈顶状态 当前输入」查动作表决定移进、归约、接受还是报错。// LR 分析器主循环骨架 // action[state][terminal] - {SHIFT, REDUCE, ACCEPT, ERROR} // gotoTable[state][nonTerminal] - nextState bool Parser::runLR() { std::vectorint stateStack{0}; // 状态栈初始状态 0 std::vectorSymbol symStack{$}; // 符号栈底部放 $ while (true) { int s stateStack.back(); const Token t ts_.peek(); Action act action[s][t.type]; if (act.kind SHIFT) { stateStack.push_back(act.target); symStack.push_back(t.type); ts_.next(); } else if (act.kind REDUCE) { auto prod prods[act.prodIndex]; // 要归约的产生式 for (size_t i 0; i prod.rhs.size(); i) { stateStack.pop_back(); symStack.pop_back(); } int top stateStack.back(); stateStack.push_back(gotoTable[top][prod.lhs]); symStack.push_back(prod.lhs); } else if (act.kind ACCEPT) { return true; } else { error(语法错误当前 token: t.type); return false; } } }这段循环里stateStack和symStack必须同步弹压这是最容易写错的地方——归约时弹几个符号取决于产生式右部长度弹完再用gotoTable压新状态。参数上action表的 key 是「状态 终结符」gotoTable的 key 是「状态 非终结符」两张表分开存别混成一个。报错分支里带上当前 token 类型是后面做错误恢复的基础。4.2 SLR、LR(1)、LALR 的差别项目集规范族的构造LR 分析表不是凭空来的它来自项目集规范族的构造。一个「项目」就是产生式加一个圆点表示「识别到哪了」比如E - E · T。从初始项目出发不断做闭包和转移得到一族项目集每个项目集就是一个状态。SLR 在归约时用 FOLLOW 集判断简单但可能冲突LR(1) 给每个项目带上向前看符号能力强但状态数爆炸LALR 把同心项目集合并折中了两者。类型归约依据状态数适用场景SLR(1)FOLLOW 集较少教学实验、简单文法LR(1)项目自带向前看符最多需要强表达力的场景LALR(1)合并后的向前看符中等实际工具常用构造项目集时闭包运算的规则是如果项目里圆点后面是非终结符 B就把 B 的所有产生式以圆点开头加入当前集合反复直到不再新增。转移则是对每个符号 X把圆点后是 X 的项目移过一位再求闭包。梳理下来会发现手算项目集规范族时最容易漏的是「闭包要递归」——加入 B 的产生式后如果这些新项目的圆点后又出现非终结符还得继续加直到稳定。4.3 冲突处理移进归约冲突与归约归约冲突构造表时出现一格多动作就是冲突。移进归约冲突最常见于悬空 else 这类文法默认策略是「移进优先」因为移进相当于把决策往后推通常更符合直觉归约归约冲突则说明文法本身有歧义得靠优先级或改写文法解决。实验里遇到冲突别急着改代码先确认是文法问题还是表构造问题——很多时候是 FIRST/FOLLOW 或闭包算错了导致本该不冲突的格子出现两个动作。踩坑经验是把冲突的格子、对应的项目集、涉及的产生式一起打印出来比盯着表干看有效得多。5. 语法树、错误恢复与实验里最容易翻车的地方5.1 语法树的节点设计与输出语法分析的结果是一棵树节点设计直接决定后面语义分析好不好接。常见做法是定义一个基类ASTNode派生TerminalNode和NonTerminalNode非终结符节点持有子节点列表和产生式信息。输出时用缩进或括号表示层次方便肉眼核对。struct ASTNode { Symbol name; // 节点对应的符号 std::vectorASTNode* children; // 子节点 bool isTerminal; explicit ASTNode(Symbol n, bool term false) : name(std::move(n)), isTerminal(term) {} }; // 递归打印缩进表示层级 void printTree(const ASTNode* node, int depth 0) { std::cout std::string(depth * 2, ) node-name \n; for (const auto* c : node-children) printTree(c, depth 1); }节点里存name和children就够了别急着塞语义值那是下一阶段的事。输出格式建议固定成「每层两空格缩进」实验验收时对照语法树和源程序一眼就能看出哪条产生式用错了。注意内存管理实验规模小可以不管但如果用new建树记得在析构里递归释放否则长输入下内存会涨。5.2 错误恢复恐慌模式与短语级恢复语法分析器不能一遇错就退出得能继续往下分析尽量多报几个错。最常用的是恐慌模式发现错误后丢弃输入符号直到遇到一个「同步符号」比如分号、右括号、语句开始关键字然后从这个符号继续。短语级恢复则是在局部做小修正比如插入一个缺失的右括号。实验里实现恐慌模式性价比最高同步符号集合按文法定通常选那些能明确划分语句边界的终结符。提示错误恢复的目标是「报得准、不崩溃」不是「自动修对」。恢复后继续分析得到的语法树可能是残缺的别拿它当正确结果用。5.3 易漏点五个高频翻车现场易漏点一空产生式在 FIRST 集里被忽略。为什么漏直觉上「空」不是符号写代码时容易跳过。怎么补把 ε 当成 FIRST 集的合法成员计算时显式判断「该符号能否推出 ε」并在 FOLLOW 传播时用上。易漏点二FOLLOW 集忘了给开始符号加结束符。为什么漏只盯着产生式传播忘了初始化。怎么补构造一开始就把$放进 FOLLOW(开始符号)这是所有传播的源头。易漏点三LR 归约时状态栈和符号栈弹压不同步。为什么漏两个栈分开维护弹的个数没对齐。怎么补归约时按产生式右部长度同时弹两个栈弹完立刻用gotoTable压新状态写成一个小函数封装起来。易漏点四递归下降没处理左递归就开写。为什么漏课本文法直接照抄没做变换。怎么补写代码前先过一遍「消除左递归 提取左公因子」改完手工推一个句子验证。易漏点五错误信息只报「语法错误」不报位置。为什么漏图省事error()里就一句字符串。怎么补报错时带上当前 token 类型、行号如果词法阶段有、期望的符号集合调试效率差好几倍。6. 复习清单从能跑通到能讲清楚的查漏补缺法复习语法分析别从第一页重新看按「能不能讲清楚」来筛。我的做法是拿一张白纸合上资料把下面这张清单逐条自问讲不顺的才回去翻。检查项能讲清楚的标准讲不清就补文法表示说得出产生式怎么存、空串怎么标回到 2.1 的结构设计消除左递归能现场改写一个含左递归的文法练直接和间接两种FIRST/FOLLOW能手算一个小文法的两个集合重点练 ε 传播递归下降能写出一个非终结符的解析函数注意分支判断依据LL(1) 表能说清每格填哪条产生式检查 SELECT 集LR 主循环能说清移进、归约时两个栈怎么变盯弹压同步项目集构造能对一个产生式做闭包和转移闭包要递归到稳定错误恢复能说出同步符号怎么选恐慌模式优先具体操作上我习惯分三轮。第一轮只做「口述」对着清单每一条用两三句话讲给空气听卡壳的地方做记号。第二轮做「手算」挑一个五到八条产生式的小文法从消除左递归一路手算到 LL(1) 表或 LR 项目集全程不查资料算完再对照。第三轮做「对照代码」把这份 C 实验里的TokenStream、递归下降函数、LR 主循环各读一遍确认每个参数和分支都能对应到前面的理论点。三轮下来哪些是真懂、哪些是背下来的一目了然。最容易忽略的是「错误路径」的复习——大家习惯验证正确句子能分析通过却很少故意喂一个错句子看报错是否合理。查漏补缺时专门造几个错误输入缺右括号、多余运算符、非法 token观察分析器是崩溃、是静默通过、还是准确报错。这一步能暴露大量隐藏问题尤其是错误恢复逻辑写没写对。从那以后我每次复习这类实验课都强制自己先合上资料口述一遍清单再动手手算一个小例子最后才碰代码——顺序反了就变成「代码能跑但讲不出为什么」。希望这份梳理能帮到你把语法分析这块从「考试会算」推进到「实验能写、面试能讲」。本文还有配套的精品资源点击获取