8.3 SimpleJava在线视频

各位同学

大家好

我们在学习完编译器

基本的知识之后

我们是不是可以自己来编写一个

编译器

从这节课开始

我们就来学习一下

基于Python的简易编译器实现

我们可以从头到尾

来学习一下

如何自己来编写一个编译器

这里我们以simpleJava编译器

做为一个简单的例子

来说明编译器的开发过程

首先

我们需要给出simpleJava

所有源程序的设计说明

也就是源代码的编写规范

那么在这里

我们使用上下文无关文法说明

其中包括了程序的语句、

表达式、计算、声明、if 语句、

while语句、for语句、return语句

以及控制语句等等

最上面的三行

用来说明语句和语句的列表

第二部分

用来说明运算符相关的文法

接下来

是变量与函数声明的相关文法

第4部分是申请堆内存

新建对象和数组相关的文法

第5部分

蓝色框框起来的是流程控制语句

相关的上下文无关文法

包含了while语句、if语句、for语句

等一些常见的流程控制语句

接下来是类型相关的上下文关文法设计

包含了 int、float、double

等一些常见的数据类型

最后一部分是关于基本数据单元的

上下文无关文法设计

在完成simpleJava的上下文关文法设计之后

我们来看一下相关的程序

这几行程序

主要用来读取类型的定义

给出相关的上下文无关文法cfg

生成我们所需要的Action和Goto表

并且我们要把Action和Goto表保存下来

我们来看一个例子

根据左侧的这些代码

是我们在simpleJava当中

所支持的一些源代码

那么根据这些源代码

我们可以根据之前生成的

Action和Goto表

对上面的代码来进行分析

分析的结果

可以得到右侧这样的一棵分析树

通常分析树是比较大的

它可能会包含一些没有用的节点

因此

我们需要构造抽象语法树

只保留有用的节点

接下来我们看一下抽象语法树

我们设计了一个ASPNode这样的类

用来表示抽象语法树上的一个节点

我们也设计了

AbstractSyntaxTree这样的一个类

用来实现抽象语法树

ASTActionRegister用来记录

抽象语法树当中的Action表

下面我们来看一下

生成的抽象语法树

我们来看一下相关的实现

上面的一个部分

是用来处理语句和语句列表

中间我们省略了

大概330行的内容

大多数是比较类似的一些内容

下面部分

是处理其他的这些产生式语句

总的来说

我们主要在这一步

用来减少多余的节点

这一页给出了一段源程序

产生的抽象语法树

我们可以看出来

实际上生成的抽象语法树

仍然是比较大的

接下来我们看一下Code Block代码块的实现部分

在这一部分

我们需要存储

由抽象语法树产生的三地址代码

我们还需要给每个statementList

设置一个新的代码块属性

用来存储一个代码块对象的引用

我们还需要将父结点的代码块引用

传递给对应的子节点

这样我们就可以在任意的节点当中

填加三地址代码TAC

在生成三地址代码之前

我们还有一件事情需要去考虑

就是作用域

每个statement list都会产生一个新的作用域

我们可以利用嵌套的深度

和在这个深度的编号

可以唯一的确定对应的作用域

我们利用深度和每个深度已有的作用域数量

产生唯一的编号

接下来我们看一下声明

和查询变量的处理方法

我们将变量的基本信息

都封装在一个类当中，Object这个类中

包括标志符、类型、

占用的字节数、命名空间等等

在实现的过程中

我们在声明语句当中去创建变量

在普通的语句当中

溯根去查询父作用域

直到到达根作用域

或者命中

我们将结果放置在var属性当中

接下来我们看一下

生成的三地址代码

下面我们来看一下

条件判断与循环语句的处理

需要讨论的一个问题是

汇编语言只有无条件跳转语句jmp

还有根据CPU flags进行跳转的jz、jnz等等

那么我们要怎么才能把if while for

转换成 jmp跳转语句呢？

我们观察一下

左侧的这样的if else语句

可以通过右侧的if goto语句来实现同样的功能

针对左侧的while语句

我们也可以使用右侧的goto if语句

来实现同样的功能

显然我们可以通过if和goto语句

就可以描述if和while这样的结构

除此之外

我们还需要提供

对代码块切分的操作

在我们实现的三地址代码中

包含着if伪指令

也就是这一条

if cond val cb0 [cb1]

if伪指令的意思是说

当条件等于val的时候

我们需要跳转到cb0

如果有cb1，则在cb0完成后跳转到cb1

goto伪指令

用来跳转到cb0

如果存在cb1，那么则在cb0完成后，跳转到cb1

seg用来作为一个划分

从这里开始往后的代码

将会被划分为一个新的代码块

当前代码块的next属性

会被设定为新划分的代码块的引用

在实现的过程中

我们可以利用元组来表示

现在不能确定的代码块

针对continue和break语句

我们也只需要简单的添加跳转

即可完成对应的功能

由于指定代码块的下一个代码块

并不是在生成时确定的

因为next会因为seg伪指令而改变

因此

我们需要在生成完三地址代码之后

先切分代码块

在切分了代码块之后

我们可以先替换

所有没有确定代码块当中的cur

作为当前代码块的引用

由于未确定的代码块

可能依赖于其他的未确定代码块

因此

为了确定计算的次序

在这一步

我们需要建立依赖图

在建立了依赖图之后

我们还需要计算一下拓扑排序

这样就可以计算出

所有代码块的下一个代码块

最后

我们把 goto 和 if 语句

转换成真正的目标代码即可

下面我们看一下函数定义的实现

我们设计了function这个类

我们只对函数做最基本的封装

也就是记录变量的列表、函数的名、

返回值的类型、以及相应的代码块

在实现的时候

需要在对应的Action处

产生新的Function方式对象

并且把它记录下来

我们再来看一下函数调用的实现

在说明函数调用之前

我们需要理解函数之间

是如何来传递值的

我们看一下右侧的图示

这是程序运行时

操作系统为它分配的内存

如果函数需要传值的话

需要把参数逆序压入到栈中

例如当前的printf包含了两个参数

%S和hello

%S和hello作为参数值

是逆序进入到栈中

再将这些参数压入到栈中

就是push这些参数之后

那么我们可以利用call指令来调用函数

返回值

我们在这里约定使用EAX寄存器来保存

在windows当中

EBP指针用来指向栈底

ESP指针用来指向栈顶

在windows上

call只存储了原来的EBP指针

也就是指向栈底的指针

在那之后

我们就可以利用ESP

也就是指向栈顶的指针

加上偏移的方式

来读取之前压入到栈里的值

在实现的过程中

我们需要注意如下的几个问题

首先我们需要保护

EAX和EBX寄存器的值

不被其他的数值所污染

所以我们需要使用push语句

进行压栈

第二

我们需要逆序

将这些函数的参数压入栈中

第三

我们需要使用push语句

将 var的值压入到栈中

第四

使用call来调用对应的函数

第五

我们需要清理实参占用的栈空间

第六

我们还需要从EAX寄存器

获取返回的数值

最后我们看一下实现的效果

左边我们给出一段源程序

这段源程序是满足simpleJava编译器

所要求文法的代码

那么针对这段源代码

而使用simpleJava编译器进行编译

得到的结果如右侧所示

这也就是程序运行的结果

我们再来看一下

这段程序所产生的汇编源码

当然这段汇编源码太长了

这一讲就到这里

谢谢大家