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

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

免费提供编译原理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