当前课程知识点:Compilers Techniques > 6 Intermediate Code Generation > 6.1 Overview of Intermediate Code Generation > 6.1 Overview of Intermediate Code Generation
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课我们开始学习第7章
中间代码生成
我们先来看一下
编译器的整体结构
中间代码生成
处于前端的最后一个阶段
也就是我们在完成词法分析、
语法分析和语义分析之后
我们需要将我们得到的结果
翻译成中间代码
然后供编译器的后端来使用
中间代码
用来区分编译器的前端和后端
方便我们来针对新的机器
提出新的编译器
我们还可以针对中间代码
来设计更好的程序优化器
我们看到中间代码
这个部分
是连接前端和后端的重要组成部分
得到的结果是中间代码
使用中间代码的优点是
中间代码和机器无关
便于我们在不同的机器上进行移植
便于进行独立于机器的优化
有几种常用的中间表示
包括后缀表示、
图形表示
和三地址代码表示
我们要用语法制导的定义
和翻译方案
可以将源程序翻译成中间代码
我们首先来学习一下
后缀表示方法
后缀表示方法
相当于是我们有一个如下的递归定义
假设 E是一个变量或者参数
那么它的后缀表示就是它本身
也就是id这个表达式
它的后缀表示就是id
num这个表达式
它的后缀表示就是num
如果E是形式为E1 Op E2这样的表达式
那么E的后缀表示
就是E1'E2'Op
其中E1'是E的后缀表示
E2'是E2的后缀表示
如果是单目运算符uop E
那么它的后缀表示
就变成了E' uop
E'是E的后缀表示
如果E的表示形式是(E1)
那么E1的后缀表示就是E的表示
也就是说
(E)它的后缀表示形式就是E
也就是说后缀表示形式不需要带括号
我们再看一个表达式
(8-4)+2
那么(8-4)这个括号
在我们使用后缀表达式之后
就不再需要括号了
我们可以将它写为84-2+
后缀表示的最大优点
是方便计算机来处理
我们可以通过一个例子
来了解一下后缀表达式的优点
比如说
(8-4)+2这样的后缀表示是84-2+
它非常方便计算机来进行处理
我们看到
我们会在栈里边
将临时变量8写入到栈底
然后我们读取到第二个数字是4
4也放入到栈中
接下来计算机会读取到减号
我们就来计算8-4的结果
将4写入到栈中
下一步我们读取到数字2
我们将2写入到栈中
然后我们读取到加号
我们就把4和2相加的结果
写入到栈中
我们观察到这种后缀
表示非常方便计算机来进行处理
接下来我们来学习
第二种表达方法
图形表示
假设有一个表达式
a=(-b+c×d)+c×d
对于这样的一个表达式
我们可以将它化为语法树的形式加以表达
我们看到
对于这棵语法树来说
我们读取的时候
是从上到下开始进行读取
a=-b+c×d+c×d
这样的形式
还有一种表达方法
是有向无环图
它是语法树的一个简便的表达方式
我们注意到
刚才的表达式当中
c×d出现了两次
我们实际上不需要计算两次
而是需要在语法树当中
将加号的右结点
引入到c×d的父结点当中
也就是乘号上
这样我们就可以将c×d的结果
直接来进行使用
根据图形化的表示
我们可以来构造语法树对应的语法指导定义
我们来观察一下
针对如下的这些产生式它的语法规则
我们针对第一个产生式S→id := E
针对这个表达式
我们需要去构造一个新的结点
我们用了mknode这样的一个函数
来构造一个新的结点,assign这个结点
然后它的左边的叶子结点是id
右边的页子结点是E
第二个产生式 E→E1+E2
我们对应的语义规则是
E的指针
等于mknode('+', 左子树E1.nptr, 右子树E2.nptr)
那么我们观察到根结点是加号
左子树是E1,右子树是E2
对于第三条产生式 E→E1×E2
和加法的产生式类似的
只是乘号作为了当前的父结点
对于第4个产生式来说
E→-E
我们看到这是一个单目运算符
所以我们对应的语义规则是
构造单目运算符所对应的结点
然后它的子结点是E1
下一个产生式,E→(E)
那么我们知道
对于语法树来说
不需要有括号的存在
所以只需要把E1的指针赋给E即可
最后一个产生式E→id
那么我们需要为id构造一个子结点
也就是
最后一个语义规则
E的指针等于mkleaf
也就是我们当前构造了一个叶子结点
叶子结点的值是id
下面我们来学习
第三种表达方法
三地址代码
三地址代码的一般形式是x=y op z
也就是说
在一条语句当中
最多包含三个地址
假设有一个表达式x+y×z
它的三地址代码表示形式是
t1=y×z
t2=x+t1
其中t1和t2
我们把它称之为临时变量
临时变量需要在我们
栈中存储在局部数据的下边
我们可以根据语法树
或者是有向无环图
来写出它对应的三地址代码
我们来看一下这个例子
针对这棵语法树
我们可以将它的三地址代码
写为左侧的形式
t1=-b
t2=c×b
t3=t1+t2
t4=c×b
t5=t3+t4
a=t5
针对有向无环图
我们同样可以把它的三地址代码
写出来
t1=-b
t2=c×d
t3=t1+t2
t4=t3+t2
a=t4
下面我们给出一些
常用的三地址代码
一般的表示形式
对于赋值语句来说
x=y op z
里边只包含三个地址
直接就可以写为三地址代码
x=op y或者x=y
这都是满足三地址代码的形式
对一个无条件转移语句
我们将它写为goto L
也就是无条件跳转到L
对于条件转移语句
我们将它写为 if x relop y goto L的形式
也就是,如果x和y满足一定的条件
我们跳转到L
下一个是过程调用语句
首先是我们将n个参数写出来
param x1, param x2, 一直到param xn
然后我们来调用这n个参数
所对应的这个过程
也就是call p, n
n指出了参数的个数
下一个是给出过程的返回语句return y
我们将y返回
接下来是索引赋值语句x=y[i]
也就是我们从y这个地址出发
向下取i个存储单元之后
取出对应的值赋给x
对于x[i]=y来说
我们把y的值取出来
赋给x[i]对应的单元
也就是从x出发
向下寻找i个存储单元
将y的值存入其中
最后是地址和指针赋值语句
x=&y
我们取出y的地址赋给x
x=*y
我们取出y的指针赋给x
*x=y
我们将y的值取出来
赋给x所指的位置
最后还有一种表达方式
我们将它称为静态单赋值形式
我们看一下静态单赋值形式
同样是一种中间代码的表示形式
它可以用来方便某些代码
来进行进一步的优化
它和三地址代码的主要区别有两点
首先
所有的赋值指令
都是对不同名字的变量的赋值
在三地址代码当中
比如说
我们可以将它写为一个代码序列
p=a+b
q=p-c
p=q×d
我们发现在这一步我们重用了p
p=e-p
q=p+q
在这里我们多次重复了p和q
在静态单赋值形式当中
我们强调的是
每一个变量只有一次赋值
p1=a+b
q1=p1-c
p2=q1×d
也就是我们不可以对一个值
进行两次重复的赋值
p1只可以进行一次的赋值
p3=e-p2
q2=p3+q1
如果是这样的话
对于静态单赋值的形式
我们会碰到的另一个问题是
一个变量
如果在不同的路径上都有不同的定值
如何去解决这个问题呢?
比如说
if (flag) x=-1; else x=1
我们发现其实在不同的路径上
x的值是不同的
在后边y=x×a
对x进行引用的时候
我们究竟取哪个x的值呢?
那么在静态单赋值中
是这样解决这个问题的
我们将它改写成
if (flag) x1=-1; else x2=1
也就是在两个不同的路径上
我们使用了不同的变量名称去表示它
然后我们写成一个函数
x3=Φ(x1, x2)
这个函数是由flag值来决定的
由flag来决定
我们在此处
x3的值是取x1还是取x2
这一小节就到这
谢谢大家
-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