編譯原理簡(jiǎn)明教程（第3版）-課件 第7章 語(yǔ)義分析及中間代碼的生成

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理16目錄第一章概述第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章

面向?qū)ο笳Z(yǔ)言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造22024/11/63學(xué)習(xí)目標(biāo)語(yǔ)義分析的概念語(yǔ)法制導(dǎo)翻譯常見語(yǔ)法成分的表示中間代碼語(yǔ)言7語(yǔ)義分析及中間代碼的生成重點(diǎn)：語(yǔ)義分析的概念、常見的中間語(yǔ)言形式難點(diǎn)：常見語(yǔ)法成分的表示

目錄7.1語(yǔ)義分析概述7.2中間語(yǔ)言代碼7.3語(yǔ)法制導(dǎo)翻譯7.4本章小結(jié)47.1.1語(yǔ)義分析的概念5語(yǔ)義分析：分析語(yǔ)法結(jié)構(gòu)的含義，將其表示成中間語(yǔ)言或生成目標(biāo)指令。語(yǔ)義形式化(或形式語(yǔ)義學(xué))：是個(gè)專門的研究課題，如操作語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、指稱語(yǔ)義學(xué)等。不論哪種方法，其本身的符號(hào)系統(tǒng)比較繁雜，其描述文本不易讀，因此都不能成為標(biāo)準(zhǔn)的形式語(yǔ)義系統(tǒng)。7.1.1語(yǔ)義分析的概念6主要指程序中所用標(biāo)識(shí)符及與其相關(guān)的數(shù)據(jù)對(duì)象的含義如if語(yǔ)句、for循環(huán)等結(jié)構(gòu)；由語(yǔ)言來(lái)定義。7.1.1語(yǔ)義分析的概念7語(yǔ)義分析的基本任務(wù)：類型的確定類型的檢查確認(rèn)含義其他語(yǔ)義檢查數(shù)據(jù)對(duì)象的數(shù)據(jù)類型對(duì)運(yùn)算及運(yùn)算量的類型檢查確認(rèn)控制結(jié)構(gòu)的含義不允許體外到體內(nèi)等7.1.1語(yǔ)義分析的概念控制結(jié)構(gòu)的含義有兩種確定形式：形式化：如E→E+T|E-T|T

先“*，/”后“+，-”T→T*F|T/F|F左結(jié)合……p→(E)|i非形式：如賦值語(yǔ)句含義，非形式化的規(guī)定

V：=e

87.1.2屬性文法技術(shù)

目前許多編譯程序采用語(yǔ)法制導(dǎo)翻譯的方法。

不是一種形式化系統(tǒng)，但比較接近形式化。以語(yǔ)法分析為主導(dǎo)的語(yǔ)義處理，即在語(yǔ)法分析的過(guò)程中嵌入語(yǔ)義處理程序，生成中間代碼或目標(biāo)代碼。97.1.2屬性文法技術(shù)1.增量式文法文法中加入語(yǔ)義動(dòng)作符號(hào)。一般形式：A

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

α∈V*語(yǔ)義動(dòng)作

作用：在語(yǔ)法分析時(shí)，遇到帶有語(yǔ)義動(dòng)作的花括號(hào)即執(zhí)行語(yǔ)義動(dòng)作，執(zhí)行完后再進(jìn)行下一步分析。10為了實(shí)現(xiàn)語(yǔ)法制導(dǎo)翻譯，對(duì)文法中終結(jié)符號(hào)和非終結(jié)符號(hào)引進(jìn)一些屬性，例如，變量的數(shù)據(jù)類型、表達(dá)式的值以及存儲(chǔ)器中變量的地址等。以描述相應(yīng)語(yǔ)言結(jié)構(gòu)的語(yǔ)義值。7.1.2屬性文法技術(shù)例：表達(dá)式文法G[E]：

117.1.2屬性文法技術(shù)

對(duì)于表達(dá)式“12-a/b”，語(yǔ)法樹如下：

E

TE’FT’-T

E’

12

ε

FT’ε

a

/

F

T’

b

ε127.1.2屬性文法技術(shù)

對(duì)于表達(dá)式“12-a/b”，帶有語(yǔ)義動(dòng)作的語(yǔ)法樹如下：

E

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

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

ε

