编译原理第三版陈火旺第五章

### 编译原理第三版陈火旺第五章内容概述

#### 5.1 符号表的作用与设计原则
符号表是编译器中的一个重要数据结构，用于存储源程序中各种名字的信息。这些信息对于语义分析、中间代码生成以及目标代码优化至关重要[^1]。

#### 5.2 符号表的内容
通常情况下，符号表会记录变量名、函数名及其属性（如类型、作用域等）。随着编译过程推进，符号表不断更新以反映最新的定义情况。此外，在处理嵌套作用域或多文件项目时，还需要考虑如何有效地管理和查询不同层次上的符号条目。

#### 5.3 动态数组实现方式下的符号表管理
当采用动态数组来构建符号表时，可以方便地支持按索引访问操作；然而为了提高效率并减少内存碎片化现象，则需引入哈希函数来进行散列映射从而加快查找速度。此方法适用于规模较小的应用场景或是作为其他更复杂方案的基础组件之一。

#### 5.4 基于链地址法的符号表解决方案
另一种常见的做法就是利用链地址法建立冲突解决机制，即每当发生碰撞时就创建一个新的节点链接到已有列表之后形成单向循环链表形式的数据集合体。这种方法虽然牺牲了一定程度的空间利用率但却极大地简化了插入删除逻辑同时也保持较好的平均性能表现。

class SymbolTableEntry:
    def __init__(self, name, type_info=None):
        self.name = name
        self.type_info = type_info
        self.next = None


def insert_symbol(head, entry):
    if not head or head.name == entry.name:
        return entry
    
    current = head
    while current.next and current.next.name != entry.name:
        current = current.next
        
    new_entry = SymbolTableEntry(entry.name, entry.type_info)
    new_entry.next = current.next
    current.next = new_entry