第59集：语义分析的基本概念

学习目标

  • 理解语义分析的基本概念和作用
  • 掌握语法制导翻译的基本原理
  • 了解属性文法的定义和分类
  • 学会类型检查的基本方法
  • 理解语义错误处理的策略

1. 语义分析概述

1.1 基本概念

语义分析是编译过程的第三阶段，紧跟在语法分析之后。它的主要任务是：

  • 验证语义正确性：检查程序是否符合语言的语义规则
  • 收集语义信息：收集变量声明、类型信息等语义信息
  • 生成中间表示：将语法结构转换为更适合后续处理的中间表示
  • 进行语义优化：在语义层面进行一些简单的优化

1.2 与语法分析的区别

语法分析：

  • 关注程序的结构是否正确
  • 检查是否符合文法规则
  • 不关心程序的含义
  • 输出语法树或分析树

语义分析：

  • 关注程序的含义是否正确
  • 检查是否符合语义规则
  • 验证类型是否匹配、变量是否定义等
  • 输出带语义信息的中间表示

1.3 语义分析的重要性

语义分析的重要性在于：

  • 确保程序的正确性：检测类型错误、未定义变量等语义错误
  • 为后续阶段做准备：收集的语义信息是中间代码生成和优化的基础
  • 提高程序的可靠性：提前发现潜在的语义问题
  • 支持语言的高级特性：如类型推断、重载解析等

2. 语法制导翻译

2.1 基本概念

语法制导翻译是一种将语法分析和语义处理相结合的方法，它的基本思想是：

  • 为文法中的每个产生式关联一个语义动作
  • 在语法分析过程中，当使用某个产生式进行推导或归约时，执行相应的语义动作
  • 语义动作可以计算属性值、生成代码、进行类型检查等

2.2 属性

在语法制导翻译中，属性是与文法符号相关联的值，用于表示语义信息。常见的属性包括：

  • 类型：变量、表达式的类型
  • 值：常量的值
  • 存储位置：变量在内存中的位置
  • 代码：生成的中间代码
  • 符号表入口：指向符号表中对应条目的指针

2.3 属性的分类

根据属性的计算方向：

  • 综合属性：由子节点的属性计算父节点的属性，自底向上计算
  • 继承属性：由父节点的属性计算子节点的属性，自顶向下计算

示例：

对于产生式 E → E1 + E2，如果 E 的类型是 E1 和 E2 类型的和，那么 E 的类型是综合属性。

对于产生式 S → if (E) S1 else S2，如果 S1 和 S2 的环境继承自 S 的环境，那么 S1 和 S2 的环境是继承属性。

2.4 语法制导定义

语法制导定义（Syntax-Directed Definition, SDD）是一种形式化的方法，用于描述语法制导翻译。它由以下部分组成：

  • 文法：上下文无关文法
  • 属性：为每个文法符号关联的属性集合
  • 语义规则：为每个产生式关联的语义规则集合，用于计算属性值

示例：简单表达式的语法制导定义

产生式               语义规则
E → E1 + T          E.type = if (E1.type == int && T.type == int) then int else error
E → T                E.type = T.type
T → T1 * F           T.type = if (T1.type == int && F.type == int) then int else error
T → F                T.type = F.type
F → ( E )            F.type = E.type
F → id               F.type = id.entry.type
F → num              F.type = int

2.5 翻译方案

翻译方案（Translation Scheme, TS）是语法制导定义的一种具体实现，它将语义动作嵌入到产生式中，指明了语义动作的执行时机。

示例：简单表达式的翻译方案

E → E1 { if (E1.type != int) error() } + T { if (T.type != int) error(); E.type = int }
E → T { E.type = T.type }
T → T1 { if (T1.type != int) error() } * F { if (F.type != int) error(); T.type = int }
T → F { T.type = F.type }
F → ( E ) { F.type = E.type }
F → id { F.type = id.entry.type }
F → num { F.type = int }

3. 属性文法

3.1 基本概念

属性文法是一种特殊的语法制导定义，它的语义规则只包含属性的计算，不包含其他操作。属性文法的核心是属性的定义和计算规则。

3.2 属性文法的分类

根据属性的计算方式：

  • S属性文法：只包含综合属性，语义规则在产生式的末尾，适合自底向上计算
  • L属性文法：包含综合属性和继承属性，继承属性的计算只依赖于父节点和左侧兄弟节点的属性，适合自顶向下计算

3.3 S属性文法

S属性文法是最简单的属性文法，它的特点是：

  • 所有属性都是综合属性
  • 语义规则在产生式的末尾
  • 可以在自底向上的语法分析过程中计算属性值
  • 适合与LR分析器配合使用

示例：计算表达式值的S属性文法

产生式               语义规则
E → E1 + T          E.val = E1.val + T.val
E → T                E.val = T.val
T → T1 * F           T.val = T1.val * F.val
T → F                T.val = F.val
F → ( E )            F.val = E.val
F → num              F.val = num.value

3.4 L属性文法

L属性文法是一种更通用的属性文法，它的特点是：

  • 包含综合属性和继承属性
  • 继承属性的计算只依赖于父节点和左侧兄弟节点的属性
  • 可以在自顶向下的语法分析过程中计算属性值
  • 适合与LL分析器配合使用

示例：符号表查找的L属性文法

产生式               语义规则
P → D ; E            E.env = D.env
D → D1 , id          D.env = D1.env; id.entry = add_entry(D1.env, id.name)
D → id               D.env = create_env(); id.entry = add_entry(D.env, id.name)
E → E1 + T           E.type = if (E1.type == int && T.type == int) then int else error
E → T                E.type = T.type
T → id               T.type = lookup_type(E.env, id.entry)

3.5 属性计算

自底向上计算：

  • 适用于S属性文法
  • 在归约时计算综合属性
  • 从叶节点开始，向上计算到根节点

自顶向下计算：

  • 适用于L属性文法
  • 在推导时计算继承属性
  • 从根节点开始，向下计算到叶节点

混合计算：

  • 同时使用自底向上和自顶向下计算
  • 先计算继承属性，再计算综合属性

4. 类型检查

4.1 基本概念

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

  • 验证类型兼容性：检查表达式、赋值、函数调用等的类型是否兼容
  • 推断类型：在某些语言中，自动推断变量和表达式的类型
  • 确保类型安全：防止类型错误导致的运行时错误

4.2 类型系统

类型系统是一组规则，用于规定程序中值的类型以及类型之间的关系。类型系统的主要组成部分包括：

  • 类型定义：基本类型、复合类型、用户定义类型等
  • 类型规则：类型推断、类型转换、类型兼容性等规则
  • 类型检查算法：实现类型检查的具体算法

4.3 类型检查的方法

基于规则的类型检查：

  • 为每种语言构造定义类型规则
  • 根据类型规则检查程序的类型正确性
  • 适合静态类型语言

基于约束的类型检查：

  • 收集程序中的类型约束
  • 求解类型约束系统
  • 适合类型推断和动态类型语言

4.4 类型检查的实现

符号表：

  • 存储变量、函数、类型等的声明信息
  • 支持作用域管理
  • 提供快速查找功能

类型环境：

  • 表示当前的类型上下文
  • 包含变量名到类型的映射
  • 在作用域进入和退出时更新

类型检查器：

  • 遍历抽象语法树
  • 检查每个节点的类型正确性
  • 推断表达式的类型
  • 生成类型错误信息

4.5 类型转换

隐式类型转换：

  • 编译器自动进行的类型转换
  • 例如：int 到 float 的转换
  • 需要遵循语言的类型转换规则

显式类型转换：

  • 程序员显式指定的类型转换
  • 例如：(float)x
  • 可能会导致类型信息丢失

5. 语义错误处理

5.1 常见的语义错误

  • 类型错误：类型不匹配、类型转换错误等
  • 声明错误：未声明的变量、重复声明等
  • 作用域错误：变量在作用域之外使用
  • 函数调用错误：参数数量不匹配、参数类型不匹配等
  • 表达式错误：除零错误、数组越界等

5.2 语义错误处理策略

错误检测：

  • 在语义分析过程中检测语义错误
  • 使用类型检查器和语义分析器进行检测
  • 基于语言的语义规则进行验证

错误报告：

  • 生成清晰、准确的错误信息
  • 包含错误位置、错误类型和错误原因
  • 提供修复建议

错误恢复：

  • 在遇到语义错误时，尝试继续分析
  • 使用默认值或假设来恢复分析
  • 记录错误但不立即终止编译

5.3 语义错误与语法错误的区别

  • 语法错误：违反语言的语法规则，如缺少分号、括号不匹配等
  • 语义错误：违反语言的语义规则，如类型不匹配、未定义变量等
  • 检测时机：语法错误在语法分析阶段检测，语义错误在语义分析阶段检测
  • 恢复难度：语义错误的恢复通常比语法错误更困难

