简介面向编译原理课程学习者与需要完成语法分析实验的高校学生压缩包提供了一份基于C实现的递归子程序法语法分析完整代码与配套说明。代码针对给定文法规则依次识别词法分析阶段输出的单词序列并按要求在output.txt中逐行输出单词信息及对应语法成分名称可覆盖常量说明等各类语法成分的判别。配套文档对实验问题描述、输入输出规范与实现要点作了梳理适合对照实验要求进行理解、修改与复用。资源包共2个文件包含1个cpp源文件和1个doc文档压缩包整体仅17KB内容精简、目标明确。作者标明该方案已在CG实验平台满分通过具备较高的参考价值目前已有6109人浏览学习适合编译原理课程实验备赛与代码思路借鉴。1. 一个语法分析器到底在干什么从混乱 token 流里还原出程序结构你也许写过这样的代码读进一整份源代码文件按空白和符号切开成 token然后……然后不知道该拿这堆 token 怎么办。这是刚接触编译原理的人最常见的卡壳点——词法分析器像切菜把源码切成碎片而语法分析器是拼图要把这些碎片按文法规则重新拼成一棵有层次的树。这个 c 版语法分析实验项目解决的就是拼图这一步它实现了包括 FIRST 集计算、FOLLOW 集计算、预测分析表构建、递归下降解析和语法树输出在内的完整语法分析流程输入一段源代码输出一棵可读的抽象语法树AST。适合正在上编译原理课、被 LL(1) 文法折腾得睡不着或者想在一周内手撸一个能跑的小型语法分析器的同学。它的价值不在于用了多高深的算法而在于把教科书里互相割裂的概念串成了一整条可运行的流水线文法定义放左边token 流从右边进来语法树从下边出来中间每一步都有日志可查。即便你已经工作多年想回顾编译原理底层是怎么处理优先级和结合性的这份代码也能帮你把记忆里的碎片重新拼起来。2. 项目整体设计一条输入到语法树的流水线2.1 目录结构与构建入口拿到代码后先别急着读算法建议从目录结构入手建立整体感。这个项目是典型的「头文件 实现文件」组织方式按功能划分得非常清楚syntax-analyzer/ ├── include/ │ ├── Token.h // token 类型定义 │ ├── Lexer.h // 词法分析器接口简单实现 │ ├── Grammar.h // 文法产生式、终结符/非终结符定义 │ ├── FirstFollow.h // FIRST 集与 FOLLOW 集计算 │ ├── LL1Table.h // 预测分析表构建 │ ├── Parser.h // 递归下降解析器 │ ├── ASTNode.h // 语法树节点定义 │ └── ASTPrinter.h // 语法树可视化输出 ├── src/ │ ├── Lexer.cpp │ ├── Grammar.cpp │ ├── FirstFollow.cpp │ ├── LL1Table.cpp │ ├── Parser.cpp │ ├── ASTPrinter.cpp │ └── main.cpp // 入口串联整个流程 ├── test/ │ └── test_parser.cpp // 几组内建测试用例 ├── CMakeLists.txt └── README.md编译方式很常规如果你习惯 CMake直接走标准流程就行如果只想快速验证也可以把 src 目录下所有 cpp 文件加上 include 路径一起编译。注意项目的词法分析器是简化版只负责把整数、标识符、四则运算符、括号和赋值号切成 token。它没有做字符串和浮点字面量的处理——这是刻意为之为了把焦点留在语法分析本身。2.2 Token 设计与词法接口语法分析的输入契约语法分析器眼里没有「源码」只有 token 流。所以理解这个项目的第一步是看 Token 这个基础数据结构enum class TokenType { IDENTIFIER, // 变量名 INT_LITERAL, // 整数常量 ASSIGN, // PLUS, // MINUS, // - STAR, // * SLASH, // / LPAREN, // ( RPAREN, // ) SEMICOLON, // ; END, // 输入结束 UNKNOWN // 非法字符 }; struct Token { TokenType type; std::string lexeme; // 原始文本比如 abc123 int line; // 所在行号用于报错定位 };每个 token 除了类型还保存了原始文本和行号。行号在语法分析报错时特别关键——没有行号的报错信息对用户来说就是天书。Lexer 的接口则非常简单class Lexer { public: explicit Lexer(const std::string source); std::vectorToken tokenize(); // 一次性返回全部 token private: std::string source_; size_t pos_ 0; };这里有个设计取舍它没有做「按需取 token」的惰性接口而是先一次性把整个源码切完。对于实验项目这是合理的——语法分析阶段不需要关心 IO 性能一次性切完反而方便后续调试时直接把 token 流打印出来核对。2.3 文法定义方式用最小代码描述表达式语言这个项目内置的文法是个典型的表达式文法支持赋值语句、加减乘除和括号。文法在 Grammar.h 里以产生式列表的形式组织struct Production { std::string lhs; // 产生式左部如 expr std::vectorstd::string rhs; // 产生式右部如 {term, expr_prime} }; class Grammar { public: std::vectorstd::string terminals; // 终结符集合 std::vectorstd::string nonTerminals; // 非终结符集合 std::vectorProduction productions; // 所有产生式 std::string startSymbol; // 开始符号 const std::vectorProduction getProductionsFor(const std::string nt) const; };注意这里有个巧妙之处getProductionsFor在类内部提前把所有产生式按左部做了索引解析器查产生式时不需要每次都遍历全部产生式列表。项目选择的文法做了消除左递归处理比如expr → term expr_prime expr_prime → term expr_prime | - term expr_prime | ε term → factor term_prime term_prime → * factor term_prime | / factor term_prime | ε factor → ( expr ) | IDENTIFIER | INT_LITERAL终结符和非终结符都用字符串表示优点是打印方便、调试时一眼能看懂缺点是每一步查表都有字符串开销。对实验项目来说可读性远重要于那点性能损耗这个取舍我认为是对的。3. 核心算法实现FIRST 集、FOLLOW 集与预测分析表3.1 FIRST 集的迭代计算实现FIRST 集是 LL(1) 分析的地基。这个项目里用的是常见的迭代不动点算法——不断给集合添加新元素直到某轮循环没有任何变化才停止#include set #include map std::mapstd::string, std::setstd::string FirstFollow::computeFirst( const Grammar grammar) { std::mapstd::string, std::setstd::string first; // 初始化终结符的 FIRST 集就是它自己 for (auto t : grammar.terminals) { first[t].insert(t); } // 非终结符初始为空集 for (auto nt : grammar.nonTerminals) { first[nt] {}; } bool changed true; while (changed) { changed false; for (auto prod : grammar.productions) { auto lhsFirst first[prod.lhs]; if (prod.rhs.empty() || prod.rhs[0] ε) { // 空产生式把 ε 加入左部 FIRST 集 if (lhsFirst.insert(ε).second) changed true; continue; } bool allNullable true; for (auto symbol : prod.rhs) { // 把当前符号的 FIRST 集中所有非 ε 元素加入左部 size_t beforeSize lhsFirst.size(); for (auto elem : first[symbol]) { if (elem ! ε) { lhsFirst.insert(elem); } } if ((int)lhsFirst.size() ! (int)beforeSize) { changed true; } // 如果当前符号的 FIRST 集不含 ε则后续符号不再贡献 if (first[symbol].find(ε) first[symbol].end()) { allNullable false; break; } } // 所有右部符号都能推导出 ε则左部 FIRST 集也含 ε if (allNullable) { if (lhsFirst.insert(ε).second) changed true; } } } return first; }这段代码的核心逻辑是对每条产生式右部从左往右扫描把每个符号的 FIRST 集并入左部如果某个符号的 FIRST 集里没有 ε说明这个符号不能为空那右部更后面的符号就不用再看了。如果右部所有符号都可能为空最终需要把 ε 也并入左部的 FIRST 集。changed这个标志位是典型的迭代不动点写法——每一轮至少有一个集合变大集合变大又可能导致下一轮其他集合变大。这个算法的最坏复杂度是 O(n * m²) 量级对实验规模的小文法来说性能完全不是问题。3.2 FOLLOW 集的依赖处理FOLLOW 集的计算比 FIRST 集麻烦因为它依赖产生式右部上下文——你得知道一个非终结符「后面跟着什么」。项目里同样用迭代法但初始化和迭代规则要复杂一些std::mapstd::string, std::setstd::string FirstFollow::computeFollow( const Grammar grammar, const std::mapstd::string, std::setstd::string first) { auto follow std::mapstd::string, std::setstd::string(); for (auto nt : grammar.nonTerminals) { follow[nt] {}; } // 开始符号的 FOLLOW 集初始包含文件结束符 follow[grammar.startSymbol].insert($); bool changed true; while (changed) { changed false; for (auto prod : grammar.productions) { for (size_t i 0; i prod.rhs.size(); i) { std::string B prod.rhs[i]; if (grammar.isNonTerminal(B)) { auto followB follow[B]; // 情况一A → αBβ把 FIRST(β) 中除 ε 外的元素加入 FOLLOW(B) for (size_t j i 1; j prod.rhs.size(); j) { for (auto elem : first[prod.rhs[j]]) { if (elem ! ε) { size_t oldSize followB.size(); followB.insert(elem); if (followB.size() ! oldSize) changed true; } } if (first[prod.rhs[j]].find(ε) first[prod.rhs[j]].end()) { break; // 后面不会再推导出 ε停止 } } // 情况二A → αB 或 A → αBβ 且 β 可以推导出 ε // 此时把 FOLLOW(A) 全部并入 FOLLOW(B) bool canDeriveEmpty true; for (size_t j i 1; j prod.rhs.size(); j) { if (first[prod.rhs[j]].find(ε) first[prod.rhs[j]].end()) { canDeriveEmpty false; break; } } if (canDeriveEmpty) { for (auto elem : follow[prod.lhs]) { size_t oldSize followB.size(); followB.insert(elem); if (followB.size() ! oldSize) changed true; } } } } } } return follow; }这段实现里最容易晕的是「什么时候把 FOLLOW(A) 传给 FOLLOW(B)」。教科书表述是如果存在产生式 A → αB或者 A → αBβ 且 β 能推导出 ε那么 FOLLOW(A) 就是 FOLLOW(B) 的子集。代码里canDeriveEmpty就是检查右部中 B 之后的所有符号是否都能推导出 ε。初始时 FOLLOW 集可能全是空集但随着迭代推进FOLLOW 会像水波一样在文法依赖图里扩散传播。3.3 预测分析表构建LL(1) 冲突一测便知有了 FIRST 集和 FOLLOW 集构建预测分析表就是纯机械操作class LL1Table { public: // 表项非终结符 - 终结符 - 产生式编号 std::mapstd::string, std::mapstd::string, int table; bool hasConflict false; void build(const Grammar grammar, const std::mapstd::string, std::setstd::string first, const std::mapstd::string, std::setstd::string follow) { for (size_t pi 0; pi grammar.productions.size(); pi) { auto prod grammar.productions[pi]; // 对每个终结符 a ∈ FIRST(右部)把该产生式放入 M[A][a] auto rhsFirst calcFirstOfRhs(prod.rhs, first); for (auto a : rhsFirst) { if (a ! ε) { insertEntry(prod.lhs, a, (int)pi); } } // 若右部能推导出 ε则对 b ∈ FOLLOW(左部)也放入该产生式 if (rhsFirst.find(ε) ! rhsFirst.end()) { for (auto b : follow[prod.lhs]) { insertEntry(prod.lhs, b, (int)pi); } } } } private: void insertEntry(const std::string nt, const std::string term, int prodIdx) { auto entry table[nt][term]; // 同一个格子里出现第二条产生式 文法不是 LL(1) if (entry ! 0 entry ! prodIdx 1) { hasConflict true; std::cerr [冲突] 非终结符 nt 遇到终结符 term 时同时匹配 entry 和 prodIdx 1 号产生式 std::endl; } else { entry prodIdx 1; // 存储时 1避开默认值 0 } } };这代码里有个小细节值得注意表项用 0 表示「空」产生式编号存储时做了 1 偏移。这是为了避免「第 0 号产生式」和「空表项」混淆。虽然多一层心智负担但调试时不会产生二义性。LL(1) 这个名字的含义就是「从左到右扫描 最左推导 向前看一个符号」。如果你的文法在构建表时报了冲突在进入解析器调试之前就应该停下来——因为继续写下去也是无底洞。预测分析表的意义不光是给驱动算法查表用它本身就是文法合法性的检测器。4. 解析器的两种实现路径与语法树输出4.1 表驱动预测分析用栈模拟最左推导拿到预测分析表后第一种解析方式是表驱动。它维护一个符号栈模仿自动机的移进-归约过程bool Parser::parseWithStack(const std::vectorToken tokens, const LL1Table table, const Grammar grammar) { std::vectorstd::string stack; stack.push_back($); stack.push_back(grammar.startSymbol); size_t ip 0; // token 流指针 while (!stack.empty()) { std::string X stack.back(); Token currentToken tokenTypeToString(tokens[ip].type); if (X $ currentToken $) { return true; // 栈空 输入读完 接受 } if (grammar.isTerminal(X)) { if (X currentToken) { stack.pop_back(); ip; } else { reportError(X, currentToken, tokens[ip].line); return false; } } else { int prodIdx table.table[X][currentToken] - 1; if (prodIdx 0) { reportError(X, currentToken, tokens[ip].line); return false; } stack.pop_back(); auto rhs grammar.productions[prodIdx].rhs; // 逆序入栈保证栈顶是最左待处理符号 for (auto it rhs.rbegin(); it ! rhs.rend(); it) { if (*it ! ε) stack.push_back(*it); } } } return ip tokens.size(); }后面逆序入栈这段是关键推导时栈顶必须是最左边的待处理符号所以产生式右部要反着压栈。如果你正序入栈解析结果会整个颠倒——这一个 bug 能让你调试到怀疑人生。4.2 递归下降实现把产生式变成嵌套函数调用表驱动代码短、通用但项目主推的是递归下降解析。原因是递归下降解析器可以直接在递归函数里构建语法树节点不必额外维护符号栈和产生式栈结构std::unique_ptrASTNode Parser::parseExpr() { // expr → term expr_prime auto node std::make_uniqueASTNode(expr); node-children.push_back(parseTerm()); node-children.push_back(parseExprPrime()); return node; } std::unique_ptrASTNode Parser::parseExprPrime() { auto node std::make_uniqueASTNode(expr_prime); if (matchAndConsume(TokenType::PLUS)) { node-children.push_back(makeTokenNode(previous())); node-children.push_back(parseTerm()); node-children.push_back(parseExprPrime()); // 右递归处理左结合 } else if (matchAndConsume(TokenType::MINUS)) { node-children.push_back(makeTokenNode(previous())); node-children.push_back(parseTerm()); node-children.push_back(parseExprPrime()); } // 否则产生式应用 ε直接返回无子节点的 expr_prime return node; }parseExprPrime这里的右递归处理的是左结合运算符。很多人初学时会疑惑a b c明明是左结合的为什么产生式里用右递归原因是右递归能写成标准的 LL(1) 产生式等到语法树构建完成后再通过树形结构来恢复运算顺序——expr_prime递归展开会形成向左倾斜的树求值时天然是左结合。4.3 AST 遍历与树形输出解析器构建语法树之后ASTPrinter负责把树以直观的缩进形式打印到终端struct ASTNode { std::string label; // 节点名称如 expr / factor std::string value; // 叶节点的值如变量名 abc std::vectorstd::unique_ptrASTNode children; bool isLeaf() const { return children.empty(); } }; void ASTPrinter::print(const ASTNode* node, int depth) { std::string indent(depth * 2, ); if (node-isLeaf()) { std::cout indent node-label (node-value.empty() ? : ( node-value )) std::endl; } else { std::cout indent node-label std::endl; for (auto child : node-children) { print(child.get(), depth 1); } } }比如输入a b c * 2输出类似下面的结构program assign_stmt assign_stmt_prime expr term factor(IDENTIFIER: a) expr_prime PLUS() expr term factor(IDENTIFIER: b) expr_prime expr_prime ...这个树形的缩进输出是调试的利器——对比预期树和实际输出树你一眼能看出哪个嵌套层次错了。4.4 完整链路main 函数里发生了什么最后把整条链路串起来的 main 函数逻辑非常直白int main(int argc, char* argv[]) { // 1. 读入源码命令行参数或标准输入 std::string source readSource(argc, argv); if (source.empty()) { std::cerr 未读取到任何代码 std::endl; return 1; } // 2. 词法分析 Lexer lexer(source); auto tokens lexer.tokenize(); // 3. 初始化文法计算 FIRST/FOLLOW 集 Grammar grammar; auto first FirstFollow::computeFirst(grammar); auto follow FirstFollow::computeFollow(grammar, first); // 4. 构建预测分析表并检查冲突 LL1Table table; table.build(grammar, first, follow); if (table.hasConflict) { std::cerr 文法存在冲突无法继续 std::endl; return 2; } // 5. 递归下降解析得到语法树 Parser parser(tokens, grammar, table); auto ast parser.parseProgram(); if (!ast) { std::cerr 语法错误第 parser.getErrorLine() 行处退出 std::endl; return 3; } // 6. 打印语法树 ASTPrinter printer; printer.print(ast.get(), 0); return 0; }每一步都能独立查看中间产物——想检查 token 流在步骤 2 后打印想确认 FIRST/FOLLOW 集算对没有在步骤 3 后打印想验证分析表在步骤 4 后按行列打印。这种「每步可验证」的设计是这个实验项目最好的学习资产。5. 常见踩坑与排查清单三天调试血泪经验5.1 现象一运行就栈溢出程序直接崩溃原因文法里残留了左递归产生式递归下降解析时parseExpr无限自调用每一层调用消耗一块栈空间很快把栈挤爆。很多同学从复制教科书文法开始做起而教科书文法常常为了解释概念保留了左递归形式。解决手动将左递归转换成右递归转换方法就是前面代码里expr和expr_prime的分层写法。注意转换后产生式里出现了一个新的非终结符别忘记把它加入grammar.nonTerminals否则后面查表会直接映射到空表项报错信息会让你完全摸不着头脑。5.2 现象分析表构建时疯狂报「冲突」但没有一行我看得懂原因你的文法不是 LL(1) 文法。最常见的情况是提取公共左因子没做干净。解决别急着改代码先在纸上把有冲突的那条产生式和对应终结符圈出来用 FIRST 集去手动模拟推导过程找到「同一个终结符出现在两条路径的 FIRST 集里」的位置提取公共因子。项目的报错格式已经帮你定位到了非终结符和终结符的二元组剩下的就是纯手工文法术。在写你的文法之前养成先自测几条性质的习惯——每个非终结符的各个产生式右部的 FIRST 集两两不相交任何能推导出 ε 的非终结符的 FIRST 集和 FOLLOW 集不相交。这两条过了冲突基本不会出现。5.3 现象程序跑通但语法树输出缺了某个子树且毫无报错原因递归下降解析器匹配 ε 产生式时有「吞 token」问题。具体来说某个 parse 函数在遇到不属于它的 token 时应当立即返回空节点但你可能不小心多消费了一个 token导致整个语法树的边界错位。解决给每个 parse 函数加一条前置断言——进入函数时记录当前 token 下标函数返回时检查下标移动是否在预期范围内。这个调试手法我反复用每次都有效。5.4 现象解析a b c时没有报错但树的嵌套方向错了原因赋值号被设计成右结合但产生式写成了左递归形式。这是 LL(1) 文法的经典陷阱左结合运算符要写成右递归产生式但语法树求值的方向仍然要保持左结合。解决在语法树节点上加一个evalOrder字段求值时显式按中序排列而不是信任递归调用的先后次序。5.5 现象报错信息提示的行号永远是最后一行的行号原因Lexer 在读文件时没有正确累加行号最常见的情况是只检查了\n而没有同时处理 Windows 风格的\r\n换行。解决在词法分析的字符扫描循环里遇到\r\n或\n时都执行line并用一个lastCharWasCR标志避免\r\n被当成两行计算。这个小 bug 容易烦人但是排查很快——打印 token 流时查看每个 token 的 line 字段即可确认。6. 二次开发如何扩充成支持变量声明与布尔表达式的小型语言拿到这份代码后最常见的改造需求是添加新语法。以添加变量声明let x 10;为例我会按四条路径走先改文法再改 token然后改解析器最后回归验证。先看文法层。加两条产生式program → stmt_list stmt_list → stmt stmt_list | ε stmt → let IDENTIFIER ASSIGN expr SEMICOLON // 新增 | IDENTIFIER ASSIGN expr SEMICOLON对应在Grammar类初始化的productions里追加产生式把let关键字加到terminals把stmt加进nonTerminals。注意要让stmt取代原来program直接指向的位置否则无法在一个程序里写多条语句。再看 token 层。在TokenType枚举中加一个LET类型并在Lexer::tokenize()的标识符分支里做关键字匹配——常见做法是先按标识符切出来再查一个mapstring, TokenTypestatic const std::mapstd::string, TokenType keywords { {let, TokenType::LET}, // 未来加 if/while 也在这个表里扩展 }; // 识别完一个标识符后 auto it keywords.find(lexeme); token.type (it ! keywords.end()) ? it-second : TokenType::IDENTIFIER;接下来是解析器。新增一个parseStmt()函数在parseProgram中循环调用它因为多条语句在 LL(1) 下最简单的组织方式是右递归循环std::unique_ptrASTNode Parser::parseStmt() { if (matchAndConsume(TokenType::LET)) { auto node std::make_uniqueASTNode(let_stmt); node-children.push_back(makeTokenNode(previous())); node-children.push_back(makeTokenNode(consume(TokenType::IDENTIFIER))); consume(TokenType::ASSIGN); node-children.push_back(parseExpr()); consume(TokenType::SEMICOLON); return node; } // 原有赋值语句逻辑... }写到这里必须提醒解析器的matchAndConsume和consume都是带报错语义的如果直接调用consume把不匹配的 token 吞掉解析器会傻在原地。所以我一般会让consume在失败时抛一个内部异常外层 catch 之后统一转成带行号的语法错误——这个「内部异常中断 统一报错」的设计比在每个函数里判返回值干净得多。改完之后按目录里的test_parser.cpp模式补两组用例一组是合法性用例比如let x 1 2 * 3;解析后检查 AST 根节点是let_stmt另一组是错误用例比如let x 10;必须在第 1 行报错而不是崩溃。这一步不能省因为语法分析器的改动极易牵一发动全身——加一个新产生式很可能让原来的stmt_list的 FIRST 集和 FOLLOW 集发生连锁变化。等这些都跑通再回头看你的收获递增地扩充文法、保持每步可验证、用错误用例倒逼解析器健壮性——这套工作流比起直接学「如何写一个编译器」更能帮你理解语法分析的工程本质。我在自己做这个改造时最深的感受是过了新鲜劲之后真正有意思的不是写出新功能而是通过控制台里几十行树形输出亲眼看到「输入文本 - 抽象结构」这一层转换在眼前变得透明。希望这些拆解能帮到你动手试试跑一遍完整链路你会有不一样的体会。本文还有配套的精品资源点击获取