第五章语义分析与代码生成

type

status

date

slug

summary

语义分析及中间代码生成

语义分析

语义分析目的——读懂代码并且根据语法分析生成的抽象语法树生成中间代码

类型检查

定义检查（是否定义，有没有重复定义）

操作检查（检查操作是否合法，当前数据的类型是否支持当前操作）

等等

静态语义检查（静态的意思就是在编译的时候就已经确定了）

类型检查

控制流检查

一致性检查

具体如下图：

如何进行语义检查——通过符号表（符号表存储了标识符的相关信息，如值，类型，作用域等）

符号表

符号表存储的内容：标识符及其相关的信息（注意标识符不止有变量名，还包含了函数名）

符号表的形式：每一个标识符（名字）对应一个表项，然后每一个表项内记录了当前标识符的信息，即：

这里分别称这两个区域为名字域和属性域（很像tok，但是tok是种类加上属性值）

名字域中就是存储标识符的，没什么好讲的

属性域

属性域中包含了多个子域，用来记录不同信息，如类型、值、存储大小、相对地址、形参标志（对于函数而言）等等

语义分析时如何使用符号表

核心问题（抽象语法树在语法分析阶段就已经完成了）：

这里提供一种栈式符号表（这里的缩进代表作用域。这里可以发现，符号表只显示当前作用域内可使用的标识符，并且进入一个作用域或者退出一个作用域时要进行状态变化。）：

将上面的缩进换一种形式进行表达可以用下图的栈来表示（每次进入一个作用域的时候就加入一个灰色的栈元素，返回的时候就退回到上一个栈元素。引用标识符的时候就对栈进行查找，通常使用哈希）：

上面的都是栈加哈希的符号表，下面提供一个线性表加树的符号表（这就能说明符号表的数据结构不是定死的，是自己设计的，但是符号表常见的数据结构就是线性表和哈希表）：

符号表的操作（实际上还包括了上面所说的作用域变化时进行的符号表状态变化）：

接下来进入语义分析部分

语义分析方法

语法制导的语义分析翻译方法：在语法分析时不建立抽象语法树，而是直接生成中间代码（就相当于将语义分析融合到了语法分析中，根据语法分析的行为进行语义分析，所以称为语法制导），适用于比较简单的语言（毕竟将两步合在一起做了）

以抽象语法树为基础的语义分析：进行语法分析的时候并没有进行类型检查，而是通过语法制导翻译生成了抽象语法树，然后在后续的语义分析阶段根据语法树进行操作

可以发现上面的两个语义分析方法的主要区别就是语法分析时有没有生成抽象语法树

在目前的编译器中在语法分析时建立抽象语法树是一个标准步骤，所以第二种是用的比较多的

但是实际上生成抽象语法树是应用了语法制导的思想的（龙书上写的）

现在谈谈我自己对语法制导翻译的理解：

语法制导翻译应该就是根据语法分析时进行的动作（推导规约等）来进行相应的操作（这个操作可以是语义分析，也可以是抽象语法树的建立），由于操作是由语法动作支配的，所以称为语法制导翻译（就是将一个语法动作翻译为一个我们自己的操作）

语法制导语义分析

概述

语法制导翻译的分析过程：给每一个产生式都配上一个语义子程序，在对产生式进行推导（自上而下方法）或规约（自下而上）时顺便调用相应的语义分析程序进行语义分析。（相比较实验三，实验三是给每一个规约项目都配了一个抽象语法树的建立函数，而这里的语法制导就直接不要这个抽象语法树创建函数了，而是替换为一个语义分析程序，这个时候就将语法分析和语义分析合在一起了，也就是语法制导翻译）

这里的语义子程序需要针对产生式进行语义检查和中间代码生成（中间代码生成是核心），也就是做语义分析应该做的事情

但是有下面这个弊端：

语法制导翻译示例如下：

这个时候就是直接进行结果的传递了，并没有生成抽象语法树（这里的lexval代表的是在词法分析阶段生成的tok的属性值，对整型值而言这个就是一个整数）

后面的括号里面实际上就是当进行规约的时候就进行后面的操作（就是自底向上的分析方法，这个时候还是需要去做自底向上那一套找句柄等等的东西）

