简介面向编译原理课程实验三的语义分析实现资料基于Java语言完成编译器前端语义分析阶段涵盖词法分析、语法分析、抽象语法树构建与类型检查。资源包共101个文件以35个Java源码、14个XML配置、12个prefs工程设置为主另有class编译产物、log与txt说明文件等整体约88KB结构紧凑、便于下载。已有1781人浏览学习。实验工程包含完整的IDE项目结构导入后可直接运行调试适合对照学习类型检查、作用域解析、符号表设计、常量折叠等语义分析核心点。通过阅读源码可直观理解AST的表示与遍历方式以及强类型语言中变量定义与类型匹配的检查流程。资料还保留了工程缓存与索引文件可作为排查编译器构建问题的参考。该资源尤其适合正在完成编译原理实验、课程设计或备考复习的高校学生也适合用于教学演示与二次开发。1. 语义分析到底在查什么为什么语法正确的程序照样会崩做过编译原理实验的人都知道词法分析过了、语法分析也过了不代表程序就能跑。语法分析只保证句子“形状”对好比一句话主谓宾都齐了但宾语到底是不是个动词、主语存不存在它不管。语义分析干的就是这件事在生成目标代码之前先把“类型对不上”“变量没声明”“作用域串了”“函数参数个数不对”这一类错误拦住。我的经验是这一站最容易被新手低估。很多人把语法分析写得挺漂亮一到语义分析就开始糊弄最后要么是符号表设计得一塌糊涂要么是类型检查只做了个皮毛。本篇文章就把语义分析实验面向常见教学编译器比如类 C 的 Mini 语言或 PL/0 的扩展拆开讲清楚符号表怎么组织、类型检查怎么设计、错误怎么恢复、边界情况怎么处理以及怎么验证你做出来的东西真的合格。2. 把语义分析拆成两件事符号表与类型系统的设计语义分析看似复杂但核心就两件事收集信息、检查约束。收集信息靠符号表检查约束靠类型系统。搞懂这两个东西后面所有代码都是围绕它们在转。2.1 三个阶段的边界词法、语法、语义到底各管什么在写代码前先彻底分清一个常见误区。词法分析Lexer负责把源码切成 token它只认字符不认上下文看到int就返回一个 INT 关键字 token它根本不在乎这个int是用在变量声明还是函数返回类型。语法分析Parser负责根据文法把 token 序列组织成一棵语法树它只关心结构例如int a hello在语法上完全合法——因为这符合“类型 标识符 等号 表达式 分号”的产生式。语义分析则站在语法树之上问三个问题这个a在当前的代码块里声明过吗符号a的类型和字符串hello的类型一致吗函数调用时实参的个数和形参对得上吗如果语义分析发现了这些问题就说明代码“可以被语法接受但不可能被机器正确执行”。三个阶段的输入输出可以看这张表阶段输入输出关注点词法分析源码字符流Token 序列单词拼写是否合法语法分析Token 序列语法树 / 分析树句子结构是否符合文法语义分析语法树 / 分析树带类型标注的语法树 错误报告名字是否绑定、类型是否一致、作用域是否合法这张表帮我解决过很多次“这个报错该归谁管”的争执。语法分析器遇到a b它只知道这是一个加法表达式a是标识符还是函数名它不判断。语义分析器才会去查符号表。你要是把语义检查的职责塞进语法分析里代码会变得难以维护错误报告也会经常在错误的阶段被打印出来。2.2 顶层符号表与嵌套作用域的组织形式大多数教学编译器的作用域规则都参考了 C 语言一个块Block内声明的变量只能在本块内访问嵌套块看到外层变量但内层可以遮蔽外层同名变量。我用得最顺手的结构是“符号表栈”也叫作用域栈。具体做法是全局作用域作为栈底每进入一个{ }块或一个函数体就往栈顶压一个新的作用域表每离开这个块就弹出它。查询符号时从栈顶往栈底逐层找最先找到的那个就是当前可见的定义。这里的第一版实现可以长这样以 Python 为例很多课设也允许用 Python 搭整个前端class SymbolTableStack: def __init__(self): # 栈底的全局作用域 self.scope_stack [{}] def enter_scope(self): # 进入新作用域压一个新的字典作为符号表 self.scope_stack.append({}) def exit_scope(self): # 离开当前作用域弹出最上层 assert len(self.scope_stack) 1 self.scope_stack.pop() def declare(self, name, symbol): # 只在最顶层作用域声明 scope self.scope_stack[-1] if name in scope: raise SemanticError(f变量 {name} 在本作用域重复声明) scope[name] symbol def lookup(self, name): # 从顶层往底层遍历 for scope in reversed(self.scope_stack): if name in scope: return scope[name] return None这里有个设计决策需要注意declare只检查当前顶层作用域有没有同名符号而不是查整条作用域链。也就是说外层声明了int x内层再声明float x是允许的——这叫遮蔽shadowing。有的实验要求禁止遮蔽有的允许以你的实验指导书为准。如果要求禁止把重复检查改成lookup(name) is not None即可。2.3 类型系统的取舍到底要不要做类型等价类型检查是语义分析的另一个重头戏。教学编译器里一般有两种策略完全等价比对以及兼容性比对。完全等价比对要求两边的类型必须是同一个节点例如int和int才能通过兼容性比会额外处理int到float的提升通常发生在算术表达式里。我建议实验的第一版只做“精确匹配”不要一开始就引入类型提升。原因是提升规则会让检查函数变得发散——你很快会发现自己纠结于char能不能和int相加、float数组和int数组是不是同一类型这类问题而这些问题在课程实验里通常不是重点。类型本身也需要设计成结构化数据。很多课设采用字符串表示类型例如int、float[]这样做简单但不严密。函数类型尤其容易翻车例如int foo(int, float)不能简单存成字符串去比较。我常用的做法是定义一个统一的表示class Type: def __init__(self, kind, elemNone, paramsNone): self.kind kind # int / float / char / array / function self.elem elem # 数组类型指向元素类型 self.params params # 函数类型指向形参类型列表 def __eq__(self, other): if other is None: return False if self.kind ! other.kind: return False if self.kind array: return self.elem other.elem if self.kind function: return len(self.params) len(other.params) and all( a b for a, b in zip(self.params, other.params) ) return True这段代码的要点是递归比较。数组类型要比较元素类型函数类型要比较形参列表的每一项。不要指望用id()或者字符串拼出来比那是给自己埋坑。3. 把语法树接到语义分析遍历、属性标注与最小检查器有了符号表和类型系统接下来就是从语法分析器手里接过那棵语法树完成真正的检查。教学编译器里这一步通常有两种做法一种是在语法分析的同时边归约边做语义动作另一种是先建完整棵语法树再单独遍历。我强烈建议用后者。混在一起写语法分析的排错和语义的排错会互相干扰改一个文法就要动一遍语义代码。3.1 语法树的节点设计要预留语义信息的位置如果你是从零开始写实验语法树节点不要只存儿子列表。每个节点最好留一个attr字段用来存放推导出的类型、符号引用或常量值。否则你后面做类型标注时会发现要么额外维护一张“节点到类型”的映射表要么到处改节点的构造函数。class ASTNode: def __init__(self, kind, childrenNone): self.kind kind # Program / VarDecl / Assign / ... self.children children or [] self.type None # 语义分析后填充可能是 Type 对象 self.symbol None # 指向符号表中的条目 self.value None # 常量折叠需要的值可选这是整个语义分析实验里最容易被忽略的一步。所有后来的检查逻辑都依赖这两个字段type用于类型检查symbol用于变量使用与声明之间的绑定。如果没有它们你每走到一个表达式节点都不得不再查一次符号表不仅慢而且处理嵌套赋值和函数调用时会丢失上下文。3.2 一次完整的语义分析流程声明收集、表达式检查、函数体检查配合上面这种 AST 结构我会写一个递归下降式的语义分析器把三种主要节点分开处理。一是声明节点负责向符号表里登记变量二是表达式节点负责推导类型并检查二元运算的操作数类型三是语句节点负责处理赋值左侧的可写性、条件表达式是否为布尔类型等。class SemanticAnalyzer: def __init__(self): self.tables SymbolTableStack() def visit_program(self, node): for child in node.children: self.visit(child) def visit_var_decl(self, node): # 声明节点type 已经由语法分析或之前的步骤告知 # 检查重复声明在 declare 里已经存在此处只需登记 for name, init_node in node.items: if init_node is not None: init_type self.visit(init_node) if init_type is not None and not (node.var_type init_type): self.error(node, f初始化器类型不匹配期望 {node.var_type}得到 {init_type}) self.tables.declare(name, Symbol(name, node.var_type)) def visit_binary_expr(self, node): left_type self.visit(node.left) right_type self.visit(node.right) if node.op in (, -, *, /): if left_type is None or right_type is None: return None if not (left_type right_type): self.error(node, f双目运算两侧类型不一致{left_type} / {right_type}) node.type left_type return left_type # 关系运算要求两侧类型一致结果类型为 int1 表真0 表假 if node.op in (, , , , , !): if left_type is not None and right_type is not None and left_type ! right_type: self.error(node, f关系运算两侧类型不一致{left_type} / {right_type}) node.type int_type return int_type def error(self, node, msg): # 收集错误而不是立即抛出以便一次性报告所有问题 self.errors.append(f{node.line}:{node.col} {msg})这段代码有一个非常重要的设计error只是记录不中断分析。这是语义分析和语法分析在错误处理上的最大区别——语法分析经常使用 panic mode 跳过错词语义分析更适合“收集完所有错误最后一起报”。因为语义错误相互独立的时候更多你查到一半停下来用户每改一次错误就要重新跑一遍编译非常低效。3.3 赋值检查与函数调用检查的攻防细节赋值语句的正确性检查重点在左侧。a b c在语法上可能是合法的取决于文法定义但语义上左侧不是一个左值lvalue因此要在visit_assign里单独检查左侧节点的可写性。函数调用检查则要同时做两件事查函数符号是否存在逐个检查实参类型与形参类型是否一致。很多初级实现只会检查参数的个数把类型比对漏了。漏掉类型比对的结果非常隐蔽一个期望int形参的函数被传入了float数组生成的代码可能恰好能算出某几个值原因是内存布局上的巧合。下面的检查函数把这两个规则合在一起def visit_func_call(self, node): # node.name 是函数名node.args 是实参节点列表 sym self.tables.lookup(node.name) if sym is None or sym.type.kind ! function: self.error(node, f调用未声明的函数 {node.name}) return None if len(node.args) ! len(sym.type.params): self.error(node, f函数 {node.name} 的实参个数不正确期望 {len(sym.type.params)}得到 {len(node.args)}) return None for arg_node, param_type in zip(node.args, sym.type.params): arg_type self.visit(arg_node) if arg_type is not None and arg_type ! param_type: self.error(node, f函数 {node.name} 的实参类型不匹配期望 {param_type}得到 {arg_type}) node.type sym.type.return_type return node.type这里我特意用了sym.type.kind function而不是用isinstance或单独的字段来区分变量与函数。原因是一个名字可以在不同作用域里分别代表变量和函数统一用类型的kind去判断可以少写很多分支。4. 错误报告与错误恢复报错要准、停得要晚语义分析器的输出不是“有没有错误”而是一份让人改得动的错误清单。这一章专门讲怎么把错误报告做好以及分析过程里遇到错误之后程序该怎样继续走下去。4.1 错误分级的三个等级与输出格式我不会把所有问题都一刀切当作“错误”。在实验里我常用三个等级error、warning、note。error 是必须修的语义问题比如类型不匹配、未声明变量warning 是可疑但不至于阻断生成代码的情况比如变量声明了却从未被读取note 是辅助信息例如“该符号在上一个作用域里的定义在这里”。输出格式我统一用文件名:行号:列号: 等级: 信息这和主流的编译器输出风格对齐也方便在编辑器里点击跳转。一个具体的输出例子是test.c:12:5: error: variable p is not declared in this scope test.c:13:2: warning: variable cnt is set but not used注意不要只给错误信息不给位置。语义分析的报错位置比语法分析还讲究——同样的变量名在不同行可能指不同的实体你不给行列号用户在很长的一个函数里根本定位不到是哪一次引用出了问题。4.2 如何在检测到错误后继续分析而不是直接崩溃继续分析的常见术语叫“错误恢复”。语法分析里常用同步记号集合的办法删除 token 直到下一个分号或}。语义分析里则不同我们的抓手是在某个节点检查失败后给这个节点一个合规的默认类型让父节点继续计算。例如检查二元表达式int int * float时内层乘法节点的两侧类型不一致那么我记录一条错误后把乘法节点的类型临时标记为int或干脆标记为 unknown然后让外层加法继续比较。这样一次运行能同时报出多个独立的类型错误。def visit_binary_expr(self, node): left_type self.visit(node.left) right_type self.visit(node.right) if left_type is None or right_type is None: node.type int_type return int_type if left_type ! right_type: self.error(node, f类型不匹配{left_type} / {right_type}) # 关键仍然设置一个默认类型让上面的访问者能够继续 node.type int_type else: node.type left_type return node.type这条“污染但继续”的策略是语义分析器的保命绳。放弃任何一个节点的类型传播都会导致一连串虚假错误用户看到 50 条报错其中 45 条是同一处错误引发的次生灾害。你的实验报告里如果能写明白自己是怎么区分“原始错误”和“次生错误”的会比只贴代码更有说服力。4.3 错误列表的收集全局累计、按序报告我坚持把错误收集到一个列表等整棵树遍历完再统一输出。不要在error()方法里直接print。原因是编译器的前端可能会在多线程场景下多次调用分析器例如学生提交批量测试)直接打印会把不同源文件的问题混在一起。统一收集也方便你做去重——同一个节点被访问两遍时错误不应该记两次。class Diagnostic: def __init__(self, filename): self.filename filename self.errors [] self.warnings [] def report_error(self, node, msg): self.errors.append(f{self.filename}:{node.line}:{node.col}: error: {msg}) def report_warning(self, node, msg): self.warnings.append(f{self.filename}:{node.line}:{node.col}: warning: {msg}) def has_error(self): return len(self.errors) 0 def dump(self): # 先输出错误再输出警告避免警告淹没错误 for e in self.errors: print(e) for w in self.warnings: print(w)这里要强调一个细节错误先于警告输出但警告不要丢弃。很多人图省事只收集错误结果变量未使用的提示全没了。这类警告在教学实验的查重和代码规范检查里经常被关注留着它对你只有好处。5. 语义分析避坑手册按现象、原因、解决三步走这一章写的是我见过、也踩过的最典型的坑。每条都按现象、原因、解决三个层次写方便你在自己的实验里对照排查。5.1 坑一同一个变量名在内层声明后外层同名变量消失现象代码里有全局变量int x主函数里声明了float x函数内部使用x时类型正确但函数结束之后继续使用x分析器却报“变量 x 未声明”。如果你只有一张平铺的符号表没法解释这个问题。原因符号表没有做作用域栈或者exit_scope()把整张表都弹掉了而不是只弹当前层。另一个常见原因是在声明新变量时使用了覆盖写而不是在顶层新作用域里插入导致全局表的x被破坏。解决确认enter_scope()和exit_scope()是成对调用且退出时只弹出栈顶。查询使用reversed从栈顶开始遍历。调试时可以打印整个作用域栈的完整状态确认全局作用域始终在栈底未被动过。5.2 坑二数组下标用浮点数表达式居然没报错现象float a[10]; a[i0.5] 1;被分析器放行直到目标代码生成阶段才发现下标不是整数。这一般不是生成器的问题而是语义分析时数组下标没有检查类型。原因访问数组元素时很多同学的实现只检查了下标表达式的语法树存在没有检查它的类型。更隐蔽的是有的检查只比对kind到底是不是float忽略了int float这种表达式的整体类型已经是float。解决在visit_array_access节点里递归拿到下标表达式的类型只允许整型有的实验还允许字符型因为字符本质是小整数。一旦发现浮点型下标直接报 error 并把默认类型标为整型以继续分析。5.3 坑三函数声明重复时错误信息位置乱跳现象声明了两次int foo(int x) { ... }第一次报错的位置在函数体内部而不是在函数名那一行。这让用户一头雾水。原因很多实现在分析函数头之后、分析函数体之前没有立刻检查重复函数名。等到分析函数体时符号表里已经登记了第二个函数这时才发现冲突但报错位置已经指向了函数体内的某个语句。解决把“函数名唯一性检查”放到进入函数体之前。也就是说检查时机应当和旧的作用域清理保持严格同步函数头部分一旦发现表里已有同名函数马上报错并跳过后面的整个函数体。5.4 坑四三元表达式两个分支的类型不一致时分析器直接崩溃现象输入a b ? 1 : x分析器报错后整棵树的后续节点全部变成 UnknownType连没有错误的下一行语句也跟着报错。原因在visit_conditional_expr里检测到类型不一致后直接抛了异常或返回了 None而没有给整个条件表达式一个默认类型。父节点拿到 None 后所有类型运算都失败了后续检查连环爆炸。解决与前面“错误恢复”一节完全一致分支类型不同时记录 error 后统一给条件表达式标记为默认类型按实验语言的定义通常是 int然后继续向上传播。这样原始错误只报一条次生错误为零。6. 验证语义分析器是否合格AST 标注与符号表快照两种手段写完了分析器接下来的问题是你怎么知道它真的对了手动测几条简单用例远远不够这一章分享两个落地且低成本的验证手段。6.1 给语法树打类型标注并输出让你的分析器在遍历 AST 的同时把每个节点的type填充好然后写一个 dump 函数把这些类型打印出来。比较输入源码的预期类型和实际输出的差异能快速定位是哪个函数漏查了。这个 dump 不用做得复杂有缩进就够了。def dump_typed_ast(node, indent0): prefix * indent if node.type is not None: print(f{prefix}{node.kind} : {node.type.kind}) else: print(f{prefix}{node.kind}) for child in node.children: dump_typed_ast(child, indent 1)注意这步的输出本身也是你写实验报告时的重要截图素材。很多老师的评分点里有一条叫“能够展示语义分析后的中间表示”你不可能靠运行时的打印来证明但 dump 出来的带类型 AST 是最直观的证据。6.2 符号表快照每个作用域结束后打印一次在exit_scope()之后把当前作用域里的所有名字和类型打印出来。作用域栈的每一层单独成块显示既能看到遮蔽现象又能验证生命周期。操作方法是写一个snapshot()函数放在 SymbolTableStack 里只打印scope_stack[-1]这一层在exit_scope调用它。然后构造一个带嵌套块的小程序逐层对照输出。这种方法对付作用域泄漏最有效。我有一次就是靠这个快照发现某个数组定义被错误地放进了函数体内的子作用域出了函数体后数组消失了但引用它的代码还在。6.3 批量测试思路与常见测试用例设计当一个手动用例也测不过时你需要的最简单的测试策略是按类目分组变量类未声明、重复声明同层、遮蔽跨层、声明未使用类型类初始化器类型不匹配、二元运算两侧不一致、数组下标非整数、赋值类型不匹配控制流类条件表达式的分支类型不一致、while 循环条件非整数教学语言里常以 0/1 表真假函数类调用未声明函数、实参个数错误、实参类型错误、返回值类型与函数声明不一致每一类准备一个正面用例和一个反面用例。正面用例必须零错误通过反面用例必须精确报出你期望的那一条错误。我自己的习惯是把这些用例放进一个目录再用一个小脚本批量运行语义分析器并比对退出码。发现某条报错不匹配时先用 6.1 的 dump 和 6.2 的 snapshot 查看中间状态再决定改符号表还是改类型检查函数。这比在集成环境里逐个调试快得多。这一套流程走下来语义分析器才算是真正能交出去的东西。希望帮到你。本文还有配套的精品资源点击获取