简介：面向编译原理课程中的语法分析实验，这是一份采用C++实现的递归子程序法分析程序，适合正在完成相关作业的高校学生，也适合想对照自动评测要求检查自己实现的开发者。程序基于词法分析输出的单词序列，按给定文法递归下降识别常量说明、表达式、语句等各类语法成分，并只在指定成分分析结束前另起一行输出该语法成分的名字，对预读情况不做多余输出，完整契合testfile与output文件的评测规范。压缩包内共2个文件，包含可直接编译运行的cpp源代码，以及doc格式的实验问题描述文档，整体大小仅17KB，代码集中、长度可控，方便阅读和二次修改。目前已有6107人学习下载。作者在CG实验平台获得满分通过，说明其对输出格式、单词顺序和边界条件的处理都较为严谨，既是一份可直接运行的完整方案，也可作为调试思路和实验报告撰写的参考，能帮助理解递归下降分析的整体流程。
1. 语法分析实验在编译原理课程里是最容易让人“卡住”的一环：词法分析还能照猫画虎，一到语法分析就要面对文法、FIRST/FOLLOW集、递归下降还是表驱动这些选择。用 C++ 写一份语法分析实验，不只是为了交作业，更是把“上下文无关文法如何驱动一个真实的解析过程”亲手拆开。这篇文章会沿着“文法设计 → 手写递归下降 → 用生成器对比 → 踩坑 → 进阶错误恢复”的顺序，给你一条能在自己机器上跑通的路。不管你是第一次接触编译原理的本科生，还是想快速搭一个表达式解析器的C++开发，下面这些步骤都直接可复现。
2. 语法分析的核心：文法设计与LL(1)判定
2.1 词法分析结束后，语法分析器到底拿到什么
词法分析器把源代码字符流切成一个个token，但token之间的组合规则完全由语法分析器负责。语法分析器的输入是一片token序列，输出是一棵语法树（或者至少是一次合法性判定）。比如输入12 + 5 * 3，词法分析给出NUM(12) PLUS NUM(5) MUL NUM(3)，语法分析器需要根据文法确定：5 * 3先结合成乘积，再与12相加。这个优先级和结合性不是写死代码，而是由文法结构决定的。
常见做法是先用BNF写出一套上下文无关文法，然后决定用自顶向下的递归下降，还是自底向上的LR分析器。C++实验里，前者代码直观、适合手写，后者通常用生成器（如bison）来完成。无论选那条路，文法本身必须无左递归、无公共前缀，才有资格进入LL(1)分析表的构建流程。
2.2 用BNF描述一个最简单的算术表达式语言
以四则运算加括号为例，原始文法长这样：
E -> E + T | E - T | T T -> T * F | T / F | F F -> (E) | NUM这是标准教科书写法，它已经天然体现了优先级：E通过T、T通过F强制约束了乘除先于加减。但问题是，E和T都包含直接左递归。递归下降分析器遇到E -> E + T时，函数parseE会先调用自己，无限递归下去直到栈溢出。所以实验里第一步不是写代码，而是消除左递归。
消除后的等价文法：
E -> T E' E' -> + T E' | - T E' | ε T -> F T' T' -> * F T' | / F T' | ε F -> (E) | NUM这里ε代表空串。E'和T'不断吸收同优先级的右结合？不，这里其实是左结合的实现——当解析到12 + 5 + 3时，T先吃掉12，然后E'读+ 5，继续递归时E'再读+ 3，在代码里用循环或递归构建左结合节点。理解这一点，后面写代码时不会把AST方向搞错。
2.3 手算FIRST集与FOLLOW集，判断是不是LL(1)
LL(1)要求每个非终结符的候选产生式两两之间，FIRST集不相交；同时，若有空产生式，该非终结符的FOLLOW集也不能与任何候选的FIRST集相交。实验报告里必须包含这四个集合的计算过程，否则老师一问“你怎么知道这个文法能递归下降”，答不上来就是白做。
先算FIRST：
FIRST(F) = { ( , NUM } FIRST(T') = { * , / , ε } FIRST(T) = FIRST(F) = { ( , NUM } FIRST(E') = { + , - , ε } FIRST(E) = FIRST(T) = { ( , NUM }FOLLOW集需要从头推导。初始FOLLOW(E) = { $ }，因为输入结束符$属于起始非终结符的FOLLOW。然后看产生式F -> (E)，括号右部之后的)要加入FOLLOW(E)；E' -> + T E'，E'在产生式末尾，所以FOLLOW(E')包含FOLLOW(E)；T后跟E'，所以FOLLOW(T)包含FIRST(E')去除ε，即+和-，又因为E'可空，FOLLOW(T)还要包含FOLLOW(E)。逐条算完：
FOLLOW(E) = { $ , ) } FOLLOW(E') = { $ , ) } FOLLOW(T) = { + , - , $ , ) } FOLLOW(T') = FOLLOW(T) = { + , - , $ , ) } FOLLOW(F) = FIRST(T') 去除ε ∪ FOLLOW(T) = { * , / , + , - , $ , ) }对照产生式：E'有两个非空候选+ T E'和- T E'，它们的FIRST分别为{+}和{-}，不相交；空候选的FOLLOW是{$}，也不和{+}/{-}相交。T'同理。所以这个文法是LL(1)的，适合手写递归下降。
2.4 为什么我劝你从递归下降而不是从LR开始
很多学校的实验要求用yacc/bison，但如果你连递归下降都没写过，直接上生成器会变成“调工具”而不是“学原理”。手写递归下降让你把每个非终结符变成一个C++函数，调用关系就是文法产生式本身，调试时能看到函数栈，报错时能精确定位到哪个非终结符出错。而且C++的函数调用天然适合这种结构，不需要额外的分析栈。
匹配考试或求职面试时，面试官问“手写一个表达式解析器”，你如果只能回答“我会用bison”，基本等于不会。反过来，递归下降的分析代码控制在两百行内，遇到1+2*3能立刻算对优先级，这才算真正理解语法分析。后面部分我用实际代码展示怎么在C++里落地。
3. 手写递归下降解析器：从Token流到C++类实现
3.1 定义Token结构与词法接口
语法分析器不关心源代码字符，它只消费一个token数组。实验里为了方便，我会把词法分析器的输出直接构建成std::vector<Token>。Token定义如下：
enum TokenType { NUM, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, END }; struct Token { TokenType type; double value; // 仅当type==NUM时有意义 }; using TokenStream = std::vector<Token>;这个结构足够四则运算实验用。如果你的实验还要支持变量名和赋值，再增加ID类型并附加字符串字段即可。词法分析器一般单独实现，这里我假设你已经有一个std::vector<Token> tokenize(const std::string& input)，它负责把"12+5*3"切分成{ NUM(12), PLUS, NUM(5), MUL, NUM(3), END }。注意最后一定要加一个END标记，否则解析器不知道该在哪里停。
3.2 每个非终结符一个成员函数
递归下降的核心是文法到代码的一一映射。非终结符F对应factor()，T对应term()，T'对应term_prime()，以此类推。每个函数职责单一：尝试按照某个候选产生式去匹配输入，成功后返回该子树的语法树节点（或直接求值），失败则抛出异常或设置错误标志。
需要引入一个位置指针pos_，以及peek()和advance()两个方法。peek()返回当前token不消耗，advance()让指针后移。这是标准写法。下面的代码片段展示了这个骨架：
class Parser { public: explicit Parser(const TokenStream& tokens) : tokens_(tokens), pos_(0) {} ASTNode* parse() { ASTNode* node = expr(); if (peek().type != END) { std::cerr << "Unexpected trailing token" << std::endl; } return node; } private: TokenStream tokens_; size_t pos_; const Token& peek() const { return tokens_[pos_]; } void advance() { if (pos_ < tokens_.size() - 1) pos_++; } bool match(TokenType t) { if (peek().type == t) { advance(); return true; } return false; } // expr, term, factor等函数后面定义 };注意advance()判断pos_ < tokens_.size() - 1是为了永不越过最后的END。这样peek()总是安全。很多新手忘记这一点，导致读数组越界，这是第一个隐蔽的坑。
3.3 表达式文法的完整C++实现
我们直接构建AST节点，而不是边解析边求值。因为实验通常要求输出语法树，抽象语法树比直接算结果更有展示价值。节点定义：
struct ASTNode { virtual ~ASTNode() {} }; struct NumNode : ASTNode { double value; explicit NumNode(double v) : value(v) {} }; struct BinOpNode : ASTNode { char op; ASTNode* left; ASTNode* right; BinOpNode(char o, ASTNode* l, ASTNode* r) : op(o), left(l), right(r) {} };现在实现解析函数。文法E -> T E'，但用递归E'在代码里常表达为循环，因为E' -> + T E' | - T E' | ε，右递归用迭代更清晰。但为了贴合文法，我先给出递归版：
ASTNode* Parser::expr() { ASTNode* left = term(); return expr_prime(left); } ASTNode* Parser::expr_prime(ASTNode* left) { if (peek().type == PLUS || peek().type == MINUS) { char op = (peek().type == PLUS) ? '+' : '-'; advance(); ASTNode* right = term(); BinOpNode* node = new BinOpNode(op, left, right); return expr_prime(node); } return left; // ε产生式 }这里expr_prime接收已经解析好的左节点，每遇到一个运算符就结合一个右操作数，然后递归调用自己。这保证了左结合性：1+2+3会生成((1+2)+3)，而不是(1+(2+3))。term和term_prime同理：
ASTNode* Parser::term() { ASTNode* left = factor(); return term_prime(left); } ASTNode* Parser::term_prime(ASTNode* left) { if (peek().type == MUL || peek().type == DIV) { char op = (peek().type == MUL) ? '*' : '/'; advance(); ASTNode* right = factor(); BinOpNode* node = new BinOpNode(op, left, right); return term_prime(node); } return left; } ASTNode* Parser::factor() { if (peek().type == NUM) { double val = peek().value; advance(); return new NumNode(val); } if (peek().type == LPAREN) { advance(); ASTNode* inner = expr(); if (!match(RPAREN)) { std::cerr << "Missing closing parenthesis" << std::endl; } return inner; } // 错误处理 std::cerr << "Unexpected token in factor()" << std::endl; return nullptr; }factor遇到NUM直接构造数字节点，遇到左括号递归调expr()，然后必须消费一个右括号。如果输入是(1+2，match(RPAREN)失败，这里只打印一条错误信息。真实实验里应该抛异常或设置错误标志，但先跑通流程更重要。
3.4 递归版右递归的问题：栈深度与循环写法
上面expr_prime用递归表达右递归，但在C++里对处理长表达式不友好。比如1+2+3+4+...+1000，递归调用链深度随操作符数量线性增长，可能爆栈。更地道的写法是把expr_prime改成循环，同时仍然保持文法语义：
ASTNode* Parser::expr_loop(ASTNode* left) { while (peek().type == PLUS || peek().type == MINUS) { char op = (peek().type == PLUS) ? '+' : '-'; advance(); ASTNode* right = term(); left = new BinOpNode(op, left, right); } return left; }这样expr()就调用term()获得初始左节点，然后进入循环。循环里每读到一个运算符就构造一个新的BinOpNode，新的左节点覆盖旧的。不但避免了深递归，代码也更符合“读token流直到不匹配为止”的直觉。在实验报告的代码里，我建议两种都写：一种是文法到代码的直接映射，另一种是循环优化版，老师会欣赏你对递归与迭代的理解。
注意AST节点的内存管理。上面new出来的节点没有释放，真实项目会有泄漏。C++实验里可以在解析完成后用递归函数删除整棵树，或使用std::unique_ptr替代裸指针。不过为了没接触过智能指针的新手能看懂，我这里先用裸指针，后面避坑章节再讲怎么防泄漏。
4. 用Flex+Bison生成C++解析器：对比与联调
4.1 生成器方案到底解决什么问题
手写递归下降适合小文法，但你的实验如果要求支持完整的C--语言子集，比如声明、函数、结构体，文法规则可能有几十上百条，手写就有维护地狱。此时业界标准方案是Flex做词法，Bison（GNU版本的yacc）做语法分析，生成C++代码。这个组合最经典的“赛车理论”：手写就像手动挡，生成器像自动挡，先学会手动挡再开自动挡，才能理解自动挡在背后做什么。
Bison的核心输入是带语义动作的BNF规则。你定义token类型、优先级、产生式，Bison为你生成一个LALR(1)分析器，它内部用状态机和栈来解析，比手写的LL(1)更强大，能直接处理左递归（LR不怕左递归）。所以文法可以保留原始形式E -> E + T，不用消除左递归。
4.2 一个可编译的Flex词法文件
假设文件叫lexer.lex。这是Flex输入，作用是生成词法分析器，把输入字符流转成token并传给Bison：
%option noyywrap %{ #include "parser.tab.hh" // Bison生成的头文件，包含token编号和yyunion %} %% [0-9]+(\.[0-9]+)? { yylval.dval = atof(yytext); return NUM; } [+] { return PLUS; } [-] { return MINUS; } [*] { return MUL; } [/] { return DIV; } [()] { return LPAREN; } [()] { return RPAREN; } [ \t\n] { /* 跳过空白 */ } . { fprintf(stderr, "Unknown input: %s\n", yytext); } %%注意一行的[()]其实有两行，分别匹配(和)。上面代码里我写在一行是笔误，分隔符要拆开。写成"(" { return LPAREN; }和")" { return RPAREN; }最稳妥。yylval.dval里的dval是后面Bison%union里的成员名，两边需要保持一致。
4.3 Bison语法规则与语义动作
Bison文件parser.ypp语法如下，用%union定义所有语义值的类型，然后每个token声明类型：
%{ #include <cstdio> #include <cstdlib> extern int yylex(); void yyerror(const char* s) { fprintf(stderr, "Error: %s\n", s); } %} %union { double dval; }; %token <dval> NUM %token PLUS MINUS MUL DIV LPAREN RPAREN %left PLUS MINUS %left MUL DIV %type <dval> expr term factor %% start : expr { printf("%.6f\n", $1); } ; expr : expr PLUS term { $$ = $1 + $3; } | expr MINUS term { $$ = $1 - $3; } | term { $$ = $1; } ; term : term MUL factor { $$ = $1 * $3; } | term DIV factor { $$ = $1 / $3; } | factor { $$ = $1; } ; factor : NUM { $$ = $1; } | LPAREN expr RPAREN { $$ = $2; } ; %%注意%left PLUS MINUS声明了加法和减法是左结合，且优先级低于下一行的%left MUL DIV。这样Bison会为乘除构建优先级更高的状态，语法树自动让1+2*3先算乘法。$$是我们的目标语义值，$1、$3引用右侧第一个、第三个符号的值。
4.4 编译这条自动流水线
Flex和Bison生成的文件需要一起编译。常见步骤：
bison -d -o parser.cpp parser.ypp flex -o lexer.cpp lexer.lex g++ -std=c++11 -o calc lexer.cpp parser.cpp解释一下：bison -d会生成parser.cpp和一个parser.tab.hh（头文件），flex -o lexer.cpp强制指定输出文件名。两个.cpp文件里都引用了对方暴露的函数（如yylex），最后用g++一起编译链接。运行./calc后输入1+2*3回车，Bison默认的main入口读stdin，我们的start规则直接打印结果。
如果用的是旧版Bison或Windows环境，可能需要额外链接-lfl，或者自行提供一个main函数。常见做法是：
g++ -std=c++11 -o calc lexer.cpp parser.cpp -lfl -ly其中-lfl是Flex库（不一定需要），-ly是Bison库（包含 yyerror 的默认版本，但既然我们自己写了，也可以不链接）。实验环境千差万别，遇到链接错误时优先检查是不是缺库或头文件路径。
4.5 手写与生成器的核心差异
手写递归下降是LL(1)族，代码可读性高，但必须自己处理左递归和回溯。Bison是LALR(1)，能处理更广泛的文法，并且自带冲突检测——当文法二义或优先级冲突时，bison编译会报warning甚至error，这对初学者是好事，因为它倒逼你修正文法。代价是生成的C++代码非常难读，黑匣子一样，出了问题只能依赖yydebug开关和状态调试。
实验中我建议两个方案都做：先手写递归下降，确保原理掌握；再用Bison生成一个对比版，写进报告的“实验对比”部分。这样既不违背课程实验的目标，又能展示工程化能力。
5. 语法分析实验的五个常见坑：现象、原因与解法
5.1 递归下降无限递归：左递归没有消除干净
现象：程序一跑就栈溢出，或者卡死在高CPU占用，调试器指向expr()自己调用自己。
原因：直接使用了左递归文法E -> E + T，在函数里第一行就去expr()自身，没有任何基础情况。
解决：回顾第二章，必须消除直接和间接左递归。检查所有形如A -> Aα的产生式，用标准方法改写成右递归A -> βA'。写代码时测试expr()能否在消耗至少一个token之前停止递归。一个土办法：在expr()开头打印当前token类型，如果每次调用的第一个token都没变化，就是左递归。
5.2 FIRST/FOLLOW集算错导致非终结符冲突，或分析表里有重复项
现象：手写代码在某个分支处判peek().type时发现两个候选都能匹配，或者Bison报“conflicts: 1 reduce/reduce”。
原因：FIRST集漏算空串，FOLLOW集某个符号没加入。比如求FOLLOW(T)时忘记T后面可能是可空的E'，导致FOLLOW(T)少了$或)。
解决：别偷懒，把所有产生式一条条画成“箭头图”，每次X -> αYβ，把FIRST(β)（去ε）加入FOLLOW(Y)，若β可空，再把FOLLOW(X)加入FOLLOW(Y)。重复直到集合不再变化。写一个小脚本验证也可以；但如果手算，务必交叉检查。我在实验里经常把FOLLOW(F)算成漏了+，后来用1+2*3测试时解析错误才发现。
5.3 Bison的%union不能直接放std::string
现象：编译Bison文件时报错‘%union’ cannot be used with std::string，或者运行段错误。
原因：Bison的语义值是C语言风格的union，C++对象（如std::string、std::vector）有非平凡构造和析构，不能直接放进union。
解决：如果你的实验不支持变量名，用double完全够。如果一定要字符串，用%define api.value.type variant让Bison使用C++标准库类型的可扩展语义栈，或者用std::string*指针（记得在action里delete）。最省心的做法：把语义值定义成一个自定义结构体，包含double和std::string，放入%union中结构体本身没有复杂构造也可行。但建议优先避免这个坑，实验里就用数字类型。
5.4 AST内存泄漏：解析一万个表达式后内存爆炸
现象：程序运行一会内存占用持续上升，最后被系统杀掉。
原因：递归下降里new出的ASTNode没人释放。你在expr_prime循环里不断把left换新，旧节点丢了指针。
解决：至少写一个递归销毁函数：
void freeAST(ASTNode* node) { if (!node) return; if (auto* bin = dynamic_cast<BinOpNode*>(node)) { freeAST(bin->left); freeAST(bin->right); } delete node; }解析完整个输入后调用freeAST(root)。更现代的做法是用std::unique_ptr，让所有权自动管理。由于实验代码通常一遍过，很多人忽略这个问题，但老师如果在代码审查里问“你泄漏多少内存”，这个细节能拿加分。
5.5 错误处理太简单：非法输入直接崩溃
现象：输入1+*2，程序打印一个错误就返回nullptr，然后让你delete空指针，或者继续用nullptr算表达式。
原因：解析器在factor()里遇到非法token时只打印，没能恢复到下一个安全位置，外层也没判断返回值是否为nullptr。
解决：最简单是每层函数返回nullptr表示语法错误，上层立刻停止并报告，不再继续解析。进阶一点是“同步错误恢复”，丢弃输入直到遇到分号或END等同步标记，让分析器能继续检查后面的错误。这个能力在下一章展开。你现在至少做到：遇到非法token时，打印带行号或token上下文的信息，然后exit(EXIT_FAILURE)，总比崩溃好。
6. 进阶：错误恢复、可视化语法树与调试技巧
错误恢复是实验加分项。手写递归下降里，实现“恐慌模式”其实不难。在每个函数里检测到意外token时，调用synchronize()：
void Parser::synchronize() { while (peek().type != END && peek().type != RPAREN) { advance(); } }这里假设括号是同步点。更通用的做法是维护一个同步token集合，比如}、;、END。跳到同步点后，打印一行明确的错误信息，然后从当前非终结符重新开始解析。注意每个函数的入口处要检查错误标志，避免连续报一堆无关错误干扰阅读。
可视化语法树对调试很有用。写一个递归打印函数，以带缩进的形式输出树结构：
void dumpAST(ASTNode* node, int depth) { for (int i = 0; i < depth; ++i) std::cout << " "; if (auto* num = dynamic_cast<NumNode*>(node)) { std::cout << num->value << std::endl; } else if (auto* bin = dynamic_cast<BinOpNode*>(node)) { std::cout << bin->op << std::endl; dumpAST(bin->left, depth + 1); dumpAST(bin->right, depth + 1); } }跑12+5*3，输出会清晰显示+是根节点，右子树是*，左子树是12。任何一次优先级错误都会让树形异样，不用瞪眼调逻辑。
最后说个我的血泪经验：曾经在expr_prime里，我把advance()放到了判断条件之前，导致消费了一个运算符之后立刻判断下一个token又当成运算符，整数2被吞掉，报出“缺少数字”。这类“多吞token”错误很难用肉眼发现，必须用单步调试。在gdb里给Parser::term打断点，观察每次进入时pos_的值，对照输入token序列，能立刻看出是哪个分支多移动了指针。用std::cerr打桩也行，但调试完记得删掉。
这份实验做完，你会真正理解为什么编译原理强调“形式语言的递归结构”。C++的强大类型和指针操作让AST构建顺手，但随之而来的内存问题也逼着你去思考所有权和生命周期。我在做的时候，最大的收获不是成功解析了表达式，而是学会怎么让报错信息变得对用户友好、让自己好调试。希望帮到你。
本文还有配套的精品资源，点击获取
