第六章 中间代码生成 主要内容 常见的中间代码结构 语法制导方法概论 四元式中间代码生成过程.

Presentation on theme: "第六章 中间代码生成 主要内容 常见的中间代码结构 语法制导方法概论 四元式中间代码生成过程."— Presentation transcript:

1 第六章 中间代码生成 主要内容 常见的中间代码结构 语法制导方法概论 四元式中间代码生成过程

2 中间代码:是一种复杂性介于源程序语言和目标语言之间一种语言,中间代码与具体机器无关。
C语言： f (x<y) x+=15 ; else x-=15; 用Pentium机器语言目标代码： ………………….. 四元式中间代码： (<,x,y,t1) (then,t1,-,-) (addi,x,15,t2) ; (:=,t2,-,x) (else,-,-,-) (subi,x,15,t3) ; (:=,t3,-,x) (ifend,-,-,-)

3 1. 生成中间代码的目的 便于优化 便于移植 让生成的目标代码效率更高 优化不等同于对代码的精简和算法的优化 编译前端：与目标机无关
编译后端：与目标机相关 1、便于优化，我们想让生成的目标程序的执行效率是最高的，应该在生成中间代码的时候对源程序进行一些优化。这些优化工作可以提高目标程序的效率。同学可能会想是不是我们在设计程序的时候可以设计比较优秀的程序结构和良好的代码使得生成的目标代码效率比较好，是不是就不需要在编译过程中进行优化了呢？ 其实不然。一种情形是程序设计者未必都是编程的高手，这样在他写的代码中有可能出现一些不是效率很高的情形，譬如说，我们写程序的时候会有一些不太注意的问题没有考虑到，同时有一些我们为了让计算机发挥它的计算优势，有一些中间结果我们没有算出来，比方说3.14*1.5我们一般不会把他的结果写在程序中，而是把这样一个结果写在这里。这样的计算如果在编译中把他计算出来，在生成目标程序就没有这样的计算，执行效率就会得到提高。 由于程序设计语言的一些限定条件，即使是程序设计者具有很强的程序设计能力，有些优化工作他也是不能做的，比方说多维下标变量地址计算过程，比方说a[i][j]和 a[i][k]，我们在计算他们的地址的时候都先要计算a[i]的地址然后再计算j k 的地址，实际上a[i]的计算过程实际上是重复计算了，这样的问题在程序设计语言中，程序员是没有办法解决的，所以在编译中对他们进行优化是很必要的。在前面词法、语法、语义分析完了以后，我们直接对他进行优化可以么？ 实际上是可以的，但是操作起来很麻烦，所以我们要把它变为一种中间的表示形式，然后基于这种中间的表示形式可能更方便一些，这是我们生成中间代码的第一个目的。 2、便于移植，一个编译程序从结构上来说我们可以把它分成是编译前端和编译后端两个组成部分，编译前端是指和目标机没有关联的部分，和目标机相关联的部分是编译后端。一个是有关一个是无关的。大家可以想象，同一个程序设计语言如果在不同的目标机上实现的话通常是需要构建不同的编译器，因为目标机不一样，生成的目标代码就不一样 ，那么怎么办呢？比方说我在某一种型号的机器上有一个编译器，又要在另一个型号的机器上生成编译器，我们需要把整个编译器都重新做么？实际上肯定是没必要的，因为有相当一部分程序是一样的，比方说词法、语法、语义，不管在什么样的目标机上执行他都是一样的，这些和目标机不相关的部分，在不同的目标机上实际上也是要做相同的工作，所以为了便于把一个编译器移植到另一个目标机，我们把编译前端的工作做的越多越好，因为编译前端的工作是不用改变的，而编译后端是需要和目标机相关的需要变化的。生成中间代码我们就可以把编译前端的工作做的非常的多。类似的工作比方说java语言的编译器，他是把java源程序，编译到中间一个语言上，在不同的目标机执行的时候映射到不同的目标语言，就可以执行了。这样的方法，对于我们处理源程序的翻译工作是非常有利的，因此一般的编译器都要做中间代码生成的工作，这就是我们做中间代码的目的。

4 前端 后端 前端1 后端1 L1 M1 M2 L2 前端2 M3 L3 前端3 M4 M5 目 标 代 码 生 成 中 间 优 化 语 义
分 析 法 词 程 序 源 前端1 后端1 L1 M1 M2 L2 前端2 M3 L3 前端3 M4 M5

