简介这份资源面向正在学习编译原理、需要完成语法分析实验的高校学生聚焦递归子程序法这一经典实现思路。内容围绕给定文法设计并实现语法分析程序展开要求基于词法分析识别出的单词进一步判定各类语法成分并按规则输出单词信息与语法成分名称适合作为课程实验的参考实现与对照样例。压缩包共2个文件包含1个cpp源码文件与1个doc实验说明文档整体约17KB源码可直接在CG实验平台运行验证文档则交代问题描述与输入输出约定。该资源在CG实验平台满分通过已有6110人学习说明其实现思路经过实际评测检验。读者可从中获取完整的递归下降分析框架、各语法成分的识别与输出组织方式以及实验平台提交时的格式处理细节便于对照自己的代码排查分析顺序与输出时机上的问题也可作为理解语法分析流程的入门参考。1. 语法分析实验到底在做什么从一段 C 代码说起很多人第一次打开编译原理课设的压缩包看到Lexer、Parser、AST这几个文件第一反应是“这不就是课本上那张状态转换图吗”然后照着抄一遍跑通一个12*3就交差。真正动手写才发现词法分析器吐出来的 token 流和语法分析器要的输入格式对不上递归下降写深了栈溢出写浅了左递归死循环。这份 C 版的语法分析实验资源解决的就是从“看得懂文法”到“跑得动分析器”之间那段没人细讲的路。它面向的是正在做编译原理课程设计、需要一份能编译能调试能改文法的参考实现的开发者也适合想补一遍手写递归下降和 LL(1) 表驱动两种路子的熟手。下面按“这东西怎么组织、怎么跑起来、怎么改文法、哪里容易翻车”的顺序拆。2. 工程结构与技术选型一个不依赖第三方库的 C 语法分析器骨架2.1 目录分层与各模块职责这份实验代码的组织方式很典型按编译前端流水线切分每个阶段一个目录互不越界。常见做法是下面这种结构具体文件名可能略有出入但职责划分基本一致syntax-analyzer/ ├── include/ │ ├── token.h # Token 类型定义与枚举 │ ├── lexer.h # 词法分析器接口 │ ├── ast.h # 抽象语法树节点定义 │ ├── parser.h # 语法分析器接口 │ └── error.h # 错误码与错误报告 ├── src/ │ ├── lexer.cpp # 手写词法扫描 │ ├── parser.cpp # 递归下降 预测分析表 │ ├── ast.cpp # AST 构建与打印 │ └── main.cpp # 命令行入口 ├── grammar/ │ └── expr.g # 文法规则文件可选供表驱动使用 ├── tests/ │ ├── valid/ # 合法输入样例 │ └── invalid/ # 错误输入样例 └── CMakeLists.txtinclude放接口src放实现grammar放文法描述tests放正反样例。这种分法最大的好处是改文法时只动grammar和parser.cpp词法层不用碰。我一般会先看token.h里的枚举因为它决定了整个分析器能识别哪些符号后面所有逻辑都围绕这个枚举展开。技术选型上这份代码只依赖 C 标准库没有引入任何第三方解析库。原因很直接语法分析实验的目的就是让你自己实现 FIRST 集、FOLLOW 集、预测分析表的构造用现成的库等于把要考的东西外包了。构建用 CMake最低 C11 即可std::vector、std::map、std::string撑起全部数据结构不需要额外配置。2.2 Token 定义与词法分析器接口整个分析链路的起点是 Token。token.h里通常长这样// include/token.h #pragma once #include string enum class TokenType { INT_LITERAL, // 整数字面量如 42 IDENTIFIER, // 标识符如 x、count PLUS, MINUS, STAR, SLASH, // 算术运算符 LPAREN, RPAREN, // 左右括号 ASSIGN, // 赋值 SEMICOLON, // 分号 END_OF_FILE, // 输入结束 UNKNOWN // 无法识别 }; struct Token { TokenType type; std::string lexeme; // 原始文本 int line; // 所在行号报错用 int column; // 所在列号 };TokenType用enum class而不是普通enum是为了避免枚举值污染外层命名空间这在多人协作改文法时能少踩一类重定义坑。Token里带line和column是后面错误报告能定位到具体位置的前提很多同学省掉这两个字段结果报错只能打印“语法错误”调试时等于黑匣子。词法分析器接口一般只暴露一个方法// include/lexer.h #pragma once #include vector #include token.h class Lexer { public: explicit Lexer(const std::string source); std::vectorToken tokenize(); // 一次性扫描全部 token private: std::string src_; size_t pos_ 0; int line_ 1; int col_ 1; char peek() const; char advance(); void skipWhitespace(); Token makeToken(TokenType type, const std::string lexeme); };tokenize()返回std::vectorToken把整个源文件一次性扫完而不是流式吐 token。这样做的好处是语法分析器可以随机向前看lookahead递归下降里判断分支时不用反复回退词法状态。代价是内存占用随源文件线性增长但对课程实验这种规模完全不是问题。peek()和advance()是手写扫描器的标准双指针套路skipWhitespace()单独抽出来方便后面加注释跳过逻辑。2.3 递归下降分析器的核心骨架语法分析器有两种常见实现递归下降和表驱动 LL(1)。这份代码以递归下降为主表驱动作为对照。递归下降的核心是每个非终结符对应一个函数函数内部按产生式右部依次匹配 token// src/parser.cpp节选 #include parser.h #include error.h // Expr - Term (( | -) Term)* std::unique_ptrAstNode Parser::parseExpr() { auto left parseTerm(); // 先解析一个 Term while (match(TokenType::PLUS) || match(TokenType::MINUS)) { TokenType op previous().type; // 记录运算符 auto right parseTerm(); // 解析右操作数 left std::make_uniqueBinaryNode(op, std::move(left), std::move(right)); } return left; } // Term - Factor ((* | /) Factor)* std::unique_ptrAstNode Parser::parseTerm() { auto left parseFactor(); while (match(TokenType::STAR) || match(TokenType::SLASH)) { TokenType op previous().type; auto right parseFactor(); left std::make_uniqueBinaryNode(op, std::move(left), std::move(right)); } return left; } // Factor - INT_LITERAL | IDENTIFIER | ( Expr ) std::unique_ptrAstNode Parser::parseFactor() { if (match(TokenType::INT_LITERAL)) { return std::make_uniqueNumberNode(previous().lexeme); } if (match(TokenType::IDENTIFIER)) { return std::make_uniqueIdentifierNode(previous().lexeme); } if (match(TokenType::LPAREN)) { auto expr parseExpr(); consume(TokenType::RPAREN, expected ) after expression); return expr; } throw ParseError(unexpected token: peek().lexeme, peek().line); }这段代码的关键点在while循环而不是if。Expr - Term (( | -) Term)*里的星号表示零次或多次用while匹配才能处理123这种连续运算。如果写成if123只会解析出12剩下3被当成错误这是递归下降最常见的翻车点之一。match()和consume()是辅助函数match(type)检查当前 token 是否为目标类型是则前进并返回 trueconsume(type, msg)强制要求当前 token 为目标类型否则抛ParseError并带上行号。previous()返回刚消费的 token用来取运算符类型。这套组合让每个解析函数的逻辑非常直白基本就是文法产生式的逐行翻译。std::unique_ptrAstNode和std::move的用法也值得注意。AST 节点用独占指针管理父节点持有子节点转移所有权时用std::move避免拷贝整棵子树。这在表达式嵌套很深时能明显减少内存开销也避免了手动delete的麻烦。2.4 预测分析表与 FIRST/FOLLOW 集表驱动部分通常放在parser.cpp的另一组函数里或者单独一个table.cpp。核心是构造一张二维表M[非终结符][终结符] - 产生式构造依据是 FIRST 集和 FOLLOW 集// 构造预测分析表的简化逻辑 void Parser::buildTable() { for (const auto prod : grammar_.productions) { // 对产生式 A - α把 α 的 FIRST 集填入 M[A][a] for (TokenType a : firstOf(prod.rhs)) { table_[prod.lhs][a] prod; } // 若 α 可推导出 ε则把 FOLLOW(A) 填入 M[A][b] if (nullable(prod.rhs)) { for (TokenType b : followOf(prod.lhs)) { table_[prod.lhs][b] prod; } } } }firstOf和followOf是集合计算函数nullable判断某个符号串能否推导出空串。这段逻辑对应课本上的表构造算法但实际写的时候容易在“可空产生式”上出错如果某个非终结符能推出 ε它的 FOLLOW 集必须填进表里否则遇到该非终结符后面跟的终结符时查表为空分析器直接卡死。我见过不少实现漏掉nullable分支结果文法里一加可选结构就崩。表驱动分析的主循环是标准的栈式匹配bool Parser::parseWithTable(const std::vectorToken tokens) { std::stackSymbol stk; stk.push(Symbol::endMarker()); stk.push(Symbol::nonTerminal(S)); // 开始符号 size_t idx 0; while (!stk.empty()) { Symbol top stk.top(); Token cur tokens[idx]; if (top.isTerminal()) { if (top.type cur.type) { stk.pop(); idx; } else return reportError(cur, top); } else { auto prod table_[top.name][cur.type]; if (!prod) return reportError(cur, top); stk.pop(); for (auto it prod.rhs.rbegin(); it ! prod.rhs.rend(); it) stk.push(*it); // 逆序压栈保证左部先匹配 } } return true; }逆序压栈是这里唯一需要记死的细节产生式右部从左到右匹配栈是后进先出所以必须从右往左压。写反了会导致第一个符号就匹配失败而且报错位置看起来莫名其妙。3. 从源码到可执行编译、运行与样例验证3.1 构建环境与编译命令这份代码用 CMake 管理标准流程三步走。先确认本机有cmake和g或clang版本要求不高C11 即可# 在项目根目录执行 mkdir -p build cd build cmake .. make -j4cmake ..读取根目录的CMakeLists.txt生成 Makefilemake -j4并行编译四个任务加快速度。编译产物通常是build/syntax-analyzer或build/bin/parser具体看CMakeLists.txt里add_executable的目标名。如果编译报错找不到头文件检查CMakeLists.txt里有没有include_directories(include)这是新手最容易漏的一行。Windows 下用 MinGW 的话命令一样只是生成器换成cmake -G MinGW Makefiles ..。用 Visual Studio 的话直接打开 CMake 项目即可不需要额外配置。3.2 命令行入口与输入方式main.cpp一般支持两种输入命令行参数传文件路径或者从标准输入读。典型用法# 方式一从文件读 ./syntax-analyzer ../tests/valid/expr1.txt # 方式二交互输入CtrlD 结束 ./syntax-analyzer 1 2 * (3 - 4)main.cpp里的逻辑很薄读入源码字符串构造Lexer调tokenize()再构造Parser调parse()最后根据返回值打印 AST 或错误信息。如果项目带 AST 打印功能合法输入会输出类似下面的树形结构Binary() ├── Number(1) └── Binary(*) ├── Number(2) └── Binary(-) ├── Number(3) └── Number(4)这个输出是验证分析结果对不对的最直接手段。很多人只看“没报错”就认为通过了但 AST 结构错了照样是错的比如运算符优先级搞反12*3被解析成(12)*3不打印树根本发现不了。3.3 用正反样例做回归验证tests/valid和tests/invalid两个目录是这份资源的实用价值所在。合法样例覆盖基本表达式、嵌套括号、多语句非法样例覆盖缺右括号、连续运算符、非法字符。跑一遍全部样例# 批量跑合法样例期望全部返回 0 for f in ../tests/valid/*.txt; do ./syntax-analyzer $f /dev/null 21 echo $f - $? done # 批量跑非法样例期望全部返回非 0 for f in ../tests/invalid/*.txt; do ./syntax-analyzer $f /dev/null 21 echo $f - $? done返回码约定一般是合法输入返回 0语法错误返回 1文件读取失败返回 2。这个约定写在main.cpp的return语句里改的时候要同步改测试脚本。批量跑的好处是改完文法后能快速确认没有回归比手动一个个敲输入可靠得多。提示非法样例的期望返回码因实现而异有的项目统一返回 1有的区分错误类型。跑之前先看main.cpp的返回值定义别拿自己的假设去套。4. 改文法、加节点二次开发时最常动的三处4.1 新增运算符的完整改动链路假设要给表达式加上取模%改动会横跨四个文件顺序不能乱。第一步在token.h的TokenType里加PERCENT第二步在lexer.cpp的扫描循环里识别%字符并生成对应 token第三步在parser.cpp的parseTerm()里把PERCENT加进while条件第四步如果文法文件expr.g存在同步更新产生式。漏掉任何一步都会出现“词法认得出、语法不认”或“语法认得出、词法不吐”的割裂状态。// lexer.cpp 中扫描运算符的分支节选 case %: tokens.push_back(makeToken(TokenType::PERCENT, %)); advance(); break;这段加在switch的运算符分支里和、-的处理并列。注意advance()的位置先取字符再前进还是先前进再取取决于peek()和advance()的具体实现改之前先读一遍这两个函数的语义别凭感觉写。4.2 AST 节点扩展与访问者模式加新语法结构比如if语句时AST 节点要跟着扩。常见做法是给AstNode加一个accept方法配合访问者模式这样打印、求值、类型检查可以各写一个 visitor不用改节点本身// include/ast.h节选 class AstVisitor { public: virtual void visit(BinaryNode) 0; virtual void visit(NumberNode) 0; virtual void visit(IfNode) 0; // 新增节点对应新增纯虚函数 virtual ~AstVisitor() default; }; class IfNode : public AstNode { public: IfNode(std::unique_ptrAstNode cond, std::unique_ptrAstNode thenBranch) : cond_(std::move(cond)), then_(std::move(thenBranch)) {} void accept(AstVisitor v) override { v.visit(*this); } private: std::unique_ptrAstNode cond_; std::unique_ptrAstNode then_; };加IfNode时AstVisitor要加一个纯虚函数所有已有 visitor 实现都得补上对应方法编译器会强制你补全不会漏。这是访问者模式在语法树场景下的最大好处新增节点时编译期就能定位所有需要改的地方而不是运行时才发现某个 visitor 没处理新节点。4.3 错误恢复从“遇错即停”到“跳过同步”原始实现遇到第一个语法错误就抛异常退出这对课程演示够用但真实场景下希望一次报告多个错误。常见做法是在consume失败时不直接抛而是记录错误、跳到同步 token比如分号或右括号继续解析下一段void Parser::synchronize() { advance(); // 先跳过当前错误 token while (!isAtEnd()) { if (previous().type TokenType::SEMICOLON) return; switch (peek().type) { case TokenType::IF: case TokenType::WHILE: case TokenType::RETURN: return; // 遇到语句起始关键字恢复解析 default: advance(); } } }previous().type SEMICOLON判断的是“刚跳过一个分号”说明上一条语句边界已过可以从这里重新开始。switch里的关键字是语句起始符遇到它们说明进入了新语句同样可以恢复。这套同步策略是恐慌模式恢复的简化版够用且好懂改的时候按自己的文法调整关键字列表即可。5. 避坑与排查语法分析实验里最容易翻车的五件事5.1 左递归导致栈溢出现象解析123时程序直接崩溃或卡死调用栈越来越深。原因文法写成Expr - Expr Term递归下降直接照抄parseExpr()第一行又调parseExpr()无限递归。解决把左递归改写成右递归加循环即Expr - Term (( | -) Term)*对应代码里用while而不是递归调用自身。这是递归下降的第一课改完记得重新跑一遍连续运算样例。5.2 预测分析表查空导致卡死现象表驱动模式下某些合法输入解析到一半栈不空也不前进程序挂起。原因某个非终结符可推导出 ε但构造表时漏了 FOLLOW 集填充查表返回空产生式主循环既没匹配也没压栈。解决检查buildTable()里nullable分支是否覆盖所有可空产生式打印 FIRST/FOLLOW 集和表内容逐格核对。我一般会在构造完表后加一段调试输出把每个非空格子打出来对照课本手算结果。5.3 Token 行号错位导致报错定位不准现象报错说第 3 行有错实际错误在第 5 行。原因skipWhitespace()里遇到换行只advance()没更新line_或者更新了line_没重置col_。解决把行号列号更新收敛到一个advance()函数里所有字符前进都走它换行时line_、col_1其余情况col_。别在多个地方各自维护行列号迟早对不上。5.4 文法文件与硬编码解析函数不同步现象改了expr.g里的产生式表驱动模式生效了递归下降模式还是老行为。原因递归下降的解析函数是手写的和文法文件是两套独立描述改一处不改另一处就分裂。解决要么以文法文件为唯一真相源递归下降函数只做对照参考要么在文法文件头部注释里写明“修改后需同步更新 parser.cpp 的 parseXxx 函数”。我倾向后者因为课程实验里递归下降才是重点文法文件更多是文档作用。5.5 智能指针误用导致重复释放现象程序退出时崩溃报 double free 或 heap corruption。原因AST 节点用std::unique_ptr管理但某处又手动delete了裸指针或者把同一个unique_ptr移动了两次。解决全链路统一用unique_ptr父节点构造时用std::move转移子节点所有权任何地方不再出现new配delete的裸指针组合。改完用 AddressSanitizer 跑一遍g -fsanitizeaddress -g ...能直接定位到重复释放的那一行。6. 二次开发的一个实用技巧用差分测试守住文法改动改文法最怕的不是改错是改完之后不知道哪里错了。递归下降和表驱动两套实现同时存在恰好给了我们一个低成本的验证手段同一批输入分别喂给两条路径比较 AST 结构或接受/拒绝结果是否一致。这叫差分测试在语法分析这种“同一文法多种实现”的场景里特别好用。具体做法是给main.cpp加一个--mode参数rd走递归下降ll1走表驱动然后写个脚本对tests/下所有样例跑两遍#!/bin/bash # diff-test.sh对比两种分析模式的结果 fail0 for f in tests/valid/*.txt tests/invalid/*.txt; do ./build/syntax-analyzer --mode rd $f /tmp/rd.out 21 rd_code$? ./build/syntax-analyzer --mode ll1 $f /tmp/ll1.out 21 ll1_code$? if [ $rd_code -ne $ll1_code ]; then echo MISMATCH: $f (rd$rd_code, ll1$ll1_code) fail1 fi done exit $fail脚本只比较返回码不比较 AST 文本因为两种实现的树打印格式可能不同强行对齐格式反而引入噪音。返回码一致说明“接受/拒绝”的判断一致这已经能抓住大部分文法改动引入的偏差。如果某个样例两边不一致先看是递归下降多接受了还是表驱动多接受了再回去查对应的产生式或表项定位速度比盲猜快得多。这个技巧的代价很低--mode参数只是在main.cpp里加一个分支差分脚本二十行不到。但它带来的收益是每次改完文法跑一遍心里有底。我早期做这类实验时习惯改完直接手动敲几个输入看看结果有一次把parseTerm的while误改成if手动测的样例恰好都是单个运算符没暴露问题交上去才被指出连续运算解析不全。从那以后我每次动文法或解析函数都强制先跑一遍差分脚本再手动验证宁可多花两分钟也不赌“这次应该没问题”。希望这个习惯也能帮到你。本文还有配套的精品资源点击获取