1
int foo(int x) {
2
    float y = 3.14;
3
    return x + y;  // int + float → 隐式转换为 float，但返回 int → 类型错误？
4
}

1
# 类型规则的表示
2
# Γ ⊢ e1 : T1    Γ ⊢ e2 : T2    T1 和 T2 可相加
3
# ────────────────────────────────────────────────────
4
# Γ ⊢ e1 + e2 : T_result
5

6
class TypeChecker:
7
    """类型检查器"""
8

9
    # 算术运算的类型规则
10
    ARITH_RULES = {
11
        ('int', 'int'): 'int',
12
        ('int', 'float'): 'float',
13
        ('float', 'int'): 'float',
14
        ('float', 'float'): 'float',
15
    }
16

17
    # 比较运算的结果类型
18
    CMP_RESULT = 'bool'
19

20
    def check_binary_op(self, op: str, left_type: str, right_type: str) -> str:
21
        """检查二元运算的类型合法性"""
22
        if op in ('+', '-', '*', '/'):
23
            key = (left_type, right_type)
24
            if key not in self.ARITH_RULES:
25
                raise TypeError(
26
                    f"Cannot apply '{op}' to {left_type} and {right_type}"
27
                )
28
            return self.ARITH_RULES[key]
29

30
        elif op in ('<', '>', '==', '!=', '<=', '>='):
31
            if left_type != right_type:
32
                raise TypeError(
33
                    f"Cannot compare {left_type} and {right_type}"
34
                )
35
            return self.CMP_RESULT
36

37
        else:
38
            raise TypeError(f"Unknown operator: {op}")

1
@dataclass
2
class Symbol:
3
    name: str           # 符号名称
4
    type: str           # 类型
5
    kind: str           # 种类：variable, function, parameter, type
6
    scope: int          # 所在作用域层级
7
    offset: int         # 栈帧偏移（用于代码生成）
8
    is_initialized: bool  # 是否已初始化
9
    line: int           # 声明所在行号
10

11
class SymbolTable:
12
    """符号表"""
13

14
    def __init__(self):
15
        self.scopes = [{}]  # 作用域栈，全局作用域在最底层
16
        self.scope_counter = 0
17

18
    def enter_scope(self):
19
        """进入新作用域"""
20
        self.scope_counter += 1
21
        self.scopes.append({})
22

23
    def exit_scope(self):
24
        """退出作用域"""
25
        self.scopes.pop()
26

27
    def define(self, symbol: Symbol):
28
        """在当前作用域定义符号"""
29
        current_scope = self.scopes[-1]
30
        if symbol.name in current_scope:
31
            raise SemanticError(
32
                f"Redefinition of '{symbol.name}' at line {symbol.line}"
33
            )
34
        current_scope[symbol.name] = symbol
35

36
    def lookup(self, name: str) -> Symbol:
37
        """查找符号，从内层作用域向外层搜索"""
38
        for scope in reversed(self.scopes):
39
            if name in scope:
40
                return scope[name]
41
        raise SemanticError(f"Undefined symbol: '{name}'")
42

43
    def lookup_current_scope(self, name: str) -> Symbol:
44
        """只在当前作用域查找"""
45
        if name in self.scopes[-1]:
46
            return self.scopes[-1][name]
47
        return None

1
# HM 类型推导的核心算法：Algorithm W
2

3
class TypeVar:
4
    """类型变量"""
5
    def __init__(self, name):
6
        self.name = name
7
        self.instance = None  # 绑定的具体类型
8

9
class TypeOperator:
10
    """类型构造器"""
11
    def __init__(self, name, args):
12
        self.name = name
13
        self.args = args  # 参数类型列表
14

15
# 基本类型
16
INT_TYPE = TypeOperator('int', [])
17
FLOAT_TYPE = TypeOperator('float', [])
18
BOOL_TYPE = TypeOperator('bool', [])
19

20
# 函数类型：a -> b
21
def function_type(arg_type, ret_type):
22
    return TypeOperator('->', [arg_type, ret_type])
23

24
def unify(t1, t2, subst):
25
    """合一算法：找到使 t1 = t2 的替换"""
26
    t1 = prune(t1, subst)
27
    t2 = prune(t2, subst)
28

29
    if isinstance(t1, TypeVar):
30
        if t1 != t2:
31
            if occurs_in(t1, t2, subst):
32
                raise TypeError("Recursive type")
