语义分析实战（二）—— 类型检查器
章节标题
类型检查器的核心作用
类型检查是语义分析的重要组成部分，它的主要作用是：
- 确保类型一致性：检查表达式和语句中的类型是否匹配
- 捕获类型错误：在编译时发现潜在的类型错误，避免运行时错误
- 支持类型推导：在某些语言中，根据上下文推导变量的类型
- 为代码生成提供信息：类型信息对后续的代码生成和优化非常重要
类型环境的设计
类型环境是类型检查器的核心数据结构，它用于：
- 存储变量类型：记录程序中变量的类型信息
- 管理作用域：处理不同作用域中的类型信息
- 支持类型查找：在类型检查过程中快速查找变量的类型
类型环境的实现
我们可以基于之前实现的符号表来构建类型环境：
class TypeEnvironment:
"""类型环境类"""
def __init__(self, symbol_table):
self.symbol_table = symbol_table
def get_type(self, name):
"""获取变量的类型"""
symbol = self.symbol_table.lookup(name)
if symbol and symbol.symbol_type == "variable":
return symbol.attributes.get("datatype")
return None
def set_type(self, name, datatype):
"""设置变量的类型"""
symbol = self.symbol_table.lookup(name)
if symbol and symbol.symbol_type == "variable":
symbol.attributes["datatype"] = datatype
return True
return False
def add_variable(self, name, datatype):
"""添加变量到类型环境"""
return self.symbol_table.insert(name, "variable", {"datatype": datatype})
def add_function(self, name, return_type, param_types):
"""添加函数到类型环境"""
return self.symbol_table.insert(name, "function", {
"return_type": return_type,
"param_types": param_types
})
def get_function_type(self, name):
"""获取函数的类型信息"""
symbol = self.symbol_table.lookup(name)
if symbol and symbol.symbol_type == "function":
return symbol.attributes
return None表达式类型检查
表达式类型检查的基本原理
表达式类型检查的核心是根据表达式的结构和操作符的类型规则，推导出表达式的类型，并检查类型是否一致。
常见表达式的类型检查
变量引用：
- 查找变量的类型
- 如果变量未定义，报告错误
常量：
- 数字常量：int 或 float
- 字符串常量：string
- 布尔常量：bool
算术表达式：
- 检查操作数是否为数值类型
- 推导出结果类型
关系表达式：
- 检查操作数类型是否兼容
- 结果类型为 bool
逻辑表达式：
- 检查操作数是否为 bool 类型
- 结果类型为 bool
函数调用：
- 检查函数是否存在
- 检查实参类型是否与形参类型匹配
- 结果类型为函数的返回类型
语句类型检查
语句类型检查的基本原理
语句类型检查的核心是检查语句的语法和语义是否正确，特别是类型是否一致。
常见语句的类型检查
赋值语句：
- 检查左值是否可赋值
- 检查右值类型是否与左值类型匹配
条件语句：
- 检查条件表达式是否为 bool 类型
- 递归检查分支语句
循环语句：
- 检查循环条件是否为 bool 类型
- 递归检查循环体语句
函数定义：
- 检查参数类型是否合法
- 检查函数体语句
- 检查返回语句类型是否与函数返回类型匹配
变量声明：
- 检查类型是否合法
- 检查初始化表达式类型是否与声明类型匹配
类型检查器的实现
1. 类型检查器类
class TypeChecker:
"""类型检查器类"""
def __init__(self, type_env):
self.type_env = type_env
self.errors = []
def error(self, message, line=None):
"""记录类型错误"""
if line:
error_msg = f"Line {line}: {message}"
else:
error_msg = message
self.errors.append(error_msg)
print(f"ERROR: {error_msg}")
def get_errors(self):
"""获取所有类型错误"""
return self.errors
def has_errors(self):
"""检查是否有类型错误"""
return len(self.errors) > 02. 表达式类型检查方法
def check_expression(self, expr, line=None):
"""检查表达式类型"""
if expr['type'] == 'variable':
return self.check_variable(expr, line)
elif expr['type'] == 'constant':
return self.check_constant(expr, line)
elif expr['type'] == 'binary_op':
return self.check_binary_op(expr, line)
elif expr['type'] == 'unary_op':
return self.check_unary_op(expr, line)
elif expr['type'] == 'function_call':
return self.check_function_call(expr, line)
else:
self.error(f"Unknown expression type: {expr['type']}", line)
return None
def check_variable(self, expr, line=None):
"""检查变量引用"""
name = expr['name']
var_type = self.type_env.get_type(name)
if var_type is None:
self.error(f"Undefined variable: {name}", line)
return None
return var_type
def check_constant(self, expr, line=None):
"""检查常量"""
value = expr['value']
if isinstance(value, int):
return 'int'
elif isinstance(value, float):
return 'float'
elif isinstance(value, str):
return 'string'
elif isinstance(value, bool):
return 'bool'
else:
self.error(f"Unknown constant type: {type(value).__name__}", line)
return None
def check_binary_op(self, expr, line=None):
"""检查二元操作符"""
op = expr['op']
left_type = self.check_expression(expr['left'], line)
right_type = self.check_expression(expr['right'], line)
if left_type is None or right_type is None:
return None
# 算术操作符
if op in ['+', '-', '*', '/', '%']:
if left_type not in ['int', 'float'] or right_type not in ['int', 'float']:
self.error(f"Arithmetic operation requires numeric types, got {left_type} and {right_type}", line)
return None
# 如果有一个操作数是 float，结果就是 float
if left_type == 'float' or right_type == 'float':
return 'float'
return 'int'
# 关系操作符
elif op in ['==', '!=', '<', '<=', '>', '>=']:
if left_type != right_type:
self.error(f"Comparison requires compatible types, got {left_type} and {right_type}", line)
return None
return 'bool'
# 逻辑操作符
elif op in ['&&', '||']:
if left_type != 'bool' or right_type != 'bool':
self.error(f"Logical operation requires boolean types, got {left_type} and {right_type}", line)
return None
return 'bool'
# 赋值操作符
elif op == '=':
# 赋值操作符的类型检查在语句检查中处理
return right_type
else:
self.error(f"Unknown operator: {op}", line)
return None
def check_unary_op(self, expr, line=None):
"""检查一元操作符"""
op = expr['op']
operand_type = self.check_expression(expr['operand'], line)
if operand_type is None:
return None
if op == '!':
if operand_type != 'bool':
self.error(f"Logical negation requires boolean type, got {operand_type}", line)
return None
return 'bool'
elif op == '-':
if operand_type not in ['int', 'float']:
self.error(f"Unary minus requires numeric type, got {operand_type}", line)
return None
return operand_type
else:
self.error(f"Unknown unary operator: {op}", line)
return None
def check_function_call(self, expr, line=None):
"""检查函数调用"""
name = expr['name']
args = expr['args']
# 检查函数是否存在
func_info = self.type_env.get_function_type(name)
if func_info is None:
self.error(f"Undefined function: {name}", line)
return None
# 检查参数数量
expected_params = func_info.get('param_types', [])
if len(args) != len(expected_params):
self.error(f"Function {name} expects {len(expected_params)} parameters, got {len(args)}", line)
return None
# 检查参数类型
for i, (arg, expected_type) in enumerate(zip(args, expected_params)):
arg_type = self.check_expression(arg, line)
if arg_type != expected_type:
self.error(f"Function {name} parameter {i+1} expects {expected_type}, got {arg_type}", line)
return None
# 返回函数的返回类型
return func_info.get('return_type', 'void')3. 语句类型检查方法
def check_statement(self, stmt, line=None):
"""检查语句类型"""
if stmt['type'] == 'assignment':
return self.check_assignment(stmt, line)
elif stmt['type'] == 'if':
return self.check_if(stmt, line)
elif stmt['type'] == 'while':
return self.check_while(stmt, line)
elif stmt['type'] == 'for':
return self.check_for(stmt, line)
elif stmt['type'] == 'return':
return self.check_return(stmt, line)
elif stmt['type'] == 'variable_declaration':
return self.check_variable_declaration(stmt, line)
elif stmt['type'] == 'expression_statement':
return self.check_expression_statement(stmt, line)
elif stmt['type'] == 'block':
return self.check_block(stmt, line)
else:
self.error(f"Unknown statement type: {stmt['type']}", line)
return False
def check_assignment(self, stmt, line=None):
"""检查赋值语句"""
left = stmt['left']
right = stmt['right']
# 检查左值是否为变量
if left['type'] != 'variable':
self.error("Left-hand side of assignment must be a variable", line)
return False
# 获取左值类型
left_type = self.type_env.get_type(left['name'])
if left_type is None:
self.error(f"Undefined variable: {left['name']}", line)
return False
# 检查右值类型
right_type = self.check_expression(right, line)
if right_type is None:
return False
# 检查类型是否匹配
if left_type != right_type:
self.error(f"Type mismatch in assignment: expected {left_type}, got {right_type}", line)
return False
return True
def check_if(self, stmt, line=None):
"""检查 if 语句"""
# 检查条件表达式类型
condition_type = self.check_expression(stmt['condition'], line)
if condition_type != 'bool':
self.error(f"If condition must be boolean, got {condition_type}", line)
return False
# 检查 then 分支
if not self.check_statement(stmt['then_branch'], line):
return False
# 检查 else 分支（如果有）
if 'else_branch' in stmt:
if not self.check_statement(stmt['else_branch'], line):
return False
return True
def check_while(self, stmt, line=None):
"""检查 while 语句"""
# 检查条件表达式类型
condition_type = self.check_expression(stmt['condition'], line)
if condition_type != 'bool':
self.error(f"While condition must be boolean, got {condition_type}", line)
return False
# 检查循环体
if not self.check_statement(stmt['body'], line):
return False
return True
def check_for(self, stmt, line=None):
"""检查 for 语句"""
# 检查初始化语句
if not self.check_statement(stmt['init'], line):
return False
# 检查条件表达式类型
condition_type = self.check_expression(stmt['condition'], line)
if condition_type != 'bool':
self.error(f"For condition must be boolean, got {condition_type}", line)
return False
# 检查更新语句
if not self.check_statement(stmt['update'], line):
return False
# 检查循环体
if not self.check_statement(stmt['body'], line):
return False
return True
def check_return(self, stmt, line=None):
"""检查 return 语句"""
# 获取当前函数的返回类型
# 注意：这里简化处理，实际实现需要跟踪当前函数
current_function = "current_func" # 占位符
func_info = self.type_env.get_function_type(current_function)
if func_info is None:
self.error("Return statement outside function", line)
return False
expected_type = func_info.get('return_type', 'void')
# 如果函数返回类型是 void，检查是否有返回值
if expected_type == 'void':
if 'expression' in stmt:
self.error("Void function should not return a value", line)
return False
return True
# 检查返回表达式类型
if 'expression' not in stmt:
self.error(f"Function expects return type {expected_type}, got nothing", line)
return False
return_type = self.check_expression(stmt['expression'], line)
if return_type != expected_type:
self.error(f"Return type mismatch: expected {expected_type}, got {return_type}", line)
return False
return True
def check_variable_declaration(self, stmt, line=None):
"""检查变量声明"""
name = stmt['name']
var_type = stmt['type']
# 检查类型是否合法
valid_types = ['int', 'float', 'bool', 'string', 'void']
if var_type not in valid_types:
self.error(f"Invalid type: {var_type}", line)
return False
# 检查变量是否已在当前作用域定义
if self.type_env.type_env.symbol_table.lookup_current_scope(name):
self.error(f"Variable {name} already declared in current scope", line)
return False
# 添加变量到类型环境
self.type_env.add_variable(name, var_type)
# 检查初始化表达式（如果有）
if 'initializer' in stmt:
init_type = self.check_expression(stmt['initializer'], line)
if init_type != var_type:
self.error(f"Type mismatch in variable initialization: expected {var_type}, got {init_type}", line)
return False
return True
def check_expression_statement(self, stmt, line=None):
"""检查表达式语句"""
return self.check_expression(stmt['expression'], line) is not None
def check_block(self, stmt, line=None):
"""检查块语句"""
# 进入新作用域
self.type_env.type_env.symbol_table.enter_scope()
# 检查块中的所有语句
for s in stmt['statements']:
if not self.check_statement(s, line):
# 退出作用域
self.type_env.type_env.symbol_table.exit_scope()
return False
# 退出作用域
self.type_env.type_env.symbol_table.exit_scope()
return True实用案例分析
案例：类型检查简单程序
假设我们有以下简单的程序：
int main() {
int x = 5;
float y = 3.14;
bool flag = true;
x = x + 1;
y = y * 2;
flag = x > y;
if (flag) {
int z = x + y;
return z;
} else {
return 0;
}
}我们来看看类型检查器是如何处理的：
- 初始化类型环境：创建全局作用域
- 处理函数定义：
- 添加
main函数到类型环境 - 进入函数作用域
- 添加
- 处理变量声明：
- 添加
x(int) 到类型环境 - 添加
y(float) 到类型环境 - 添加
flag(bool) 到类型环境
- 添加
- 处理赋值语句：
- 检查
x = x + 1：类型匹配 - 检查
y = y * 2：类型匹配 - 检查
flag = x > y：类型匹配
- 检查
- 处理 if 语句：
- 检查条件
flag：类型为 bool - 进入 then 分支作用域
- 添加
z(int) 到类型环境 - 检查
return z：类型匹配 - 退出 then 分支作用域
- 进入 else 分支作用域
- 检查
return 0：类型匹配 - 退出 else 分支作用域
- 检查条件
- 退出函数作用域
类型检查器的测试
下面是一个简单的测试代码，用于测试类型检查器的功能：
# 测试类型检查器
if __name__ == "__main__":
# 创建符号表
from symbol_table import SymbolTable
st = SymbolTable()
# 创建类型环境
te = TypeEnvironment(st)
# 创建类型检查器
tc = TypeChecker(te)
# 添加内置函数
te.add_function("print", "void", ["string"])
te.add_function("input", "string", [])
# 测试表达式类型检查
print("=== Testing Expression Type Checking ===")
# 测试变量声明
var_decl = {
'type': 'variable_declaration',
'name': 'x',
'type': 'int',
'initializer': {
'type': 'constant',
'value': 5
}
}
tc.check_statement(var_decl)
# 测试赋值语句
assignment = {
'type': 'assignment',
'left': {'type': 'variable', 'name': 'x'},
'right': {
'type': 'binary_op',
'op': '+',
'left': {'type': 'variable', 'name': 'x'},
'right': {'type': 'constant', 'value': 1}
}
}
tc.check_statement(assignment)
# 测试类型错误
type_error = {
'type': 'assignment',
'left': {'type': 'variable', 'name': 'x'},
'right': {
'type': 'constant',
'value': "string"
}
}
tc.check_statement(type_error)
# 打印错误
print("\n=== Type Errors ===")
for error in tc.get_errors():
print(error)类型检查器的优化
类型推导：实现 Hindley-Milner 类型推导算法，支持更复杂的类型推导
类型多态：支持泛型和多态类型
类型别名：支持类型别名和自定义类型
错误信息优化：提供更详细、更准确的错误信息
性能优化：使用缓存和其他技术提高类型检查的性能
常见问题及解决方案
类型不匹配：
- 解决方案：在类型检查过程中严格检查类型一致性，提供清晰的错误信息
未定义变量：
- 解决方案：在变量引用时检查变量是否已定义
函数参数不匹配：
- 解决方案：检查函数调用时的参数数量和类型
返回类型不匹配：
- 解决方案：检查 return 语句的类型是否与函数返回类型匹配
复杂表达式的类型推导：
- 解决方案：实现更复杂的类型推导算法，处理嵌套表达式
总结
类型检查器是编译器语义分析阶段的核心组件，它负责检查程序中的类型是否一致，捕获类型错误，为后续的代码生成和优化提供必要的类型信息。
在本集的实战中，我们实现了一个基本的类型检查器，包括类型环境设计、表达式类型检查、语句类型检查等核心功能。这个类型检查器可以处理简单的表达式和语句，但在实际编译器中，类型检查器会更加复杂，需要处理更多的语言特性和类型规则。
通过本集的学习，我们了解了类型检查的基本原理和实现方法，为后续的语义分析和代码生成奠定了基础。在后续的实战中，我们将继续完善语义分析器，实现更复杂的语义分析功能。