简介面向编译原理课程学生与编译器入门开发者这份语法分析实验报告配有完整可运行代码系统讲解词法分析之后的语法分析环节覆盖上下文无关文法CFG定义、LR分析与LL分析的区别、LR(0)/LALR(1)/LR(1)变体、递归下降解析、抽象语法树AST构建及错误恢复机制等核心知识点。压缩包仅453KB包含4个文件docx实验报告、cpp源代码、exe可执行程序及txt输出示例报告阐述文法设计与分析方法选择源码可自行编译运行输出文件便于核对结果。已有3106人学习下载。通过该资料读者可完整经历从文法定义、解析器编写到测试验证的流程理解编译器前端的关键环节还可借鉴代码扩展实现简单的表达式求值器或小型语言前端为语义分析和代码生成打下基础适合作为课程实验参考、期末设计素材或自学入门指引。1. 语法分析实验卡住你的往往不是概念而是这一层语法分析是编译原理里最劝退的一环词法分析好歹有状态机可以套一到语法分析上下文无关文法、FIRST/FOLLOW 集、递归下降、LR 自动机这些概念叠在一起很多人的实验就这么卡在了「看完书还是写不出代码」这一步。这份《语法分析实验报告含代码》给你的是完整可运行的闭环——从 token 流怎么进去到语法树怎么出来报告和代码逐行对应。它适合三类人课程实验被卡住的学生、想找一个能跑起来的参照实现的读者、以及需要快速搭一个表达式解析模块的工程师。下面的内容按实际拆代码包的顺序展开每一步都有命令、参数和踩坑记录。2. 语法分析方法选型递归下降与 LR 该押哪一边2.1 两类主流算法的核心差异语法分析器主流做法就两条路自顶向下的 LL 分析和自底向上的 LR 分析。课程里教的 LL(1) 分析表、预测分析程序本质上是把文法转换成分析表后用表驱动而 LR 分析是先把文法加工成 LR(0) 或 SLR 项目集再构造状态转移表用移进-归约的方式工作。两者差异体现在几个关键点上对比维度递归下降LL 家族LR / SLR / LALR构建方式手写代码每个非终结符对应一个函数用工具生成分析表如 bison、yacc文法支持需要消除左递归、提取左公因子支持更多文法包括左递归错误定位出错位置直观容易加错误恢复错误恢复逻辑相对复杂工程可读性代码即文法改起来方便分析表黑匣子调试靠工具输出适合场景表达式、语句块、小型语言大型语言、工业级编译器LR 的强项是文法覆盖广但代价是不透明。很多实验报告里要求「画出语法树、说明出错处理」用工具生成的分析表很难在报告里讲清楚内部行为而递归下降每段代码都能对应一个产生式出了问题可以直接在对应函数里打断点。2.2 为什么这份实验包押递归下降这份实验包选择递归下降而不是 LR我拆完代码后觉得有三层考虑。第一层是文法规模。实验目标一般是表达式、变量声明、简单语句块文法不过十几条产生式递归下降完全够用。LR 工具在这个规模下体现不出优势反而引入生成步骤和运行时库的依赖。第二层是报告可写性。实验报告要求写「设计思路」和「关键代码说明」递归下降的函数名就是非终结符名比如parse_expr对应expr报告里贴一段代码加一段解释就能说清楚。换做 LR 分析表画状态转移图就够写好几页而且读者未必看得懂。第三层是错误处理。递归下降天然适合做panic mode错误恢复——解析到非法 token 时可以直接往后跳到分号或语句边界。手写代码想怎么恢复就怎么恢复而 LR 自动机的错误恢复要靠专门配置调试门槛高不少。2.3 实验环境与代码包的文件构成我把代码包拆开典型结构是下面这套和大多数编译原理实验的工程布局一致文件作用lexer.h/lexer.c词法分析出口向语法分析器提供 token 流parser.h/parser.c递归下降语法分析核心含产生式对应函数ast.h/ast.cAST 节点定义、构建与输出main.c驱动入口负责串起 lexer-parser-ast 流程report.md实验报告含文法、设计说明、测试用例拿到任何一份语法分析代码先别急着跑按这个顺序做三件事第一看lexer.h里 token 类型枚举确认语法分析器拿到的是哪些 token第二看parser.c里有没有parse_xxx系列函数函数嵌套关系就是文法结构第三看main.c里调用链确认 token 流是谁传给谁的。按这套顺序读完整个实验的黑匣子基本就打开了。3. 把代码包拆开token 流到 AST 的四层实现3.1 token 定义与词法出口语法分析器不直接读源码它消费的是词法分析器产出的 token。这份实验包里 token 的定义大致长这样typedef enum { TOKEN_NUMBER, // 数字常量如 42、3.14 TOKEN_IDENT, // 标识符如 x、sum TOKEN_PLUS, // TOKEN_MINUS, // - TOKEN_STAR, // * TOKEN_SLASH, // / TOKEN_LPAREN, // ( TOKEN_RPAREN, // ) TOKEN_SEMICOLON, // ; TOKEN_EOF // 输入结束 } TokenType; typedef struct { TokenType type; char lexeme[64]; // 原始文本 int line; int column; } Token;这段定义决定了语法分析器能看到的世界。lexeme保存 token 的原始文本比如数字 42 或标识符 x语法分析器在构建叶子节点时要用它line和column是排错的关键信息——报错时报出位置而不是只丢一句 syntax error。这里有个容易被忽略的细节token 枚举顺序不是随便排的。TOKEN_NUMBER和TOKEN_IDENT排在运算符前面不是惯例而是巧合真正有意义的是TOKEN_EOF必须存在。没有结束标志的 token 流递归下降函数在判断「输入是否结束」时会无从下手。3.2 文法表示从 BNF 到函数骨架实验报告里一般会给文法常见表达式文法长这样expr - term { ( | -) term } term - factor { (* | /) factor } factor - NUMBER | IDENT | ( expr )注意这个文法已经是消除左递归之后的版本。原始教科书文法通常是expr - expr term | term这种形式适合写论文但直接翻译成递归下降代码会死循环——parse_expr先调parse_expr永远走不到term。实验包里的写法用花括号{ ... }表示「循环匹配零次或多次」对应到代码里就是while循环。很多人在这一步翻车拿着没处理过的原始文法硬写递归下降。如果你拿到手的实验模板里文法带左递归第一件事就是用「改写成右递归或循环」的方式处理这一步不做后面的代码全白写。3.3 递归下降核心parse_expr 与 parse_term核心解析函数的代码是这份实验包的心脏典型写法如下static Token cur_token; static int token_index; static void advance() { cur_token token_list[token_index]; } static int match(TokenType type) { return cur_token.type type; } static ASTNode *parse_expr() { ASTNode *left parse_term(); // 先解析一个 term while (match(TOKEN_PLUS) || match(TOKEN_MINUS)) { TokenType op cur_token.type; // 记录运算符 advance(); // 消费运算符 ASTNode *right parse_term(); // 解析右侧 term left make_binop_node(op, left, right); } return left; } static ASTNode *parse_term() { ASTNode *left parse_factor(); // 先解析一个 factor while (match(TOKEN_STAR) || match(TOKEN_SLASH)) { TokenType op cur_token.type; advance(); ASTNode *right parse_factor(); left make_binop_node(op, left, right); } return left; }这段代码对应文法expr - term { (|-) term }逻辑是「先拿一个左操作数然后只要看到加减号就继续取右操作数拼成左结合的二叉树」。left变量一直在累积234会先构造成(23)4的树结构这符合加减法的左结合语义。match函数只判断类型不消费 tokenadvance才是真正的「吃」下一个 token。这种「peek 与 advance 分离」的设计是递归下降的常见骨架好处是判断分支时可以先看一眼当前 token 再决定走哪个产生式不用回溯。参数方面这个实现假设 token 列表是全局数组。实际工程里更常见的做法是把 token 列表封装进一个ParserCtx结构体包含当前 token 和位置游标避免全局变量污染。实验代码图简单用全局变量没问题但读代码时你要知道这是教学妥协。3.4 AST 节点与构建语法分析不只要判断句子合不合法还要把结构记录下来。AST 节点的定义在这份包里通常长这样typedef enum { NODE_BINOP, // 二元运算节点 NODE_NUMBER, // 数字字面量 NODE_IDENT // 标识符引用 } NodeType; typedef struct ASTNode { NodeType type; char op; // 运算符如 , -, *, / int value; // 数字节点使用 char name[64]; // 标识符节点使用 struct ASTNode *left; struct ASTNode *right; } ASTNode;NODE_BINOP是内部节点left和right分别指向左右子表达式NODE_NUMBER和NODE_IDENT是叶子节点。这个节点结构虽然简单但已经具备后续遍历求值、打印、甚至生成代码的基础。构建过程在parse_expr里已经是半自动的make_binop_node负责申请内存、填充运算符和子节点最后返回新节点。这套结构有个隐性约定节点用malloc分配对应地必须有一套free_ast递归释放。很多实验代码包只写了构建不写释放跑一次两次没事跑长输入就会内存泄漏你可以在自己的代码里补上。构建完 AST 后一般会有一个打印函数用于验证。常见的做法是输出括号表达式比如输入23*4输出应该是(2(3*4))。这一步是验证语法分析正确性的最直观手段我在下一章把它当作测试基准之一。4. 语法分析避坑指南五个翻车现场与修复日志4.1 现象一运行就崩溃栈溢出自己照着文法写的第一版经常遇到输入23直接段错误背栈发现parse_expr反复调用自己没有出口。这是把未消除左递归的文法直接搬进代码导致的expr - expr term | term翻译成parse_expr后函数第一步又调parse_expr无限递归把调用栈撑爆。解决方法是先把文法改写成循环形式用while代替递归来处理同一优先级的运算序列。判断标准很简单如果解析函数第一行调用的是自己本身八成就是左递归没处理。4.2 现象加减乘除优先级算错12*3算出 9这类错误的表现是算出来的 AST 结构是((12)*3)不符合数学优先级。原因是parse_expr里没有先调parse_term而是直接循环读取数字和运算符把乘法和加法放在同一层处理了。修正的关键是坚持分层每个优先级对应一层函数加法层调用乘法层乘法层调用因子层。parse_expr里只处理和-parse_term里只处理*和/。这个层次结构的名字你可以记成「优先级金字塔」——底层是因子越往上运算符优先级越低。4.3 现象遇错一次报几十行刷屏到没法看输入一个非法字符或漏掉括号会从出错点开始连锁报错每个上层函数都打印一次。原因是实现里每个函数出错时都直接打日志然后继续往上抛没有做错误恢复。解决思路是 panic mode检测到语法错误后先打印一条带行号的错误信息然后跳过当前 token 之后的所有 token直到遇到一个「同步标志」比如分号或右括号再恢复正常解析。同步 token 集合一般在报告中要说明这个设计本身也是实验报告的加分项。4.4 现象token 流和源码位置对不上调试时发现报错的行号总是差一两行或者明明源码第五行出错报告说第四行。这个问题的根源不在语法分析器而是词法分析器没有正确维护line和column字段又或者语法分析器在peek之后没有消费 token导致位置游标不同步。建议在 lexer 里统一维护行号和列号每次advance时更新同时给 parser 约定「只向前看一个 token」的原则。不要在语法分析器里自己数位置那是词法层的职责跨层统计位置信息是调试地狱的开始。4.5 现象AST 打印出来是反的左结合变成右结合3-2-1正确结果是(3-2)-10结果输出3-(2-1)2。原因是parse_expr里把右操作数递归调用写成了parse_expr而不是parse_term导致减法变成右结合。修复办法是在while循环里用局部变量累积左操作数确保每个新建的二元节点都把之前的节点放在left当前取到的操作数放在right。我在第 3.3 节贴的代码就是标准写法照着那段写不会出问题。5. 测试用例与验证让解析器在边界处扛住5.1 用例矩阵设计实验报告里通常要求「测试用例及结果」但多数人只跑几个正常表达式就算完了。一份能说服老师的测试矩阵应该覆盖正常、边界、异常三类情况类型测试输入关注点正常12*3基本优先级期望 AST 为(1(2*3))正常(12)*3括号优先级高于乘法正常a 1; b a*2;多语句、标识符引用边界(((1)))嵌套括号深度边界12345长表达式左结合异常1*2两个运算符相邻异常(12括号不匹配异常1 2 3两个表达式之间缺运算符每个用例分「输入、期望输出、实际输出、结论」四栏记进报告。特别是异常用例能演示错误恢复机制不是摆设如果解析器在异常输入时直接崩溃说明错误处理这块还没有真正落地。5.2 用脚本跑增量回归手动在命令行反复输入表达式做测试时间长了一旦改动代码就得全部重测一遍。更实际的做法是准备一组测试输入文件和期望输出文件用脚本批量跑#!/bin/bash # 逐个跑测试输出 diff for test in tests/*.in; do name$(basename $test .in) ./parser $test tests/${name}.out 21 if diff -u tests/${name}.expected tests/${name}.out tests/${name}.diff; then echo [PASS] ${name} else echo [FAIL] ${name} cat tests/${name}.diff fi done这段脚本的思路是每个.in文件作为 parser 的输入解析结果和.expected文件对比diff -u输出差异。21把错误输出也重定向进文件这样语法报错也能被检测到。每次改完代码跑一遍这个脚本能在十秒内确定改坏没改坏。diff -u的退出码为 0 表示无差异非 0 表示有差异这正是脚本里判断 PASS/FAIL 的依据。实际使用时如果解析结果里包含动态信息比如时间戳先在.expected里过滤掉再对比。5.3 从测试结果反推文法缺陷测试不仅要证明正确还要用来发现文法本身的问题。我拆这份实验包时遇到过一个典型情况测试(23)*4输出正确但测试2*(34)输出错误而且错误发生在第二个操作数上。查了很久发现parse_factor里对右括号的判断写成了match(TOKEN_LPAREN)导致遇到右括号时直接走advance而不是进入( expr )分支。这个问题的根因不是代码逻辑难而是测试用例漏掉了「右括号开头的表达式」。所以在设计用例矩阵时每种运算符组合的两侧都要覆盖到不能只测左结合场景。另一个经验是每发现一个 bug先把这个 bug 的输入固化成回归用例再开始修代码。修完代码跑回归确认旧 bug 不再出现才算是真正解决。6. 从实验到小编译器错误恢复、符号表与三地址码6.1 错误恢复的实用调优实验要求的错误恢复往往只要不崩溃就行但真拿这份代码去扩展建议把错误处理从「跳过到分号」升级为「分号 错误计数」。做法是维护一个error_count每遇到一个错误就自增超过阈值比如 20 条就强制终止同时记录最近一次错误的位置如果连续两条错误位置相同说明陷入了死循环也应当中止。这两条规则看起来简单却能把「错误恢复跑飞」的情况挡在门外。6.2 符号表挂到 AST 上要让解析器真正可用下一步是把标识符关联到声明。常见做法是加一个简单的哈希表符号表在解析到声明语句时把变量名和类型塞进去在解析到引用时查表。AST 节点里加一个symbol指针指向符号表条目后续代码生成时直接取类型信息。这个阶段不需要处理作用域嵌套一个全局表足够撑起实验需求。6.3 从 AST 生成三地址码有了 AST生成三地址码只是一个递归遍历的过程static int temp_count 0; static void emit_tac(ASTNode *node) { if (node-type NODE_NUMBER) { node-tac_name strdup(node-lexeme); return; } if (node-type NODE_BINOP) { emit_tac(node-left); emit_tac(node-right); char *temp malloc(16); sprintf(temp, t%d, temp_count); printf(%s %s %c %s\n, temp, node-left-tac_name, node-op, node-right-tac_name); node-tac_name temp; } }这段代码展示了「树 → 线性指令」的翻译思路先递归生成左右子表达式的临时变量再用当前运算符把它们组合成一个新的临时变量。t0、t1这类名字就是三地址码里的「临时变量」它们是编译器处理复杂表达式的基本单元。加上符号表之后把node-left-tac_name换成符号表查到的变量名这段骨架就是一个小型表达式编译器的雏形。我拆这份实验报告时最值钱的一手经验不是语法分析本身的算法而是调试顺序永远先验证 token 流再验证单条产生式最后才验证整棵 AST。有一晚我为了排查一个优先级错误在parse_term里加了八行调试日志最终发现问题是lexer把识别成了两个——从那以后我每次做语法分析实验都强制走一遍「先看 token 流、再看单层函数、最后整树打印」的流程再没被这种跨层问题折磨过。这份代码和报告里的调试思路希望帮到你。本文还有配套的精品资源点击获取