从零写一个编译器（七）：语义分析之符号表的数据结构 - 好文

项目的完整代码在 C2j-Compiler <https://github.com/dejavudwh/C2j-Compiler>

前言

有关符号表的文件都在symboltable包里

前面我们通过完成一个LALR(1)有限状态自动机和一个reduce信息来构建了一个语法解析表，正式完成了C语言的语法解析。接下来就是进入语义分析部分，和在第二篇提到的一样，语义分析的主要任务就是生成符号表来记录变量和变量的类型，并且发现不符合语义的语句

描述变量

在C语言里对变量声明定义里，主要有两种描述

*
说明符（Specifier）

说明符也就是对应C语言的一些描述变量类型或者像static，extern的关键字（像extern这些关键词在这次实现的编译器里并没有用到，因为extern可能还要涉及到多个源文件的编译和链接）
*
修饰符（Declarator）

修饰符则是由变量名或者代表指针类型的星号，数组的中括号组成，修饰符属于可以复杂的一部分，因为修饰符可以进行组合。所以对于组合的修饰符就可以创建多个Declarator，按顺序链接起来

这样就可以完成两个类，这两个类的逻辑都比较简单：

Declarator类

* declareType：用来表示当前的Declarator是一个指针还是数组或者函数
* numberOfElements、elements：如果当前的类型是个数组的话，它们就表示数组的元素个数和数组元素 public class
Declarator { public static int POINTER = 0; public static int ARRAY = 1; public
static int FUNCTION = 2; private int declareType; private int numberOfElements
= 0; HashMap<Integer, Object> elements = null; public Declarator(int type) {
this.declareType = type; } ... }
Specifier类

Specifier的属性会比较多一点，但是在后面编译器可能只支持int, char, void, struct四种类型

*
basicType：用来表明当前变量的类型

*

storageClass：表示变量的存储方式（fixed，auto），这里我们把typedef的信息也放在这里，也就是说如果遇见typedef，那么storageClass会被设置为TYPEDEF

*

constantValue和vStruct：这两个属于比较特殊的两个属性，它们表示枚举类型和结构体，之所以特殊是因为它们之后要进行特殊处理。如果遇见枚举类型相当于构造一个basicType是CONSTANT的Specifier，对应的值也就是constantValue了
public class Specifier { /** * Variable types */ public static int NONE = -1;
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; public static int PUBLIC = 1; public static
int PRIVATE = 2; public static int EXTERN = 3; public static int COMMON = 4;
private int basicType; private int storageClass; private int outputClass =
NO_OCLASS; private boolean isLong = false; private boolean isSigned = false;
private boolean isStatic = false; private boolean isExternal = false; private
int constantValue = 0; private StructDefine vStruct = null; }
描述符号表

在前面定义两个描述变量的类，但是仅靠这两个类还是无法准确的表达一个符号，所以我们需要包装一下这两个类，让它更具表达力

编程很多时候都是根据特定的需求完成特定的数据结构，符号表在计算机里本质上也只是用来描述变量的数据结构而已

这个数据结构作为符号表有几个基本的条件：

* 速度
因为符号表需要频繁的插入和查找，所以查询和插入速度必须要足够的快
* 灵活
因为变量的定义的可能会很复杂，比如说多个修饰符再加上指针（(long int, long doube *)，所以在设计上必须足够灵活
因为学习编译器一直是跟着陈老师的课，所以符号表的设计也沿用老师的设计

为了保证上面两个条件，我们选用链式哈希表来实现

这张图是我网上找的，实际上没有那么复杂

所有的变量都存储到这个哈希表中，同名变量被哈希会被同一个地方，当然它们要属于不同作用域，而区分不同作用域就在于这张图上面一部分，它会把同一个作用域的变量连接起来

symboltable.Symbol

这个类用来描述符号表里的一个符号

如果从github下载源文件的话，里面有许多是在后面代码生成才需要用到的，现在可以忽略

主要属性有：

* level: 用来表明变量的层次
* duplicate：是否是一个同名变量
* args：如果该符号对应的是函数名,那么args指向函数的输入参数符号列表
* next: 指向下一个同层次的变量符号 public class Symbol { String name; String rname; int
level; boolean duplicate; Symbol args; Symbol next; }
这时候用Symbol加上之前的Specifier和Declarator就有足够的表达力来描述一个符号，那么就需要把这三个类联系起来，先增加一个TypeLink

TypeLink

TypeLink表示一个Specifier或者一个Declarator，这里用继承来实现可能会显得更好看一点
public class TypeLink { public boolean isDeclarator; /** * typedef int */
public boolean isTypeDef; /** * Specifier or Declarator */ public Object
typeObject; private TypeLink next = null; public TypeLink(boolean isDeclarator,
boolean typeDef, Object typeObj) { this.isDeclarator = isDeclarator;
this.isTypeDef = typeDef; this.typeObject = typeObj; } public Object
getTypeObject() { return typeObject; } public TypeLink toNext() { return next;
} public void setNextLink(TypeLink obj) { this.next = obj; } }
这样在Symbol里就要加入两个属性

typeLinkBegin和typeLinkEnd就是用来描述变量的说明符和修饰符的整个链表，也就是之前说的把这些修饰符或者说明符按顺序连接起来
public class Symbol { String name; String rname; int level; boolean implicit;
boolean duplicate; Symbol args; Symbol next; TypeLink typeLinkBegin; TypeLink
typeLinkEnd; }
例子

这样完成之后，例如
long int (*e)[10];
就可以这样表示

Symbol declartor declartor specifer
name:e declareType = PONITER declareType = array basicType = INT isLong = TRUE
-> -> -> ->
结构体符号的定义

StructDefine这个文件还没讲过，这个文件是用来描述结构体的，因为结构体本身的复杂性，所以就需要对它进行特殊处理，但是结构体本质上还是一堆变量的组合，所以依旧可以用上面的方法描述

* tag: 结构体的名称
* level: 结构体的嵌套层次
* Symbol：对应结构体里的变量 public class StructDefine { private String tag; private
int level; private Symbol fields; public StructDefine(String tag, int level,
Symbol fields) { this.tag = tag; this.level = level; this.fields = fields; } }
例子

看一个结构体定义的例子
struct dejavidwh { int array1[5]; struct dejavudwh *pointer1; } one;

小结

所以最后只需要
private HashMap<String, ArrayList<Symbol>> symbolTable = new HashMap<>();
private HashMap<String, StructDefine> structTable = new HashMap<>();
就可以描述一个符号表

symbolTable里的key相当于变量的名字，而后面的ArrayList存放着同名变量，因为每个Symbol都有一个next指针来指向同级的其它Symbol，所以这样的结构就相当于开头描述的那个哈希表

这一节主要是描述了符号表的数据结构，两个关键点是

*
描述变量

所以定义了修饰符和描述符来描述一个变量

*
关联变量

定义了Symbol链表来串联各个变量

另外我的github博客：https://dejavudwh.cn/ <https://dejavudwh.cn/>

热门工具换一换