栈式散列符号表(Stacked Hash Symbol Table)是编译原理中常用的符号表实现方式,结合了哈希表的高效查找与栈结构的作用域管理,广泛用于编译器的词法分析和语法分析阶段。
设计思想
- 哈希表:用于高效存储和查找符号(如变量、函数名等)。
- 栈结构:用于管理作用域(如函数、代码块、循环等的嵌套)。每进入一个新作用域,压入一层新表;离开作用域时弹出。
工作原理
- 进入新作用域时,创建一个新的哈希表并压入栈顶。
- 查找符号时,从栈顶向下依次查找,遇到第一个命中即返回。
- 插入符号时,只在当前作用域(栈顶哈希表)插入。
- 离开作用域时,弹出栈顶哈希表,自动移除该作用域的所有符号。