简介：面向编译原理课程学习者与需要完成语法分析实验的高校学生，压缩包提供了一份基于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::vector<Token> tokenize(); // 一次性返回全部 token private: std::string source_; size_t pos_ = 0; };这里有个设计取舍：它没有做「按需取 token」的惰性接口，而是先一次性把整个源码切完。对于实验项目这是合理的——语法分析阶段不需要关心 IO 性能，一次性切完反而方便后续调试时直接把 token 流打印出来核对。2.3 文法定义方式：用最小代码描述表达式语言这个项目内置的文法是个典型的表达式文法，支持赋值语句、加减乘除和括号。文法在 Grammar.h 里以产生式列表的形式组织：struct Production { std::string lhs; // 产生式左部，如 "expr" std::vector<std::string> rhs; // 产生式右部，如 {"term", "expr_prime"} }; class Grammar { public: std::vector<std::string> terminals; // 终结符集合 std::vector<std::string> nonTerminals; // 非终结符集合 std::vector<Production> productions; // 所有产生式 std::string startSymbol; // 开始符号 const std::vector<Production>& 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::map<std::string, std::set<std::string>> FirstFollow::computeFirst( const Grammar& grammar) { std::map<std::string, std::set<std::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::map<std::string, std::set<std::string>> FirstFollow::computeFollow( const Grammar& grammar, const std::map<std::string, std::set<std::string>>& first) { auto follow = std::map<std::string, std::set<std::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::map<std::string, std::map<std::string, int>> table; bool hasConflict = false; void build(const Grammar& grammar, const std::map<std::string, std::set<std::string>>& first, const std::map<std::string, std::set<std::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::vector<Token>& tokens, const LL1Table& table, const Grammar& grammar) { std::vector<std::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_ptr<ASTNode> Parser::parseExpr() { // expr → term expr_prime auto node = std::make_unique<ASTNode>("expr"); node->children.push_back(parseTerm()); node->children.push_back(parseExprPrime()); return node; } std::unique_ptr<ASTNode> Parser::parseExprPrime() { auto node = std::make_unique<ASTNode>("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::vector<std::unique_ptr<ASTNode>> 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()的标识符分支里做关键字匹配——常见做法是先按标识符切出来，再查一个map<string, TokenType>：static const std::map<std::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_ptr<ASTNode> Parser::parseStmt() { if (matchAndConsume(TokenType::LET)) { auto node = std::make_unique<ASTNode>("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 集发生连锁变化。等这些都跑通，再回头看你的收获：递增地扩充文法、保持每步可验证、用错误用例倒逼解析器健壮性——这套工作流比起直接学「如何写一个编译器」更能帮你理解语法分析的工程本质。我在自己做这个改造时最深的感受是，过了新鲜劲之后真正有意思的不是写出新功能，而是通过控制台里几十行树形输出，亲眼看到「输入文本 -> 抽象结构」这一层转换在眼前变得透明。希望这些拆解能帮到你，动手试试跑一遍完整链路，你会有不一样的体会。本文还有配套的精品资源，点击获取
简介：面向编译原理课程学习者与需要完成语法分析实验的高校学生，压缩包提供了一份基于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::vector<Token> tokenize(); // 一次性返回全部 token private: std::string source_; size_t pos_ = 0; };这里有个设计取舍：它没有做「按需取 token」的惰性接口，而是先一次性把整个源码切完。对于实验项目这是合理的——语法分析阶段不需要关心 IO 性能，一次性切完反而方便后续调试时直接把 token 流打印出来核对。2.3 文法定义方式：用最小代码描述表达式语言这个项目内置的文法是个典型的表达式文法，支持赋值语句、加减乘除和括号。文法在 Grammar.h 里以产生式列表的形式组织：struct Production { std::string lhs; // 产生式左部，如 "expr" std::vector<std::string> rhs; // 产生式右部，如 {"term", "expr_prime"} }; class Grammar { public: std::vector<std::string> terminals; // 终结符集合 std::vector<std::string> nonTerminals; // 非终结符集合 std::vector<Production> productions; // 所有产生式 std::string startSymbol; // 开始符号 const std::vector<Production>& 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::map<std::string, std::set<std::string>> FirstFollow::computeFirst( const Grammar& grammar) { std::map<std::string, std::set<std::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::map<std::string, std::set<std::string>> FirstFollow::computeFollow( const Grammar& grammar, const std::map<std::string, std::set<std::string>>& first) { auto follow = std::map<std::string, std::set<std::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::map<std::string, std::map<std::string, int>> table; bool hasConflict = false; void build(const Grammar& grammar, const std::map<std::string, std::set<std::string>>& first, const std::map<std::string, std::set<std::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::vector<Token>& tokens, const LL1Table& table, const Grammar& grammar) { std::vector<std::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_ptr<ASTNode> Parser::parseExpr() { // expr → term expr_prime auto node = std::make_unique<ASTNode>("expr"); node->children.push_back(parseTerm()); node->children.push_back(parseExprPrime()); return node; } std::unique_ptr<ASTNode> Parser::parseExprPrime() { auto node = std::make_unique<ASTNode>("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::vector<std::unique_ptr<ASTNode>> 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()的标识符分支里做关键字匹配——常见做法是先按标识符切出来，再查一个map<string, TokenType>：static const std::map<std::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_ptr<ASTNode> Parser::parseStmt() { if (matchAndConsume(TokenType::LET)) { auto node = std::make_unique<ASTNode>("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 集发生连锁变化。等这些都跑通，再回头看你的收获：递增地扩充文法、保持每步可验证、用错误用例倒逼解析器健壮性——这套工作流比起直接学「如何写一个编译器」更能帮你理解语法分析的工程本质。我在自己做这个改造时最深的感受是，过了新鲜劲之后真正有意思的不是写出新功能，而是通过控制台里几十行树形输出，亲眼看到「输入文本 -> 抽象结构」这一层转换在眼前变得透明。希望这些拆解能帮到你，动手试试跑一遍完整链路，你会有不一样的体会。本文还有配套的精品资源，点击获取