简介面向编译原理课程中的语法分析实验这是一份采用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集相交。实验报告里必须包含这四个集合的计算过程否则老师一问“你怎么知道这个文法能递归下降”答不上来就是白做。先算FIRSTFIRST(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 EE在产生式末尾所以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”基本等于不会。反过来递归下降的分析代码控制在两百行内遇到12*3能立刻算对优先级这才算真正理解语法分析。后面部分我用实际代码展示怎么在C里落地。3. 手写递归下降解析器从Token流到C类实现3.1 定义Token结构与词法接口语法分析器不关心源代码字符它只消费一个token数组。实验里为了方便我会把词法分析器的输出直接构建成std::vectorToken。Token定义如下enum TokenType { NUM, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, END }; struct Token { TokenType type; double value; // 仅当typeNUM时有意义 }; using TokenStream std::vectorToken;这个结构足够四则运算实验用。如果你的实验还要支持变量名和赋值再增加ID类型并附加字符串字段即可。词法分析器一般单独实现这里我假设你已经有一个std::vectorToken tokenize(const std::string input)它负责把125*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接收已经解析好的左节点每遇到一个运算符就结合一个右操作数然后递归调用自己。这保证了左结合性123会生成((12)3)而不是(1(23))。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()然后必须消费一个右括号。如果输入是(12match(RPAREN)失败这里只打印一条错误信息。真实实验里应该抛异常或设置错误标志但先跑通流程更重要。3.4 递归版右递归的问题栈深度与循环写法上面expr_prime用递归表达右递归但在C里对处理长表达式不友好。比如1234...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. 用FlexBison生成C解析器对比与联调4.1 生成器方案到底解决什么问题手写递归下降适合小文法但你的实验如果要求支持完整的C--语言子集比如声明、函数、结构体文法规则可能有几十上百条手写就有维护地狱。此时业界标准方案是Flex做词法BisonGNU版本的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会为乘除构建优先级更高的状态语法树自动让12*3先算乘法。$$是我们的目标语义值$1、$3引用右侧第一个、第三个符号的值。4.4 编译这条自动流水线Flex和Bison生成的文件需要一起编译。常见步骤bison -d -o parser.cpp parser.ypp flex -o lexer.cpp lexer.lex g -stdc11 -o calc lexer.cpp parser.cpp解释一下bison -d会生成parser.cpp和一个parser.tab.hh头文件flex -o lexer.cpp强制指定输出文件名。两个.cpp文件里都引用了对方暴露的函数如yylex最后用g一起编译链接。运行./calc后输入12*3回车Bison默认的main入口读stdin我们的start规则直接打印结果。如果用的是旧版Bison或Windows环境可能需要额外链接-lfl或者自行提供一个main函数。常见做法是g -stdc11 -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)算成漏了后来用12*3测试时解析错误才发现。5.3 Bison的%union不能直接放std::string现象编译Bison文件时报错‘%union’ cannot be used with std::string或者运行段错误。原因Bison的语义值是C语言风格的unionC对象如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_castBinOpNode*(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_castNumNode*(node)) { std::cout num-value std::endl; } else if (auto* bin dynamic_castBinOpNode*(node)) { std::cout bin-op std::endl; dumpAST(bin-left, depth 1); dumpAST(bin-right, depth 1); } }跑125*3输出会清晰显示是根节点右子树是*左子树是12。任何一次优先级错误都会让树形异样不用瞪眼调逻辑。最后说个我的血泪经验曾经在expr_prime里我把advance()放到了判断条件之前导致消费了一个运算符之后立刻判断下一个token又当成运算符整数2被吞掉报出“缺少数字”。这类“多吞token”错误很难用肉眼发现必须用单步调试。在gdb里给Parser::term打断点观察每次进入时pos_的值对照输入token序列能立刻看出是哪个分支多移动了指针。用std::cerr打桩也行但调试完记得删掉。这份实验做完你会真正理解为什么编译原理强调“形式语言的递归结构”。C的强大类型和指针操作让AST构建顺手但随之而来的内存问题也逼着你去思考所有权和生命周期。我在做的时候最大的收获不是成功解析了表达式而是学会怎么让报错信息变得对用户友好、让自己好调试。希望帮到你。本文还有配套的精品资源点击获取