当前位置：文档之家 › 第七章 中间代码生成(2)

第七章 中间代码生成(2)

  • 格式：ppt
  • 大小：566.00 KB
  • 文档页数：42

下载文档原格式

  / 42

合集下载

第七章语义分析和中间代码生成

第七章语义分析和中间代码生成

* id b uminus
id c
id b id c unimus 1 * 02 id b id c unimus 5 * 46 + 37 id a assign 9 8 ...
7.1.3 三地址代码
三地址代码是由下面一般形式的语句构成的序列: X:=y op z
其中，x、y、z为名字、常数或编译时产生的临时 变量（存放中间结果，对应于语法树的内部节点）；
• 通过对抽象语法树的不同形式的遍历可以形成不同形 式的缀式表达式
– 前序遍历：前缀式 – 中序遍历：中缀式 – 后序遍历：后缀式
+
+ *
*
4
6
5
4
6
产生赋值语句抽象语法树的属性文法
产生式
语义规则
S.nptr:=mknode('assign',mkleaf(id,id.place),E.nptr) S→id:=E E→E1+E2 E.nptr:=mknode('+',E1.nptr,E2.nptr)
7.1中间语言
中间语言的形式： 逆波兰表示：后缀式 图表示法：DAG 和AST 三地址代码:四元式、三元式、间接三元式
7.1.1 后缀式
后缀式表示法又称逆波兰表示法。这种方法是，把运算量（操 作数）写在前面，把算符写在后面（后缀）。
一个表达式的后缀式可以如下定义： （1）如果E是一个变量或常量，则E的后缀式是E自身。 （2）如果E是E1 op E2形式的表达式，这里op是任何二元操 作符，则E的后缀式为 E1’ E2’op,这里E1’ 和E2’分别为 E1和E2的后缀式。 （3）如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀 式。

第7章 语义分析与中间代码生成

第7章 语义分析与中间代码生成

(4) 无条件转移语句goto L，即下一个将被执 行的语句是标号为L的语句。 (5) 条件转移语句if x rop y goto L，其中rop为 关系运算符，如<、<=、==、!=、>、>=等。 若x和y满足关系rop就转去执行标号为L的语 句，否则继续按顺序执行本语句的下一条语 句。
(6) 过程调用语句par x和call p,n。源程序中的 过程调用语句p(x1, x2, …, xn)可用下列三地址 代码表示： par x1 par x2 par xn call p,n 其中，整数n为实参个数。 过程返回语句为return y，其中y为返回值， 可选。
{enter(, T.type, offset); offset := offset + T.width} {T.type := int; T.width := 4｝ {T.type := float; T.width := 8} {T.type := array(num.val, T(1).type); T.width := num.val * T(1).width} {T.type := pointer(T(1).type); T.width := 4}
2．三地址语句的种类 三地址语句非常类似于汇编代码，它可以 有符号标号和各种控制流语句。 常用的三地址语句： (1) x = y op z形式的赋值语句，其中op为二目 的算术运算符或逻辑运算符。 (2) x = op y形式的赋值语句，其中op为一目运 算符，如一目减uminus、逻辑否定not、移位 运算符以及类型转换符。 (3) x = y形式的复制语句，将y的值赋给x。
例如，赋值语句a = b * (c + d)的四元式代码： ① (+, c, d, t1) ② (*, b, t1, t2) ③ (=, t2, _, a) 约定：一元运算符一律使用arg1。此外，如果 op是一个算术或逻辑运算符，则result总是一 个新引进的临时变量，它用来存放运算结果。 结论：四元式出现的顺序与表达式计值的顺序 是一致的，四元式之间的联系是通过临时变量 实现的。四元式由于其表示更接近程序设计的 习惯而成为一种普遍采用的中间代码形式。

编译原理张晶版 第七章 语法制导翻译和中间代码生成

编译原理张晶版 第七章 语法制导翻译和中间代码生成

(1)s=s0
(2)s=s1 (3)s=ε
课程名称
第七章 语法制导翻译和中间代码生成（22）
输入输出对可由(,)表示，其中是输入句子形式而是输出句子形 式。
(S,S)开始用产生式s0s来扩展得到(0S,S0).
再用一次规则(1)，得到(00S,S00)。 再用规则(2)，就得到(001S,S100). 然后应用规则(3)并得到(001,100)。
L id
T.type=integer T.type:=real
L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)
课程名称
第七章 语法制导翻译和中间代码生成（17）
Real id1,id2,id3
D T.type=real real L.in= real L.in= real ， id3
E T T F F
T T1 * F F (E) digit
设表达式为3＊5+4，则语义动作打印数值19
. L
E.val=19 E.val=15
+
T.val=3 F.val=3 digit.lexval=3 F.val=5
*
F.val=4
digit.lexval=4 digit.lexval=5
课程名称
第七章 语法制导翻译和中间代码生成（23）
课程名称
第七章 语法制导翻译和中间代码生成（3）
属性文法 表达式文法 E—>T+T| T or T T—>n | b ET1 + T2 { T1.type = int T2.type= T1.type E.type :=int} E T1 or T2 { T1.type = bool T2.type= T1.type E.type :=bool} T n { T.type := int} T b { T.type := bool}

第七章语义分析与中间代码生成

第七章语义分析与中间代码生成
第七章 语义分析和中间代码产生
紧接在词法分析和语法分析之后，编译程序 要做的工作就是进行静态语义检查和翻译。 静态语义检查通常包括： 1）类型检查 2）控制流检查 3）一致性检查 4）相关名字检查 其它如名字的作用域分析等也都是静态语义 分析的工作。
1
虽然源程序可以直接翻译为目标语言代码，但是许 多编译程序却采用了独立于机器的、复杂性介于源 语言和机器语言之间的中间语言。这样的好处是： 1）便于进行与机器无关的代码优化工作； 2）使编译程序改变目标机更容易； 3）使编译程序的结构在逻辑上更为简单明确。以 中间语言为界面，编译前端和后端的接口更清晰。 静态语义检查和中间代码产生在编译程序中的地位 如图7.1 如图7.1
15
例如：赋值语句A:=-B*(C+D)的四元式表示。 A:=例如：赋值语句A:= B*(C+D)的四元式表示。 的四元式表示
OP ARG1 ARG2 (1) @ (2) + (3) * (4) := B C T1 T3 — D T2 — RESULT T1 T2 T3 A 注解 T1为临时变量 T2为临时变量 T3为临时变量 赋值运算
表达式的三元式： 表达式的三元式：w*x+(y+z) (1) *, w, x (2) +, y, z (3) +, (1), (2) 第三个三元 式中的操作数(1) 式中的操作数 (2)表示第 和第 表示第(1)和第 表示第 (2)条三元式的计 条三元式的计 算结果。 算结果。
E → E1 * E2
E.place := newtemp; E.code := E1.code || E2.code ||
gen(E.place':='E1.place'*'E2.plac

编译原理第七章中间代码生成汇编

编译原理第七章中间代码生成汇编
assign a + a assign + * uminus c b uminus
*
b
*
b
uminus
c
a= b*-c + b*-c
c abc uminus * bc numinus *+ assign
抽象语法树
• 构造赋值语句语法树的语法制导定义： 产生式
S→id = E E→E1 + E2 E→E1 * E2 E→- E1 E→(E1)
• param x1 • param x2 • …… • param x2 • call p, n n表示实参个数。return y中y为过程返回的一个值
– 形如x = y[i]及x[i] = y的索引赋值。
– 形如x = &y, x = *y和*x = y的地址和指针赋值。象形式。 • 这些语句可以以带有操作符和操作数域的记录 来实现。四元式、三元式及间接三元式是三种 这样的表示。
x = y op z
其中，x、y和z是名字，常量或编译器生成的临时变量 op代表任何操作符（定点运算符、浮点运算符、逻辑运算 符等）
• 像x+y*z这样的表达式要翻译为:
T1 = y * z
T2 = x + T1 其中T1 ，T2为编译时产生的临时变量。
三地址语句的类型
• 三地址语句类似于汇编语言代码。语句可以有 符号标号，而且存在各种控制流语句。
– 临时变量也要填入符号表中。
三元式
• 为了避免把临时变量填入符号表，可以通过计 算临时值语句的位置来引用该临时变量。 • 这样三地址代码的记录只需要三个域op, arg1 和arg。
• 对于单目运算符op, arg1和arg2只需用其一。

编译原理第7章-中间代码生成

编译原理第7章-中间代码生成

-16-
表达式代码生成的例子
College of Computer Science & Technology
class[5].age + *ptr.age
typedef struct { char name[30]; int age; float height; }person;
int x[10]; person class[10]; person *ptr;
(cSlaUsBs[I5,]5, 0,t4t5) (MULTI, t5, 33, t6) cla(sAsA[5D].aDg,eclasst,1t6, t4) (AADD , t4, 30, t1) *p(t*Arp.astsgrieg,ptt7tr2, _, t7) (AADD , t7, 30, t2)
-7-
四元式
• 表达式运算符 College of Computer Science & Technology
– ADDI, ADDF, SUBI, SUBF, MULTI, MULTF,
– DIVI, DIVF, MOD,
– AND, OR, EQ, NE, GT, GE, LT, LE
• I/O 操作
Compiler Construction Principles & Implementation Techniques
-12-
7.2 表达式的四元式代码
College of Computer Science & Technology
• 表达式的运算分量可以很复杂：
– 多维数组下标变量：A[i][j][k] – 结构体域名变量：st.address.city – 函数调用：f(x,y) – 指针引用：*(p+1) – ……

编译原理中间代码生成

编译原理中间代码生成在编译原理中，中间代码生成是编译器的重要阶段之一、在这个阶段，编译器将源代码转换成一种中间表示形式，这种中间表示形式通常比源代码抽象得多，同时又比目标代码具体得多。

中间代码既能够方便地进行优化，又能够方便地转换成目标代码。

为什么需要中间代码呢？其一，中间代码可以方便地进行编译器优化。

编译器优化是编译器的一个核心功能，它能够对中间代码进行优化，以产生更高效的目标代码。

在中间代码生成阶段，编译器可以根据源代码特性进行一些优化，例如常量折叠、公共子表达式消除、循环不变式移动等。

其二，中间代码可以方便地进行目标代码生成。

中间代码通常比较高级，比目标代码更具有表达力。

通过中间代码，编译器可以将源代码转换成与目标机器无关的形式，然后再根据目标机器的特性进行进一步的优化和转换，最终生成目标代码。

中间代码生成的过程通常可以分为以下几步：1.词法分析和语法分析：首先需要将源代码转换成抽象语法树。

这个过程涉及到词法分析和语法分析两个步骤。

词法分析将源代码划分成一个个的词法单元，例如标识符、关键字、运算符等等。

语法分析将词法单元组成树状结构，形成抽象语法树。

2.语义分析：在语义分析阶段，编译器会对抽象语法树进行静态语义检查，以确保源代码符合语言的语义规定。

同时，还会进行类型检查和类型推导等操作。

3.中间代码生成：在中间代码生成阶段，编译器会将抽象语法树转换成一种中间表示形式，例如三地址码、四元式、特定的中间代码形式等。

这种中间表示形式通常比较高级，能够方便进行编译器的优化和转换。

4.中间代码优化：中间代码生成的结果通常不是最优的，因为生成中间代码时考虑的主要是功能的正确性，并没有考虑性能的问题。

在中间代码生成之后，编译器会对中间代码进行各种优化，以产生更高效的代码。

例如常量折叠、循环优化、死代码删除等等。

5.中间代码转换：在完成了中间代码的优化之后，编译器还可以对中间代码进行进一步的转换。

这个转换的目的是将中间代码转换成更具体、更低级的形式，例如目标机器的汇编代码。

第07章 语义分析和中间代码生成(2)


中原工学院 计算机学院
类型转换：itr，rti
S → id := E S.code := E.code || {if id.type=E.type then
gen( id.place':='E.place ) else if id.type=real then gen(id.place’:=‘ itr( E.place) else gen(id.place’:=‘rti ( E.place)} E → E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || {E.type:=E1.type; if E1.type=E2.type then gen(E.place':='E1.place'+'E2.place) else{ if E1.type=real then
/* ‘34’ 为E22.place */
|| gen( ‘t1:=t2+t3’ ) || gen( ‘a:=t1’ ) /* E21.code和 E22.code 为空 */
中原工学院 计算机学院
表达式翻译中的其它问题
临时变量空间的统计 了解需求、及时释放 运算合法性检查 利用符号表保存的名字类型 类型自动转换 添加专用指令
中原工学院 计算机学院
赋值语句的翻译规则
S → id := E S.code := E.code || gen( id.place':='E.place )
E → E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ':=‘ E1.place '+‘ E2.place) E → E1 * E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place ':=‘ E1.place '*‘ E2.place)

第七章语义分析和中间代码生成

L {t := mktable (nil); push(t, tblprt); push(0, offset) }
7.3 赋 值 语 句
7.3.1 简单算术表达式及赋值语句 S id := E {p := lookup();
if p nil then emit ( p，‘:=’, E.place)
重写成 i w + (base low w)
7.3 赋 值 语 句
二维数组 • 列为主
A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3]
7.3 赋 值 语 句
二维数组 • 列为主
A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] • 行为主
• 如果E是变量或常数，那么E的后缀式就是E
本身。 • 如果E是形式为E1 opE2的表达式，那么E的后
缀式是E1 E2 op，其中E1和E2分别是E1和E2 的后缀式。 • 如果E是形式为(E1)的表达式，那么E1的后缀 表示也是E的后缀式。
7.1 中 间 语 言
• 后缀式表示法是波兰逻辑学家卢卡西维奇（ Lukasiewicz）发明的一种表示表达式的方法 因此又称逆波兰表示法。这种表示法是把运 算量（操作数）写在前面把算符写在后面（ 后缀）。
T real {T.type := real; T.width := 8 }
T array [ num ] of T1 {T.type := array (num.val, T1.type); T.width := num.val T1.width}
T T1 {T.type := pointer (T1.type); T.width := 4 }

第七章中间代码生成

第七章中间代码生成在第一章已经介绍，编译器的前端把源程序翻译成中间表示，后端从中间代码产生目标代码，与目标语言有关的细节尽可能限制在后端。

使用独立于机器的中间形式的好处是：1. 再目标（retargeting）比较容易。

把针对新机器的后端加到现成的前端上，可以得到另一种机器的编译器。

2. 独立于机器的代码优化器可用于这种中间表示。

第九章将介绍这种代码优化。

因此，虽然可以把源程序直接翻译并生成目标代码，但编译器一般都采用中间语言。

本章将用第四章的语法制导定义方法来说明程序设计语言的结构怎样被翻译成中间形式。

为简单起见，假定对源程序的分析和静态检查已经完成，如图7.1表示的那样。

本章大多数语法制导定义可以用第四章的技术在自下而上或自上而下的分析期间实现，所以，如果愿意的话，中间代码生成可以在分析阶段完成。

图7.1 中间代码生成器的位置7.1中间语言4.2节介绍的语法树是一种图形化的中间表示，本节再介绍几种常用的中间表示：后缀表示、其它图形表示和三地址代码。

本章主要使用三地址代码。

从程序设计语言的各种结构产生三地址代码的语义规则类似于产生语法树或后缀表示的那些规则。

7.1.1后缀表示表达式E的后缀表示可以如下递归定义：（1）如果E是变量或常数，那么E的后缀表示就是E本身。

（2）如果E是形式为E1 opE2的表达式，其中op是任意的二元算符，那么E的后缀表示是E1' E2'op，其中E1'和E2'分别是E1和E2的后缀表示。

（3）如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀表示。

后缀表示不需要括号，因为算符的位置及其运算对象的个数使得后缀表示仅有一种解释。

例如，(8 - 4) + 2 的后缀表示是8 4 -2 +，而8 - (4 + 2)的缀表示8 4 2 + -。

上面的定义很容易拓广到含一元算符的表达式。

后缀表示的最大优点是便于计算机处理表达式。

利用一个栈，自左向右扫描表达式的后缀表示。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(RETURN, _, _, E.Form)
函数调用语句
f(E1, …, En) 从符号表中获取f 的属性

– Level, params, type

生成中间代码
E1.code …… En.code 形实参结合
(VALACT, 实参.Form, offset, size) (VARACT, 实参.Form, offset, size) (call, f, true, t) (call, f, false, t)
复合变量的四元式生成
复合变量：下标变量 A[i][j], 域名变量 , 指针 变量 *p 复合变量的中间代码是计算复合变量地址的四元式

变量的语法: V id V1 V2 [E] V1 V2.id
地址: addr(V) = addr(id) addr(V1) = addr(V2)+(E-low+1)*Elesize addr(V1) = addr(V2)+offset(id)
7.4 原子语句的中间代码生成
赋值语句: V = Exp; I/O 语句

– Read(V); – Write(Exp);
Goto 语句 : Goto Label 标号语句: Label: Statement; 函数调用返回语句: Return Exp; 函数调用: F(Exp1, …, Expn)

id<Push(id)> <GenCode(*)> Ts <GenCode(+)> Es) <GenCode(*)> Ts Es b) <Push(id)> <GenCode(*)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es ) <GenCode(*)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es ) Ts <GenCode(+)> Es )<GenCode(*)> Ts Es ) <GenCode(+)> Es ) <GenCode(*)> Ts Es ) Es ) <GenCode(*)> Ts Es ) ) <GenCode(*)> Ts Es ) <GenCode(*)> Ts Es Ts Es Es
第七章 中间代码生成
7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题
7.3 表达式的中间代码生成
7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成
7.2 中间代码生成中的几个问题
1.
–
语义信息的获取和保存
–
目标代码阶段保留符号表，则可用标识符在符号表中的 地址 不保留符号表，则用FORM结构保存标识符的语义信息
产生一条中间代码子程序GenCode()
产生一条中间代码子程序GenCode() 调用该函数时，左右操作数已进语义栈Sem; 分别取出左右操作数； 检查类型是否相同，不同则进行转换，产生类型转 换四元式； 产生中间代码（ *, Sem[top-1], Sem[top],t） pop(2); //弹出左右分量 push(t) //压入结果t的类型和Form
top
R.typ, R.form L.typ, L.form
Sem
7.3 表达式的中间代码生成

表达式的中间代码就是依据原表达式的语 义产生出正确计算表达式值的四元式中间 代码（即将计算顺序体现出来）
– 表达式的运算分量可以是简单变量、复杂变
量和函数调用 – 表达式的运算符可以是算术运算符，关系运 算符，逻辑运算符等
–
变量及操作：

7.2 中间代码生成中的几个问题
3.
常用的语义子程序
申请临时单元 new_dir(t): 在临时变量区申请一个单元t，且t是直接 寻址 new_indir(t): t是间接寻址
存放中间代码子程序Generate(,left,right,result) 将一条四元式中间代码存放到中间代码区中
第七章 中间代码生成
7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题
7.3 表达式的中间代码生成
7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成
7.5 结构语句的中间代码生成

条件语句
– If 语句 – Switch 语句
int x[10]; (L, 0) person class[10]; (L, 10) person *ptr; (L, 340)
第七章 中间代码生成
7.1 几种常见的中间表示 7.2 中间代码中生成的几个问题
7.3 表达式的中间代码生成
7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成

E T Es P Ts Es id <Push(id)> Ts Es <Push(id)> Ts Es Ts Es *P<GenCode(*)>Ts Es P <GenCode(*)> Ts Es (E)<GenCode(*)> Ts Es E) <GenCode(*)> Ts Es T Es) <GenCode(*) Ts Es P Ts Es) <GenCode(*)> Ts Es C <Push(C)> Ts Es )<GenCode(*)> Ts Es <Push(C)> Ts Es )<GenCode(*)> Ts Es
首先给出简单算术表达式的中间代码生成 复合变量的中间代码生成