5 前端 后端 前端1 后端1 L1 M1 后端2 M2 L2 后端3 M3 L3 后端4 M4 M5 后端5 目 标 代 码 生 成 中 间
优 化 语 义 分 析 法 词 程 序 源 前端1 后端1 L1 M1 后端2 M2 L2 后端3 M3 L3 后端4 M4 M5 后端5

6 2 常用的中间代码结构 后缀式----逆波兰式 图结构中间代码 三地址中间代码 特别是表达式的内部表示 抽象语法树 有向无环图DAG 三元式
2　常用的中间代码结构 后缀式----逆波兰式 特别是表达式的内部表示 图结构中间代码 抽象语法树 有向无环图DAG 三地址中间代码 三元式 四元式

7 2.1 后缀式(逆波兰式 ) 将运算对象写在前面，把运算符写在后面，因而也称后缀式。 a+b ab+ a+b*c abc* +
程序设计语言中的表示 逆波兰表示 a+b ab+ a+b*c abc* + (a+b)*c ab+c * 逆波兰式的特点: 逆波兰式中的变量的次序与中缀式中的变量的次序完全一致。 逆波兰式中无括号。 逆波兰式中的运算符已按计算顺序排列。

8 后缀式的计算机处理 后缀式的最大优点是易于计算机处理
处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。  例：表达式－b＋c*d的后缀式 b-cd*+的计值过程 b t1 d c t1 t2 t1 t3 t1= - b t2= c*d t3= t1+t2

9 2.2 抽象语法树 抽象语法树AGT（Abstract Grammar Tree）可以显示地表示源程序的结构，是常用的一种标准中间代码形式。它的应用由开始的表达式已经推广到了整个程序。 例如： c := a * b + a *b := c + * * a b a b

10 2.3 三地址中间代码 所谓三地址是指操作符的两个运算分量及其该操作的运算结果的抽象地址。
2.3 三地址中间代码 所谓三地址是指操作符的两个运算分量及其该操作的运算结果的抽象地址。 (op，operand1，operand2，result) 表示result:=operand1 op operand2 最常见的三地址中间代码有三元式和四元式两种。

