当前课程知识点:Compilers Techniques >  7 Code Generation >  7.4 A Simple Code Generator >  7.4 A Simple Code Generator

返回《Compilers Techniques》慕课在线视频课程列表

7.4 A Simple Code Generator在线视频

下一节:8.1 Demonstration of Compiler Framework based on Python

返回《Compilers Techniques》慕课在线视频列表

7.4 A Simple Code Generator课程教案、知识点、字幕

各位同学大家好

这节课我们继续来学习代码生成

我们以之前用到的这段代码序列

作为一个例子

来学习一个基本的代码生成器

在没有搜集全局信息之前

我们暂且以基本块

作为我们的程序基本单元

来生成我们想要的代码

我们需要考虑的问题有如下几个

首先

我们需要依次去考虑

基本块当中的每条语句

为它来产生代码

假定三地值语句的每种算符

都有对应的目标机器算符

假设计算结果留在寄存器当中

尽可能长的时间

除非这个寄存器要用于其它的计算

或者基本块要进行结束

为此

我们在生成代码过程当中

需要记录一些基本的信息

比如说

对于a=b+c这样的语句来说

如果寄存器 Ri含有b的信息

Rj含有c的信息

并且b在此后不再活跃了

那么我们可以产生

ADD Rj, Ri

我们将a留在 Ri当中

如果Ri包含b的值

c在内存单元当中

b仍然不再活跃了

那么我们可以产生 ADD c, Ri

或者也可以产生 MOV c, Rj

ADD Rj, Ri

也就是我们根据不同的情况

来使用不同的寄存器

或者不同的语句序列

如果c的值以后

还要去使用的话

我们会发现第二种代码

是更为合适的

在代码生成的过程当中

我们需要去跟踪寄存器的内容

和它对应的名字的地址

寄存器需要记住哪些信息呢?

寄存器需要知道

当前的这一点

它所描述的所有的变量是哪一些

也就是寄存器

要保存若干个名字的值

它要一直知道

保存的是哪些名字的值

比如说b=a 在b=c这个语句之前

R0假设保存的是变量a的值

那么b=a这样的一条赋值

我们不用为这条语句

就是产生任何的指令

在这条语句之后

R0仍然保存变量a的值和变量b的值

在代码生成的过程当中

我们需要讨论的另一个问题是

名字的地址

它需要描述记住运行时每个名字的值

应该在什么地方去找到它

这个场所

可以是寄存器

也可以是栈的单元

或者内存的单元

甚至是它们的一个集合

比如说

我们在产生MOV c, R0之后

我们知道c的值

可能在R0中和c中

对应的存储单元找到

还有名字的地址信息

存放于符号表当中

另外我们需要建立寄存器来描述

对应的符号表

这两个描述

在代码生成过程当中

可能是变化的

我们再看一下,对一个三地址语句

x=y op z

我们可以调用一个函数

getreg来决定y op z计算的结果

存放的场所

假设是L

我们需要查看y的地址描述

确定y的值当前所对应的一个场所

我们写为y'

如果y的值不在L中

我们产生一个指令序列

MOV y', L

我们将y'移动到L中

然后我们产生对应的指令序列

op z', L

其中z'是z当前的场所之一

如果y和z或者是z当前的值

不再引用了

那么在块的出口

也不再活跃

并且还在寄存器当中

那么我们知道这个时候

可以去修改寄存器的描述

接下来如果y的值在R当中

这个R不含有其它名字的值

并且在执行x=y op z之后

y不再有下次引用

那么我们可以返回这个R作为L

否则如果有的话

我们可以返回一个空闲的寄存器

也就是去使用空闲的寄存器

否则如果x在块中

如果有下一次引用

或者op必须用寄存器的算符

那么我们需要找到

另外一个已经占用的寄存器R

去存放它的值

可能产生MOV R, M这样的指令

并且需要修改M的描述

否则

如果x在基本块中不再使用了

不再引用了

或者找不到适当的被占用的寄存器的话

我们只能选择x的内存单元作为L

我们再看一个赋值语句

假设d= (a-b)+ (a-c) + (a-c)

我们可以通过编译

得到它的三地址代码序列

也就是中间代码

t1=a-b

t1是临时变量

t2=a-c

t3=t1+t2

d=t3+t2

然后我们可以针对这个三地址代码序列

得到对应的汇编语句

我们来看一下

在最开始寄存器是空的

第一个语句t1=a-b

我们可以生成对应的代码

MOV a, R0

将A移动到R0中

R0中含有了a

然后SUB b, R0

我们从 a当中,也就是R0当中减去b

R0在此刻的状态是含有t1

然后第二行语句

t2=a-c

MOV a, R1

我们将a移动到R1中

然后SUB c , R1

我们用R1去减去c的值

此刻R0含有t1的值

R1含有t2的值

然后第三行语句

t3=t1+t2

我们可以产生对应的代码

ADD R1, R0

我们把R1加到R0之上

我们知道R0含t3的值

R1含有的是t2的值

最后一行语句d=t3+t2

我们产生的代码是ADD R1, R0

这个时候

R0含有的是d的值

在最后我们产生最后一行代码

MOV R0, d

我们再将R0移动到d当中

这样我们就将上述的赋值语句

变为我们想要的生成的代码

那么这个语句序列当中

我们还需要考虑的一些

额外的问题是

前三行指令

其实是可以修改的

使执行的代价变得更低

比如说在修改之前

是我们之前写好的语句

那么修改之后

可以将它变为 MOV a, R0

这一行跟原来是一样的

第二行

我们用了寄存器 MOV R0, R1

降低了这条指令的代价

然后我们再可以用 SUB b, R0

SUB c, R1

同样的,我们可以得到想要的结果

接下来我们需要考虑

为变址和指针产生代码的情况

变址和指针运算的三地址代码的处理

和二元运算符的处理

是一样的

我们接下来讨论一下条件语句

对于条件语句来说

需要实现条件转移

那么有两种方式

首先我们可以根据寄存器的值

来讨论是否为如下

我们所需要的6个条件之一

这6个条件是

负、零、正、非负、非零、非正

我们可以用条件码来表示

我们想要的计算的结果

或者装入寄存器的值是负的、

是零、还是正的

比如说

有这样的一个语句

if x小于Y goto z

那么需要进行一个条件的判断

我们把x-y的值

存入到寄存器R当中

然后来判断R的值是否为负

如果为负的话,我们跳转到z

我们把它写出来

if x小于y goto z

对应的实现就是CMP x, y

也就是比较 x和y来做一个减法

那么如果它的值是小于0的,跳转到z

接下来对于x=y+w

if x小于0 goto z

我们得到它对应的语句序列是

MOV y, R0

我们将y移动到R0中

ADD w, R0

将w累加到R0之上

MOV R0, x

我们再把R0移动到x

然后我们来比较x的值

是否为0

如果小于0

我们跳转到z

这小节就到这

谢谢大家

Compilers Techniques课程列表:

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-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.2 Regular form

-2.3  Finite automata

--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 Syntax Analysis

-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.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--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.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--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 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--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

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

7.4 A Simple Code Generator笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。