C++递归下降语法分析器实现：从文法设计到AST构建与错误恢复

简介这份资源面向正在学习编译原理、需要完成语法分析实验的高校学生与自学者核心是提供一个可直接参考的递归子程序法语法分析实现方案。它基于词法分析程序识别出的单词序列按给定文法对各类语法成分进行识别并按要求输出单词信息与语法成分名称适合作为课程实验的对照范例与调试参考。压缩包共2个文件包含1个cpp源码文件与1个doc实验说明文档整体约17KB源码对应语法分析主程序文档则给出问题描述与处理要求便于快速理解实验目标。该代码已在CG实验平台满分通过目前已有6106人学习下载说明其参考价值得到较多验证。读者可从中获取完整的递归下降分析思路、文法成分处理顺序、输出格式控制方法以及实验平台评测的注意事项适合在动手实现前梳理结构或在调试受阻时对照排查问题。1. 语法分析实验到底在做什么从一段报错信息说起你在 VS Code 里敲完int a 1 2 * ;编译器立刻甩出一行error: expected expression before ; token。这行报错不是凭空冒出来的它来自编译原理里最核心的一环——语法分析。语法分析实验要你亲手写一个程序把词法分析器吐出来的 token 流按给定的文法规则组装成一棵语法树并在组装不下去的时候准确指出哪一行、哪一列、期望什么、实际遇到什么。C 版实验通常要求你实现一个递归下降分析器或 LL(1) 分析器输入是 token 序列输出是语法树或错误信息。这个实验能让你真正理解编译器前端怎么把一堆字符变成结构化的程序表示适合正在上编译原理课、需要交实验报告、或者想搞明白expected expression这类报错从哪来的同学。做完它你看待 C 代码的眼光会从“能跑就行”变成“这棵语法树长什么样”。2. 文法设计与 token 约定递归下降分析器的地基2.1 为什么实验里优先选递归下降而不是 LR编译原理教材比如清华大学出版社第三版通常先讲 LL(1) 和递归下降再讲 LR。实验里我一般推荐递归下降原因很直接代码结构和文法产生式几乎一一对应调试时你能看着文法逐条对代码出错位置一目了然。LR 分析器需要构造 ACTION/GOTO 表表生成错了很难排查对第一次做语法分析实验的人来说血泪经验就是表驱动调试成本太高。递归下降的代价是要求文法不能有左递归也不能有公共左因子所以你得先对文法做改写。常见做法是把E - E T | T改成E - T EE - T E | ε。这个改写过程本身就是实验报告里值得写的一段。选递归下降还有一个现实好处C 里用函数调用来表达“尝试匹配某个非终结符”非常自然。每个非终结符写一个函数函数返回bool表示是否匹配成功同时通过引用参数把语法树节点带出来。这样你不需要额外维护一个分析栈调用栈就是你的分析栈。2.2 token 结构体与词法分析器的对接约定语法分析器的输入是词法分析器输出的 token 序列。实验里通常词法分析器已经给好了或者要求你自己写一个简单的。不管哪种你都需要一个统一的 token 结构。我一般会定义成下面这样// token.h #pragma once #include string enum class TokenType { INT, // int 关键字 ID, // 标识符 NUMBER, // 数字字面量 PLUS, // MINUS, // - STAR, // * SLASH, // / LPAREN, // ( RPAREN, // ) SEMI, // ; ASSIGN, // END // 输入结束 }; struct Token { TokenType type; std::string lexeme; // 原始文本报错时用 int line; // 行号从 1 开始 int col; // 列号从 1 开始 };这个结构体里line和col是必须的因为语法分析实验的评分点之一就是错误定位。很多同学只存 token 类型不存位置最后报错只能写“语法错误”拿不到定位分。lexeme用来在报错信息里回显实际遇到的符号比如expected ; but got 。词法分析器每识别一个 token 就填一个Token对象末尾追加一个END类型的 token 作为哨兵语法分析器读到END就知道输入结束了。注意ENDtoken 的line和col要设成最后一行的位置否则报“文件意外结束”时定位会跑到第 0 行。2.3 文法改写与 FIRST/FOLLOW 集的手工验算假设实验要求的文法是表达式和赋值语句Program - StmtList StmtList - Stmt StmtList | ε Stmt - ID Expr ; | int ID Expr ; Expr - Term Expr Expr - Term Expr | - Term Expr | ε Term - Factor Term Term - * Factor Term | / Factor Term | ε Factor - ( Expr ) | ID | NUMBER这个文法已经消除了左递归可以直接写递归下降。但在动手写代码之前我建议手工算一遍 FIRST 和 FOLLOW 集尤其是StmtList和Expr这种带 ε 产生式的非终结符。算 FIRST 集是为了知道每个函数在开头该看哪些 token 来决定走哪条分支算 FOLLOW 集是为了知道什么时候可以安全地返回匹配 ε。比如StmtList的 FOLLOW 集包含END和}如果有块语句那么当StmtList函数看到END时就应该返回成功而不是报错。手工验算还有一个好处你能提前发现文法里的冲突。比如Stmt - ID Expr ;和Expr - ... - ID在开头都是ID如果Stmt和Expr在同一个上下文里出现就需要提取公共左因子。实验里通常不会这么刁难但验算一遍能让你在写代码时心里有数。3. 用 C 写递归下降分析器从函数骨架到语法树构建3.1 分析器类的成员设计与 token 流推进我一般把分析器封装成一个类成员包括 token 数组、当前下标、以及一个错误列表。错误列表而不是遇错就退出是因为实验通常要求报告多个错误或者至少报告第一个错误后能继续分析。类骨架如下// parser.h #pragma once #include token.h #include vector #include memory #include string struct ASTNode { std::string label; // 节点名如 Expr、ID std::string value; // 叶子节点的文本 std::vectorstd::shared_ptrASTNode children; int line 0; int col 0; }; class Parser { public: Parser(const std::vectorToken tokens); std::shared_ptrASTNode parse(); // 入口返回语法树根 const std::vectorstd::string errors() const { return errors_; } private: std::vectorToken tokens_; size_t pos_ 0; std::vectorstd::string errors_; const Token peek() const; // 看当前 token不推进 const Token advance(); // 返回当前 token 并推进 bool check(TokenType t) const; // 当前 token 是否是指定类型 bool match(TokenType t); // 匹配则推进并返回 true void error(const std::string msg); // 记录错误 // 每个非终结符一个函数 std::shared_ptrASTNode parseProgram(); std::shared_ptrASTNode parseStmtList(); std::shared_ptrASTNode parseStmt(); std::shared_ptrASTNode parseExpr(); std::shared_ptrASTNode parseExprPrime(); std::shared_ptrASTNode parseTerm(); std::shared_ptrASTNode parseTermPrime(); std::shared_ptrASTNode parseFactor(); };peek()和advance()是核心。peek()返回tokens_[pos_]的引用但要注意pos_可能越界所以实现里要判断pos_ tokens_.size()越界时返回最后一个ENDtoken。advance()返回当前 token 后pos_同样要防越界。match()是语法分析里最常用的如果当前 token 类型匹配就推进并返回 true否则返回 false 且不推进。这样你在每个非终结符函数里可以写if (match(PLUS)) { ... }代码非常直观。3.2 表达式分析的递归下降实现与语法树节点挂接以parseExpr和parseExprPrime为例展示递归下降怎么把树建起来// parser.cpp 片段 std::shared_ptrASTNode Parser::parseExpr() { auto node std::make_sharedASTNode(); node-label Expr; node-line peek().line; node-col peek().col; auto term parseTerm(); if (!term) return nullptr; node-children.push_back(term); auto rest parseExprPrime(); if (rest) node-children.push_back(rest); return node; } std::shared_ptrASTNode Parser::parseExprPrime() { if (check(PLUS) || check(MINUS)) { auto node std::make_sharedASTNode(); node-label Expr; node-line peek().line; node-col peek().col; Token op advance(); // 吃掉 或 - auto opNode std::make_sharedASTNode(); opNode-label Op; opNode-value op.lexeme; opNode-line op.line; opNode-col op.col; node-children.push_back(opNode); auto term parseTerm(); if (!term) return nullptr; node-children.push_back(term); auto rest parseExprPrime(); if (rest) node-children.push_back(rest); return node; } // ε 产生式不消耗 token返回空节点表示空 return nullptr; }这段代码的逻辑说明parseExpr先解析一个Term然后尝试解析Expr。parseExprPrime检查当前 token 是不是或-如果是就吃掉运算符再解析一个Term然后递归解析剩余的Expr。如果不是说明匹配了 ε 产生式返回nullptr。参数说明check(PLUS)只看不推进advance()推进并返回被吃掉的 token。node-line和node-col记录该节点对应源位置用于后续报错或可视化。提示返回nullptr表示 ε 产生式调用方要判断if (rest)再挂到 children 里否则语法树里会出现空指针。3.3 错误恢复同步集与报错信息里的行列号语法分析实验最容易被扣分的地方是错误处理。只报第一个错误然后退出通常只能拿一半分。我一般用“恐慌模式”恢复发现错误时记录错误信息然后不断advance()直到当前 token 属于某个同步集比如SEMI、END、RPAREN再继续分析。同步集的选择依据是 FOLLOW 集。比如在parseStmt里如果期望;但遇到了就报错然后跳到下一个;或END。void Parser::error(const std::string msg) { const Token t peek(); errors_.push_back(line std::to_string(t.line) , col std::to_string(t.col) : msg , got t.lexeme ); } bool Parser::match(TokenType t) { if (check(t)) { advance(); return true; } return false; } // 在 parseStmt 里期望分号 if (!match(SEMI)) { error(expected ;); // 同步跳到分号或 END while (!check(SEMI) !check(END)) advance(); if (check(SEMI)) advance(); }报错信息里带上line和col以及实际遇到的lexeme是拿满分的关键。很多实验评分脚本会用正则匹配line \d, col \d所以格式要稳定。同步集不要设得太大否则会吞掉太多 token 导致后续误报也不要太小否则一个错误会引发连锁报错。我一般用SEMI、END、RPAREN三个作为同步锚点。4. 避坑与排查语法分析实验里最容易翻车的五个点4.1 左递归没消除干净导致栈溢出现象程序一跑就崩溃报stack overflow或者直接段错误。原因文法里还有直接左递归比如Expr - Expr Term递归下降函数parseExpr第一件事就是调用parseExpr无限递归。解决检查所有产生式把左递归改成右递归形式。间接左递归也要处理比如A - B x、B - A y需要先代入再消除。改完后用 FIRST 集验算一遍确保每个函数开头至少能消耗一个 token 或者能明确返回。4.2 token 流越界访问导致pos_跑到 size 之外现象分析到文件末尾时程序崩溃或者报错信息里lexeme是乱码。原因peek()和advance()没有做边界检查pos_等于tokens_.size()时还在访问tokens_[pos_]。解决在peek()里判断pos_ tokens_.size()就返回一个静态的ENDtoken在advance()里判断越界就不推进直接返回END。另外词法分析器输出的 token 数组末尾一定要手动加一个END不要依赖 vector 的越界行为。4.3 语法树节点挂接顺序错误导致树结构反了现象输出的语法树里1 2 * 3被解析成(1 2) * 3而不是1 (2 * 3)。原因parseExpr和parseTerm的调用层级搞反了或者Expr里先递归了Expr再解析Term。解决严格按照文法层级写函数调用。Expr调TermTerm调Factor优先级高的在更深的调用层。Expr里先解析运算符再解析Term再递归Expr这样乘号会被更深的Term吃掉自然形成正确的优先级。4.4 错误恢复时同步集选错导致连锁误报现象一个缺失分号的错误报了十几条错误后面全乱了。原因同步集选得太小比如只跳到SEMI但后面还有RPAREN和END结果在括号里卡住反复报错。解决同步集至少包含SEMI、END、RPAREN三个。如果实验文法里有}也加进去。同步时用while (!check(SEMI) !check(END) !check(RPAREN)) advance();然后根据当前 token 决定是否消耗。报错后不要立即返回继续分析下一个语句这样能报出多个独立错误。4.5 VS Code 里 C 环境没配好导致编译命令找不到现象在 VS Code 里按 F5 调试提示g: command not found或者launch: program ... does not exist。原因VS Code 本身不带 C 编译器需要单独装 MinGW-w64 或 MSVC并且配置tasks.json和launch.json。解决Windows 上装 MinGW-w64把bin目录加到 PATH然后在 VS Code 里装 C/C 扩展。tasks.json里command写g.exeargs里加-g和-stdc17。launch.json里program指向${fileDirname}\\${fileBasenameNoExtension}.exe。如果用的是 Microsoft Visual C Redistributable 相关的运行库问题那是运行阶段缺 DLL和编译阶段找不到编译器是两回事先确认g --version能在终端里跑通。5. 进阶技巧用 AST 可视化验证分析结果以及一个我常犯的错语法树建出来之后光看控制台输出很难判断对不对。我一般会加一个简单的 DOT 格式导出然后用 Graphviz 或者在线工具渲染成图。DOT 导出函数大概长这样// ast_dot.cpp #include parser.h #include fstream static void dumpDot(const std::shared_ptrASTNode node, std::ofstream out, int id) { if (!node) return; int cur id; out n cur [label\ node-label; if (!node-value.empty()) out \\n node-value; out \];\n; for (auto child : node-children) { if (!child) continue; int cid id; dumpDot(child, out, id); out n cur - n cid ;\n; } } void exportDot(const std::shared_ptrASTNode root, const std::string path) { std::ofstream out(path); out digraph AST {\n; int id 0; dumpDot(root, out, id); out }\n; }这个函数递归遍历语法树每个节点分配一个编号输出digraph格式。参数说明id是引用传递保证递归过程中编号不重复node-value非空时作为节点标签的第二行比如ID节点下面显示a。生成.dot文件后用dot -Tpng ast.dot -o ast.png就能看到树形图。我一般会在parse()成功后调用exportDot然后肉眼检查运算符优先级和结合性对不对。注意如果节点很多DOT 文件会很大Graphviz 渲染可能很慢。实验规模的语法树通常几十个节点没问题。还有一个我常犯的错在parseStmtList里判断递归终止条件时用check(END)判断输入结束但忘了StmtList的 FOLLOW 集里可能还有RPAREN。结果解析( int a 1 ; )这种带括号的语句时StmtList在RPAREN处不返回继续尝试解析Stmt然后报一堆错。后来我养成了一个习惯每写一个带 ε 产生式的函数先把它的 FOLLOW 集写在注释里函数开头用if (check(END) || check(RPAREN)) return nullptr;显式处理。这个习惯帮我省了很多调试时间。最后说一个验证技巧准备一组测试用例覆盖正确输入、缺分号、缺右括号、运算符连续、空语句等场景每跑一个用例就对比预期错误数量和错误行号。如果错误行号对不上八成是peek()和advance()的推进时机有问题。我一般会在advance()里加一行// std::cerr advance: tokens_[pos_].lexeme \n;调试时打开看 token 流是不是按预期推进。这个笨办法在排查“为什么报错位置偏了一行”时特别管用。希望帮到你。本文还有配套的精品资源点击获取