从零写一个编译器(七):语义分析之符号表的数…
2019-08-26 06:01:45来源:博客园 阅读 ()
从零写一个编译器(七):语义分析之符号表的数据结构
项目的完整代码在 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://www.cnblogs.com/secoding/p/11373929.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:MyBatis集成到Spring
- 作为一个面试官,我想问问你Redis分布式锁怎么搞? 2020-06-10
- 我可真是醉了,一个SpringBoot居然问了我30个问题 2020-06-08
- java对象指向问题 2020-06-07
- 呵呵,一个 bug 你改了两天?难吗? 2020-06-06
- 一个程序员的水平能差到什么程度?看到他我明白了! 2020-06-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash