中国科学技术大学 编译原理 语义分析(类型检查、上下文相关分析)

本文已收录于 中科大编译原理学习笔记 系列,共计 6 篇,本篇是第 4 篇

语义分析做什么事情?

下面一段代码有7个语义错误,编译器的语义分析就是研究这样的问题。

语法分析器所做的事情:输入程序语言的语义规则,输出Yes或者No。

同时语义分析器也是代码和编译器的工作界限,一段代码如果通过了语义分析器再有任何问题就不属于代码的问题,而是编译器的问题。

程序语言的语义规则

与之前的语法分析规则一样,语义分析也是计算机科学中的一个研究点,这是一个难点。不过大多数语言都是采取自然语言描述的,是教条的,是人为规定的,例如在C语言中会告诉你加号前后应该是整型数字或浮点型数字。

编程语言的使用者可以仅仅知道加号两边只用数字就行了,但是

,实现者还必须知道 浮点数+浮点数、浮点数+整数等等是否属于一个语言中的语义。

语义检查

实例:通过一门名叫C–的语言研究语义

问题:为什么要检测?

答:这部分语义检查、程序合法性检测是人为设计的,就是人为规定的,编译器在这里是研究怎么实现的,不是研究为什么要这么做的。为啥要检测,要这么设计?请看本小结末尾的总结。

表达式合法检测

这是C–语言表达式的语法规则:

下面的两个都是合法的程序:

下面的两个不合法:

对于上面的四种情况的表达式,我们语义分析意在通过自己编写的函数来实现传入“3+4”、“false && true”这种表达式进行处理,希望对于3和4两个表达式返回语义错误;对于表达式1返回INT,对于表达式2返回BOOL。

下面就是验证表达式的函数 check_exp:

Ps: switch(e->kind) 是抽象语法树中定义的成员变量,可以参考 –> 抽象语法树的设计

变量声明检测

问:什么要设计成变量使用前必须声明?这样做有什么实际的意义?

答:在硬件看来,一切皆数据,连代码也可以是数据,只有大小/粒度之分。但显然大家实际编程时,数据和数据之间是有区别的。因为编程语言设计了:数据的组合、排布、约束属性等,共同构成了数据的“类型”。所以编程语言人为规定了必须要有数据类型,就算为了方便/特性等设计了没有数据类型的语言,无需用户去声明数据类型(例如PHP语言),但是!哪怕编译时不做类型检查,在运行时也是要做的,就算你是JS也要做。如果是C语言的话,最主要的作用就是约束对数据的操作。比如你不能修改const,或者不能操作这个struct里没有的东西。而其他支持重载的语言还会考虑到函数决议问题。再往后说其实就是语言的设计思想。

符号表

符号表有什么用途?

符号表是为生成中间代码所服务的,在生成中间代码后符号表就不要了。

访问控制信息:public、private、包等。

根据符号表构造访问链(符号表的数据结构)

符号表也是数据结构中讲的一种存储结构,具体的实现跟具体的语言有关,中科大 编译原理以C语言介绍了符号表的伪代码实现。具体的真实代码可以参考高一凡的数据结构实现书籍。

先来看下符号的使用接口:

符号表内部的实现:符号表的内部就是查找,具体用哈希表还是树索引、还是二分查找、链表等等方式,这里我们不讨论,这是数据结构中研究的内容。看下面的符号表的操作部分。

空间和时间不可兼得,根据shijixu

eg:

一段程序中的符号表指向内存的图,符号表内需存储变量名实际在内存中的地址,这也叫指向。

第四行:OPN1是操作数1,OPN2是操作数2,Result是结构变量,OPR是操作运算符。

 

对符号表的操作

可以把常数组织成一张表、把变量组织成一张表;也可以把所有符号放在一张表中;还可以按照属性相似程度组织成一张表。

本质就是查找,关于查找在数据结构中有详细的讲解。可以参考 –> 数据结构 思维导图 分享(2020.3.2版)~未完结CMU15-445数据库系统:哈希表CMU15-445数据库系统:树索引

对符号表的操作就是对线性表、有序表、树、哈希表等的操作,与数据结构一模一样。本质就是查找,这块内容建议参考 CMU数据库系统 中的哈希表和树索引章节,里面非常详细的说明了查找的各种数据结构。

符号表处理作用域的方法

方法一:用一张表,可以通过栈来实现控制作用域。

每个程序块中的变量都是独立的,我们通过栈来实现,进入到内部的数据块(进入作用域时)就压栈(插入元素),退出作用域的时就弹栈删除元素。这样就可以保证栈顶元素是最内部的作用域,外部的作用域在栈底。

当然,通过哈希表的方式也可以。

方法二:用链表方式组成的栈

符号表处理名字空间的方法

在程序里面 有好几个地方用到同一个变量名。

处理方法:每个“list”虽然都叫list,但不会混淆。处理方式是每类都定义一个符号表。

其他问题

类型相等

如果这个编程语言采取 名字相等 的策略来检查类型,那么 x = y 这个语句就会报错,因为 struct B与 struct A,A与B不相等。

但如果采取结构相等的策略检查类型,那么遇到 x = y 语句后还需要去结构体内部查看结构体的成员是否可以一一赋值。

在面向对象的语言中,还需要考虑对象之间的继承关系,一般是通过树来存储的。

如果存在多态特性,就会更复杂一些… …

错误诊断

代码翻译

代码的翻译部分后续我们继续讨论 … …

 

参考文献:

https://www.zhihu.com/question/348502876/answer/848425608

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。