6. 实战案例：简单类型检查器

6.1 文法定义

P → D ; E
D → D , id : T | id : T
T → int | float
E → E + T | T
T → id | num

6.2 符号表实现

class SymbolTable:
    def __init__(self):
        self.symbols = {}
    
    def add_symbol(self, name, type_):
        if name in self.symbols:
            print(f"Error: Symbol {name} already declared")
            return False
        self.symbols[name] = type_
        return True
    
    def get_type(self, name):
        if name not in self.symbols:
            print(f"Error: Symbol {name} not declared")
            return None
        return self.symbols[name]

6.3 类型检查器实现

class TypeChecker:
    def __init__(self, symbol_table):
        self.symbol_table = symbol_table
        self.errors = []
    
    def error(self, message):
        self.errors.append(message)
        print(f"Error: {message}")
    
    def check_declaration(self, decls):
        """检查声明部分"""
        for decl in decls:
            name, type_ = decl
            if not self.symbol_table.add_symbol(name, type_):
                self.error(f"Symbol {name} already declared")
    
    def check_expression(self, expr):
        """检查表达式部分"""
        return self.check_expr(expr)
    
    def check_expr(self, expr):
        """检查表达式类型"""
        if isinstance(expr, tuple) and expr[0] == '+':
            # 处理加法表达式
            left_type = self.check_expr(expr[1])
            right_type = self.check_expr(expr[2])
            if left_type == right_type and left_type in ['int', 'float']:
                return left_type
            else:
                self.error(f"Type mismatch in addition: {left_type} + {right_type}")
                return None
        elif isinstance(expr, str):
            # 处理标识符
            return self.symbol_table.get_type(expr)
        elif isinstance(expr, (int, float)):
            # 处理常量
            return 'int' if isinstance(expr, int) else 'float'
        else:
            self.error(f"Invalid expression: {expr}")
            return None

6.4 测试示例

测试1：正确的程序

输入：

x : int, y : int; x + y

输出：

Type of expression: int
No errors found.

测试2：类型不匹配

输入：

x : int, y : float; x + y

输出：

Error: Type mismatch in addition: int + float
Type of expression: None
1 error found.

测试3：未声明的变量

输入：

x : int; x + y

输出：

Error: Symbol y not declared
Error: Type mismatch in addition: int + None
Type of expression: None
2 errors found.

7. 自测题

  1. 语义分析的主要任务是什么？它与语法分析有什么区别？

  2. 什么是语法制导翻译？它的基本思想是什么？

  3. 解释综合属性和继承属性的区别。

  4. 类型检查的主要任务是什么？常见的类型错误有哪些？

  5. 实现一个简单的类型检查器，处理以下文法：

    E → E + T | T
T → T * F | F
F → ( E ) | id | num

    假设所有变量都是 int 类型。

8. 小结

在本集中，我们详细介绍了语义分析的基本概念，包括语法制导翻译、属性文法、类型检查和语义错误处理等内容。语义分析是编译过程的重要组成部分，它负责验证程序的语义正确性，收集语义信息，为后续的中间代码生成和优化做准备。

语法制导翻译是一种将语法分析和语义处理相结合的方法，通过为文法产生式关联语义动作来实现翻译。属性文法是语法制导定义的一种形式，它通过属性的计算来传递和处理语义信息。类型检查是语义分析的核心任务之一，它确保程序的类型正确性，防止类型错误导致的运行时错误。

通过本集的学习，我们了解了语义分析的基本原理和实现方法，为后续学习中间代码生成和代码优化奠定了基础。

9. 下集预告

下一集将介绍 中间代码生成，详细讲解中间代码的形式、生成方法和优化技术，帮助我们理解编译器如何将语义分析的结果转换为更适合后续处理的中间表示。

10. 参考资料

  1. 《编译原理》（龙书），Alfred V. Aho 等著
  2. 《编译原理教程》，蒋立源等著
  3. 《编译器设计》，Alexander A. Stepanov 等著
  4. 语义分析 - Wikipedia：https://en.wikipedia.org/wiki/Semantic_analysis_(compilers)
  5. 语法制导翻译 - Wikipedia：https://en.wikipedia.org/wiki/Syntax-directed_translation
  6. 属性文法 - Wikipedia：https://en.wikipedia.org/wiki/Attribute_grammar
  7. 类型系统 - Wikipedia：https://en.wikipedia.org/wiki/Type_system
« 上一篇 语法分析器的错误处理 下一篇 » 中间代码生成
↑