语义分析实战（一）—— 符号表实现

章节标题

符号表的核心作用

在编译器的语义分析阶段，符号表是一个至关重要的数据结构，它用于：

  • 存储标识符信息：记录变量、函数、类型等标识符的名称、类型、作用域等信息
  • 作用域管理：处理不同作用域中的标识符，解决名称冲突问题
  • 符号查找：在编译过程中快速查找标识符的相关信息
  • 类型检查：为类型检查提供必要的类型信息

符号表的数据结构设计

符号表的基本结构

一个典型的符号表可以设计为以下结构：

class Symbol:
    """符号类"""
    def __init__(self, name, symbol_type, scope_level, attributes=None):
        self.name = name  # 符号名称
        self.symbol_type = symbol_type  # 符号类型：变量、函数、类型等
        self.scope_level = scope_level  # 作用域层级
        self.attributes = attributes or {}  # 其他属性

class Scope:
    """作用域类"""
    def __init__(self, level, parent=None):
        self.level = level  # 作用域层级
        self.parent = parent  # 父作用域
        self.symbols = {}  # 当前作用域的符号字典

class SymbolTable:
    """符号表类"""
    def __init__(self):
        self.current_scope = Scope(0)  # 全局作用域
        self.scope_level = 0  # 当前作用域层级

符号表的核心操作

1. 进入新作用域

def enter_scope(self):
    """进入新作用域"""
    self.scope_level += 1
    new_scope = Scope(self.scope_level, self.current_scope)
    self.current_scope = new_scope

2. 退出作用域

def exit_scope(self):
    """退出当前作用域"""
    if self.current_scope.parent:
        self.current_scope = self.current_scope.parent
        self.scope_level -= 1

3. 插入符号

def insert(self, name, symbol_type, attributes=None):
    """在当前作用域插入符号"""
    symbol = Symbol(name, symbol_type, self.scope_level, attributes)
    self.current_scope.symbols[name] = symbol
    return symbol

4. 查找符号

def lookup(self, name):
    """查找符号，从当前作用域向上查找"""
    scope = self.current_scope
    while scope:
        if name in scope.symbols:
            return scope.symbols[name]
        scope = scope.parent
    return None

实用案例分析

案例：处理变量声明和引用

假设我们有以下简单的程序：

int global_var;

void func() {
    int local_var;
    global_var = 10;
    local_var = 20;
}

我们来看看符号表是如何处理的：

  1. 初始化符号表：创建全局作用域
  2. 处理全局变量声明：
    • 在全局作用域插入 global_var 符号
  3. 处理函数定义：
    • 进入新作用域（函数作用域）
    • 在函数作用域插入 func 符号
  4. 处理函数体：
    • 进入新作用域（块作用域）
    • 在块作用域插入 local_var 符号
  5. 处理变量引用：
    • 查找 global_var：在全局作用域找到
    • 查找 local_var：在当前块作用域找到
  6. 退出作用域：
    • 退出块作用域
    • 退出函数作用域

符号表的实现代码

下面是一个完整的符号表实现示例：

class Symbol:
    """符号类"""
    def __init__(self, name, symbol_type, scope_level, attributes=None):
        self.name = name
        self.symbol_type = symbol_type  # 'variable', 'function', 'type'
        self.scope_level = scope_level
        self.attributes = attributes or {}
    
    def __str__(self):
        return f"Symbol(name='{self.name}', type='{self.symbol_type}', level={self.scope_level}, attrs={self.attributes})"

class Scope:
    """作用域类"""
    def __init__(self, level, parent=None):
        self.level = level
        self.parent = parent
        self.symbols = {}
    
    def __str__(self):
        return f"Scope(level={self.level}, symbols={list(self.symbols.keys())})"

class SymbolTable:
    """符号表类"""
    def __init__(self):
        self.current_scope = Scope(0)  # 全局作用域
        self.scope_level = 0
    
    def enter_scope(self):
        """进入新作用域"""
        self.scope_level += 1
        new_scope = Scope(self.scope_level, self.current_scope)
        self.current_scope = new_scope
        return self.current_scope
    
    def exit_scope(self):
        """退出当前作用域"""
        if self.current_scope.parent:
            self.current_scope = self.current_scope.parent
            self.scope_level -= 1
        return self.current_scope
    
    def insert(self, name, symbol_type, attributes=None):
        """在当前作用域插入符号"""
        # 检查当前作用域是否已存在同名符号
        if name in self.current_scope.symbols:
            return None  # 符号已存在
        
        symbol = Symbol(name, symbol_type, self.scope_level, attributes)
        self.current_scope.symbols[name] = symbol
        return symbol
    
    def lookup(self, name):
        """查找符号，从当前作用域向上查找"""
        scope = self.current_scope
        while scope:
            if name in scope.symbols:
                return scope.symbols[name]
            scope = scope.parent
        return None
    
    def lookup_current_scope(self, name):
        """仅在当前作用域查找符号"""
        return self.current_scope.symbols.get(name)
    
    def get_all_symbols(self):
        """获取所有作用域中的符号"""
        symbols = []
        scope = self.current_scope
        while scope:
            for symbol in scope.symbols.values():
                symbols.append(symbol)
            scope = scope.parent
        return symbols
    
    def dump(self):
        """打印符号表内容"""
        print("=== Symbol Table Dump ===")
        scope = self.current_scope
        while scope:
            print(f"Scope level {scope.level}:")
            for name, symbol in scope.symbols.items():
                print(f"  {name}: {symbol}")
            scope = scope.parent
        print("=======================")

# 测试符号表
if __name__ == "__main__":
    st = SymbolTable()
    
    # 插入全局变量
    st.insert("global_var", "variable", {"datatype": "int"})
    
    # 打印符号表
    st.dump()
    
    # 进入函数作用域
    st.enter_scope()
    st.insert("func", "function", {"return_type": "void", "params": []})
    
    # 进入块作用域
    st.enter_scope()
    st.insert("local_var", "variable", {"datatype": "int"})
    
    # 打印符号表
    st.dump()
    
    # 查找符号
    print("\nLooking up symbols:")
    print(f"global_var: {st.lookup('global_var')}")
    print(f"local_var: {st.lookup('local_var')}")
    print(f"nonexistent: {st.lookup('nonexistent')}")
    
    # 退出作用域
    st.exit_scope()
    st.exit_scope()
    
    # 打印最终符号表
    st.dump()

符号表的优化

  1. 使用哈希表：对于大型程序，使用哈希表存储符号可以提高查找效率
  2. 作用域缓存：缓存最近查找的符号，减少重复查找
  3. 符号分类：将不同类型的符号分开存储，提高查找效率
  4. 批量操作：支持批量插入和删除符号，减少操作开销

常见问题及解决方案

  1. 符号冲突：

    • 解决方案：在插入符号前检查当前作用域是否已存在同名符号

  2. 作用域管理错误：

    • 解决方案：确保每次进入作用域后都有对应的退出操作

  3. 性能问题：

    • 解决方案：使用高效的数据结构，如哈希表，减少查找时间

  4. 内存泄漏：

    • 解决方案：及时清理不再使用的作用域和符号

总结

符号表是编译器语义分析阶段的核心组件，它负责管理程序中的标识符信息，为类型检查、作用域分析等提供支持。通过合理的数据结构设计和高效的实现，可以显著提高编译器的性能和正确性。

在本集的实战中，我们实现了一个基本的符号表，包括作用域管理、符号插入和查找等核心功能。在后续的实战中，我们将使用这个符号表来实现类型检查和其他语义分析功能。

« 上一篇 语义错误处理 下一篇 » 语义分析实战（二）—— 类型检查器
↑