C语言的符号表和类型系统1

绝大多数语言都可以分成三部分：声明(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当做普通的变量处理，而是当做关键字来处理。

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

速度。由于符号表会被编译器频繁写入和读取，因此记录的写入，查询速度必须足够快。为了保证速度，整个符号表会直接存储在内存中，由此符号表的设计必须仔细考虑内存消耗。 维护性。符号表几乎是编译器中，最复杂的数据结构。它的设计必须灵活可扩展，使得除了编译器外，其他应用程序或模块也能良好的访问符号表。 灵活性。c语言的变量声明很复杂，例如它允许类型关键字的相互组合等(long int, long doube *…), 因此符号表必须能支持各种不同的变量声明方式。 重复性支持。由于对大多数编程语言而言，在不同的间套下，重复的变量名是允许的：

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也在同一个队列中。喎? f/ware/vc/"="" target="_blank" class="keylink">vcd4ncjxwpttazbe2pbu509dsu7j2ttpb0kos08patltmtkkyu82ssuo0zrxesetbv8bwyrzwunxro6za/cjnr29kb3qsihdhaxrpbmcgyvtt2rxa0ruy47totcsx5mg/o6zs8rtlzbeyv7btwdc1xlxa0ru49tsqy9i05rsi1rjv66os1rjp8rxa0ru49rhkwb9hb2rvdcwgylu680dvzg9019s8utpw0v2z9tk7upbwunxro6zwum/yzazsu7ljtctb7dk7upax5mg/d2fpdcwg08m0y6oszazsu7ljtcsx5mg/yrw8ysnpysfnqln90ru49rbtwddbrl3txvdatkos1ek49rbtwdc1xm231rjv677ntoa0ottaq3jvc3mgbgluaydb0lht1tchozwvcd4ncjxwprxatv6y48j9upax5mg/dmxhzg1pciwgzxn0cmfnb24sihbvenpvicwg0rlx6bpj0ru49rbtwdcjunzsywrtaxitjmd0o2vzdhjhz29ulsznddtwb3p6bywg1ek49rbtwdc1xm231rjv677ntoa3xdtay3jvc3mgbglua8hqse21xlxatv649tsqy9iho7xayp2y49lutmva4m3goam8l3a+dqo8cd63+7rfse3w0lxe0ru49rzhwryjrm7sw8e/ydlu08pi58/camf2ybt6wuux7cq+o6hzew1ib2wuamf2ysmjujwvcd4ncjxwcmugy2xhc3m9"brush: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来表示。这种类型系统，称之为限制行类型系统，因为这种方法只能表示有限中类型。

像c语言这种拥有复杂类型表示方式的语言，上面的方法就捉襟见肘了。因此要表示c语言的类型系统，必须设计足够灵活的数据结构。c语言的变量声明包括两部分，一部分叫说明符(specifier),这部分对应各种数据类型关键字，int long, extern, struct等。另一部分叫修饰符，由变量名以及星号，中括号组成，例如 *a, a[10] 等。

说明符部分是有限的，毕竟关键字的数量有限，因此关键字的组合方式也有限，但是，修饰符部分就相当灵活，例如星号*就可以有多个，*和[]又可以相互组合，因此c语言的类型必须由两部分组成，一部分表示说明符部分，另一部分表示修饰符部分。整个类型系统就由包含这两种结构的链表构成。例如声明语句：
short in quasimodo;
long *gringoire;

他们的类型系统如下：

类型系统中，说明符部分只有一个，而修饰符部分可以有多个，当然也可以没有，同时，说明符始终放在链表的末尾。通过把链表顺序念下来，就可以读出变量声明语句，例如对于第二个队列，顺序读下来就是：gringoire is a pointer to long.

如果是一个长整形数组，例如 long coppenole[10],类型系统的表示如下：

一个指向10个长整形元素的数组指针，long (*frollo)[10],类型系统表示如下：

这种类型系统有个显著特点是，容易促进代码生成。后面我们可以看到这个效果。

类型系统的实现

修饰符的实现比较简单，代码如下：

public class declarator {
    public static int  pointer = 0;
    public static int  array = 1;
    public static int  function = 2;

    private int  declaretype = pointer;
    private int  numberofelements = 0;

    public declarator(int type) {
        if (type < pointer) {
            declaretype = pointer;
        } 

        if (type > function) {
            declaretype = function;
        }
    }

    public void setelementnum(int num) {
        if (num < 0) {
            numberofelements = 0;
        } else {
            numberofelements = num;
        }
    }

    public int gettype() {
        return declaretype ;
    }

    public int getelementnum() {
        return numberofelements;
    }
}

上面代码中，declaretype 用来表示要修饰的变量是一个指针，数组，还是函数，如果是数组的话，numberofelements 这个成员用来表示数组含有多少个元素。

说明符的实现稍微麻烦些，代码如下：

public class specifier {
    //type
    public static int  int = 0;
    public static int  char = 1;
    public static int  void = 2;
    public static int  structure = 3;
    public static int  label = 4;

    //storage
    public static int  fixed = 0;
    public static int  register = 1;
    public static int  auto = 2;
    public static int  typedef = 3;
    public static int  constant = 4;

    public static int  no_oclass = 0;  //如果内存类型是auto, 那么存储类型就是no_oclass
    public static int  public = 1;
    public static int  private = 2;
    public static int  extern = 3;
    public static int  common = 4;

    private  int  basictype;
    public   void settype(int type) {
        basictype = type;
    }
    public int gettype() {
        return basictype;
    }

    private int storageclass;
    public  void setstorageclass(int s) {
        storageclass = s;
    }
    public int getstorageclass() {
        return storageclass;
    }

    private int outputclass;
    public void setoutputclass(int c) {
        outputclass = c;
    }
    public int getoutputclass() {
        return outputclass;
    }

    private boolean islong = false;
    public void setlong(boolean l) {
        islong = l;
    }
    public boolean getlong() {
        return islong;
    }

    private boolean issigned = false;
    public void setsign(boolean signed) {
        issigned = signed;
    }
    public boolean issign() {
        return issigned;
    }

    private boolean isstatic = false;
    public void setstatic(boolean s) {
        isstatic = s;
    }
    public boolean isstatic() {
        return isstatic;
    }

    private boolean isexternal = false;
    public void setexternal(boolean e) {
        isexternal = e;
    }
    public boolean isexternal() {
        return isexternal;
    }

    private int  constantvalue = 0;
    public void setconstantval(int v) {
        constantvalue = v;
    }
    public int getconstantval() {
        return constantvalue;
    }

    private structdefine  vstruct;
}

basictype用来表明变量属于什么类型，当前要做的编译器暂时只支持4种类型，int , char, void , struct, label. storageclass 表示变量的存储方式，fixed表示变量只能存放在固定的内存地址，auto表示当前变量是局部变量，可以存放在堆栈上。如果当前变量是经过typedef修饰的，那么他的值也会设置成typedef, 例如：

typedef char  single;

那么变量single对应的说明符中，storageclass的值等于typedef。
constant 用来标识常量类型，加入你声明了一个枚举类型：
enum days {
mon, tue, wed, tur, fri, sau, sun
};

编译器会将mon,tue等当做int类型的常值变量加入符号表：

constant int mon = 0;

于是mon, tue, 等对应的specifier类中，storageclass的值就是constant. 同时constantvalue也会做相应的设置，例如mon对应的specifier类，constantvalue 等于0， tue对应的specifier类的constantvalue 等于1.

对于字符串常量，编译器会把它转换成一个初始化了的char数组，例如

“contents of string”;

会转换成：
char s1[] = “contents of string”;
这样，编译器就可以建立一个类型列表来描述字符串常量。

specifier最后还有一个structdefine类型的成员，如果当前的变量是一个结构体的话，vstruct就不是null, structdefine的具体定义，我们后面再给出。

islong用来表示当前变量占据多大字节，默认下int类型占据2字节，long int 占据4字节，因此：

long int x;

变量x对应的specifier类，islong就会设置为true.由于编译器默认没有long修饰的变量都占据2字节，所以short关键字会被自动忽略。

issigned, isstatic, isexternal 用来表明变量是否被对应的关键字所修饰，例如：

external unsigned long int y;

那么变量y对应的specifier 中，isexternal 等于true, issigned 等于false, islong等于true.

类型系统是一个复杂而且繁琐的技术要点，一节不可能讲清楚，本节我们先探讨一部分，在后面的章节中，我们继续就类型系统的理论和代码实现进行深入的了解。

喎?>