11 例如：语句 a := b * c + b / d 三元式 ： 编号 (op，ARG1，ARG2） (1) ( * , b , c ) (2) ( / , b , d ) (3) ( + , (1) , (2)) (4) ( := , (3) , a ) 四元式: (op，ARG1，ARG2，RESULT） ( * , b , c , t1 ) ( / , b , d , t2 ) ( + , t1 , t2 , t3 ) ( := , t3 ,-, a ) 注： ARG1，ARG2 ， RESULT为操作分量和运算结果的抽象地址表示，应包含相应语义信息。

12 一般的四元式操作符应包括以下几类： 1．算术、逻辑、关系运算符 ADDI、ADDF、SUBI、SUBF、MULTI、
MULTF、 DIVI、DIVF、MOD、AND、 OR、EQ、NE、GT、GE、LT、LE 2．I/O操作 ( READI，─， ─，id )…………整数输入 ( READF ，─，─，id )…………实数输入 ( WRITE，─，─ ，id )…………输出id

13 3．类型转换 ( FLOAT，id1， ─， id2 ) …id2 := float ( id1 ) 4．赋值 ( ASSIG ，id1，-， id2 ) …id2 := id1 5．地址加 ( AADD ，id1，id2， id3 ) …addr(id3 ):= addr ( id1 ) + id2

14 6．标号定义 ( LABEL，─，─，label )….定义标号label 7．条件/无条件转移 ( JMP，─，─ ，label )…转向标号label ( JMP0，id，─ ，label ) …若id＝0，则转label ( JMP1，id，─，label ) …若id＝1，则转label

15 8．过程调用 (ENTRY，Label，Size，Level ) ………子程序入口 (CALL，f，─，Result ) ………过程或函数调用 9．传送参数 VARACT VALACT FUNACT PROACT

16 3 语法制导方法概论 什么是语法制导方法：语法制导方法就是基于文法结构，在每个产生式的右部增加语义动作（或语义子程序），在语法分析过程中，随着分析的步步进展，如果遇到文法符号则做语法分析；如果遇到语义动作，就完成对应的语义处理。把这种在语法分析的同时进行语义处理的办法称为语法制导方法。 语法制导方法：基于文法结构，在每个产生式的右部增加语义动作，在语法分析过程中，如遇语义动作，就完成对应的语义处理，完成语义分析、中间代码生成和目标代码生成部分。

17 语法制导方法的组成：语法制导方法包括两个部分: 抽象描述部分：即带有动作符的文法描述，称为动作方法；
实现部分：语法分析的同时能够处理语义动作的驱动程序。 例如：有动作语义文法G 　G: S→ #Init# AB A → aA│ b #Add# B → b #Add# B│c #Out_Val# 各动作符对应的语义子程序如下： Init m = 0 Out_Val if （m！= 0） { printf (“%d”, m ); m = 0; } Add m++ ;

18 语法制导方法的种类：语法制导方法依赖于具体的语法分析方法，因此可以分为自顶向下语法制导方法和自底向上语法制导方法。自顶向下语法制导方法中通常采用LL(1)分析方法为基础，而自底向上语法制导方法中通常以LR(1)分析方法为基础。

19 LL(1)语法制导方法的实例 设有如下LL(1)文法： G: S → A B A → a A │ b B → b B │ c 要求：应用语法制导翻译方法完成如下任务： 对输入文法 G 的任意句子 L ，输出 L 中 b 串的长度。如串 abbbc 是 G 的句子，则该 处理器将输出3。

20 G的原始LL(1)分析表 a b c # S A B G: S → AB A → aA │b B → bB │c S → A B

21 G 的动作文法如下： G: S→ #Init# AB A → aA│ b #Add# B → b #Add# B│c #Out_Val# 各动作符对应的语义子程序如下： Init m = 0 Out_Val if （m！= 0） { printf (“%d”, m ); m = 0; } Add m++ ;

22 G的带动作符的LL(1)分析表 a b c # S A B G[S]: S→ #init# A B A → a A│ b #Add#
B → b #Add# B│c#Out_Val# G的带动作符的LL(1)分析表 a b c # S S → #init# A B S → #init## A B A A → a A A → b #Add# B B → b #Add# B B → c#Out_Val##

23 语法制导的实现过程（1） 替换 替换 匹配Match 对给定的终极符串abbbc，分析过程： S# abbbc # 替换
例 G[s] : [1] S→ #init# A B [2] A → a A [3] A → b #Add# [4] B → b#Add# B [5] B → c#Out_Val# {a,b} {b} {c} {a} 对给定的终极符串abbbc，分析过程： S# abbbc # 替换 #init# A B # abbbc # # Init # m=0 替换 A B # abbbc # aA B # abbbc # 匹配Match 替换 A B # bbbc # b #Add#B # bbbc # 匹配Match #Add# B # bbc # #Add# m=1 B # bbc #

24 语法制导的实现过程（2） 替换 匹配Match 替换 匹配Match 匹配Match 对给定的终极符串abbbc，分析过程(续）： B #
例 G[s] : [1] S→ #init# A B [2] A → a A [3] A → b#Add# [4] B → b#Add#B [5] B → c#Out_Val# {a,b} {b} {c} {a} 对给定的终极符串abbbc，分析过程(续）： B # 替换 bbc # b #Add# B # bbc # 匹配Match #Add# B # bc # #Add# m=2 B # bc # b#Add# B # 替换 匹配Match #Add#B # c # #Add# m=3 c # Out_Val # # c # 匹配Match # Out_Val # # # #Out_Val# 输出3 # # Success

25 5 中间代码生成中的几个问题 （1）语义信息的提取与保存： 四元式: (算符op，ARG1，ARG2，运算结果RESULT）
如：3.5+i (ADDF,3.5,(i.level,i.off,dir),(-1,t3,dir)) 语义信息的两种表示方式： 指向相应符号表的指针 把对应分量的语义信息放在此处 下面我们要考虑一下进行中间代码生成的时候应该注意的问题，这里有几个情况先和大家做一下交代，1、语义信息的提取，我们现在写的四元式都是+xy t1，大家读起来可能比较方便，但是实际上这个x y存的并不是x和y的符号，而是一个指针，指向xy在符号表中的位置，一个变量标识符的语义信息包括三个部分：种类信息 类型信息 抽象地址，我们要进行xy的计算，这些语义信息实际上是应该能够提到的，你让他俩进行计算这里涉及到一些类型检查类型转换等等操作，如果这些语义信息提取不出来的话，这个事儿就没法做了， 一种方式是把他们的语义信息都放到四元式里，这样的方式对于四元式的管理和组织，还有信息的冗余都会产生很大的影响，比方说x在程序中出现很多次，你要是把x的语义信息都存在四元式中就会产生很多的冗余信息， 所以最好的一种方式就是x y都是一个指针，指向对应的位置，需要提取信息的时候我们就可以通过指针到符号表中把信息提取出来，为了方便，同学看起来也方便，以后在我们的课堂中，我们还是用xy来表示，但是大家一定要清楚这里实际上是一个指针，通过符号表可以把它们的语义信息提取出来。

26 四元式中操作分量或运算结果的地址表示ARG结构：
form分为三大类： 标号类LabelForm：语义信息Label是相应的标号值，包括过程 ⁄ 函数体的入口标号； 数值类ValueForm：语义信息Value就是该数据值； 地址类AddrForm：语义信息Addr由四部分组成：变量名、层数、偏移和访问方式(分为直接访问方式和间接访问方式)。 ARG结构：

27 （2）语义栈Sem及其操作 中间代码生成尤其是变量和表达式的处理过程中要用到语义栈Sem ，该栈主要存放运算分量和运算结果的类型和地址表示 。 SemElem=record typ:ElemType ; {运算分量或结果的类型} FORM:ARG_Record {地址表示分类语义信息} end; SemStack=array[1..Max] of SemElem; var Sem:SemStack ; top:integer ; 对语义栈Sem的操作有 push(x):将标识符x的类型和Form压入Sem栈；pop(n):从Sem的栈顶删除n个元素。

28 （3） 常用的语义子程序 申请临时单元 new_dir(t): 申请一个临时变量t，且t是直接寻址；
new_indir(t):申请一个临时变量t，且t是间接寻址。 GenCode(ω) : ω为操作码，该子程序功能是产生一条四元式中间代码。此时左、右运算分量语义信息已经在语义栈Sem的次栈顶和栈顶。

29 6 表达式的中间代码生成 简单表达式的LL(1)文法 （1）E →T Es （2）Es → （3）Es →+ T Es
（5）T → P Ts （6）Ts→ （7）Ts →* P Ts （8）Ts →/ P Ts （9）P →C （10）P →id （11）P →( E )

30 （3）Es →+T#GenCode(+)#Es （4）Es →-T#GenCode(-)#Es （5）T → PTs （6）Ts→
简单表达式的带有动作符的LL(1)文法 （1）E →TEs （2）Es → （3）Es →+T#GenCode(+)#Es （4）Es →-T#GenCode(-)#Es （5）T → PTs （6）Ts→ （7）Ts →*P#GenCode(*)#Ts （8）Ts →/P#GenCode(/)#Ts （9）P →C#Push(C)# （10）P →id#Push(id)# （11）P →(E) 当遇到常量C和简单变量id时，把它们的语义信息压入语义栈； 当处理完一个运算符（+，-，*，/）的右分量时，该运算符的左、右运算分量已经分别存放在语义栈 Sem 的次栈顶和栈顶的位置，因此可以生成相应的运算符的四元式，并把运算结果的语义信息压入语义栈。

31 简单表达式的LL(1)分析表 C id ( ) + - * / # E 1 Es 2 3 4 T 5 Ts 6 7 8 P 9 10 11
产生式 Predict集 (1 ) E → T Es C, id , ( （2）Es →  #, ) （3）Es → + T Es ＋ （4）Es → - T Es － （5）T → P Ts （6）Ts→ #, ),+,- （7）Ts → * P Ts ＊ （8）Ts → / P Ts ／ （9）P → C Ｃ （10）P → id Id (11）P → ( E ) (

32 # EsT x + y * z # LL [ T ,id ] = [5]
# E x + y * z # LL[ E ,id ] = [1] # EsT x + y * z # LL [ T ,id ] = [5] # EsTs P x + y * z # LL [ P ,id ] = [10] # EsTs #Push ( id )# id x + y * z # Match # EsTs #Push ( id )# y * z # #Push ( id )# # EsTs y * z # （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top Top intptr (x,level,off, dir) 语义栈Sem

33 # EsTs + y * z # LL [ Ts,+ ] = [6] #Es + y * z # LL [ Es,+] = [3]
表达式 x + y * z 的中间代码生成过程(2) 分析栈S 输入流T 动作 # EsTs y * z # LL [ Ts,+ ] = [6] #Es y * z # LL [ Es,+] = [3] # Es #GenCode ( + )# T y * z # Match # Es #GenCode ( + )# T y * z # LL [ T,id ] =[5] # Es #GenCode ( + ) #TsP y * z # LL [ P,id ] = [10] # Es #GenCode ( + )# Ts#Push ( id )# id y * z # （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (x.level, x.off, dir) 语义栈Sem

34 表达式 x + y * z 的中间代码生成过程(3) 分析栈S 输入流T 动作
# Es# GenCode (+) # Ts # Push (id) # id y * z # Match # Es# GenCode (+) # Ts # Push (id) # * z # # Push (id) # # Es # GenCode (+) # Ts * z # （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (y,level, off, dir) Top intptr (x.level, x.off, dir) 分析表 语义栈Sem

35 表达式 x + y * z 的中间代码生成过程(4) 分析栈S 输入流T 动作
# Es # GenCode (+ )# Ts * z # LL [ Ts,* ] = [7] # Es # GenCode (+) # Ts # GenCode (*) # P* * z # Match # Es # GenCode (+) # Ts # GenCode (*) # P z # （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (y.level, y.off, dir) intptr (x.level, x.off, dir) 语义栈Sem

36 # Es # GenCode (+) # Ts # GenCode (*) # # Push (id) # #
表达式 x + y * z 的中间代码生成过程(5) 分析栈S 输入流T 动作 # Es # GenCode (+) # Ts # GenCode (*) # P z # LL[P,id] = [10] # Es # GenCode (+) # Ts # GenCode (*) # # Push ( id ) # id z # Match # Es # GenCode (+) # Ts # GenCode (*) # # Push (id) # # （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (y.level, y.off, dir) intptr (x.level, x.off, dir) 语义栈Sem

37 # Es # GenCode (+) # Ts # GenCode (*) # # #GenCode (*)#
表达式 x + y * z 的中间代码生成过程(6) 分析栈S 输入流T 动作 # Es # GenCode (+) # Ts # GenCode (*) # # Push (id) # # #Push (id)# # Es # GenCode (+) # Ts # GenCode (*) # # #GenCode (*)# # Es # GenCode (+) # Ts # (MULTI, (y,level, off, dir), (z,level, off, dir), (-1,-1, t1, dir)) （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (z, level, off, dir) Top intptr intptr (y,level,off, dir) (-1,-1, t1, dir) 分析表 intptr (x,level, off, dir) 语义栈Sem

38 # Es # GenCode (+) # Ts # LL [ Ts,# ] = [6]
表达式 x + y * z 的中间代码生成过程(7) 分析栈S 输入流T 动作 # Es # GenCode (+) # Ts # LL [ Ts,# ] = [6] # Es # GenCode (+) # # #GenCode (+)# # Es # LL [ Es,# ] = [2] # # Success (MULTI, y ,z, t1) (ADDI, x, t1. t2) (MULTI, (y,level,off, dir), (z,level, off, dir), (-1,-1, t1, dir)) (ADDI, (x,level,off, dir), (-1,-1, t1, dir) , (-1, -1,t2, dir)) （1）E → T Es （2）Es → （3）Es → + T # GenCode ( + ) # Es （4）Es → - T # GenCode ( - ) # Es （5）T → P Ts （6）Ts→ （7）Ts → * P # GenCode ( * ) # Ts （8）Ts → / P # GenCode ( / ) # Ts （9）P → C # Push ( C ) # （10）P → id # Push ( id ) # （11）P → ( E ) Top intptr (-1,-1, t1, dir) Top intptr intptr (-1,1-, t2, dir) (x, level, off,dir) 语义栈Sem

39 例：将下列表达式翻译成四元式序列。 X*2+A*(i+1)/(j+1) 其中i和j为整型变量，其它为实型变量。 (FLOAT, 2, _ , t1) (MULTF, X , t1, t2) (ADDI, i, 1, t3) (FLOAT, t3, _ , t4) (MULTF,A, t4, t5) (ADDI, j, 1, t6) (FLOAT, t6, _ , t7) (DIVF,t5, t7, t8) (ADDF, t2, t8, t9)