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

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

对于C语言中的一段函数代码，便可以分割成对于上面所说的三部分，函数声明中的函数名，返回值和输入参数例如：

int fun(int arg1,int arg2)

就可以对应上面三部分的声明部分，函数的主题则对应于表达式和语句模块部分。

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

{

int var = 0;

}

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

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

typedef char SingleByte

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

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

1、速度，由于符号表会被编译器频繁的写入和读取，因此记录的写入，查询速度必须足够快，为了保证速度，整个符号表会直接存储在内存中，由此符号表的设计必须仔细考虑内存消耗。

2、维护性，符号表几乎是编译器中最复杂的数据结构，它的设计必须灵活可扩展，是的除了编译器外，其他应用程序或模块也能良好的访问符号表。

3、灵活性，C语言的变量声明系统很复杂， 例如它允许关键字相关组合，long int *，因此符号表必须能支持各种不同的变量声明方式。

4、重复性支持，由于大多数编程语言，在不同的嵌套下重复的变量名是允许的。

int var=0；

{

int var =1;

}

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

5、易删除，由于变量可能随时超出作用范围，因此一旦语法解析器发现变量失效后，必须能快速地将其从符号表中删除。

符号表的数据结构设计

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

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

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

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

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

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

第二层的三个变量vladmir estragon，pozzo，也组成一个队列，这个队列的头指针就存放在cross link列表的第二个元素，第三层依次类推。

符号表中的一个记录，我们可用如下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;
    }

}

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

类型系统

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

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

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

short int Quasimodo

long *Gringoire

他们的类型系统如下：

类型系统中，说明符部分只有一个，而修饰符部分可以有多个，当然也可以没有，同时，说明符始终在链表的末尾，通过把链表顺序年下来，就可以读出变量声明语句。例如对于第二个队列，孙旭读下来就是Gringire 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用来表明变量属于什么类型，当前瑶族ode编译器暂时只支持四种类型，int，char，void，struct，label，storageClass表示变量的存储方式，FIXED表示变量只能存放在固定的内存地址，AUTO表示当前变量和局部变量，可以存放在堆栈上。如果当前变量是经过typeDef修饰的，那么它的值也会设置成TYPDEDEF。

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修饰的变量都占据两字节，所以short关键字会被自动忽略。isSigned，isStatic，isExternal用来表示变量是否被对应的关键字所修饰，例如：

external unsigned long int y;

那么变量y对应的Specifier 中，isExternal 等于true, isSigned 等于false, isLong等于true.

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