以抽象语法树为基础的语义分析

概述

此时下面的图片中就是一个纯语法分析过程了

可以发现相对于上面的语法制导翻译，基于抽象语法树的翻译在后面的操作就是建立抽象语法树的操作（就跟实验三是一样的）

此时在产生式后面函数的有一些节点直接上提的操作（实际上就是在简化语法树）。所以这里本质上是根据文法的语法树（就是上图中的绿色的树）然后经过自己的操作（写在产生式后面的函数）生成了一个抽象语法树

抽象语法树的建立（抽象语法树的建立用到了语法制导翻译）

设计抽象语法树的数据结构的时候需要考虑下面这些：

如上图，在程序中存在很多并列结构，这个时候就需要在节点的定义中加入一个新的指针域next来表示并列结构（所以生成的抽象语法树可以理解为一个链表上每一个节点都是一个树的根节点）

注意这里的处理，他给链表额外增加了一个头结点（不代表external_declartion），这个节点的左右子树指向这个链表的头节点和尾节点，如下图：

这样看的话生成中间代码的过程实际上就是遍历抽象语法树的过程（只不过每次都需要做一点操作,比如实验四中的print），也就是下图所说的：

这个就很像实验三的思想了，就是向上返回节点类型（需要告诉上层函数当前节点是什么东西，这样上层函数才能知道应该如何处理产生式中的一些符号，也就是选择匹配哪一个产生式，比如这里如果是复合语句的话就在ed节点处认为是一个函数定义的节点，否则就认为是一个变量声明的节点，然后在ed节点处进行语法制导的时候也就调用不同的函数构建结构不同的抽象语法树），不同情况不同处理（也就是实验三的建树过程，每次规约生成一个节点，虽然规约生成的非终结符是一样的，但是可能该符号的不同产生式规约生成的抽象语法树节点是不一样的，然后上层的产生式就根据这个类型进行操作（这么想的话实验三做的不是很好，每次都没有进行节点类型检查，也可能是文法并没有出现上面所说的情况，就是同一个非终结符不同产生式规约生成的节点类型不一样，我都是直接重新给节点赋类型））

这个也是一样的道理，要给上层函数提供信息上层函数才能做出来对应的操作

符号表在何时建立？——在建立抽象语法树的同时（也就是语法分析阶段）需要将已经获取的信息存入符号表

基于抽象语法树的语义分析

根据语法分析阶段生成的抽象语法树及符号表，通过遍历抽象语法树进行类型检查，类型检查之后再次遍历抽象语法树生成中间代码

这个是在语法分析阶段就该做的事情（所以说语法分析阶段应该是边建立符号表，边查找符号表）

上面就是语法分析阶段应该做的事情，第一个产生式后面的内容中的第一行实际上就对应了在符号表中查找该变量的操作，然后如果查找到了该变量，就生成一个变量引用节点（所以实验三里面的变量都叫REF，就是引用）

这些都是在语法分析阶段完成的操作，也就是抽象语法树的建立（应用了语法制导翻译）

这个比较复杂，就是要先查找当前的变量是否已经声明过了（也就是是否已经在符号表内了），声明过才能对其进行赋值（这么想的话实验四的时候建立符号表就应该将int a=2这样的语句分开处理，要拆成声明和赋值两步）

具体的抽象语法树建立过程如下：

这个语义栈实际上就是实验三yylval对应的那个栈，这里面存储每个符号对应的属性（这里的飘号实际上就是实验三当时的token类型）。这个实际上是一个自下而上的分析方法，当规约的时候语义栈就跟着符号栈一起进行变化（注意这里的符号栈底放了一个结束符号，如果在LR分析中让画状态栈和符号栈的时候也记得在栈底放一个#来表示栈底）

此时规约结束的时候就通过语法制导翻译的方法生成了一颗抽象语法树。这个语义栈就是实验三当时yylval对应的栈（也就是当时所说的数值栈）

建立了抽象语法树之后就是遍历一遍进行类型检查，然后再遍历一次生成中间代码（这个是重点，所以在这里只说如何生成中间代码，但是不说怎么去进行类型检查，类型检查实际上就是根据某个子树的根节点去看左右子树的类型是否合法）