编译原理简明教程（第3版）-课件 第7、8章 语义分析及中间代码的生成、代码优化

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造22024/11/63学习目标语义分析的概念语法制导翻译常见语法成分的表示中间代码语言7语义分析及中间代码的生成重点：语义分析的概念、常见的中间语言形式难点：常见语法成分的表示

目录7.1语义分析概述7.2中间语言代码7.3语法制导翻译7.4本章小结47.1.1语义分析的概念5语义分析：分析语法结构的含义，将其表示成中间语言或生成目标指令。语义形式化(或形式语义学)：是个专门的研究课题，如操作语义学、公理语义学、指称语义学等。不论哪种方法，其本身的符号系统比较繁杂，其描述文本不易读，因此都不能成为标准的形式语义系统。7.1.1语义分析的概念6主要指程序中所用标识符及与其相关的数据对象的含义如if语句、for循环等结构；由语言来定义。7.1.1语义分析的概念7语义分析的基本任务：类型的确定类型的检查确认含义其他语义检查数据对象的数据类型对运算及运算量的类型检查确认控制结构的含义不允许体外到体内等7.1.1语义分析的概念控制结构的含义有两种确定形式：形式化：如E→E+T|E-T|T

先“*，/”后“+，-”T→T*F|T/F|F左结合……p→(E)|i非形式：如赋值语句含义，非形式化的规定

V：=e

87.1.2属性文法技术

目前许多编译程序采用语法制导翻译的方法。

不是一种形式化系统，但比较接近形式化。以语法分析为主导的语义处理，即在语法分析的过程中嵌入语义处理程序，生成中间代码或目标代码。97.1.2属性文法技术1.增量式文法文法中加入语义动作符号。一般形式：A

(α|{f（…）；})*

α∈V*语义动作

作用：在语法分析时，遇到带有语义动作的花括号即执行语义动作，执行完后再进行下一步分析。10为了实现语法制导翻译，对文法中终结符号和非终结符号引进一些属性，例如，变量的数据类型、表达式的值以及存储器中变量的地址等。以描述相应语言结构的语义值。7.1.2属性文法技术例：表达式文法G[E]：

117.1.2属性文法技术

对于表达式“12-a/b”，语法树如下：

E

TE’FT’-T

E’

12

ε

FT’ε

a

/

F

T’

b

ε127.1.2属性文法技术

对于表达式“12-a/b”，带有语义动作的语法树如下：

E

TE’FT’-T{writecode(‘-’)}E’

12{writecode(‘12’)}εFT’

ε

a{writecode(‘a’)}/F{writecode(‘/’)}T’

b{writecode(‘b’)}

ε

13执行相应的子程序后打印出逆波兰式12ab/-7.1.2属性文法技术2.属性文法（1）文法的属性:

指与文法符号相关信息,如它的类型、值、代码序列、符号表内容等。

继承属性：用于“自上而下”传递信息（非终结符可有）

综合属性：用于“自下而上”传递信息（VT或VN）

（2）属性文法：

指在语言的文法中增加了属性的文法。

记号N.t表示与非终结符N相联的属性t

属性有助于更详细地指定文法中的代码生成动作。147.1.2属性文法技术例：G[E]属性文法：157.2中间语言代码采用中间语言的优点：有利于重定目标,即一种中间表示可以生成不同的目标语言。有利于提高目标代码的质量，因为可对中间语言进行与机器无关的优化。

常见的中间语言有：抽象语法树、逆波兰式、四元式、三元式。167.2.1抽象语法树抽象语法树：经变换后的语法树

(去掉一些对翻译不必要的信息)。

叶结点：表示运算对象，如常量或变量。

其它结点：表示运算符。

在语法规则中有些符号起标点符号或解释的作用。17如：x:=a-b*c

语法树和抽象语法树如下：

SV:=ExE-EaE*Ebc抽象语法树的特点：结构紧凑、容易构造、结点数少的图形表示。assign(:=)x-a*bc7.2.1抽象语法树187.2.2逆波兰表示（后缀式）例：a+b*cabc*+(a+b)*cab+c*a+b*c/(d-e)abc*de-/++a/*-bcde抽象语法树逆波兰式是抽象语法树的线性表示。即：后序遍历抽象语法树便得到逆波兰式19

约定几个符号：

（1）BL表示转向某标号处

（2）BT表示条件为真转

（3）BF表示条件为假转

（4）BR表示无条件转7.2.2逆波兰表示（后缀式）201.赋值语句的逆波兰式<左部>:=<表达式><左部><表达式>:=例:x:=a+b*cx:=a*b-c/dxabc*+:=xab*cd/-:=7.2.2逆波兰表示（后缀式）217.2.2逆波兰表示（后缀式）2.GOTO语句的逆波兰式GOTO<语句标号><语句标号>BL例:GOTO1010BL227.2.2逆波兰表示（后缀式）3.条件语句的逆波兰表示IF(e)THENS1ELSES2逆波兰式:<e的逆波兰式><顺序号1>BF<S1的逆波兰式><顺序号2>BR<S2的逆波兰式>237.2.2逆波兰表示（后缀式）例:IFm<nTHENk:=i*j+2ELSEk:=i*j-2(1)mn<(4)15BF(6)kij*2+:=(13)22BR(15)kij*2-:=(22)或:mn<15BFkij*222BRkij*2-:=247.2.2逆波兰表示（后缀式）例：if(a<b)thenx:=a+belsex:=a-b(1)ab<(4)13BF(6)xab+:=(11)18BR(13)xab-:=(18)或:ab<13BFxab+:=18BRxab-:=257.2.2逆波兰表示（后缀式）4.循环语句的逆波兰式Fori:=mTonDosfor(i=m;i<=n;i++){s}首先展开，i:=m;10:IFi<=nTHENBEGINS;i:=i+1;GOTO10;END267.2.2逆波兰表示（后缀式）例：FORi=1TO100DOs:=s+i展开

i:=1;10:IFi<=100THEN

BEGINs:=s+i;i:=i+1;GOTO10END

(1)i1:=(4)10:(6)i100<=23BF(11)ssi+:=(16)ii1+:=(21)10BL(23)277.2.3四元式1.四元式

(运算符,运算量1,运算量2,中间结果)例:a*b+c*d(*,a,b,T1)(*,c,d,T2)(+,T1,T2,T3)对于单目运算符⊕,⊖如+a，-a（⊕，a，_，T）（⊖，a，_，T）287.2.3四元式2.表达式和赋值语句的四元式例:(1)a+b*c/d(*,b,c,T1)(/,T1,d,T2)(+,a,T2,T3)

(2)-b*(c+d)(⊖,b,_,T1)

(+,c,d,T2)(*,T1,T2,T3)

(3)x:=-b*(c+d)(⊖,b,_,T1)(+,c,d,T2)(*,T1,T2,T3)(:=,T3,_,x)297.2.3四元式3.转向语句和条件语句的四元式(BR,A,_,_)无条件转到序号如A处(BT,A,B,_)B为真时转到A处(BF,A,B,_)B为假时转到A处307.2.3四元式例:IFa>bTHENmax:=aELSEmax:=b

四元式(1)(>,a,b,T1)(2)(BF,(5),T1,_)(3)(:=,a,_,max)(4)(BR,(6),_,_)(5)(:=,b,_,max)(6)()317.2.3四元式4.

循环语句的四元式FORi:=1TO100DOs:=s+i首先展开

四元式:(1)(:=,1,_,i)

i:=1

(2)(<=,i,100,T1)

10:IFi<=100THEN

(3)(BF,(7),T1,_)

BEGIN

(4)(+,s,i,s)

s:=s+i;

(5)(+,i,1,i)i:=

i+1;

(6)(BR,(2),_,_)GOTO10;

(7)END

327.2.4三元式1.三元式

(运算符,运算量1,运算量2)例:(a+b)*c(1)(+,a,b)(2)(*,(1),c)337.2.4三元式2.表达式和赋值语句的三元式例:a*(b-c)/d+e(1)(-,b,c)(2)(*,a,(1))(3)(/,(2),d)(4)(+,(3),e)X:=a*(b-c)/d+e(5)(:=,(4),x)a+b*(c-d)-e/f(1)(-,c,d)(2)(*,b,(1))(3)(+,a,(2))(4)(/,e,f)(5)(-,(3),(4))347.2.4三元式3.转向语句和条件语句的三元式IFa<bTHENx:=a+bELSEx:=a-b(1)(<,a,b)(2)(BF,(6),(1))(3)(+,a,b)(4)(:=,(3),x)(5)(BR,(8),_)(6)(-,a,b)(7)(:=,(6),x)(8)357.2.4三元式4.循环语句的三元式FORi:=1TO100DOsum:=sum+i首先展开：三元式：i:=1

(1)(:=,1,i)10:IFi<=100THEN(2)(<=,i,100)BEGIN

(3)(BF,(9),(2))sum:=sum+i;(4)(+,sum,i)i:=i+1;(5)(:=,(4),sum)GOTO10(6)(+,i,1)END(7)(:=,(6),i)(8)(BR,(2),_)(9)367.2.4三元式三元式的优缺点优点无需临时变量占用空间少缺点没有保存运算结果的属性不利于修改、优化377.3语法制导翻译语法制导翻译，直观上说就是为每个文法规则确定相应的语义，编写相应的翻译程序。7.3.1表达式的翻译387.3.4控制语句的翻译7.3.2说明语句的翻译7.3.3赋值语句的翻译7.3.1表达式翻译表达式是语言中最基本的语法成分表达式是源程序中出现频率很高的语法成分391.语法规则与代码形式

7.3.1表达式翻译40(1).算数表达式的逆波兰表示的语法制导翻译

语法规则E→E+T

E→E−TE→TT→T*FT→T/FT→FF→(E)

F→i语义子程序print(+)print(-)空

print(*)print(/)空空

print(id7.3.1表达式翻译41(2).算数表达式到四元式的语法制导翻译表达式文法：E

→E+T|E*T|−E

|(E)|i的翻译算法可由下面的语义动作予以描述：语法规则E→E

(

1)+E

(2)E→E

(

1)*E(2)

E→−E(

1)E→

(E(

1))语义动作{E.place:=Newtemp;gen(+,E(1).place,E(2).place,E.place)}{E.place:=Newtemp;gen(*,E(1).place,E(2).place,E.place)}{E.place:=Newtemp;gen(Θ,E(1).place,_,E.place)}{E.place:=E(1).place}{E.place:=entry(i)}7.3.2说明语句的翻译421、变量说明的翻译程序设计语言中最简单的说明语句是用一个基本字来定义一串名字的某种性质。Pascal语言中，变量说明部分冠以保留字VAR

作为标志，例如：VARm,n:integer;x,y:real;a:ARRAY[1..100]OFreal;7.3.2说明语句的翻译432、过程或函数说明的翻译

过程和函数说明又可以包含说明部分和语句部分，因此过程和函数是分程序，且可以嵌套。过程说明和函数说明的语法规则为:Pf→P|FP→Procedure

id(xy);

BLOF→functionid(xy):fnamet;BLOBLO→LB

CON

TP

VA

Pfs

begin

StatendPfs→Pf|PfsPfStat→S|Stat;S7.3.2说明语句的翻译44其四元式为(1)(proc,p,L1,k1)(2)(func,f,L2,k2)(3)(+,i,j,T1)(4)(/,T1,2,T2)(5)(:=,T2,_,f)(6)(funend,_,_,_)(7)(/,x2,2,T3)(8)(+,num,T3,T4)(9)(:=,T4,_,X1)(10)(*,m,x1,T5)(11)(:=,T5,_,a1)(12)(proend,_,_,_)过程说明：Procedure

p(varx1:real;x2:real);const

num=100;var

a1:real;m:integer;function

f(i,j:ineger):integer;beginf:=(i+j)/2end;beginx1:=num+x2/2；a1:=m*x1end;7.3.2说明语句的翻译45将前述过程和函数说明的语法制导翻译改写如下：Pf→P|FP→Pidxy);BLOF→Fid

xy);fnamet;BLOPid→procedure

id(Fid→function

id(Pfs→Pf|PfsPfBLO→LB

CON

TP

VA

Pfs

begin

Statend7.3.2说明语句的翻译46从而有与语法规则相应的语义子程序如下：(1)pf→p{}/*空*/(2)pf→f

