当前课程知识点:Compilers Techniques > 8 Design and Implementation of a Simple Compiler > 8.3 SimpleJava > 8.3 SimpleJava
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学
大家好
我们在学习完编译器
基本的知识之后
我们是不是可以自己来编写一个
编译器
从这节课开始
我们就来学习一下
基于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编译器进行编译
得到的结果如右侧所示
这也就是程序运行的结果
我们再来看一下
这段程序所产生的汇编源码
当然这段汇编源码太长了
这一讲就到这里
谢谢大家
-1.1 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
-2.2 Regular form
--2.2 Regular form
-2.3 Finite automata
--2.3 Finite automata
-2.4 DFA construction, Subset construction, Simpleset DFA
--2.4 DFA construction, Subset construction, Simpleset DFA
-2.5 Lex
--2.5 Lex
-3.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes
--Syntax-Directed Definitions
-4.2 Bottom-Up Calculation of S Attribute
--4.2.1 Bottom-Up Calculation of S-Attributed
-4.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--4.3.3 Design of Predictive Translator
--L-Attributed Definitions
-4.4 Bottom-Up Parsing of L-Attributed Translation
--4.4.1 Bottom-Up Parsing of L-Attributed Translation
--4.4.2 Simulate the Parsing of Inherited Properties
--Bottom-Up Parsing of L-Attributed Translation
-5.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-7.2 Target Machine
--Target Machine
-7.3 Basic Blocks and Flow Graphs
--7.3 Basic Blocks and Flow Graphs
-7.4 A Simple Code Generator
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava