编译器,符号表和代码生成

符号表在编译器语义分析过程中承担了重要的作用。通常符号表用于指明标识符(符号)的一些基本属性,诸如它们的名字,类型,域,重定位信息(地址)等。这里讨论一个具体的符号表实现,与它在编译器中承担的任务。

我们以一段C语言代码为例,详细地阐述一下符号表在编译任务中承担的角色。

1
2
3
4
5
6
7
8
9
int a;
float b;
int main() {
float a = 1.0f;
b = 2.0f;
for (int i = 0; i < 5; ++i)
b += 1.0f;
return 0;
}

根据上述代码,我们可以列出一个简易的符号表:

1
2
3
4
5
6
7
8
9
+------------------------+----------------------+-----------------------+
| Symbol name | Type | Scope |
+------------------------+----------------------+-----------------------+
| a | int | global |
| b | float | global |
| main | function, int | global |
| a | float | block local |
| i | int | for-loop statement |
+------------------------+----------------------+-----------------------+

块级作用域

我们希望设计的语言是支持块级作用域的语言。所谓块作用域,是指在一个语句块(block)中声明的变量只有在该块内作用的效力。通常,同名符号也因此具有默认的覆盖关系——内部覆盖外部。我们假设当前某一行代码处于多个块的嵌套中,每个块都声明了一些变量。此时这些变量的集合就构成了该语句所处的环境(environment)。假设这些作用域从外到内为$\sigma_1$, $\sigma_2$, $\sigma_3$,那么当前的环境包含的变量为$\sigma_1 + \sigma_2 + \sigma_3$。我们规定此处的加法中,右侧永远为内层作用域,内层同名变量覆盖外层变量。

我们所要做的是在扫描代码时,维护当前代码运行的环境,并检查变量的使用是否符合要求(类型是否相符,是否声明)。下面给出了2种维护的方法:

  1. 破坏式。新的内部变量声明时,覆盖掉父域的原有符号。在结束作用域时,回退。这要求插入时维护一个撤销动作栈,以便于在退出作用域时恢复父域被覆盖的符号。通常这种类型的符号表使用散列表实现。存储符号名到符号属性的映射。

  2. 函数式。新的内部变量声明时,即时地产生一个新的环境(表)。通常这类数据结构使用可持久化(长效)平衡树结构实现。新的树与旧树共享一部分结构,同时保证高效的访问操作。

符号表保存的信息和中间代码

类型、作用域是从语义层面对代码的约束。从本质上说,程序中出现的变量、函数、常量都会被装载入内存的某些位置,它们占据指定内存段。而程序指令对这些数据的访问和修改操作却没有太多的限制(除了操作系统对程序的限制)。符号表在代码生成中承担的作用在于为不同的变量、函数等分配内存并将这些分配好的内存地址填入指令中。比如上述的代码里就存在同名变量,为了区别它们,需要将这些变量存于不同的位置,因为它们是不同的变量(处于不同作用域中),本质上是不同变量。函数等同理。

中间代码生成

中间代码除了流程控制以外,所有的操作都是集中在变量的操作上的。对于支持函数的语言来说,我们只知道函数内的变量被存储到栈空间中;全局变量或是动态分配的变量被放置在堆空间中。而在四元式中,我们需要显式地进行内存的管理操作。比如生成函数的入栈出栈操作的指令。

对于一个只有全局作用域而且不支持函数的语言来说,变量管理只需要将变量存储至一个固定的空间内即可。此时一个静态的符号表和数据区就可以满足需求,所有的标识符都与名字绑定,并且处在内存的固定区域。而支持函数和块级作用域时,我们就不得不生成若干内存管理的代码,用于分配内存,指明这些变量所处的位置。我们需要考虑这些代码需要动态地分配所需的内存,并对他们进行操作。

而关于函数声明和调用的中间代码又是另一个繁杂的话题了,下次再表。