表达式的四元式
表达式E a *（3.5 + i *b） 假设a,b为实型变量，i为整型变量 E生成的四元式如下：

– (FLOAT, i, -, t1) – (MULTF, t1, b, t2)
– (ADDF, 3.5, t2, t3)


<Push(C)> Ts Es )<GenCode(*)> Ts Es +i*b) Ts Es) <GenCode(*)> Ts Es +i*b) Es )<GenCode(*)> Ts Es +i*b) + T <GenCode(+)> Es )<GenCode(*)> Ts Es + i*b) T<GenCode(+)> Es )<GenCode(*)> Ts Es i*b) PTs <GenCode(+)> Es) <GenCode(*)> Ts Es i*b) id <Push(id)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es i*b) <Push(id)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es *b) Ts <GenCode(+)> Es )<GenCode(*)> Ts Es *b) *P <GenCode(*)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es *b) P <GenCode(*)> Ts <GenCode(+)> Es )<GenCode(*)> Ts Es b)
V1 *V2
addr(V1) = content(addr(V2))
下标变量的四元式生成

一维下标变量 a[i]和多维下标变量 a[i][j][k]
Var A:array [L1..U1][L2..U2]…[Ln…Un] of T;(n>=1)
数组第1行的宽度是 D1=U1-L1+1; 数组第i行的宽度是 Di=Ui-Li+1； 设类型T所占单元数为，则数组A占单元数为 size(A) = D1*D2*…*Dn* 下标变量A[E1][E2]…[Ek]地址为： Addr(A) + ((E1-L1)*S1 + …(Ek-Lk)*Sk)*size(T) 其中 当 i =1时，s1 = 1，否则 si = Di+1*Di+2*…*Dn sn = 1
Exp.code
(READ, _, _, V.Form)
(WRITE, _, _, Exp.Form)
Goto语句和Label语句

Goto L

L: S
(LABEL, _, _, LL)
(JUMP, _, _, LL)
S.code
Return语句

Return E
E.code

Return
(RETURN, _, _, _ )
a*(3.5+i*b) a*(3.5+i*b) a*(3.5+i*b) a*(3.5+i*b) *(3.5+i*b) *(3.5+i*b) *(3.5+i*b) (3.5+i*b) (3.5+i*b) 3.5+i*b) 3.5+i*b) 3.5+i*b) 3.5+i*b) +i*b)