C++实现语法分析实验：递归下降与LL(1)分析器从理论到代码

简介编译原理语法分析实验C版资源包围绕递归子程序法设计实现语法分析器需结合词法分析作业识别出的单词开展适合正在学习编译原理、需要完成语法分析实验的高校学生参考。压缩包体积仅17KB共含2个文件其中doc文档详细说明实验问题描述、输入输出文件命名及预读处理等要求cpp文件为可运行的完整C源码便于快速阅读和本地运行。作者代码在CG实验平台上以满分通过具备较高参考价值源码不仅按单词识别顺序逐行输出词法结果还针对各类语法成分进行递归分析并在指定成分分析结束时另起一行输出对应名字如常量说明格式与评测要求紧密贴合。已有6106人学习/浏览尤其适合希望理解递归下降思想、或想对照验证输出格式的同学借鉴。1. 语法分析实验为什么让这么多人卡壳先聊个现象。编译原理这门课词法分析实验大多数人写起来还挺顺的无非是状态机或正则匹配循环读字符、判断、输出token。但到了语法分析实验画风突变——课本上的E→ET | T、T→T*F | F这些产生式看着挺简单真要让你用C写一个能跑的分析器很多人在键盘前直接懵住。我当年带过不少学弟学妹做这个实验发现大家卡壳的点高度一致第一是递归下降还好理解但不知道怎么和代码对应起来第二是LL(1)分析表的构建与预测分析器的模拟教材上是表格、是集合运算落到代码里就不知道用什么数据结构第三是无论选哪种方法一旦输入出错程序怎么报错、怎么恢复完全没有头绪。语法分析实验的水平差距往往不在“能不能解析合法的输入”而在“遇到非法输入时你的程序表现得像一个正常人还是像个傻子”。这篇文章我就以C为语言载体把语法分析实验从设计思路到代码实现完整过一遍。内容覆盖两种主流方案——递归下降分析器和LL(1)预测分析器重点讲清楚“每个非终结符对应一个函数”这种话到底在说什么以及错误处理怎么做得像个成熟的分析器。无论你是刚拿到实验题还是写到一半想参考别人的设计这篇都能给你一些直接能用的东西。2. 实验入门第一步选对文法并消除左递归2.1 什么样的文法适合做语法分析实验大多数课程实验会指定一个表达式文法比如典型的四则运算E → E T | E - T | T T → T * F | T / F | F F → ( E ) | id | num这个文法描述了加减乘除、括号和数字的运算优先级覆盖面足够体现语法分析的核心思想又不会复杂到失控。但如果你真的把这个文法直接拿去做递归下降或LL(1)分析立刻会撞上一个大问题——左递归。左递归的意思是非终结符E的产生式右边第一个符号还是E自己。E → E T 这种写法对应的递归下降分析函数长这样伪代码parseE() { parseE(); // 无限调用自己 ... }这会直接导致无限递归程序栈溢出。所以在写任何代码之前先要做一件事消除左递归。把左递归改成右递归上面的文法变成E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | num | id一个直观的理解是原来的 E → E T 描述了“加号左边还可以继续是加法表达式”本质上是左结合改成 E → T E 之后通过右递归实现了同样可以无限扩展的表达式链但函数的调用方向翻转了不会出现自我无限调用。这里有一个初学者很容易忽略的细节——这样改写之后运算符的结合性从“左结合”变成了“右结合”。对于加法和乘法结果不影响但如果文法里有减法或除法比如 8 - 3 - 2右结合算出来是 8 - (3 - 2) 7而正确结果应该是 (8 - 3) - 2 3。解决办法是在语义动作或AST构建阶段把右递归的树结构重新调整为左结合这个到后面第4节再细说。2.2 First集和Follow集LL(1)分析的“计算题”如果你选的是LL(1)预测分析方案接下来就是计算FIRST集和FOLLOW集。这是整个实验里最“数学”的部分也是不少人的劝退点。以消除左递归后的文法为例逐步算一遍。FIRST集的定义一个非终结符能推导出的所有终结符串中第一个终结符的集合。如果它能推出空串ε那ε也加入FIRST集。FIRST(T) FIRST(F) { ( , num , id }FIRST(E) { , - , ε }FIRST(T) { * , / , ε }FIRST(E) FIRST(T) { ( , num , id }FOLLOW集的定义在文法所有句型中紧跟在该非终结符之后的终结符集合特别地开始符号的FOLLOW集里要加入结束符$。FOLLOW(E) { $ , ) }E是开始符号且出现在F → ( E )中FOLLOW(E) FOLLOW(E) { $ , ) }FOLLOW(T) FIRST(E) ∪ FOLLOW(E) { , - , $ , ) }FOLLOW(T) FOLLOW(T) { , - , $ , ) }FOLLOW(F) FIRST(T) ∪ FOLLOW(T) { * , / , , - , $ , ) }为什么要算这两个集合因为在构造LL(1)分析表时查表动作根据栈顶符号和当前输入符号决定用哪条产生式依赖的就是这两个集合。FIRST集决定“遇到某个终结符时如果某个产生式能推导出以该终结符开头的串就用这条产生式”FOLLOW集决定“当前符号能推出ε时遇到哪些终结符应该把当前非终结符弹出”。如果你用的是递归下降方案FIRST集用来决定分支判断FOLLOW集用来设计错误恢复时的同步集合。无论哪种方案这两个集合都是绕不开的核心计算也是实验报告里老师一定会看的部分。3. 递归下降分析器的C实现从伪代码到可运行代码3.1 词法接口设计分析器该从哪里拿Token语法分析器不直接面对字符流它的输入是词法分析器输出的Token流。所以第一步是定义一个Token结构。在C里我一般这样定义enum class TokenType { Num, ID, Plus, Minus, Star, Slash, LParen, RParen, End }; struct Token { TokenType type; std::string lexeme; // 原始文本 int line; int column; };语法分析器内部的接口只需要三个基本操作class Lexer { public: Token nextToken(); // 取下一个token bool hasMoreTokens(); };实际实验更常见的做法是一次性把整个Token流读进一个std::vectorToken然后语法分析器维护一个下标指针。这样做的好处是调试时可以随时回看历史Token打印整个Token序列也很方便代价是内存占用略高。对于课程实验前者的方便性远大于后者的成本推荐直接这么做。Token流处理中有个常见的坑Token的结束符。无论是用End这种特殊Token表示输入结束还是在Token流末尾放一个EOF标记这个一定要有。递归下降函数在读到表达式末尾时需要知道什么时候该停没有结束标记就只能靠下标越界来“自然结束”那程序离崩溃就不远了。3.2 核心类的骨架与每个非终结符的函数递归下降分析器的C核心类大致长这样class RecursiveDescentParser { public: explicit RecursiveDescentParser(const std::vectorToken tokens) : tokens_(tokens), pos_(0) {} std::shared_ptrASTNode parse() { auto node parseExpr(); if (current().type ! TokenType::End) { error(表达式结束后还有多余的输入); } return node; } private: const std::vectorToken tokens_; size_t pos_; const Token current() const { return tokens_[pos_]; } void advance() { if (pos_ tokens_.size() - 1) pos_; } bool check(TokenType type) const { return current().type type; } bool match(TokenType type) { if (check(type)) { advance(); return true; } return false; } std::shared_ptrASTNode parseExpr(); std::shared_ptrASTNode parseExprPrime(); std::shared_ptrASTNode parseTerm(); std::shared_ptrASTNode parseTermPrime(); std::shared_ptrASTNode parseFactor(); };这里有一个关键的设计决策对应前面消除左递归后的文法E和T这种“尾巴”非终结符也要有对应的分析函数。而文法中的 ε 产生式对应到代码里就是什么都不匹配直接返回nullptr。具体来说parseExprPrime的实现直接对应 E → T E | - T E | εstd::shared_ptrASTNode RecursiveDescentParser::parseExprPrime() { if (match(TokenType::Plus)) { auto left parseTerm(); auto right parseExprPrime(); return std::make_sharedBinaryOpNode(, left, right); } if (match(TokenType::Minus)) { auto left parseTerm(); auto right parseExprPrime(); return std::make_sharedBinaryOpNode(-, left, right); } // ε 产生式返回 nullptr return nullptr; }parseExpr则对应 E → T Estd::shared_ptrASTNode RecursiveDescentParser::parseExpr() { auto left parseTerm(); auto right parseExprPrime(); if (!right) return left; // 把左结合关系调整回来left 是左侧操作数 return right-rebuildLeftAssoc(left); }最后这个rebuildLeftAssoc的调用就是为了解决前面提到的右递归导致的结合性问题。一个更直观的方案是**不在递归下降阶段构建AST而是只做语法合法性检查输出一棵“扁平”的语法树序列或者干脆在成功匹配后输出产生式编号序列。**很多实验的评分标准只要求“输出最左推导过程”或“输出语法树”如果明确只要求过程输出那结合性问题根本不存在因为对同一个输入串最左推导就是唯一的。只有当要求生成表达式对应的语法树并参与求值计算时才需要真正处理结合性。我建议如果实验说明里没明确要求“构建AST并求值”就不要自找麻烦去建AST把分析过程中的产生式序列或递归进入的函数名打印出来既满足要求又省去大量内存管理的工作。3.3 一个完整的表达式解析过程用输入3 5 * ( 2 - 1 )走一遍分析流程感受一下递归下降的执行轨迹parseE进入看到当前Token是Num(3) parseT进入 parseF进入 识别Num(3)advance() parseF返回 parseT进入 当前Token是Plus不属于*或/T选择ε返回nullptr parseT返回当前Token是Plus parseE进入 匹配Plusadvance() parseT进入 parseF进入 识别Num(5)advance() parseF返回 parseT进入 匹配Staradvance() parseF进入 匹配LParenadvance() parseE进入 parseT进入 parseF进入 识别Num(2)advance() parseT进入 当前Token是MinusT选择ε parseT返回 parseE进入 匹配Minusadvance() parseT进入 parseF进入 识别Num(1)advance() parseT选择ε返回 parseE继续当前Token是RParen选择ε返回 parseE返回 匹配RParenadvance() parseT继续当前Token是End选择ε parseE继续当前Token是End选择ε parseE返回整体解析完成这个手动模拟的过程是实验调试最有效的工具。如果你写的程序跑出一个奇怪的结果不要急着加调试输出先拿张纸把期望的执行顺序写出来再对照程序实际打印的函数进出顺序多半一眼就能看出是哪个分支判断写错了。4. 构建ASTC里的节点设计与内存管理如果实验要求构建语法树这里有几个C特有的设计问题值得认真想一下。4.1 节点类的组织方式AST节点可以定义为抽象基类加派生类的结构struct ASTNode { virtual ~ASTNode() default; virtual int evaluate() const 0; virtual std::string toString() const 0; }; struct NumberNode : ASTNode { int value; int evaluate() const override { return value; } std::string toString() const override { return std::to_string(value); } }; struct BinaryOpNode : ASTNode { std::string op; std::shared_ptrASTNode left; std::shared_ptrASTNode right; int evaluate() const override { int lval left-evaluate(); int rval right-evaluate(); if (op ) return lval rval; if (op -) return lval - rval; if (op *) return lval * rval; if (op /) return lval / rval; throw std::runtime_error(unknown operator: op); } };用std::shared_ptr管理子节点是课程实验的正确选择不需要手写析构函数不会出现double free代码写起来也顺。有些同学为了炫技用std::unique_ptr省那一点内存开销但移动语义的麻烦程度对初学者很不友好。实验评分看的是功能和设计思路不是智能指针的高级用法。4.2 结合性问题的最终解法前面说右递归会导致右结合那在AST构建时怎么处理这里给一个最直接的方案。以3 5 7为例使用变换后的文法递归下降构建出的AST如果直接按右递归建树是() / \ 3 () / \ 5 7求值时变成 3 (5 7) 15结果碰巧与 (35)7 一样但如果是8 - 3 - 2这颗树算出来是 8 - (3 - 2) 7就是错的。修正的办法是不在parseExprPrime里创建BinaryOpNode而是让parseExprPrime返回右子树节点然后在parseExpr中循环向左归并std::shared_ptrASTNode RecursiveDescentParser::parseExpr() { auto node parseTerm(); while (check(TokenType::Plus) || check(TokenType::Minus)) { bool isPlus check(TokenType::Plus); advance(); auto right parseTerm(); node std::make_sharedBinaryOpNode( isPlus ? : -, node, right); } return node; }这个写法本质上是把文法等价地实现成了“E → T { (|-) T }”的形式用while循环代替E的递归。这是递归下降里非常经典的技巧——尾递归改成循环。它直接保留了左结合语义代码比维护一个“尾巴返回再重排”的结构清晰得多。parseTerm也同理。这种写法还有个额外好处不用定义E和T的分析函数了代码量直接减少三分之一。课堂上讲文法变换是为了理论推导LL(1)分析表但实际写递归下降编译器时绝大多数生产级实现包括很多开源编译器的手写parser用的就是带循环的EBNF风格。实验报告里可以说明你理解了左递归问题但实现上采用循环方式解决反而能体现你对这个问题的理解深度。5. LL(1)预测分析器的实现分析表驱动的另一种思路如果你的实验指定要用LL(1)预测分析器那代码风格完全不同。它不写递归函数而是用一个显式的栈 分析表驱动。5.1 分析表的数据结构与构建分析表是一个二维映射行是非终结符列是终结符表项是产生式编号或产生式本身。C里最简单的表示#include map #include vector enum class SymbolType { NonTerminal, Terminal, EndOfInput }; struct GrammarSymbol { SymbolType type; std::string name; }; // 产生式左部 - 右部符号序列 struct Production { std::string lhs; std::vectorGrammarSymbol rhs; }; // 预测分析表非终结符, 终结符 - 产生式在 productions 中的下标 std::mapstd::pairstd::string, TokenType, size_t parseTable;填充分析表的规则依赖FIRST集和FOLLOW集对产生式 A → α对FIRST(α)中的每个终结符a把该产生式填入parseTable[{A, a}]如果α能推出ε则对FOLLOW(A)中的每个终结符b把该产生式填入parseTable[{A, b}]如果某个格子已经填了产生式说明文法不是LL(1)文法构造失败手工填表对2.1节的表达式文法来说就是一个小九宫格表格。把整个表打印出来的函数非常值得写一是实验报告要用而是调试时查起来方便。5.2 预测分析器的驱动循环分析器主体的驱动循环不复杂但细节容易写错bool LL1PredictiveParser::run() { std::stackGrammarSymbol stk; stk.push({SymbolType::EndOfInput, $}); stk.push({SymbolType::NonTerminal, E}); // 开始符号 size_t idx 0; while (!stk.empty()) { GrammarSymbol top stk.top(); if (top.type SymbolType::Terminal) { if (top.name tokenToName(tokens_[idx].type)) { stk.pop(); idx; } else { error(期望 top.name 实际得到 tokens_[idx].lexeme); return false; } } else if (top.type SymbolType::EndOfInput) { if (tokens_[idx].type TokenType::End) return true; error(输入未结束); return false; } else { // 非终结符查表 auto key std::make_pair(top.name, tokens_[idx].type); auto it parseTable.find(key); if (it parseTable.end()) { error(在状态 top.name 遇到意外的 tokens_[idx].lexeme); return false; } stk.pop(); const Production prod productions[it-second]; // 逆序入栈保证栈顶是最左侧符号 for (auto it prod.rhs.rbegin(); it ! prod.rhs.rend(); it) { if (!(it-type SymbolType::NonTerminal it-name.empty())) { // 跳过 ε stk.push(*it); } } outputProduction(prod); // 输出产生式编号作为最左推导 } } return idx tokens_.size() - 1; }几个关键点逆序入栈栈是LIFO结构要让右部符号从左到右依次匹配就得从右往左入栈。这个“反过来”的操作让很多人卡壳过。ε的处理产生式右部为空的相当于不需要压入任何内容只弹栈。一些教材会用一个特殊符号表示ε代码里直接跳过更干净。输出产生式序列每次查表并弹出非终结符后把所选产生式打印出来本质就是最左推导过程这正好符合很多实验“输出最左推导序列”的要求。6. 错误处理与恢复实验拿高分的关键差异6.1 基本错误报告要给出位置和期望很多人的第一次提交是这样的遇到错误直接cout Error! endl;然后exit(0)。这只能保证“检测到错误”但根本谈不上“分析器”。一个像样的错误报告至少包含三要素出错的行列位置、当前识别的Token内容、期望的Token集合或当前状态。在Token结构里记录line和column错误函数可以这样写void Parser::error(const std::string message) { std::cerr 第 current().line 行第 current().column 列 遇到 \ current().lexeme \ message std::endl; throw ParseError(); }用C异常而不是exit退出是为了给上层错误恢复流程留出返点。一个成熟的错误报告示例第1行第7列遇到 期望 ) 或数字有了这个输出做实验的人能快速定位错误评分的人也能看到你的分析器确实做了语法检查。6.2 恐慌模式恢复跳过Token到同步集合既然要做“像个正常人”的错误处理就不能一遇错就退出。业界最常用也最适合课程实验的恢复策略是恐慌模式Panic Mode。核心思想检测到错误时丢弃输入中的若干Token直到遇到一个“同步符号”再继续分析。同步符号的选择原则是当前非终结符的FOLLOW集成员或是一些能可靠重启分析的符号如分号、右括号、结束符。以表达式文法为例如果parseTerm里在期望数字或左括号的位置遇到了*就可以报错后把输入指针一路前进到FOLLOW(T)的成员也就是 - $ )中的任意一个。代码void RecursiveDescentParser::synchronize( const std::setTokenType syncSet) { while (!check(TokenType::End) syncSet.find(current().type) syncSet.end()) { advance(); } }在递归下降的每个分析函数开头判断当前Token不满足FIRST集时调用synchronize并抛异常让上层解析函数重新进入。这样输入3 * 5时分析器会报错“期望数字或左括号实际遇到 *”跳过*然后继续分析出后面的5而不是在第一个错误就“死掉”。在LL(1)预测分析器中恐慌模式的实现是查表失败时把栈顶非终结符弹掉然后跳过输入直到遇到该非终结符FOLLOW集中的终结符。这样一条E - T E的推导链断了就跳到下一个同步点重新开始。6.3 错误恢复的边界能恢复多少算多少需要提醒的是错误恢复不要做过度。课程实验的要求通常只是检测出语法错误并合理报告不要求对任意错误输入都能完整恢复并给出正确AST。做得太激进的恢复策略比如在括号不匹配时自动补一个右括号反而可能掩盖真实的语法问题让后续分析产生一连串莫名其妙的连锁报错。我见过有同学花了一整天调“完整恢复”最后评分时一个输入样例报了三行错误的效果远不如那种报一个清清楚楚的错误就停下来的简洁版本。一个务实的中间方案是检测到语法错误时打印详细诊断然后跳过整个表达式语句从下一个分号或结束符重新开始分析。它既能报告所有顶层语句的错误又不会陷入表达式内部的连锁误报实现也简单。对id (a b * c; x 5;这种输入一个错误对应一条有效诊断而不是一堆让人摸不着头脑的堆栈溢出。7. C实现中的经典坑与调试心得7.1 无限递归和栈溢出递归下降最常见的事故现场就是无限递归。除了左递归还有两种情况值得注意第一种是II型左递归A → B αB → A β。这种间接左递归肉眼不容易发现但会导致parseA调用parseBparseB又调用parseA死循环。排查方法是在每个分析函数入口打印当前行号和函数名一旦发现同一个函数在短时间内被重复进入多次基本就是间接左递归。第二种是匹配失败却不前进。比如在parseFactor里当前Token既不是数字也不是左括号但代码没有走ε分支而是调用parseExprPrime继续匹配结果parseExprPrime里的match也失败函数层层返回最终落入死循环。解决办法是保证每个非终结符函数要么消费至少一个Token要么明确地走ε分支返回绝不能陷入“不消费任何Token地重复调用自己”的状态。7.2 引用与拷贝Token流的访问方式在C里写分析器时Token流的访问方式直接影响程序的正确性。如果按值传递std::vectorToken每次递归调用都会拷贝整个Token序列性能灾难不说还会因为拷贝后的下标修改不影响原序列而导致分析逻辑完全错乱。正确做法是用引用或指针class Parser { const std::vectorToken tokens_; // 整个生命周期内引用绑定 size_t pos_; };另外注意current()函数返回的是const Token如果你在match或advance之外的地方意外修改了pos_调试起来会非常痛苦。在每个分析函数里加入断言assert(pos_ tokens_.size())能在崩溃前帮你抓住下标越界的隐患。7.3 调试输出一个被低估的利器写语法分析实验最大的调试利器不是断点而是缩进打印的递归进出信息。给分析器加一个depth成员void Parser::debugEnter(const std::string func) { for (int i 0; i depth_; i) std::cout ; std::cout -- func 当前Token: current().lexeme std::endl; depth_; }然后每个parse函数首行调用它。运行一次合法的输入你能完整看到分析器的执行轨迹对应前面3.3节手动推导的过程跑非法输入时也能立刻看出是在哪个函数、哪个状态下出的错。这比GDB打断点高效得多因为递归下降的“语义”体现在函数的调用序列里而这种动态的调用序列只有打印才能直观呈现。提示完成功能后记得把debug输出关掉或放进条件宏里否则提交的实验报告附带运行结果时会显得非常杂乱。7.4 关于cin性能与输入格式最后提一个C特有的细节。如果你的实验程序直接从命令行读表达式记住加这两行配合std::getline读整行std::ios::sync_with_stdio(false); std::cin.tie(nullptr);不加这两行cin的默认同步机制会大幅拖慢读取速度——课程实验的输入规模不是瓶颈但养成这个习惯没有坏处。更关键的是输入格式的容错不要假设所有测试数据都是规范的35*2很可能出现带空格、带换行、带制表符的输入。词法分析器跳过空白符的代码务必写对这直接决定你的程序能不能扛住评测系统里那些“故意恶心人”的用例。8. 从实验到理解我踩过坑之后的几点体会做完这个实验后回头看语法分析实验真正训练的不是“会写递归”或“会用map”而是把一个数学定义文法转化为一个能执行的判定过程的能力。这中间隔着的不是C语法而是对“产生式”“FIRST/FOLLOW集”“预测分析”这些概念有没有真正想通。拿我自己当年踩坑的经验说最有价值的一步其实是手工推演。写代码之前我拿了一篇A4纸把2.1节的文法、FIRST/FOLLOW集、几个样例表达式的推导过程全部手推了一遍然后在代码里加了深度打印把程序实际执行顺序和手推的推导树一棵棵对照。第一次发现“程序的分析顺序和手推的推导顺序完全一致”的那一瞬间整个语法分析的概念才真正变成了一种直觉而不只是课本上几个背下来的定义。如果你正在做这个实验建议不管实验要求是什么都额外做这样一件事画一棵自己输入的表达式对应的语法树。能画出树、能讲清楚每个节点对应哪条产生式就说明你真的理解了画不出来代码能跑也是碰巧。反过来讲语法树会画了代码其实只是把它翻译成C语法的问题——而后者恰恰是整个实验里最简单的那部分。本文还有配套的精品资源点击获取