a{writecode(‘a(chǎn)’)}/F{writecode(‘/’)}T’

b{writecode(‘b’)}

ε

13執(zhí)行相應(yīng)的子程序后打印出逆波蘭式12ab/-7.1.2屬性文法技術(shù)2.屬性文法（1）文法的屬性:

指與文法符號(hào)相關(guān)信息,如它的類型、值、代碼序列、符號(hào)表內(nèi)容等。

繼承屬性：用于“自上而下”傳遞信息（非終結(jié)符可有）

綜合屬性：用于“自下而上”傳遞信息（VT或VN）

（2）屬性文法：

指在語(yǔ)言的文法中增加了屬性的文法。

記號(hào)N.t表示與非終結(jié)符N相聯(lián)的屬性t

屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。147.1.2屬性文法技術(shù)例：G[E]屬性文法：157.2中間語(yǔ)言代碼采用中間語(yǔ)言的優(yōu)點(diǎn)：有利于重定目標(biāo),即一種中間表示可以生成不同的目標(biāo)語(yǔ)言。有利于提高目標(biāo)代碼的質(zhì)量，因?yàn)榭蓪?duì)中間語(yǔ)言進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化。

常見的中間語(yǔ)言有：抽象語(yǔ)法樹、逆波蘭式、四元式、三元式。167.2.1抽象語(yǔ)法樹抽象語(yǔ)法樹：經(jīng)變換后的語(yǔ)法樹

(去掉一些對(duì)翻譯不必要的信息)。

葉結(jié)點(diǎn)：表示運(yùn)算對(duì)象，如常量或變量。

其它結(jié)點(diǎn)：表示運(yùn)算符。

在語(yǔ)法規(guī)則中有些符號(hào)起標(biāo)點(diǎn)符號(hào)或解釋的作用。17如：x:=a-b*c

語(yǔ)法樹和抽象語(yǔ)法樹如下：

