简介面向编译原理学习者的语义分析实验资源包聚焦Java语言实现编译器语义分析阶段的核心逻辑涵盖类型检查、作用域解析、常量折叠等典型任务适合计算机专业学生或自学者对照实验要求动手实践也适用于复习编译原理课程设计的重点环节。包内共101个文件以35个Java源码为主体辅以XML配置、Eclipse项目偏好文件prefs、编译生成的class文件和少量辅助索引文件整体体积仅88KB结构紧凑完整可直接导入工程查看关键实现。已有1781人浏览学习热度不俗。通过这份资料学习者可参考Token、Word、Lexer等核心类的编码思路理解语义分析如何借助抽象语法树进行逐节点校验同时从项目配置文件入手梳理解析阶段的组件衔接快速定位实验中的难点与易错点为独立完成编译原理实验或深入探索编译器前端提供切实参考。1. 语义分析实验到底在做什么从「句子合法」到「意思通顺」编译原理这门课里实验三的语义分析是第一个真正逼着你做数据结构的环节。词法和语法分析把源代码变成一棵抽象语法树而语义分析要在这棵树上回答「这段话到底通不通」——变量有没有声明、类型是不是匹配、函数调用参数行不行。很多人做完实验二还很轻松到实验三就卡住原因是语法分析可以靠递归脑补语义分析却必须有真实的符号表和类型检查逻辑在背后撑着。适合正在赶编译原理实验的本科生也适合想补全编译器后端知识的一线开发。标题里的 sectionnef 通常是实验框架里符号表导出段的标识读作「符号表段」就行不用被这串字符吓到。这篇按可复现的路径把符号表、作用域链、类型检查、中间代码衔接讲透并给出能直接落地的代码和五个高频坑。2. 语义分析的输入与输出把 AST 变成一张符号表与一份类型标注语义分析夹在语法分析和中间代码生成之间输入是语法分析产出的 AST输出则是三样东西填充了类型信息的 AST、一张按作用域组织的符号表、一份错误清单。如果实验要求出中间代码那输出里还会有四元式或三地址码。很多学生把语义分析当成「再遍历一遍 AST」这个理解不算错但漏了最关键的词再遍历时你需要边遍历边往节点和符号表上写东西。2.1 输入端AST 节点要预留语义信息的槽位语法分析阶段构造的 AST 节点通常只保存结构信息例如一个二元表达式节点有 operator、left、right但它不知道 left 是 int 还是 float也不知道 right 是不是变量。语义分析的第一步就是确认每个节点上有地方可以挂这些信息。用 Python 写实验时我一般会这样定义节点class ExprNode: def __init__(self, kind, valueNone, leftNone, rightNone, lineno0): self.kind kind # num | id | bin_op | assign self.value value # 数字字面量或变量名 self.left left self.right right self.type None # 语义分析阶段填充int / float / bool / error self.lineno lineno # 报错定位用直接从 token 复制过来这里的关键是self.type这个槽位。AST 节点本身不会告诉你变量的类型只有查了符号表才知道所以要在遍历过程中把查到的类型写回节点。lineno也非常重要很多实验报告被打回就是因为报错信息没有行号。构建 AST 时每个节点创建参数里都要带上词法分析阶段记录的 token 行号语义分析报错才有依据。如果你的实验框架用 C 语言实现思路完全一样在语法树节点结构体里加一个int type或char* type_name字段再用int lineno字段保存行号。不管语言怎么变节点上必须预留「语义信息挂载点」这是实验三能否顺利展开的地基。2.2 符号表不是一张大表而是一条作用域链符号表最容易做错的地方是把整个程序的所有变量塞进一个全局字典。C 语言和类 C 语言都是块级作用域内层块可以访问外层变量但外层块不能访问内层变量。如果只有一张大表退出内层块时要么急着删符号导致外层变量丢失要么不删导致块内变量泄漏到外层。正确做法是作用域链每个作用域一个表带着指向父作用域的指针。class Symbol: def __init__(self, name, type_, kind, lineno0): self.name name self.type type_ # int | float | bool | func self.kind kind # var | param | func self.lineno lineno class Scope: def __init__(self, parentNone): self.table {} self.parent parent def define(self, sym): # 只在当前层查重不检查外层 if sym.name in self.table: raise DuplicateDeclError(sym.lineno, f重复声明: {sym.name}) self.table[sym.name] sym def lookup(self, name): scope self while scope is not None: if name in scope.table: return scope.table[name] scope scope.parent return Nonedefine只在当前作用域查重遇到同名直接抛异常或记录错误lookup从当前层开始一层层往上找找到最近的声明就返回。这个「最近」就是标准的作用域遮蔽规则内层定义了和外层同名的变量内层代码访问到的是内层那个。很多语义分析器的隐蔽 bug 就出在define时顺带检查了外层作用域把合法的遮蔽当成重复声明这是初学时最容易掉进去的坑。符号表条目的字段也要想清楚。函数和变量可以放在同一个表里但通过kind区分函数参数要跟着函数符号走否则后面做中间代码生成时拿不到参数列表。如果实验要求计算栈偏移Symbol 里还应加一个offset字段在声明处理时递增填进去。2.3 属性文法类型检查规则的教科书原型语义分析的理论基座是属性文法但实验里你不需要背定义只需要用到两类属性综合属性和继承属性。综合属性自底向上传播最典型的例子是表达式的类型1 2.0的类型由左右操作数的类型共同决定子节点的类型先算出来父节点的类型再由子节点类型推导。继承属性自顶向下传播典型例子是声明语句里的「期望类型」int a expr;遍历到 expr 时已经知道期望类型是 intexpr 要检查自己能否转换为 int。具体的类型检查规则可以用一张表提前定死这就是属性文法落到代码前的设计稿运算类别左操作数类型右操作数类型结果类型抛出条件算术运算 - * /int 或 floatint 或 float两边同为 int 则 int否则 float任一操作数不是数值类型关系运算 int 或 floatint 或 floatbool操作数不是数值类型逻辑运算 ||boolboolbool任一操作数不是 bool赋值 左值类型 T右值类型 RTR 不能隐式转换为 T这张表就是你后面写merge_type和compatible两个函数的依据。注意赋值那一行int 可以隐式转换为 floatfloat 不能隐式转换为 int否则会丢失精度。很多学生的类型检查器把所有数值类型混为一谈最后测试用例里float a 1;和int a 1.5;全被放行这在实验验收时一眼就会被看穿。属性文法的价值就是把这类规则先写成表格再翻译成代码而不是边写代码边临时想规则。3. 用 Python 从零搭一个语义分析器符号表与类型检查的最小实现这一章给一个能直接跑起来的 Python 语义分析器骨架覆盖声明、表达式、赋值的类型检查。它不依赖任何第三方库只需要一个假设好的 AST。你可以照着这个骨架把语法分析器里产出的 AST 接进来再补上语句级检查和错误收集。3.1 先搭错误收集器语义分析不要遇到第一个错就停词法语法分析常常遇到一个错就退出但语义分析最好收集完所有错误再统一报告。原因很实际实验数据量大老师希望一次跑出一个完整的错误列表而不是修一个错重跑一次。错误收集器用最简单的列表就行class ErrorCollector: def __init__(self): self.errors [] def add(self, lineno, message): self.errors.append((lineno, message)) def has_errors(self): return len(self.errors) 0 def report(self): for lineno, message in sorted(self.errors): print(f行 {lineno}: {message})按行号排序输出是因为语义分析遍历顺序可能不完全是代码顺序先排好序报告读起来更像编译器。收集错误的同时分析器不能直接崩溃遇到类型错误的表达式要返回一个error类型让上层继续检查其他子节点。这个error类型在整个类型检查里要有隔离效果任何和error参与的运算都不再报新的类型错误否则一个未声明变量会诱发七八条连环报错。def merge_type(left_t, right_t, op, lineno, errors): if left_t error or right_t error: return error numeric (int, float) if op in (, -, *, /, , , , ): if left_t not in numeric or right_t not in numeric: errors.add(lineno, f算术或关系运算的操作数必须是数值类型实际是 {left_t} 和 {right_t}) return error if op in (, , , ): return bool if left_t float or right_t float: return float return int if op in (, ||): if left_t ! bool or right_t ! bool: errors.add(lineno, f逻辑运算操作数必须为 bool实际是 {left_t} 和 {right_t}) return error return bool return error这段代码里的关键参数是 op 集合和返回类型规则。算术运算里只要有一个操作数是 float结果就是 float这是 C 语言和 Java 都遵循的数值提升规则。关系运算的结果永远是 bool即使操作数是 int。逻辑运算要求两侧严格为 bool不接受 0/1 隐式转换——如果你想放宽成「C 风格」可以改但实验报告里要写清楚你的取舍。3.2 表达式检查查符号表、推导类型、回填节点表达式的检查函数返回node.type同时把类型写回节点。这样父节点可以直接用子节点的type字段无需再次查表。对于标识符节点查表失败就报未声明错误并把类型置为error查表成功则把符号表中的类型抄到节点上。def check_expr(node, scope, errors): if node.kind num: if isinstance(node.value, int): node.type int else: node.type float return node.type if node.kind id: sym scope.lookup(node.value) if sym is None: errors.add(node.lineno, f未声明的变量: {node.value}) node.type error else: node.type sym.type return node.type if node.kind bin_op: left_t check_expr(node.left, scope, errors) right_t check_expr(node.right, scope, errors) node.type merge_type(left_t, right_t, node.op, node.lineno, errors) return node.type if node.kind assign: sym scope.lookup(node.left.value) if sym is None: errors.add(node.lineno, f赋值给未声明的变量: {node.left.value}) node.type error return node.type right_t check_expr(node.right, scope, errors) if right_t error: node.type error return node.type if not compatible(sym.type, right_t): errors.add(node.lineno, f类型不匹配: 不能把 {right_t} 赋值给 {sym.type} 变量 {node.left.value}) node.type error return node.type node.type sym.type return node.type errors.add(node.lineno, f未知的表达式节点: {node.kind}) node.type error return node.typecheck_expr对id节点的处理有讲究它把符号表中的类型值复制给节点的type字段。这样做的好处是如果后面有隐式类型转换你可以在节点上记录「实际类型」和「声明类型」两个字段但现在先保持简单。赋值节点里要先查变量是否存在再检查右值类型。compatible函数定义如下def compatible(target_type, source_type): if target_type source_type: return True if target_type float and source_type int: return True # int 隐式提升为 float return False这里只放行一种隐式转换int 到 float。char 到 int、float 到 int 这些都在实验里先禁止避免语义分析变成类型转换的深水区。如果你想做得更细可以在errors里报告「需要显式转换」的警告而不是直接报错。3.3 声明和语句检查处理作用域进入与退出声明检查负责把新符号写进当前作用域。语句检查负责控制流和赋值遇到块时需要新建子作用域并且在离开块时把子作用域移除。这里的核心难点是作用域生命周期管理。def check_decl(node, scope, errors): if node.kind var_decl: sym Symbol(node.name, node.type_name, var, node.lineno) try: scope.define(sym) except DuplicateDeclError as e: errors.add(node.lineno, str(e)) return if node.init is not None: init_t check_expr(node.init, scope, errors) if not compatible(sym.type, init_t): errors.add(node.lineno, f变量 {node.name} 初始化类型不匹配) elif node.kind func_decl: scope.define(Symbol(node.name, node.return_type, func, node.lineno)) def check_stmt(node, scope, errors): if node.kind assign: check_expr(node, scope, errors) elif node.kind if: cond_t check_expr(node.cond, scope, errors) if cond_t ! bool and cond_t ! error: errors.add(node.lineno, if 条件必须为 bool 类型) child_scope Scope(scope) for s in node.then_body: check_stmt(s, child_scope, errors) if node.else_body: for s in node.else_body: check_stmt(s, child_scope, errors) elif node.kind while: cond_t check_expr(node.cond, scope, errors) if cond_t ! bool and cond_t ! error: errors.add(node.lineno, while 条件必须为 bool 类型) child_scope Scope(scope) for s in node.body: check_stmt(s, child_scope, errors)注意if和while的检查都创建了child_scope但没有显式地「退出」作用域。因为child_scope是局部变量函数结束时它自然不可达符号表也就随之被回收。之所以还要显式建 Scope是因为需要保证块内定义变量查找时能在当前块命中而不是跑到外层去。如果换成 C 语言实现没有自动析构的便利你必须在离开块时手动把符号表指针指回父作用域否则块内符号泄漏到外层。Python 版本里也要养成「每进入一个块就 new Scope」的习惯后续做中间代码生成时需要往符号表里记录作用域 ID这个显式新建的 Scope 对象就能派上用场。3.4 跑通一个最小样例把三者串起来现在把错误收集器、符号表、表达式检查串成一个主入口。假设 AST 由上一阶段的语法分析器手动构造下面这段测试代码可以直接验证整个分析器def analyze(ast): errors ErrorCollector() global_scope Scope() for decl in ast.declarations: check_decl(decl, global_scope, errors) for stmt in ast.statements: check_stmt(stmt, global_scope, errors) errors.report() return errors.has_errors()测试输入是这段简单程序int a; float b; a 1 2; b a 1.5; if (a 0) { int c; c a; } a b;前面四句都能通过a 0是 boolc在块内声明并使用作用域链工作正常。最后一句a b应该报类型不匹配b 是 floata 是 int不能隐式降级。如果分析器报告零错误说明compatible函数可能写成了对称判断立刻去检查是不是把 int 和 float 双向放行了。这个最小实现只有一百多行足够支撑实验三的大部分要求。它缺的是函数调用的参数检查、数组声明、结构体等扩展但作用域链与类型检查的核心机制已经完整往里面加新语法只需要扩展check_stmt和check_expr的分支。4. 语义分析器避坑五个让实验成绩翻车的隐蔽错误语义分析实验难在不是「能不能跑通」而是「能不能在各种边缘输入下都给出正确结果」。这五个坑是学生在实验三里最常翻车的地方每一条都是真实场景踩中一个就会让你调半天。4.1 重复声明被静默覆盖现象内层块里声明了和外层同名的变量运行结果不报错但内层符号把外层符号覆盖了。更麻烦的是第二次声明同一作用域的同名变量编译器竟然不报错。原因define里没有查重或者只调用了lookup做全局查重。前者导致内层遮蔽变成静默覆盖后者导致合法的遮蔽被误报。解决define必须只查当前作用域scope.table。遇到同名符号就记录「重复声明」错误同时不再把新符号写入表里保留第一次的符号。这样外层变量被遮蔽时符号表里仍然保留外层符号只是查找顺序优先取内层。4.2 块退出后变量泄漏到外层现象一段代码里if块内声明了一个变量块外访问它竟然不报错。老师给你的测试用例里专门有这条直接扣分。原因检查if语句时新建了粒度为整个 then 分支的 Scope但没有处理嵌套块的退出或者 C 语言实现时忘了解除符号表引用块内定义一直留在当前表中。解决每进入一个块结构if、while、函数体都新建一个 Scope 子作用域离开时把当前作用域指针恢复成父作用域。Python 代码里利用局部变量自动回收很省事但要确保给then_body和else_body分别创建独立作用域而不是共用一个否则 else 块能访问 then 块的变量同样违规。4.3 类型判断过于宽松float 直接塞进 int现象int a 1.5;和float b a;都没有报错。老师人工检查代码时一眼看出问题实验报告写得再好也拿不到高分。原因compatible函数里把「数值类型」全部视为可互相转换。这是很多学生偷懒的写法误以为类型检查只需要区分「是不是数字」。解决严格按照可隐式转换方向表来。int 提升为 float 合法float 降级为 int 非法。把compatible(target, source)的定义改为单向判断。更严谨一点在assign分支里额外检查左值是否带const限定但那不是实验三的通用要求。4.4 报错信息没有行号拿到测试用例也定位不到现象错误输出长这样类型不匹配: float int没有行号。老师打开测试数据不知道错在那一行你调试时也只能靠猜。原因AST 节点没有保存行号字段或者语义分析报错时只传了节点类型没有传节点里的lineno属性。解决在词法阶段就把 token 的行号一路透传到 AST 节点如果写的是手写递归下降分析器创建节点时从当前 token 复制行号。如果用的是 YACC 类工具在语义动作里取1第一条目。所有报错都统一走errors.add(lineno, message)这样可以彻底治愈「找不到错在哪行」的毛病。4.5 报告写的功能和代码实现脱节现象实验报告里写了「支持类型检查、作用域、函数调用检查」但源码里根本没有函数调用检查逻辑。答辩时老师随便指一个测试用例代码就露馅。原因报告模板抄了往届代码是按最小可用写的两者不是同一套东西。这其实是实验态度问题但对成绩影响巨大。解决给每个声称支持的特性写一条最小测试用例测试文件里命名清楚比如test_duplicate_decl.c、test_if_scope.c。报告里放上这些测试用例和对应的实际输出有就是有没有就是没有。代码和报告的一致性比单方面做厚报告更能经得住追问。5. 从语义分析到中间代码把类型结果接进三地址码生成很多编译原理实验的进阶要求里语义分析做完要接中间代码生成。二者不是割裂的两个阶段类型检查时顺带生成四元式是最省事的做法。因为遍历 AST 时每个表达式节点的类型已经确定临时变量的类型也就能确定。5.1 三地址码的最小结构四元式四元式是实验里最常见的中间代码形式结构是(op, arg1, arg2, result)。比如a b c * 2翻译成两个四元式QUAD [ (*, c, 2, t1), (, b, t1, t2), (, t2, None, a), ]每次生成一个新临时变量时类型要参照参与运算的两个操作数。上一章里merge_type已经给出了结果类型的判定逻辑生成中间代码时直接复用class TempCounter: def __init__(self): self.count 0 def new_temp(self, type_): name ft{self.count} self.count 1 return name, type_t0、t1这样的命名在后续寄存器分配实验里更好处理因为名字里的数字就是序号天然有序。如果你的实验要求%1或_T0的命名风格只需改new_temp里的字符串格式。5.2 在表达式检查的返回值里多带一个«地址»到这里check_expr的返回类型要从单一的类型值扩展成一个(类型, 存放位置)的元组。存放位置可以是变量名、临时变量名或数字常量。这样父节点才能拿到子节点的结果到底存在哪从而生成四元式def gen_expr(node, scope, quads, temps, errors): if node.kind num: return node.type, str(node.value) if node.kind id: sym scope.lookup(node.value) if sym is None: errors.add(node.lineno, f未声明的变量: {node.value}) return error, None return sym.type, node.value if node.kind bin_op: lt, la gen_expr(node.left, scope, quads, temps, errors) rt, ra gen_expr(node.right, scope, quads, temps, errors) if lt error or rt error: return error, None result_t merge_type(lt, rt, node.op, node.lineno, errors) temp, _ temps.new_temp(result_t) quads.append((node.op, la, ra, temp)) return result_t, temp注意这里new_temp每次返回一个新的临时变量所以a b c * 2会先生成乘法临时变量再生成加法临时变量顺序和运算优先级天然一致。赋值语句变成四元式(, 右值地址, None, 左值名字)控制流语句需要额外处理标签和跳转。5.3 控制流的四元式标签与条件跳转if和while生成中间代码要引入标签地址。常见做法是维护一个跳转指令列表等标签真正确定位置再回填。最简单实用的方案是直接给标签编号指令统一用字符串形式的标签地址def label_new(counter): counter.count 1 return fL{counter.count}if (cond) stmt; else stmt;的四元式序列是这样的模式# 假设 cond 的四元式已经生成结果在 t0 quads.append((jz, t0, None, L_false)) # 生成 then 分支代码 quads.append((jmp, None, None, L_end)) # L_false: # 生成 else 分支代码 # L_end:jz是「条件为 false 跳转」jmp是无条件跳转。具体命名依实验要求而定但结构都逃不出这三块条件跳转到 else 入口、then 结束跳到 end、else 入口和 end 标签。写的时候最容易被漏的是 else 分支前的无条件跳转——如果没有jmp L_end执行完 then 会直接穿进 else 分支这是中间代码生成实验里最高频的翻车点。控制流代码生成加进来后语义分析就不只是「检查器」而是变成了一个小型翻译器。实验验收时如果能演示出输入源码、输出四元式文件再配上简单的解释器执行文件验证结果基本就是满分的展示了。6. 验证语义分析器的两个习惯最小测试集与符号表快照写完语义分析器别急着交报告先搭一个最朴素的回归测试。我个人的习惯是维护两个测试文件夹一个放合法程序一个放非法程序。合法程序必须全部通过非法程序必须报告你期望的错误多报和少报都算 bug。测试文件用最简单的断言脚本就能跑python analyzer.py test_legal_1.c result.txt grep -q 错误 result.txt echo FAIL: 合法程序被报错 || echo PASS: test_legal_1非法程序的检查反过来python analyzer.py test_illegal_type.c result.txt grep -q 类型不匹配 result.txt echo PASS || echo FAIL: 没报类型错误不要只测「报没报错」还要测错误信息里有没有行号。我会在测试脚本里加一个断言用正则提取行号确认它落在输入文件的真实行范围内。这个细节能逼着你把行号透传机制修干净。第二个习惯和符号表有关。调试作用域问题时光看错误列表不够我一般会在每个块的入口打印符号表快照def dump_scope(scope, indent0): for name, sym in scope.table.items(): print( * indent f{sym.kind} {name}: {sym.type}) if scope.parent: dump_scope(scope.parent, indent 1)打印时从当前层开始一层层往外打缩进代表作用域深度。配合测试用例看输出能立刻发现变量是不是在退出块后仍留在链里。这个方法比盯着 AST 发呆有效率得多因为它直接暴露了符号表的真实层次。这套验证方式我沿用了很多年从编译原理实验一直用到给静态分析工具做回归。它不依赖框架核心就是「合法用例不报错、非法用例必须报具体错」。语义分析器的复杂度会随着语法扩展快速上升没有这套最小测试集你根本分不清新加的特性是把老功能改坏了还是自己没调通。希望这个习惯帮你也把实验三做扎实。本文还有配套的精品资源点击获取