绝大多数编程语言都可以分成三部分：声明(declaration)，表达式(expression)，语句模块(statement). 每部分都有专门的语法来定义，在上一节中，我们通过语法定义了C语言的变量声明，并通过解析器成功实现了变量声明的语法解析。

对于C语言中的一段函数代码，便可分割成对应于上面所说的三部分。函数声明中的函数名，返回值和输入参数例如：
int fun(int arg1, int arg2);
就可以对应于上面三部分中的声明部分。函数的主体则对应于表达式和语句模块部分。

在对代码的声明部分进行语法解析时，我们需要构建一种数据结构，以便于支持具体的代码生成，这种数据结构，就是我们接下来要研究的符号表。符号表本质上是一种数据库，用来存储代码中的变量，函数调用等相关信息。该表以key-value 的方式存储数据。变量和函数的名字就用来对应表中的key部分，value部分包含一系列信息，例如变量的类型，所占据的字节长度，或是函数的返回值。当我们的解析器读取源代码，遇到声明部分时，便给符号表添加一条记录，如果变量或函数脱离了它的作用范围时，便将他们对应的记录从表中删除。例如：

{
int variable = 0;
}

在上面代码中，进入大括号时，解析器遇到变量的声明，于是便把变量variable 的相关信息写入符号表。当解析器读取到右括号时，便把variable在符号表中的信息给删除，因为出了variable的作用范围只在括号之内。

符号表还可以用来存储类型定义(typedef)和常量声明，在词法解析的过程，词法解析器还需要和符号表交互，用于确定一个变量名是否属于一种类型定义，例如：

typedef char SingleByte

当词法解析器读取SingleByte这个字符串后，会在符号表中查询这个字符串所对应的记录，由于每个记录都有一个标志位，用来表明该字符串是否属于变量声明，于是词法解析器从记录中读取这个标志位，发现SingleByte对应的标志位被设置为1，因此词法解析器就不会把SingleByte当做普通的变量处理，而是当做关键字来处理。

符号表作为一种数据库，它必须具备以下特点：

int variable = 0;
{
int variable = 1;
}

例如上面例子中，两个变量虽然拥有相同的名字，但却是合法的。在大括号内的变量会覆盖(shadow) 外层同名变量。因此符号表必须支持同一个key, 但却可以映射到不同的value.

符号表的数据结构设计

为了应对上面的需求，我们可通过哈希表来实现符号表的设计。由于哈希表的插入和删除平均耗时是O(1), 因此它能满足快速的插入和删除这一要求，如果遇到作用域不同的同名变量，他们必然被哈希到同一个位置，那么我们可以用链表把哈希到同一个地方的记录串联起来，这样就解决了支持重复性的问题。举个具体例子：

int Godot;
void waiting(int vladmir, int estragon) {
int pozzo;
while (condition) {
int pozzo, lucky;
}
}

在上面的代码中，Godto 和 waiting是属于第一层的变量，函数waiting的参数vladmir, estragon ,和内部变量 pozzo 属于第二层的变量。while 体内的变量 pozzo, 和 lucky 属于第三层的变量，而且两个pozzo是同名变量。

于是通过链式哈希表来实现符号表的过程如下：

所有的变量都存储到哈希表中，同名变量pozzo被哈希到同一个位置，所有用队列连接起来，由于我们使用变量名做哈希，因此不同变量名也有可能哈希到同一个地方，假定vladmir哈希到与pozzo相同的地方，所以vladmir也在同一个队列中。

在头顶还有一个队列，用来存储不同层次的变量起始指针，例如Godot, waiting 属于第一层次的变量，因此头部队列的第一个元素存储指针，指向第一个变量Godot, 然后Godot自己又引出一个指针，指向同一层的另一个变量wait, 由此，同一层的变量实际上是通过一个队列连接起来，这个队列的头指针就存储在Cross link 列表中。

第二层三个变量vladmir, estragon, pozzo , 也组成一个队列：vladmir->estragon->pozzo, 这个队列的头指针就存放在cross link列表的第二个元素。第三层以此类推。

符号表中的一个记录，我们可以用如下java代码表示（symbol.java)：

public class Symbol {
    String  name;
    String  rname;

    int       level;  //变量的层次
    boolean   implicit;  //是否是匿名变量
    boolean   duplicate;   //是否是同名变量

    Symbol    args;   //如果该符号对应的是函数名,那么args指向函数的输入参数符号列表

    Symbol    next;  //指向下一个同层次的变量符号
}

哈希表中的记录，我们用SymbolEntry来表示，代码如下：

public class SymbolEntry {
    private Symbol symbol;
    private SymbolEntry prev, next;

    public SymbolEntry(Symbol sym) {
        this.symbol = sym;
    }

    public void setPrev(SymbolEntry prev) {
        this.prev = prev;
    }

    public void setNext(SymbolEntry next) {
        this.next = next;
    }

    public SymbolEntry getPrev() {
        return prev;
    }

    public SymbolEntry getNext() {
        return next;
    }

}

用于解决哈希冲突的链表是双向链表，所以SymbolEntry中有两个对象指针，prev 和 next, 分别指向当前符号的前缀和后缀，这种双向链表的设计有利于在队列中对元素进行删除。

类型系统

接下来的问题是，如何表示变量的类型，如果语言足够简单，那么类型可以用一些整形数组来表示，例如0表示整数，1表示浮点数。指针类型，例如int* 可以用数值3来表示。这种类型系统，称之为限制行类型系统，因为这种方法只能表示有限中类型。