第115集：类型检查基础

核心知识点讲解

为什么需要类型检查？

类型检查是语义分析的重要组成部分，它的主要目的是：

  1. 提高程序正确性：在编译时发现类型错误，避免运行时崩溃
  2. 增强代码可读性：类型信息使代码意图更加清晰
  3. 优化代码生成：类型信息有助于编译器生成更高效的代码
  4. 提供更好的IDE支持：类型信息支持代码补全、重构等功能
  5. 减少运行时开销：编译时类型检查可以减少运行时类型检查的需要

类型系统

类型系统是一组规则，用于确定程序中每个表达式的类型，并检查这些类型是否符合语言的规则。类型系统通常包括：

  1. 类型定义：

    • 基本类型：int, float, char, bool 等
    • 复合类型：数组, 结构体, 类, 指针等
    • 函数类型：包含参数类型和返回类型

  2. 类型规则：

    • 类型推断规则：如何确定表达式的类型
    • 类型兼容性规则：不同类型之间何时可以转换
    • 类型等价规则：如何判断两个类型是否相同

  3. 类型检查策略：

    • 静态类型检查：在编译时进行类型检查（如C, Java）
    • 动态类型检查：在运行时进行类型检查（如Python, JavaScript）
    • 混合类型检查：结合静态和动态检查（如TypeScript）

类型等价

类型等价是判断两个类型是否相同的规则，主要有两种策略：

  1. 结构等价：

    • 两个类型的结构相同则视为等价
    • 例如：两个结构体如果有相同的字段和类型，则视为等价
    • 优点：直观，灵活性高
    • 缺点：实现复杂，可能导致意外的类型等价

  2. 名义等价：

    • 两个类型的名称相同则视为等价
    • 例如：即使两个结构体有相同的字段，不同名称也视为不同类型
    • 优点：实现简单，语义明确
    • 缺点：可能不够灵活

类型兼容性

类型兼容性是判断一个类型是否可以转换为另一个类型的规则，主要包括：

  1. 隐式转换（自动转换）：

    • 编译器自动进行的类型转换
    • 例如：int 转换为 float
    • 通常遵循"安全"原则，不丢失信息

  2. 显式转换（强制转换）：

    • 程序员通过类型转换操作符显式请求的转换
    • 例如：(int)float_value
    • 可能不安全，可能丢失信息

  3. 子类型多态：

    • 子类类型可以转换为父类类型
    • 例如：Cat 类型可以转换为 Animal 类型

  4. 接口实现：

    • 实现了接口的类型可以转换为接口类型
    • 例如：实现了 Runnable 接口的类可以转换为 Runnable 类型

实用案例分析

类型检查示例

静态类型检查

// 正确的类型使用
int x = 10;
float y = x;  // 隐式转换：int -> float

// 类型错误
int a = 10;
char* b = a;  // 错误：类型不兼容，不能将 int 转换为 char*

// 显式转换
float c = 3.14;
int d = (int)c;  // 显式转换：float -> int，可能丢失小数部分

动态类型检查

# Python 中的类型检查
x = 10  # x 是 int 类型
x = "hello"  # x 变为 str 类型（动态类型）

# 运行时类型错误
y = 10
y += "hello"  # 运行时错误：unsupported operand type(s) for +: 'int' and 'str'

类型等价判断

结构等价示例

// C 语言中的结构体（名义等价）
struct Point {
    int x;
    int y;
};

struct Position {
    int x;
    int y;
};

struct Point p;
struct Position q;
p = q;  // 错误：类型不兼容（名义等价）
// TypeScript 中的接口（结构等价）
interface Point {
    x: number;
    y: number;
}

interface Position {
    x: number;
    y: number;
}

let p: Point = { x: 1, y: 2 };
let q: Position = p;  // 正确：结构等价

类型兼容性判断

隐式转换

源类型 目标类型 是否允许隐式转换 说明
int float 是 安全转换，不丢失信息
float int 否 可能丢失小数部分
char int 是 安全转换
int char 否 可能溢出
bool int 是 false->0, true->1
int bool 是 0->false, 非0->true

子类型兼容性

// Java 中的继承关系
class Animal {
    void eat() {}
}

