C++实现语法分析实验指南：递归下降与LL(1)表驱动从零到可运行

简介：面向编译原理课程的语法分析实验（C++版），提供可运行的完整工程实现。设计采用递归子程序法，自上而下分析词法阶段识别出的单词序列，能识别常量说明、变量说明等各类语法成分；输出遵循testfile.txt读取、output.txt写出的评测约定，既按行输出每个单词信息，又在指定语法成分分析结束时另起一行输出对应名字，如“<常量说明>”，同时对预读内容不输出的边界情况做了妥善处理，代码在CG实验平台满分通过。压缩包内共2个文件：cpp源文件是完整的语法分析器实现，可直接编译运行；doc文档包含实验问题描述与输入输出要求，方便理解设计背景与细节。整个压缩包仅17KB，轻量便携。目前已有6107人学习下载，适合正在完成语法分析作业的高校学生，也可供需要参考递归下降解析实现与自动评测设计的开发者学习使用。

1. 语法分析实验到底在做什么：一个 C++ 实现最少要迈过哪几道坎

语法分析实验看起来只是编译原理课表上的一行，真正动手用 C++ 实现时，大部分时间会花在和文法本身搏斗：左递归、回溯、FIRST/FOLLOW 集合，这些概念在纸上推演很顺利，落到代码里却全是边界问题。这个实验的交付物通常不是高大上的编译器，而是一个能读入 Token 流、按文法规则输出语法树的控制台程序；它要解决的痛点很具体——把词法阶段产生的线性 Token 流变成有结构的树，让后续语义分析和代码生成有话可说。适合做这件事的，是正在上编译原理课、需要交实验报告的同学，也包括在公司里想做小 DSL 解析器、但不想一上来就引入 ANTLR 的 C++ 工程师。下面按最容易复现的路径走：先用递归下降写出能跑的最小版本，再补一个表驱动 LL(1) 对照，最后给出我在 C++ 里踩过的坑和验证手段。整个方案只依赖标准库，VSCode 配好 C/C++ 环境后，单文件即可编译运行，不需要额外依赖。

2. 选型关：递归下降还是表驱动 LL(1)，哪条路上手更快

这个实验的起点不是写代码，而是选算法。常见做法是二选一：手写递归下降，或做表驱动 LL(1)。不少实验报告把两种方案各写一遍，但讲不出为什么这么选，导致测试时一换输入就翻车。我先给结论：如果老师只要求“用 C++ 实现语法分析”，选递归下降；如果题目明确写了“预测分析”“LL(1) 分析表”，选表驱动。前者代码直观、调试方便，后者逻辑统一、适合程序化扩展，但必须先老老实实算清 FIRST/FOLLOW。

2.1 递归下降：直观但背了左递归的债

递归下降的写法是给每个非终结符准备一个函数，函数体照抄产生式右部。遇到终结符就匹配 Token，遇到非终结符就调用对应函数。它天然是自顶向下分析，代码执行顺序和语法树的自上而下构建顺序一致，所以打印推导过程、在验收现场讲思路都很方便。我们课程里最常见的验收姿势就是让同学对着输入表达式，手写出“先展开哪个非终结符、再匹配哪个终结符”，递归下降代码几乎能把这种推导过程原样打印出来。

递归下降的代价是文法必须满足 LL(1) 条件，其中最常被忽略的是左递归。如果文法写成E -> E + T | T，代码里也写成void expression(){ expression(); }，程序会在几毫秒内把调用栈打爆。这种崩溃不是算法难题，而是预处理没有做。任何递归下降实现的第一步，都是把左递归消除掉，尤其要注意间接左递归，比如A -> B ...、B -> A ...这种绕一圈又回到自己的情况。手工消除左递归虽然费一点时间，但只做一次，效果比在代码里打补丁可靠得多。

2.2 表驱动 LL(1)：一本正经但计算 FIRST/FOLLOW 费时间