SV:=ExE-EaE*Ebc抽象語(yǔ)法樹的特點(diǎn)：結(jié)構(gòu)緊湊、容易構(gòu)造、結(jié)點(diǎn)數(shù)少的圖形表示。assign(:=)x-a*bc7.2.1抽象語(yǔ)法樹187.2.2逆波蘭表示（后綴式）例：a+b*cabc*+(a+b)*cab+c*a+b*c/(d-e)abc*de-/++a/*-bcde抽象語(yǔ)法樹逆波蘭式是抽象語(yǔ)法樹的線性表示。即：后序遍歷抽象語(yǔ)法樹便得到逆波蘭式19

約定幾個(gè)符號(hào)：

（1）BL表示轉(zhuǎn)向某標(biāo)號(hào)處

（2）BT表示條件為真轉(zhuǎn)

（3）BF表示條件為假轉(zhuǎn)

（4）BR表示無(wú)條件轉(zhuǎn)7.2.2逆波蘭表示（后綴式）201.賦值語(yǔ)句的逆波蘭式<左部>:=<表達(dá)式><左部><表達(dá)式>:=例:x:=a+b*cx:=a*b-c/dxabc*+:=xab*cd/-:=7.2.2逆波蘭表示（后綴式）217.2.2逆波蘭表示（后綴式）2.GOTO語(yǔ)句的逆波蘭式GOTO<語(yǔ)句標(biāo)號(hào)><語(yǔ)句標(biāo)號(hào)>BL例:GOTO1010BL227.2.2逆波蘭表示（后綴式）3.條件語(yǔ)句的逆波蘭表示IF(e)THENS1ELSES2逆波蘭式:<e的逆波蘭式><順序號(hào)1>BF<S1的逆波蘭式><順序號(hào)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.循環(huán)語(yǔ)句的逆波蘭式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.四元式

(運(yùn)算符,運(yùn)算量1,運(yùn)算量2,中間結(jié)果)例:a*b+c*d(*,a,b,T1)(*,c,d,T2)(+,T1,T2,T3)對(duì)于單目運(yùn)算符⊕,?如+a，-a（⊕，a，_，T）（?，a，_，T）287.2.3四元式2.表達(dá)式和賦值語(yǔ)句的四元式例:(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.轉(zhuǎn)向語(yǔ)句和條件語(yǔ)句的四元式(BR,A,_,_)無(wú)條件轉(zhuǎn)到序號(hào)如A處(BT,A,B,_)B為真時(shí)轉(zhuǎn)到A處(BF,A,B,_)B為假時(shí)轉(zhuǎn)到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.

循環(huán)語(yǔ)句的四元式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.三元式

(運(yùn)算符,運(yùn)算量1,運(yùn)算量2)例:(a+b)*c(1)(+,a,b)(2)(*,(1),c)337.2.4三元式2.表達(dá)式和賦值語(yǔ)句的三元式例: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.轉(zhuǎn)向語(yǔ)句和條件語(yǔ)句的三元式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.循環(huán)語(yǔ)句的三元式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三元式三元式的優(yōu)缺點(diǎn)優(yōu)點(diǎn)無(wú)需臨時(shí)變量占用空間少缺點(diǎn)沒(méi)有保存運(yùn)算結(jié)果的屬性不利于修改、優(yōu)化377.3語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯，直觀上說(shuō)就是為每個(gè)文法規(guī)則確定相應(yīng)的語(yǔ)義，編寫相應(yīng)的翻譯程序。7.3.1表達(dá)式的翻譯387.3.4控制語(yǔ)句的翻譯7.3.2說(shuō)明語(yǔ)句的翻譯7.3.3賦值語(yǔ)句的翻譯7.3.1表達(dá)式翻譯表達(dá)式是語(yǔ)言中最基本的語(yǔ)法成分表達(dá)式是源程序中出現(xiàn)頻率很高的語(yǔ)法成分391.語(yǔ)法規(guī)則與代碼形式

7.3.1表達(dá)式翻譯40(1).算數(shù)表達(dá)式的逆波蘭表示的語(yǔ)法制導(dǎo)翻譯

語(yǔ)法規(guī)則E→E+T

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

F→i語(yǔ)義子程序print(+)print(-)空

print(*)print(/)空空

print(id7.3.1表達(dá)式翻譯41(2).算數(shù)表達(dá)式到四元式的語(yǔ)法制導(dǎo)翻譯表達(dá)式文法：E

→E+T|E*T|?E

|(E)|i的翻譯算法可由下面的語(yǔ)義動(dòng)作予以描述：語(yǔ)法規(guī)則E→E

(

1)+E

(2)E→E

(

1)*E(2)

E→?E(

1)E→

(E(

1))語(yǔ)義動(dòng)作{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說(shuō)明語(yǔ)句的翻譯421、變量說(shuō)明的翻譯程序設(shè)計(jì)語(yǔ)言中最簡(jiǎn)單的說(shuō)明語(yǔ)句是用一個(gè)基本字來(lái)定義一串名字的某種性質(zhì)。Pascal語(yǔ)言中，變量說(shuō)明部分冠以保留字VAR

作為標(biāo)志，例如：VARm,n:integer;x,y:real;a:ARRAY[1..100]OFreal;7.3.2說(shuō)明語(yǔ)句的翻譯432、過(guò)程或函數(shù)說(shuō)明的翻譯

過(guò)程和函數(shù)說(shuō)明又可以包含說(shuō)明部分和語(yǔ)句部分，因此過(guò)程和函數(shù)是分程序，且可以嵌套。過(guò)程說(shuō)明和函數(shù)說(shuō)明的語(yǔ)法規(guī)則為: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說(shuō)明語(yǔ)句的翻譯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,_,_,_)過(guò)程說(shuō)明：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說(shuō)明語(yǔ)句的翻譯45將前述過(guò)程和函數(shù)說(shuō)明的語(yǔ)法制導(dǎo)翻譯改寫如下：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說(shuō)明語(yǔ)句的翻譯46從而有與語(yǔ)法規(guī)則相應(yīng)的語(yǔ)義子程序如下：(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

賦值語(yǔ)句的翻譯471、賦值語(yǔ)句的語(yǔ)法規(guī)則S→V:=E2、賦值語(yǔ)句的語(yǔ)義

賦值語(yǔ)句的語(yǔ)義可解釋為把右部表達(dá)式E

的值賦給左部變量V。7.3.3

賦值語(yǔ)句的翻譯483、語(yǔ)法制導(dǎo)翻譯技術(shù)其引進(jìn)的四元式生成子程序表示形式為：Procedure

gen(w,c,d,e);beginP[n]:=(w,c,d,e);n:=n+1end