符号表

符号表的作用是管理符号信息，其主要目的是为符号信息的存储和访问提供一种高效、方便的途径。一个符号依据不同的场合可能有多种不同的属性，但是一般来说都具备两种基本属性：符号的名字、符号有效的作用域。

符号的作用域信息用于帮助在同名的符号中找出当前有效的符号，也用于判断作用域错误。所谓的作用域是说一个符号在源程序中的有效范围。按照记录作用域信息的不同方法，符号表有两种组织方式：

1. 单表形式

   所有的标识符都记录在同一个符号表中，同时为每个记录添加一个作用域属性来标记该记录对应的标识符所声明的作用域层次，作用域的层次用一个计数器来维护。利用散列表实现单表结构的符号表时，同名的标识符按照作用域层号递减的顺序记录在同一个桶对应的链表中。这样在访问一个标识符时，从散列表中找到的第一个表项就是最靠近内层的作用域中声明的标识符。这种结构的最大开销在于每退出一层作用域时，都需要遍历整个符号表以删除该作用域中声明的所有标识符表项。

   不过这个开销也不是必然存在的。比如可以利用一些可持久化数据结构，如Weight-balanced tree(haskell中Map的底层实现)或者更简单的可持久化Treap，以(符号名称，当前层数)的二元组作为键。每次新进入一个作用域就复制一份符号表，然后在此基础上做各种操作即可。

2. 多级符号表

   为每个作用域单独建立一个符号表，仅记录当前作用域中声明的标识符。同时建立一个栈来管理整个程序的作用域：每打开一个作用域，就把该作用域压入栈中；每关闭一个作用域，就从栈顶弹出该作用域。这样，这个作用域栈中就记录着当前所有打开的作用域的信息，栈顶元素就是当前最内层的作用域。查找一个变量时，按照自顶向下的顺序查找栈中各作用域的符号表，最先找到的就是最靠近内层的变量。这样处理的不利之处在于，查找外层变量的时间开销会变大。但这样组织的符号表实现起来比较简单，并且一般来说作用域嵌套的层次不会太深。

在目前的框架中，我们采用实现更简单的第二种符号表组织方式，不过也许未来会尝试第一种。