表驱动做法把文法分析表当成数据，驱动循环当成代码。分析表以非终结符为行、终结符为列，格子里放产生式右部。循环每次只看栈顶符号 X 和当前输入符 a，查表拿到右部，逆序压栈。这样做的好处是修改文法只改表，执行逻辑一行都不用动；坏处是建表本身要精确计算 FIRST/FOLLOW，任何一个集合出错，表里就会出现空格子，运行时查不到条目就开始乱报错。

对作业规模的文法，我一般不建议写自动建表器。手动算一遍 FIRST/FOLLOW 并硬编码进std::map，半小时搞定；自动建表器涉及闭包计算、ε 传播、集合变化检测，写起来本身就是另一套 bug 来源，而且训练调试成本远高于手算。如果实验报告里想体现“自动化”，可以单独写一个生成器，把生成的表打印成和手写表相同的格式，核心分析器仍然只消费这张表，不要在驱动循环里临时去算集合。

2.3 最小 C++ 骨架：Token、Parser、Table 三类对象怎么切

我见过不少同学的实验代码只有一个main.cpp，两百行全部塞在main()里。语法分析器虽然小，但至少要分的角色有三个：Token 流、Parser 主体、分析表（表驱动版）。下面这个骨架是我在最小实验里常用的：

#include <string> #include <vector> #include <map> struct Token { enum Type { ID, NUM, PLUS, STAR, LPAREN, RPAREN, END }; Type type; std::string lexeme; }; class Parser { public: explicit Parser(const std::vector<Token>& tokens) : tokens_(tokens) {} bool parse(); private: const std::vector<Token>& tokens_; size_t pos_ = 0; Token peek() const { return tokens_[pos_]; } Token advance() { return tokens_[pos_++]; } bool match(Token::Type t) { if (peek().type == t) { advance(); return true; } return false; } void error(const std::string& msg) const; };

这段代码有几个 C++ 细节值得说。Parser持有的是 Token 向量的引用，而不是拷贝整个向量，能省掉一次大内存移动；代价是调用方必须保证tokens_的生命周期比 Parser 长，否则引用悬空，运行时会得到一堆乱码。peek和advance是所有分析逻辑的咽喉，一个只看不动，一个推进读头，后续递归下降和表驱动版本都在它们之上做文章。match是一个语法糖，匹配成功就吃掉 Token 并返回 true，失败则不动读头。

把 Token、Parser、Table 分开之后，后面切换算法时 main 函数里的改动不超过三行。词法分析若由课程提供，只留parser.cpp；否则就按lexer.h、parser.h、main.cpp三份文件放。别把词法和语法写进同一个类，否则排错时你会同时面对两组问题，谁是谁都分不清。

3. 用 C++ 写一个能跑的最小递归下降分析器：核心函数与调用链

这章开始动手。为了让所有人都能直接复现，我用最经典的表达式文法讲。原始文法通常是：

E -> E + T | T T -> T * F | F F -> ( E ) | id

这是大多数编译原理课的第一个验收对象。但自顶向下分析不能直接吃左递归，需要先做一步等价变换。

3.1 文法：消除左递归之后的表达式文法与 FIRST/FOLLOW

消除左递归后的文法变成：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

其中 ε 代表空串。这份文法是典型的 LL(1) 文法，FIRST 和 FOLLOW 集合我直接给出来，写代码时对照着用：

表格里$是输入结束符，)出现在 FOLLOW 集合里是因为F -> ( E )这个产生式。很多同学在这里卡住：为什么T'的 FOLLOW 里有+？因为E' -> + T E'中，T后面跟着E'，而E'的 FIRST 集合里有+。这套推导关系如果没理清，后面表驱动版本的分析表一定会漏条目。

3.2 递归下降函数：expression、term、factor 怎么协作

递归下降的核心就三个函数：expression、term、factor。调用关系是 expression 调 term，term 调 factor，对应文法层级里加法低于乘法、乘法低于括号。下面这个实现直接对应消除左递归后的产生式，每行都能在文法里找到出处：