class Cat extends Animal {
    void meow() {}
}

class Dog extends Animal {
    void bark() {}
}

// 子类型可以转换为父类型
Animal animal = new Cat();  // 正确：Cat 是 Animal 的子类型
animal.eat();  // 正确
// animal.meow();  // 错误：编译时类型是 Animal

// 父类型转换为子类型需要显式转换
Cat cat = (Cat)animal;  // 正确：运行时类型是 Cat
cat.meow();  // 正确

Dog dog = (Dog)animal;  // 运行时错误：类型转换异常

类型检查的实现

类型检查器的基本工作流程

  1. 遍历抽象语法树：

    • 从根节点开始，递归遍历所有节点
    • 为每个表达式计算类型

  2. 类型环境：

    • 维护当前作用域中的变量及其类型
    • 通常使用符号表实现

  3. 类型规则应用：

    • 对每个语法构造应用相应的类型规则
    • 检查类型是否兼容
    • 报告类型错误

  4. 类型注解：

    • 将计算出的类型信息附加到语法树节点
    • 为后续的代码生成提供信息

简单类型检查器实现

class TypeChecker:
    def __init__(self, symbol_table):
        self.symbol_table = symbol_table
        self.errors = []
    
    def check_expression(self, expr):
        """检查表达式的类型"""
        if expr.type == "binary_op":
            left_type = self.check_expression(expr.left)
            right_type = self.check_expression(expr.right)
            
            if expr.op in ["+", "-", "*", "/"]:
                if left_type == "int" and right_type == "int":
                    return "int"
                elif left_type == "float" or right_type == "float":
                    return "float"
                else:
                    self.errors.append(f"Type error: invalid operands for {expr.op}")
                    return "error"
            
            elif expr.op in ["==", "!=", "<", ">", "<=", ">="]:
                if left_type == right_type:
                    return "bool"
                else:
                    self.errors.append(f"Type error: comparing different types")
                    return "error"
        
        elif expr.type == "identifier":
            symbol = self.symbol_table.lookup(expr.name)
            if symbol:
                return symbol.type
            else:
                self.errors.append(f"Type error: undefined variable {expr.name}")
                return "error"
        
        elif expr.type == "literal":
            if isinstance(expr.value, int):
                return "int"
            elif isinstance(expr.value, float):
                return "float"
            elif isinstance(expr.value, bool):
                return "bool"
            elif isinstance(expr.value, str):
                return "string"
        
        return "error"
    
    def check_statement(self, stmt):
        """检查语句的类型"""
        if stmt.type == "assignment":
            var_type = self.symbol_table.lookup(stmt.var).type
            expr_type = self.check_expression(stmt.expr)
            
            if var_type != expr_type:
                # 检查是否可以隐式转换
                if (var_type == "float" and expr_type == "int") or \
                   (var_type == "int" and expr_type == "bool"):
                    # 允许隐式转换
                    pass
                else:
                    self.errors.append(f"Type error: cannot assign {expr_type} to {var_type}")
        
        elif stmt.type == "if":
            cond_type = self.check_expression(stmt.condition)
            if cond_type != "bool":
                self.errors.append(f"Type error: if condition must be bool, got {cond_type}")
            
            for body_stmt in stmt.body:
                self.check_statement(body_stmt)
            
            if stmt.else_body:
                for else_stmt in stmt.else_body:
                    self.check_statement(else_stmt)
    
    def check_program(self, program):
        """检查整个程序的类型"""
        for stmt in program.statements:
            self.check_statement(stmt)
        
        return self.errors

小结

类型检查是编译器确保程序正确性的重要手段：

  • 类型系统：定义了类型的规则和检查策略
  • 类型等价：判断两个类型是否相同的规则
  • 类型兼容性：判断类型之间是否可以转换的规则
  • 实现方法：通过遍历AST并应用类型规则来实现

不同的编程语言有不同的类型系统设计，编译器需要根据语言的规则实现相应的类型检查器。类型检查的严格程度和灵活性之间的平衡是语言设计的重要考虑因素。

« 上一篇 符号表（三） 下一篇 » 表达式类型检查
↑