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

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

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

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

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

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

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

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

V：=e

87.1.2屬性文法技術(shù)

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

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

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

α∈V*語義動作

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

117.1.2屬性文法技術(shù)

對于表達式“12-a/b”，語法樹如下：

E

TE’FT’-T

E’

12

ε

FT’ε

a

/

F

T’

b

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

對于表達式“12-a/b”，帶有語義動作的語法樹如下：

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）文法的屬性:

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

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

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

（2）屬性文法：

指在語言的文法中增加了屬性的文法。

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

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

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

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

葉結(jié)點：表示運算對象，如常量或變量。

其它結(jié)點：表示運算符。

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

語法樹和抽象語法樹如下：

SV:=ExE-EaE*Ebc抽象語法樹的特點：結(jié)構(gòu)緊湊、容易構(gòu)造、結(jié)點數(shù)少的圖形表示。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表示轉(zhuǎn)向某標(biāo)號處

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

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

（4）BR表示無條件轉(zhuǎn)7.2.2逆波蘭表示（后綴式）201.賦值語句的逆波蘭式<左部>:=<表達式><左部><表達式>:=例:x:=a+b*cx:=a*b-c/dxabc*+:=xab*cd/-:=7.2.2逆波蘭表示（后綴式）217.2.2逆波蘭表示（后綴式）2.GOTO語句的逆波蘭式GOTO<語句標(biāo)號><語句標(biāo)號>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.循環(huán)語句的逆波蘭式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,中間結(jié)果)例: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.轉(zhuǎn)向語句和條件語句的四元式(BR,A,_,_)無條件轉(zhuǎn)到序號如A處(BT,A,B,_)B為真時轉(zhuǎn)到A處(BF,A,B,_)B為假時轉(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)語句的四元式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.轉(zhuǎn)向語句和條件語句的三元式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)語句的三元式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)缺點優(yōu)點無需臨時變量占用空間少缺點沒有保存運算結(jié)果的屬性不利于修改、優(yōu)化377.3語法制導(dǎo)翻譯語法制導(dǎo)翻譯，直觀上說就是為每個文法規(guī)則確定相應(yīng)的語義，編寫相應(yīng)的翻譯程序。7.3.1表達式的翻譯387.3.4控制語句的翻譯7.3.2說明語句的翻譯7.3.3賦值語句的翻譯7.3.1表達式翻譯表達式是語言中最基本的語法成分表達式是源程序中出現(xiàn)頻率很高的語法成分391.語法規(guī)則與代碼形式

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

語法規(guī)則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).算數(shù)表達式到四元式的語法制導(dǎo)翻譯表達式文法：E

→E+T|E*T|?E

|(E)|i的翻譯算法可由下面的語義動作予以描述：語法規(guī)則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、變量說明的翻譯程序設(shè)計語言中最簡單的說明語句是用一個基本字來定義一串名字的某種性質(zhì)。Pascal語言中，變量說明部分冠以保留字VAR

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

過程和函數(shù)說明又可以包含說明部分和語句部分，因此過程和函數(shù)是分程序，且可以嵌套。過程說明和函數(shù)說明的語法規(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說明語句的翻譯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將前述過程和函數(shù)說明的語法制導(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說明語句的翻譯46從而有與語法規(guī)則相應(yīng)的語義子程序如下：(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、賦值語句的語法規(guī)則S→V:=E2、賦值語句的語義

賦值語句的語義可解釋為把右部表達式E

的值賦給左部變量V。7.3.3

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

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