bool Parser::parse() { expression(); return peek().type == Token::END; } void Parser::expression() { term(); // 先解析优先级更低的层？这里其实是先解析乘法层 exprPrime(); // 再处理加减 } void Parser::exprPrime() { while (peek().type == Token::PLUS) { advance(); term(); } } void Parser::term() { factor(); termPrime(); } void Parser::termPrime() { while (peek().type == Token::STAR) { advance(); factor(); } } void Parser::factor() { Token t = peek(); if (t.type == Token::ID || t.type == Token::NUM) { advance(); } else if (t.type == Token::LPAREN) { advance(); expression(); if (peek().type != Token::RPAREN) { error("factor 位置缺少右括号"); } advance(); } else { error("factor 位置出现非法 Token"); } }

逻辑说明：exprPrime()用while循环而不是递归，因为文法里E' -> + T E'是右递归，写成循环后输入深一点也不会把 C++ 调用栈压爆。expression()先调term()，是为了让加减法的结合方向正确，同时保证乘除法先于加减法完成匹配。factor()处理括号时，吃掉左括号后递归调用expression()，等返回时必须确认下一个 Token 是右括号；这一步是新手最容易漏的，漏掉后输入(id+id会被当成合法表达式。

参数说明：error函数建议带行号和列号，比如error("第 1 行第 6 列：factor 位置出现非法 Token")。只打印一句“Error”的报错在验收时很难看，也说明不了问题。Token 里如果没有line和col字段，词法分析阶段就要补上。

3.3 把推导过程输出成实验报告要的东西

实验验收通常不是问“对还是错”，而是看结构。我的做法是让每个函数返回一个语法树节点，主程序把它打印成带缩进的树形文本：

struct ASTNode { std::string name; std::vector<ASTNode*> children; ~ASTNode() { for (auto* c : children) delete c; } }; void printAST(const ASTNode* n, int depth = 0) { for (int i = 0; i < depth; ++i) std::cout << " "; std::cout << n->name << "\n"; for (const auto* c : n->children) printAST(c, depth + 1); }

ASTNode持有子节点指针，析构时统一 delete。实验代码规模小，裸指针加手动管理完全够用；如果以后要把代码搬进更大的工程，记得把裸指针换成std::unique_ptr，避免拷贝语义出错。printAST用缩进表示父子关系，打印出来就是一棵树的侧视图，配合推导序列截图，验收时一眼就能看懂。

你还可以选择更省事的方案：把 AST 打印成括号字符串，比如(E (T (F id)) (E' + (T (F id))))。这种输出不需要管理任何内存，也方便和表驱动版本做diff对比，我后面就是用这个方式做回归。

3.4 主循环：从词法 Token 到语法结果的一站式 main

词法分析如果之前实验已经交过，直接复用那部分 Token 输出。要注意 Token 必须带line和col字段，语法分析的报错信息才能定位到行号。主函数长这样：

int main(int argc, char** argv) { if (argc < 2) { std::cerr << "用法: " << argv[0] << " \"表达式\"\n"; return 1; } std::vector<Token> tokens = tokenize(argv[1]); // 词法分析函数，返回 Token 流 Parser parser(tokens); bool ok = parser.parse(); std::cout << (ok ? "语法正确" : "语法错误") << "\n"; return ok ? 0 : 1; }

tokenize函数把字符串拆成 Token 向量，Parser 只依赖 Token 流。这里有个容易忽略的点：命令行传入的*会被 Linux 的 bash 展开成文件名列表，所以测试时要把参数用单引号包住，比如./parser 'id + id * id'。如果实验中改成从文件读输入，就把 argv[1] 换成文件名，Parser 部分完全不用动。

4. 表驱动 LL(1) 对照实现：一张预测分析表与一个 while 循环

递归下降能跑通之后，再写表驱动版本会轻松很多，因为文法、Token、主程序都是现成的，只换核心驱动逻辑。这个版本也更接近“自动机”的感觉：一次查表、一次入栈、一次匹配，重复直到结束。

4.1 预测分析表的 C++ 表示：“非终结符 + 终结符”映射到产生式

表驱动版本把分析表当成数据。下面这个std::map是我把 3.1 节的文法逐条誊进 C++ 的产物：key 是“非终结符、终结符”对，value 是产生式右部；ε 用字符串占位，入栈时跳过：

using Production = std::vector<std::string>; using TableKey = std::pair<std::string, std::string>; const std::map<TableKey, Production> table = { {{"E", "id"}, {"T", "E'"}}, {{"E", "("}, {"T", "E'"}}, {{"E'", "+"}, {"+", "T", "E'"}}, {{"E'", ")"}, {"ε"}}, {{"E'", "$"}, {"ε"}}, {{"T", "id"}, {"F", "T'"}}, {{"T", "("}, {"F", "T'"}}, {{"T'", "*"}, {"*", "F", "T'"}}, {{"T'", "+"}, {"ε"}}, {{"T'", ")"}, {"ε"}}, {{"T'", "$"}, {"ε"}}, {{"F", "id"}, {"id"}}, {{"F", "("}, {"(", "E", ")"}}, };

这不是唯一写法，也可以把表存成std::vector<std::vector<int>>，用行号列号做索引，查询更快但可读性差。我选std::map是因为它能自解释：一眼能看出E遇到id时应该展开成T E'。整个算法只用到了 STL 的map和vector，现代 C++ 编译器都能直接编译。唯一要注意的是查询时别用operator[]，具体原因放在避坑章讲。

4.2 表驱动主循环：栈顶符号、输入符号和预测表的三角关系

主循环代码不复杂，但每一步都必须精确：

bool tableDriveParse(const std::vector<Token>& tokens) { std::vector<std::string> stk = {"$", "E"}; size_t ip = 0; auto terminalOf = [](const Token& t) -> std::string { switch (t.type) { case Token::ID: return "id"; case Token::PLUS: return "+"; case Token::STAR: return "*"; case Token::LPAREN: return "("; case Token::RPAREN: return ")"; case Token::END: return "$"; } return "?"; }; while (stk.back() != "$") { std::string X = stk.back(); std::string a = terminalOf(tokens[ip]); if (X == a) { stk.pop_back(); ++ip; } else if (isTerminal(X)) { std::cerr << "语法错误: 期望 " << X << "，实际是 " << a << "\n"; return false; } else { auto it = table.find({X, a}); if (it == table.end()) { std::cerr << "语法错误: 在 " << X << " 遇到 " << a << "，表项为空\n"; return false; } stk.pop_back(); const Production& rhs = it->second; for (auto rit = rhs.rbegin(); rit != rhs.rend(); ++rit) { if (*rit != "ε") stk.push_back(*rit); } } } return ip == tokens.size(); }

isTerminal自己实现，判断X是否是id/+/*/(/)之一。循环里最重要的三行是：查表、弹栈、逆序压栈。逆序压栈很关键，因为栈是后进先出，先压最后一个符号，才能让产生式右部的最左元素在下一步出栈，这正是 LL(1) 的“最左推导”。第一次写漏逆序的话，输出会神秘地乱掉，你会花一下午在本来不该出错的地方找 bug。

报错信息这里只做了最短路径：查到空条目直接返回 false。课程验收时老师有时会给id +这类错误表达式，报错至少要指明“在哪一行、期望什么、实际见到什么”。如果 Token 里有line和col，把这两个值打进去，报告立刻专业一个档次。

提示：表驱动版和递归下降版必须共用同一个 Token 结构。词法阶段输出的 Token 类型名保持一致，否则两边的terminalOf映射要写两遍，且很容易不一致。

4.3 递归下降 vs 表驱动：运行同一个 case 看差异

拿id + id * id跑一遍。递归下降版会自然从 expression 展开到 term、factor；表驱动版从栈顶 E 出发，不断查表展开。如果你在两个版本的每个 factor 返回点打印当前节点名，输出的最左推导轨迹几乎一致，这个一致性就是“两种算法描述同一文法”的直观证据。

实际操作中，我会把两个版本编译成独立可执行文件，parser_recursive和parser_table，喂同一个输入，然后把输出拉到diff里对比。它们唯一的差异应该只在报错措辞上。如果正确路径的输出都不一样，一定是某一版的 FIRST/FOLLOW 或表项抄错了。用diff提前暴露这种问题，比在验收现场被老师发现要从容得多。

5. 语法分析实验避坑指南：六个让 C++ 版实验翻车的真实场景

这一章的价值来自我亲眼见过和踩过的坑。每个场景都按“现象 → 原因 → 解决”的顺序写，你可以直接拿来做排查清单。

5.1 场景一：自动 FIRST/FOLLOW 计算器死循环

现象：我写了一个自动构建 FIRST/FOLLOW 集合的函数，运行时 CPU 占用直接拉满，终端卡死，Ctrl+C 都不好使。

原因：while 循环条件写成“本轮集合有变化就继续”，但循环体里直接改了集合，没有保存循环开始前的快照。更糟的是我一边算 FIRST 一边算 FOLLOW，把依赖关系算成交叉循环，导致集合大小永远在变。

解决：先算完 FIRST 再算 FOLLOW；每轮循环开头把所有集合的size()之和存成一个旧值，结束对比，没有变化就 break。同时把文法里所有空产生式单独摘出来先处理，避免 ε 传播被遗漏。这个顺序是写自动建表器最不容易翻车的姿势。

5.2 场景二：左递归文法直接写进递归下降函数，堆栈溢出

现象：程序编译顺利通过，一运行就“段错误 (核心已转储)”，用 gdb 看调用栈，发现expression函数重复出现几千层，直到栈空间耗尽。

原因：没有消除左递归。E -> E + T直接翻译成expression()里第一步调用expression()，和死循环没有区别，每次调用栈帧只多不少，最终必然溢出。

解决：先把文法改写成 LL(1) 形式，再写递归函数。如果不想手工改写，那这一题直接改用表驱动版本，因为只要预测分析表构造正确，左递归在表里表现为同一条产生式被反复压栈，至少不会段错误。最怕的组合就是“递归下降 + 左递归”，它俩一见面就是经典崩溃。

5.3 场景三：C++ 关键字被当成文法符号名

现象：代码里把非终结符命名为class，终结符命名为new，编译器直接报出一串红色错误，还看不懂为什么全是“expected identifier”。

原因：C++ 保留字不能被用作代码里的标识符。

解决：让文法符号和 C++ 标识符彻底解耦。非终结符用ExprPrime、TermPrime这种长名字，终结符用TOKEN_NEW、TOKEN_DELETE。写在std::map里的字符串键不受 C++ 标识符规则限制，比如table[{"F", "new"}]完全合法，因为"new"是字符串字面量，不是代码标识符。

5.4 场景四：map 查询用了 operator[]，表被神秘插入空条目

现象：表驱动解析器运行时报“表项为空”，但我明明在初始化列表里把每一条都写全了。更诡异的是，跑着跑着table.size()竟然变大了。

原因：代码里为了省事写了auto rhs = table[{X, a}];。std::map::operator[]在键不存在时会插入一个默认值，然后返回引用，于是每次查询失败都会往表里写一条空记录，表越来越臃肿，语义完全失控。

解决：查询统一用find，先判断迭代器是否等于end()，再取it->second。operator[]只用于“确定要写入”的场合，分析阶段绝不能用。这个坑在 C++ 里第一次踩到会非常困惑，因为它会让问题表现成“文法算错”，而不是“代码写错”。

5.5 场景五：输入末尾没有检查 END，缺操作数被当成合法语法

现象：输入id+，控制台先打印一行“语法错误”，紧接着又打印“语法正确”。有的版本甚至只打印“语法正确”，因为 error 函数只输出信息但没有让 parse 返回 false。

原因：error()函数只打印文本，没有把解析器状态置为失败；parse()返回时只检查非终结符是否展开完毕，没有看输入指针是否越过最后一个 Token。于是exprPrime()处理完+之后，term()尝试解析一个 factor 时遇到 END，打印了错误，但调用链返回后 parse 主流程忽略了这个错误。

解决：parse()结尾必须检查peek().type == Token::END，并且error()要么抛出异常，要么把内部一个bool hasError_置位并在 parse 返回值里反映。两个条件缺一不可。表驱动版本同样要检查ip == tokens.size()才能返回 true。

5.6 场景六：实验报告和代码不一致，验收被追问就翻车

现象：报告里写“实现了错误恢复功能，遇到非法输入能跳过错误 Token 继续分析”，演示时故意输入一个错误表达式，程序直接退出且没有任何恢复行为。

原因：实验报告在代码截图之后又改过，或者报告是从模板里抄的，代码和文字各说各话。

解决：先固定验收用例，再固定代码，最后写报告。把测试用例列表放进报告附录，包含正确输入和错误输入各两组，截图里的输出必须和当前代码行为完全一致。这个习惯还能防止期末复习时对着两份对不上的材料发呆，也算一种后悔药。

6. 把实验变成可复现的小工程：一行命令跑完整轮回归

递归下降和表驱动两个版本都跑通之后，最值得做的事不是继续加功能，而是把验证自动化。语法分析器这种程序，输入一变就可能触发边界问题，手动敲几组用例根本覆盖不全。

6.1 一个最小的测试脚本，把输出拉回到可核对的状态

#!/bin/bash set -eu cases=("id" "id+id" "id*id" "(id+id)*id" "id++id" "") for c in "${cases[@]}"; do echo "=== [$c] ===" ./parser "$c" > /tmp/parser_out.txt 2>&1 code=$? echo "exit=$code" cat /tmp/parser_out.txt echo done

脚本把所有验收用例跑一遍，每个用例的退出码和输出都会打印。set -eu让脚本在某个命令失败时立刻退出，避免后面用例被吞掉。空字符串用例要放在变量里变成""再传给 parser，而不是不传参，否则程序收到argc==1直接越界，测的根本不是你想要的空输入。

6.2 错误注入三连：验证错误处理而不是只验证正确路径

./parser "id+" && echo "应报错却通过" ./parser "(id+id" && echo "应报错却通过" ./parser "id id" && echo "应报错却通过"

这三个用例分别检验缺右操作数、缺右括号、相邻非法 Token 三种错误路径。语法分析器如果在这种输入下崩溃、死循环或者“语法正确”地退出，问题比正确路径跑不通更严重。错误处理的质量决定实验分数的上限，报告里“程序能发现错误”和“程序发现错误后能给出准确定位”是完全不同的评价档次。

6.3 C++ 工程化的三个小动作：unique_ptr、-Wall、按文法改表

第一，AST 节点别裸new，换成std::unique_ptr<ASTNode>，析构时自动回收整棵子树，省掉一整类内存泄漏问题。第二，编译命令固定为g++ -std=c++11 -Wall -Wextra -g main.cpp -o parser，-Wall能查出绝大多数漏了 return 的路径，别在 IDE 里能跑就假装它没警告。第三，拿到新文法先翻译成分析表，再改驱动循环或递归函数，优先让数据改变，少让代码改变。这三条做完，代码质量已经超过一半同学。

我最后一次做这组实验时，在测试脚本里把空字符串用例写成了裸字符串，漏了一个 shell 引号，结果程序收到argc==1直接越界。这种和文法无关的边界问题，恰恰是实验里最耗时间的部分。从那以后，我所有入口函数的第一行都是参数个数检查，第二行才是业务逻辑。希望这套跑通递归下降、表驱动和回归测试的做法，能帮你们把时间花在真正的语法分析上，而不是无穷无尽的段错误地狱，希望帮到你。

本文还有配套的精品资源，点击获取