{}/*空*/(3)p→pid

xy);BLO{gen(proend,_,_,_)(4)F→Fid

xy);fnamet;BLO{gen(funend,_,_,_)}(5)Pid→Procedure

id(

{gen(proc,adr(id),L,k)(6)Fid→function

id(

{gen

(func,adr(id),L,k,)}(7)Pfs→pf{}/*空*/(8)Pfs→Pfs

Pf7.3.3

赋值语句的翻译471、赋值语句的语法规则S→V:=E2、赋值语句的语义

赋值语句的语义可解释为把右部表达式E

的值赋给左部变量V。7.3.3

赋值语句的翻译483、语法制导翻译技术其引进的四元式生成子程序表示形式为：Procedure

gen(w,c,d,e);beginP[n]:=(w,c,d,e);n:=n+1end；赋值语句的语法规则对应的语义子程序为(1)S→Assig

E{gen(:=,S[i-2],_,s[i-1])}(2)Assig→i:={S[i]:=adr(id),i:=i+1}7.3.4

控制语句的翻译49

在源程序中，控制语句用于实现程序流程的控制，一般程序流程控制分为三种基本结构：顺序结构，一般用复合语句实现。选择结构，用if和case等语句实现。循环结构，用for、while、repeat

等语句实现。

7.3.4

控制语句的翻译501．三种基本控制结构的翻译:三种结构可用如下方法描述：(1)S→ifEthenS(2)|if

E

thenSelseS(3)|whileEdo

S(4)|begin

L

end(5)|A(6)L→L;S(7)|S7.3.4

控制语句的翻译51对于下面嵌套的if语句：

在E1和E2为真的情况下执行S1，执行完S1之后的那条无条件转移指令不仅应跳过S2代码，还应跳过S3代码。这也就是说，转移目标位置的确定和语句所处的环境是密切相关的。7.3.4

控制语句的翻译522.语句标号和转移语句的翻译:大多数程序设计语言中的转移语句是通过标号和goto语句实现的，语句标号用于标识一个语句，一个带标号语句的形式是L:S带标号语句的语法规则为Ls→L:S转向语句的语法规则为S→gotoL为便于语法制导翻译，带标号语句的语法规则改写为LS→Label

SLabel→L:7.3.4

控制语句的翻译53转向语句和带标号语句的语法规则对应的语义子程序如下：S→gotoL{gen(goto,_,_,L)}Ls→Label

S{空}Label→L:{gen(label,_,_,L)}547.4本章小结1．语义分析就是分析语法结构含义，语义分析部分以语法分析部分的输出作为输入2．四种中间语言代码：抽象语法树、逆波兰表示、四元式和三元式3．语法制导翻译的概念及其翻译的主要思想4．表达式是在源程序中出现频率较高的语法成分5．变量说明的翻译，过程或函数说明的语法制导翻译6．赋值语句、控制语句的翻译55总结

本章我们学习了语义分析的基本概念，属性文法技术及常用的中间代码（抽象语法树、逆波兰式、四元式、三元式）等内容。下一章将学习代码优化。THANKS56THANKS新工科建设·计算机类系列教材

免费提供编译原理576目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造582024/11/659学习目标代码优化的概念循环优化局部优化代码优化的分类8代码优化重点：代码优化的定义和代码优化的分类难点：局部优化、循环优化

目录8.1代码优化概述8.2局部优化8.3循环优化8.4本章小结60定义

所谓优化，实质上是对代码进行等价变换，使得变换后的代码具有更高的效率，包括时间效率和空间效率。目的

获得性能较好的代码，即要尽量缩小存储空间，还要尽量提高运行速度。

618.1代码优化概述8.1.1代码优化的定义优化可在编译的不同阶段进行：源代码设计阶段--程序员选择好的算法和语句语义分析阶段--如何生成高质量的中间代码中间代码--采用优化技术目标代码--有效利用寄存器、指令、处理机

62638.1.2代码优化的分类1、与机器的相关性

与机器有关的优化：寄存器的优化、多处理机的优化、特殊指令的优化、无用代码的消除。与机器无关的优化：基本块的优化、循环优化。2、优化范围

局部优化：基本程序块上进行的优化

全局优化：全局程序范围内的优化648.1.2代码优化的分类1、局部优化：基本程序块上进行的优化

基本程序块---只有一个入口、一个出口的基本程序块

合并常量和已知量

消除公共子表达式

削减运算强度

删除无用代码2、全局优化：全局程序范围内的优化

循环优化是全局优化：

外提循环不变表达式

削减计算强度

删除归纳变量1、合并常量运算

运算对象是常量或在编译时已知，则在编译时直接计算出结果，不必等到运行时再去计算。

例：

x:=3.14*2;y:=2*5*a;z:=x+0.5;合并常量运算后： x:=6.28;y:=10*a;z:=6.78;658.1.3优化技术简介优化前的四元式：(1)(*

,3.14,2,T1)(2)(:=,T1

,_,

x)(3)(*

,2

,5,T2)(4)(*

,T2

,a,T3)(5)(:=,T3

,_,

y)(6)(+

,x

,0.5,T4)(7)(:=,T4

,

_,

z)优化后：

(1) (:=,6.28,_,x)(2)(*

,10

,a,y)(3)(:=,6.78,_,z)

662、删除无用赋值

删除程序中对运行结果没有任何作用的赋值变量。

例：

x:=2+a；

y:=2+b；

x:=2*a*b;y:=x*y;删除无用赋值后：

y:=2+b；

x:=2*a*b;y:=x*y;67优化前的四元式：(1)(+,2,a,x)(2)(+,2,b,y)(3)(*,2,

a,T1)(4)(*,T1,b,x)(5)(*,x,y,y)优化后的四元式：

(1)(+,2，b,y)(2)(*,2，a,T1)(3)(*,T1，b,x)(4)(*,x，y,y)

683、削减运算强度（运算强度大→小）

例：

fori:=1to100doa:=10*i；削减运算强度后：a:=0；fori:=1to100doa:=a+10;优化后的四元式：

(1)(:=,0

,_,a)(2)(:=,1

,_,i)(3)(<=,i,100,T1)(4)(BF,(8),T1,_)(5)(+

,a,10,a)(6)(+

,i,1,

i)(7)(BR,(3),_,_)(8)()694、删除多余运算(或删除公共子表达式)公共子表达式：重复使用两次以上的子表达式，且表达式中变量的值没有发生变化。

例：x:=a*(b+c)+d;y:=a*(b+c)-d;

70优化前：

(1)(+,b,c,T1)

(2)(*,a,T1,T2)(3)(+,T2,d,x)

(4)(+,b,c,T3)

(5)(*,a,T3,T4)(6)(-,T4,d,y)优化后：

(1)(+,b,c,T1)(2)(*,a,T1,T2)(3)(+,T2,d,x)(4)(-,T2,d,y)

715、外提不变表达式不变表达式：循环中其值始终保持不变的表达式

例：fori:=1to100dobeginx:=(a+b)*(c+d)*i;y:=x+i；end优化后的程序：e:=(a+b)*(c+d);fori:=1to100dobeginx:=e*i;y:=x+i；end72优化前的四元式：(1)(:=,1,_,i)(2)(<=,i,100,T1)(3)(BF,(11),T1,_)(4)(+, a,b,T2)(5)(+, c,d,T3)(6)(*, T2,T3,T4)(7)(*, T4,i,x)(8)(+, x,i,y)(9)(+, i,1,i)(10)(BR,(2),_,_)(11)( )

73优化后的四元式：(1)(:=,1,_，i)(2)(+,a,b,T1)(3)(+,c,d,T2)(4)(*,T1,T2,e)(5)(<=,i,100,T3)(6)(BF,(11),T3,_)(7)(*,e,i,x)(8)(+,x,i,y)(9)(+,i,1,i)(10)(BR,(5),_,_)(11)( )

74758.2局部优化a=10;b=a*10;

c=a+b;s=0;k=1;if(k<5)s=s+k;elses=s-k;一个基本块不是一个基本块

局部优化是指局部范围内的优化。把程序划分为若干个“基本块”，优化的工作将分别在各个基本块内进行。8.2.1基本块的划分

基本块，是指程序中一组顺序执行的语句序列，其中只有一个入口和一个出口，执行时只能从其入口进入，从其出口退出。即基本块内的运算要么都被执行，要么都不执行。768.2.1基本块的划分例题8.1、

考察下列四元式序列：(1)(=,(2)(+,(3)(>,(4)(

BF,(5)(_,(6)(=,(7)(BR,(8)(*,(9)(end,100,i,k,(8),

k,T3

,

(3),i,_,_,j,T1

,

T2

,

1,_,_,j,_,k)T1)T2))T3)k)_)k)_)图8.1基本块划分示例

由图8.1可以看出，以上程序段可以划分为四个基本块B1、B2、B3、B4

，而且各基本块之间通过一些有向边连接起来，这种有向图称为程序流图或流图。778.2.2基本块的DAG表示8.2.2基本块的DAG表示

为了便于对基本块进行优化，引进一种有效的数据结构——无回路有向图(DirectedAcyclicGraph，DAG)。788.2.2基本块的DAG表示

图8.2一个带环路的有向图图8.3一个无环路的有向图798.2.2基本块的DAG表示(1)(=,3.14,_,

T1)(2)(*,2,

T1

,T2)(3)(+,R,r,

T3)(4)(*,T2

,T3

,A)(5)(=,A,_,

B)(6)(*,2,

T1

,T4)(7)(+,R,r,

T5)(8)(*,T4

,T5

,T6)(9)(−,R,

r,T7)(10)(*,T5

,T7

,

B)例题8.2构造以下基本块G1的DAG808.2.2基本块的DAG表示利用算法8.2对以上基本块中10个四元式逐个进行处理，新产生的DAG

子图依次如图8.5(a)~(j)所示，其中，图8.5(j)即为要构造的DAG。图8.5基本块G

的

DAG818.2.3基本块优化的实现将四元式表示成相应的DAG

后，就可利用DAG对基本块进行优化。实际上，在对基本块执行算法8.2的过程中，已完成了对基本块进行优化的一系列基本工作。828.2.3基本块优化的实现利用这样的DAG，按照原来构造其节点的顺序，重建四元式序列G2如下：(=,3.14,_,T1)(2)(=,6.28,_,T2)(3)(=,6.28,_,T4)(4)(+,R,r,T3)(5)(=,T3,_,T5)(6)(*,6.28,T3,A)(7)(=,A,_,T6)(8)(_,R,r,T7)(9)(=,T5,T7,B)838.3循环优化循环是程序设计中一种重要的数据结构，程序运行时花费在循环上的时间往往占整个运行时间的很大部分，因此对循环的优化实为提高程序运行效率的重要途径。对循环的优化实为提高程序运行效率的重要途径。848.3.1循环的查找为了进行循环的优化，首先要查找程序中的循环。在程序流图中，具有下列性质的节点序列(即一组基本块)称为程序中的一个循环：