33
            subst[t1.name] = t2
34
    elif isinstance(t2, TypeVar):
35
        unify(t2, t1, subst)
36
    elif isinstance(t1, TypeOperator) and isinstance(t2, TypeOperator):
37
        if t1.name != t2.name or len(t1.args) != len(t2.args):
38
            raise TypeError(f"Cannot unify {t1.name} with {t2.name}")
39
        for a1, a2 in zip(t1.args, t2.args):
40
            unify(a1, a2, subst)
41
    else:
42
        raise TypeError(f"Cannot unify types")
43

44
def prune(t, subst):
45
    """跟随替换链"""
46
    if isinstance(t, TypeVar) and t.name in subst:
47
        return prune(subst[t.name], subst)
48
    return t

1
# 推导 let f = fun x -> x + 1 的类型
2
# 1. x : α (新类型变量)
3
# 2. 1 : int
4
# 3. x + 1 : 需要 x : int，所以 α = int
5
# 4. fun x -> x + 1 : int -> int
6
# 5. f : int -> int
7

8
# 推导 let id = fun x -> x 的类型
9
# 1. x : α (新类型变量)
10
# 2. x : α
11
# 3. fun x -> x : α -> α
12
# 4. id : ∀α. α -> α (多态类型)

1
class SemanticAnalyzer(ASTVisitor):
2
    """语义分析器"""
3

4
    def __init__(self):
5
        self.symbol_table = SymbolTable()
6
        self.current_function_return_type = None
7
        self.errors = []
8
        self.loop_depth = 0  # 跟踪嵌套循环深度
9

10
    def error(self, msg, node):
11
        self.errors.append(SemanticError(msg, node))
12

13
    def visit_VarDecl(self, node):
14
        # 检查类型是否有效
15
        if not self.is_valid_type(node.type_name):
16
            self.error(f"Unknown type: {node.type_name}", node)
17
            return
18

19
        # 检查初始化表达式的类型
20
        if node.init:
21
            init_type = self.visit(node.init)
22
            if init_type and not self.is_assignable(node.type_name, init_type):
23
                self.error(
24
                    f"Cannot assign {init_type} to {node.type_name}", node
25
                )
26

27
        # 在符号表中定义变量
28
        symbol = Symbol(
29
            name=node.name,
30
            type=node.type_name,
31
            kind='variable',
32
            scope=self.symbol_table.scope_counter,
33
            offset=0,
34
            is_initialized=node.init is not None,
35
            line=0
36
        )
37
        self.symbol_table.define(symbol)
38

39
    def visit_BinaryOp(self, node):
40
        left_type = self.visit(node.left)
41
        right_type = self.visit(node.right)
42

43
        if left_type and right_type:
44
            try:
45
                return self.check_binary_op(node.op, left_type, right_type)
46
            except TypeError as e:
47
                self.error(str(e), node)
48

49
        return None
50

51
    def visit_Identifier(self, node):
52
        try:
53
            symbol = self.symbol_table.lookup(node.name)
54
            return symbol.type
55
        except SemanticError as e:
56
            self.error(str(e), node)
57
            return None
58

59
    def visit_FuncDecl(self, node):
60
        # 在外层作用域定义函数
61
        func_symbol = Symbol(
62
            name=node.name,
63
            type=node.return_type,
64
            kind='function',
65
            scope=self.symbol_table.scope_counter,
66
            offset=0,
67
            is_initialized=True,
68
            line=0
69
        )
70
        self.symbol_table.define(func_symbol)
71

72
        # 进入函数作用域
73
        self.symbol_table.enter_scope()
74
        self.current_function_return_type = node.return_type
75

76
        # 定义参数
77
        for param in node.params:
78
            param_symbol = Symbol(
79
                name=param.name,
80
                type=param.type_name,
81
                kind='parameter',
82
                scope=self.symbol_table.scope_counter,
83
                offset=0,
84
                is_initialized=True,
85
                line=0
86
            )
87
            self.symbol_table.define(param_symbol)
88

89
        # 分析函数体
90
        self.visit(node.body)
91

92
        # 退出函数作用域
93
        self.symbol_table.exit_scope()
94
        self.current_function_return_type = None
95

96
    def visit_ReturnStmt(self, node):
97
        if self.current_function_return_type is None:
98
            self.error("Return outside function", node)
99
            return
100

101
        if node.value:
102
            return_type = self.visit(node.value)
103
            if return_type and not self.is_assignable(
104
                self.current_function_return_type, return_type
105
            ):
106
                self.error(
107
                    f"Cannot return {return_type} from function "
108
                    f"with return type {self.current_function_return_type}",
109
                    node
110
                )
111

112
    def is_assignable(self, target_type, source_type):
113
        """检查是否可以赋值"""
114
        if target_type == source_type:
115
            return True
116
        # 隐式转换规则
117
        implicit_conversions = {
118
            ('float', 'int'): True,   # int → float
119
            ('long', 'int'): True,    # int → long
120
            ('double', 'float'): True, # float → double
121
            ('double', 'int'): True,  # int → double
122
        }
123
        return implicit_conversions.get((target_type, source_type), False)
124

125
    def is_valid_type(self, type_name):
126
        return type_name in {'int', 'float', 'double', 'long', 'void', 'bool', 'char'}

1
class DefiniteAssignmentChecker:
2
    """定性赋值分析：确保变量在使用前已被赋值"""
3

4
    def __init__(self):
5
        self.assigned = set()  # 已赋值的变量集合
6

7
    def visit_VarDecl(self, node):
8
        if node.init:
9
            self.assigned.add(node.name)
10

11
    def visit_Identifier(self, node):
12
        if node.name not in self.assigned:
13
            raise SemanticError(
14
                f"Variable '{node.name}' used before assignment"
15
            )
16

17
    def visit_IfStmt(self, node):
18
        then_assigned = set()
19
        else_assigned = set()
20

21
        # 分析 then 分支
22
        old_assigned = self.assigned.copy()
23
        self.visit(node.then_branch)
24
        then_assigned = self.assigned - old_assigned
25

26
        # 分析 else 分支
27
        self.assigned = old_assigned.copy()
28
        if node.else_branch:
29
            self.visit(node.else_branch)
30
            else_assigned = self.assigned - old_assigned
31

32
        # 两个分支都赋值的变量才认为是已赋值
33
        self.assigned = old_assigned | (then_assigned & else_assigned)

1
class ReachabilityChecker:
2
    """可达性分析：检查死代码和缺少 return 语句"""
3

4
    def visit_FuncDecl(self, node):
5
        reachable = self.visit(node.body)
6
        if not reachable and node.return_type != 'void':
7
            self.error(
8
                f"Function '{node.name}' may not return a value", node
9
            )
10

11
    def visit_ReturnStmt(self, node):
12
        return False  # return 后的代码不可达
13

14
    def visit_IfStmt(self, node):
15
        then_reachable = self.visit(node.then_branch)
16
        else_reachable = (
17
            self.visit(node.else_branch) if node.else_branch else True
18
        )
19
        return then_reachable or else_reachable
20

21
    def visit_Block(self, node):
22
        reachable = True
23
        for stmt in node.stmts:
24
            if not reachable:
25
                self.warning("Unreachable code", stmt)
26
            reachable = self.visit(stmt)
27
        return reachable

1
# 组合词法分析、语法分析和语义分析
2
source = """
3
int add(int a, int b) {
4
    return a + b;
5
}
6

7
int main() {
8
    int x = add(3, 4);
9
    return x;
10
}
11
"""
12

13
# 词法分析
14
lexer = Lexer(source)
15
tokens = lexer.tokenize()
16

17
# 语法分析
18
parser = Parser(tokens)
19
ast = parser.parse_program()
20

21
# 语义分析
22
analyzer = SemanticAnalyzer()
23
analyzer.visit(ast)
24

25
if analyzer.errors:
26
    for error in analyzer.errors:
27
        print(f"Error: {error}")
28
else:
29
    print("Semantic analysis passed!")

1
# Rust 需要函数签名，但可以推导局部变量
2
cat > type_inference.rs << 'EOF'
3
fn main() {
4
    let x = 42;           // 推导为 i32
5
    let y = 3.14;         // 推导为 f64
6
    let z = x as f64 + y; // z: f64
7
    println!("{}", z);
8
}
9
EOF
10

11
rustc type_inference.rs && ./type_inference

1
# 观察类型错误
2
cat > type_error.c << 'EOF'
3
int main() {
4
    int x = "hello";  // 类型不匹配
5
    return x + 1.5;   // 隐式转换警告
6
}
7
EOF
8

9
clang -Wall type_error.c 2>&1