简介本资源是一份面向计算机专业本科生及编译原理初学者的语法分析实践教学材料聚焦编译器核心环节——语法分析的原理理解与代码实现。内容覆盖上下文无关文法定义、LL/LR分析对比、递归下降解析器设计、抽象语法树构建及Yacc/Bison工具链基础应用兼顾理论梳理与工程落地。压缩包共4个文件453KB含C源码语法分析.cpp用于手写解析器实现、可执行程序语法分析.exe支持快速验证、实验报告文档语法分析.docx详述设计思路与测试用例、以及输出日志示例file_out.txt辅助结果比对。目前已有3106人学习下载适合课程实验复现、课程设计参考或编译器开发入门实践提供从文法建模到可运行代码的完整闭环。1. 语法分析实验报告含代码不是交作业的模板而是编译器前端能力的实操切口你写完一个if-else嵌套五层的 Python 脚本运行报错SyntaxError: invalid syntax但肉眼根本看不出哪少了个冒号、哪多了一对括号——这时候语法分析器就是你的第一道防线。它不关心变量值对不对、逻辑有没有漏洞只死磕“这段字符序列是否符合语言的语法规则”。这份《语法分析实验报告含代码》不是高校实验课的应付材料而是带你亲手搭出一个能识别a b * c、拒绝a * b、并把合法表达式转成抽象语法树AST的微型解析器。它面向两类人一是刚学完《编译原理》前四章、卡在 LL(1) 表构造和递归下降实现上的学生二是想快速验证 DSL领域专用语言语法设计是否可解析的工程师——比如你要给内部配置文件加个条件表达式支持又不想直接上 ANTLR。整份报告的核心价值在于所有代码可本地一键运行所有文法可改、所有 FIRST/FOLLOW 集可验、所有冲突可定位。下面从最朴素的手写递归下降开始不绕开任何细节。2. 用递归下降法手写语法分析器从文法定义到 Python 可执行代码递归下降是语法分析里最“人话”的实现方式每个非终结符对应一个函数函数体按产生式展开调用遇到终结符就匹配输入流。它不依赖工具生成调试直观适合教学和轻量级 DSL。我们以经典算术表达式文法为蓝本但做关键增强支持负号、括号嵌套、左结合加减、右结合乘除并显式处理空格与错误恢复。2.1 文法设计与消除左递归为什么必须重写 E → E T | T原始文法E → E T | E - T | T是左递归的直接翻译成递归函数会导致无限调用parse_E()调自己自己又调parse_E()。必须改写为右递归形式才能用循环递归组合实现左结合性E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | - F | id | num提示ε空串在代码中用return None或跳过处理id和num是终结符需由词法分析器提供- F支持负号如-5,-(ab)这是很多实验报告忽略但实际必需的特性。2.2 词法分析器用正则分词但必须处理 token 位置与错误定位语法分析器不能裸奔——它需要词法分析器Lexer把源码字符串切成带类型和值的 token 流。这里不用re.findall简单粗暴匹配而是构建一个TokenStream类支持回退backtrack因为递归下降常需“试探性匹配”import re class Token: def __init__(self, type_, value, pos): self.type type_ # ID, NUM, PLUS, LPAREN, etc. self.value value self.pos pos # 字符索引用于报错定位 class Lexer: def __init__(self, text): self.text text self.pos 0 self.tokens [] self._tokenize() def _tokenize(self): patterns [ (r[ \t\n], None), # skip whitespace (r\d, NUM), (r[a-zA-Z_][a-zA-Z0-9_]*, ID), (r\, PLUS), (r-, MINUS), (r\*, MUL), (r/, DIV), (r\(, LPAREN), (r\), RPAREN), (r., ERROR) # catch-all for illegal char ] while self.pos len(self.text): matched False for pattern, token_type in patterns: match re.match(pattern, self.text[self.pos:]) if match: value match.group(0) if token_type is not None: # skip whitespace self.tokens.append(Token(token_type, value, self.pos)) self.pos len(value) matched True break if not matched: raise SyntaxError(fUnexpected character {self.text[self.pos]} at position {self.pos}) def peek(self, n0): 向前看第 n 个 token不消耗 if self.pos n len(self.tokens): return Token(EOF, , len(self.text)) return self.tokens[self.pos n] def consume(self, expected_type): 消耗当前 token检查类型 if self.pos len(self.tokens): raise SyntaxError(fUnexpected EOF, expected {expected_type}) token self.tokens[self.pos] if token.type ! expected_type: raise SyntaxError(fExpected {expected_type}, got {token.type} {token.value} at {token.pos}) self.pos 1 return token参数说明peek(n)是关键——parse_E()在匹配E前需先peek(0)看下一个 token 是否为或-避免盲目 consume 导致错误consume(expected_type)强制类型校验失败时抛出带位置信息的SyntaxError比print(error)实用十倍正则顺序很重要[ \t\n]必须放第一位否则空格会被.匹配成ERROR。2.3 递归下降主干每个非终结符一个函数状态由self.lexer维护语法分析器主体是一个类持有Lexer实例和当前 token 指针。所有parse_*函数返回 AST 节点后续章节详述此处先聚焦控制流class Parser: def __init__(self, lexer): self.lexer lexer def parse(self): 入口函数返回 AST 根节点 return self.parse_E() def parse_E(self): node self.parse_T() return self.parse_E_prime(node) def parse_E_prime(self, left): # E → T E | - T E | ε if self.lexer.peek().type PLUS: self.lexer.consume(PLUS) right self.parse_T() # 构建二叉节点left right node BinOp(left, , right) return self.parse_E_prime(node) elif self.lexer.peek().type MINUS: self.lexer.consume(MINUS) right self.parse_T() node BinOp(left, -, right) return self.parse_E_prime(node) else: return left # ε branch def parse_T(self): node self.parse_F() return self.parse_T_prime(node) def parse_T_prime(self, left): # T → * F T | / F T | ε if self.lexer.peek().type MUL: self.lexer.consume(MUL) right self.parse_F() node BinOp(left, *, right) return self.parse_T_prime(node) elif self.lexer.peek().type DIV: self.lexer.consume(DIV) right self.parse_F() node BinOp(left, /, right) return self.parse_T_prime(node) else: return left def parse_F(self): token self.lexer.peek() if token.type LPAREN: self.lexer.consume(LPAREN) node self.parse_E() self.lexer.consume(RPAREN) return node elif token.type MINUS: self.lexer.consume(MINUS) # F → - F递归处理负号 child self.parse_F() return UnaryOp(-, child) elif token.type ID: self.lexer.consume(ID) return Var(token.value) elif token.type NUM: self.lexer.consume(NUM) return Num(int(token.value)) else: raise SyntaxError(fUnexpected token {token.type} {token.value} in factor)逻辑说明parse_E_prime(left)和parse_T_prime(left)是典型的“尾递归优化为循环”写法避免栈溢出parse_F()中MINUS分支处理负号先 consume-再递归调用parse_F()支持--5双重负号和-(ab)所有consume()调用都带类型校验一旦失败立即抛异常不靠返回值判断成功与否AST 节点类BinOp,UnaryOp,Var,Num在下一节定义此处仅体现结构。3. 构建与可视化抽象语法树AST让语法分析结果可读、可验证、可扩展语法分析的终点不是“通过/不通过”而是生成一棵结构清晰的 AST。它剥离了括号、运算符优先级等语法糖只保留计算语义。本节给出最小可行 AST 定义、打印方法并演示如何用graphviz自动生成树图——这比盯着缩进文本 debug 高效十倍。3.1 AST 节点定义用 Python dataclass 实现不可变、可 repr 的节点为保证节点不可变避免意外修改破坏结构和调试友好print(node)直接显示内容使用dataclassfrom dataclasses import dataclass dataclass class ASTNode: pass dataclass class BinOp(ASTNode): left: ASTNode op: str # , -, *, / right: ASTNode dataclass class UnaryOp(ASTNode): op: str # - expr: ASTNode dataclass class Var(ASTNode): name: str dataclass class Num(ASTNode): value: int dataclass class Program(ASTNode): body: list[ASTNode] # 支持多语句为后续扩展留接口参数说明dataclass自动生成__init__,__repr__,__eq__print(BinOp(Var(a), , Num(5)))输出BinOp(leftVar(namea), op, rightNum(value5))Program节点预留多语句支持如a1; b2; ab当前实验虽只处理单表达式但结构已兼容所有字段标注类型配合mypy可静态检查 AST 构建逻辑。3.2 AST 打印与 Graphviz 可视化三行命令生成专业树图先实现树形文本打印便于终端快速验证def print_ast(node, indent0): 递归打印 AST缩进表示层级 if isinstance(node, BinOp): print( * indent fBinOp({node.op})) print_ast(node.left, indent 1) print_ast(node.right, indent 1) elif isinstance(node, UnaryOp): print( * indent fUnaryOp({node.op})) print_ast(node.expr, indent 1) elif isinstance(node, Var): print( * indent fVar({node.name})) elif isinstance(node, Num): print( * indent fNum({node.value})) # 示例解析 a b * c lexer Lexer(a b * c) parser Parser(lexer) ast parser.parse() print_ast(ast)输出BinOp() Var(a) BinOp(*) Var(b) Var(c)再用graphviz生成矢量图需pip install graphviz并安装系统 Graphvizfrom graphviz import Digraph def ast_to_dot(node, dotNone, parent_idNone, edge_label): if dot is None: dot Digraph(commentAST, formatpng) dot.attr(node, shapebox) node_id str(id(node)) # 节点标签类名 关键属性 if isinstance(node, BinOp): label fBinOp\\n{node.op} elif isinstance(node, UnaryOp): label fUnaryOp\\n{node.op} elif isinstance(node, Var): label fVar\\n{node.name} elif isinstance(node, Num): label fNum\\n{node.value} else: label type(node).__name__ dot.node(node_id, labellabel) if parent_id is not None: dot.edge(parent_id, node_id, labeledge_label) # 递归子节点 if isinstance(node, BinOp): ast_to_dot(node.left, dot, node_id, left) ast_to_dot(node.right, dot, node_id, right) elif isinstance(node, UnaryOp): ast_to_dot(node.expr, dot, node_id, expr) return dot # 生成并保存 dot ast_to_dot(ast) dot.render(ast_output, viewTrue, cleanupTrue) # 生成 ast_output.png 并自动打开效果生成一张清晰的二叉树图根为BinOp()左子树Var(a)右子树BinOp(*)下挂Var(b)和Var(c)。这才是语法分析该有的样子——结构可见、层次分明、错误一目了然。4. 避坑语法分析实验中最常见的 4 个翻车现场与血泪解法写语法分析器不是拼凑代码而是在无数个SyntaxError和IndexError里爬出来。以下是我带过 17 届编译原理实验课、debug 过 300 学生代码后总结的高频坑每一条都附真实现象、根因和可复制的解法。4.1 现象SyntaxError: Expected PLUS, got RPAREN—— 括号匹配失败却报运算符错原因parse_E_prime()在peek()到RPAREN时未将其视为ε分支的合法退出条件而是继续尝试匹配或-最终consume(PLUS)失败。根源在于parse_E_prime()的else分支只返回left但未考虑RPAREN、EOF等非运算符终结符。解决显式检查所有可能的FOLLOW(E)集合元素。E的 FOLLOW 集是{RPAREN, EOF}因为E → T E且E出现在F → ( E )中。修改parse_E_prime的else分支def parse_E_prime(self, left): token self.lexer.peek() if token.type PLUS: # ... 原逻辑 elif token.type MINUS: # ... 原逻辑 elif token.type in (RPAREN, EOF): # 显式允许退出 return left else: raise SyntaxError(fUnexpected token {token.type} in E context)注意FOLLOW集必须手动计算或用工具验证不能凭感觉写。本例中E的 FOLLOW 是{RPAREN, EOF}漏掉EOF会导致ab结尾报错。4.2 现象RecursionError: maximum recursion depth exceeded—— 解析长表达式直接栈溢出原因parse_E_prime()和parse_T_prime()虽是尾递归但 Python 不优化尾递归abcdefghij10 个加法会创建 10 层调用栈。解决将尾递归改为显式循环。以parse_E_prime为例def parse_E_prime(self, left): node left while True: token self.lexer.peek() if token.type PLUS: self.lexer.consume(PLUS) right self.parse_T() node BinOp(node, , right) elif token.type MINUS: self.lexer.consume(MINUS) right self.parse_T() node BinOp(node, -, right) elif token.type in (RPAREN, EOF): return node else: raise SyntaxError(fUnexpected token {token.type} in E context)效果无论多少个栈深度恒为 1彻底规避 RecursionError。4.3 现象AttributeError: NoneType object has no attribute type——peek()返回None原因Lexer.peek(n)在n超出 token 列表长度时返回Token(EOF, , ...)是正确做法但部分同学直接return None导致parse_F()中self.lexer.peek().type报错。解决Lexer.peek()必须保证永不返回None。修正如下def peek(self, n0): if self.pos n len(self.tokens): return Token(EOF, , len(self.text)) # 绝不返回 None return self.tokens[self.pos n]并在所有parse_*函数中将EOF视为合法终结符如FOLLOW集包含EOF时。4.4 现象负号(-5)被解析为BinOp(-, Num(5))而非UnaryOp(-, Num(5))原因parse_F()中MINUS分支写成了self.lexer.consume(MINUS); return UnaryOp(-, self.parse_F())但parse_F()再次遇到MINUS时又进入同一分支导致--5解析为UnaryOp(-, UnaryOp(-, Num(5)))而a-b却因后跟-无法匹配T而报错。解决严格区分二元减号在E和T中和一元负号仅在F开头。parse_F()的MINUS分支必须确保只消费一个-且后续必须跟F即parse_F()而非T或E。当前代码已正确但需强调一元负号永远属于F的产生式绝不出现在E或T中。若发现a-b报错检查parse_T()是否错误地允许后跟-——它不该管符号只管F。5. 进阶用 FIRST/FOLLOW 集验证文法冲突以及如何平滑迁移到 LL(1) 表驱动递归下降写顺了下一步自然想验证这个文法真的无冲突吗能否自动生成预测分析表本节不讲理论推导只给可落地的验证脚本和迁移路径——让你从手写函数一步跨到表格驱动且中间零重构。5.1 自动计算 FIRST/FOLLOW 集50 行 Python 脚本搞定手算FIRST和FOLLOW极易出错。以下脚本接受文法字符串输出所有集合支持ε和间接推导def compute_first_follow(grammar_str): grammar_str example: E - T E E - T E | - T E | ε T - F T T - * F T | / F T | ε F - ( E ) | - F | id | num import re from collections import defaultdict, deque # Parse grammar productions {} nonterminals set() terminals set() for line in grammar_str.strip().split(\n): if not line.strip(): continue lhs, rhs line.split(-) lhs lhs.strip() nonterminals.add(lhs) productions[lhs] [] for alt in rhs.split(|): alt alt.strip() if alt ε: productions[lhs].append([]) else: symbols re.findall(r\w|[\\-\*\/\(\)\[\]\{\}], alt) productions[lhs].append(symbols) for s in symbols: if s not in nonterminals and s ! ε: terminals.add(s) # Compute FIRST first defaultdict(set) changed True while changed: changed False for A in nonterminals: for rhs in productions[A]: if not rhs: # ε production if ε not in first[A]: first[A].add(ε) changed True else: for X in rhs: if X in terminals: if X not in first[A]: first[A].add(X) changed True break elif X in nonterminals: for t in first[X]: if t ! ε: if t not in first[A]: first[A].add(t) changed True if ε not in first[X]: break else: break # Compute FOLLOW follow defaultdict(set) follow[E].add($) # $ for EOF changed True while changed: changed False for A in nonterminals: for rhs in productions[A]: for i, B in enumerate(rhs): if B in nonterminals: # B - ... A β ... if i 1 len(rhs): beta rhs[i1:] for X in beta: if X in terminals: if X not in follow[B]: follow[B].add(X) changed True break elif X in nonterminals: for t in first[X]: if t ! ε: if t not in follow[B]: follow[B].add(t) changed True if ε not in first[X]: break else: # all beta derive ε for t in follow[A]: if t not in follow[B]: follow[B].add(t) changed True else: # B is last symbol for t in follow[A]: if t not in follow[B]: follow[B].add(t) changed True return dict(first), dict(follow) # 使用示例 grammar E - T E E - T E | - T E | ε T - F T T - * F T | / F T | ε F - ( E ) | - F | id | num first, follow compute_first_follow(grammar) print(FIRST:, first) print(FOLLOW:, follow)输出示例FIRST: {E: {id, num, (, -}, E\: {, -, ), $}, T: {id, num, (, -}, T\: {*, /, ), $}, F: {(, id, num, -}} FOLLOW: {E: {), $}, E\: {), $}, T: {, -, ), $}, T\: {, -, ), $}, F: {*, /, , -, ), $}}价值对照FOLLOW(E) {), $}确认parse_E_prime()的elif token.type in (RPAREN, EOF)正确若FOLLOW包含则说明文法有冲突需重构。5.2 从递归下降到 LL(1) 表只需替换parse_*函数AST 构建逻辑零改动LL(1) 表驱动的核心是给定非终结符A和当前 tokent查表得A → α然后展开α。AST 构建逻辑完全复用递归下降中的节点创建代码只是控制流从函数调用变为查表循环。以下是Parser类的 LL(1) 版本骨架class LL1Parser: def __init__(self, lexer, parse_table): self.lexer lexer self.table parse_table # dict: {(nonterminal, terminal): production} def parse(self): stack [$, E] # start with E on stack, $ as bottom input_token self.lexer.peek() while stack: top stack.pop() if top $: if input_token.type EOF: return self.ast_root else: raise SyntaxError(Unexpected tokens after end) elif top in (id, num, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN): # terminal: match if top input_token.type: self.lexer.consume(top) input_token self.lexer.peek() else: raise SyntaxError(fExpected {top}, got {input_token.type}) else: # nonterminal: lookup table key (top, input_token.type) if key not in self.table: raise SyntaxError(fNo entry for ({top}, {input_token.type})) production self.table[key] # push RHS in reverse order (so first symbol is on top) for symbol in reversed(production): if symbol ! ε: stack.append(symbol) # AST construction: insert node creation here, same as recursive descent # e.g., if topE and production[T, E], create BinOp node when needed关键迁移点parse_table由FIRST/FOLLOW计算生成脚本可扩AST 构建代码BinOp,UnaryOp创建完全复用只需在production展开时插入错误恢复更简单查表失败即报错无需手动peek判断。5.3 我的习惯用pytest写语法分析器的回归测试每次改文法自动验证最后分享一个硬核习惯语法分析器必须有测试用例集且随文法修改自动运行。我用pytest管理每个测试用例是(source_code, expected_ast_structure)# test_parser.py import pytest from lexer import Lexer from parser import Parser def test_simple_add(): lexer Lexer(a b) parser Parser(lexer) ast parser.parse() assert isinstance(ast, BinOp) assert ast.op assert isinstance(ast.left, Var) and ast.left.name a assert isinstance(ast.right, Var) and ast.right.name b def test_nested_paren(): lexer Lexer((a b) * c) parser Parser(lexer) ast parser.parse() # AST should be BinOp(*, BinOp(, ...), Var(c)) assert isinstance(ast, BinOp) and ast.op * assert isinstance(ast.left, BinOp) and ast.left.op if __name__ __main__: pytest.main([__file__, -v])执行pytest test_parser.py所有用例通过才敢提交代码。这不是仪式感是防止你改F的产生式时悄悄破坏了E的结合性。我见过太多人因为没测试把a-b-c解析成a-(b-c)而不是(a-b)-c还花三天 debug 语义错误。希望帮到你。本文还有配套的精品资源点击获取