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

新工科建設·計算機類系列教材

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

面向對象語言的編譯第十二章

并行編譯技術第十三章

軟件構造22024/11/63學習目標語義分析的概念語法制導翻譯常見語法成分的表示中間代碼語言7語義分析及中間代碼的生成重點：語義分析的概念、常見的中間語言形式難點：常見語法成分的表示

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

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

V：=e

87.1.2屬性文法技術

目前許多編譯程序采用語法制導翻譯的方法。

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

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

α∈V*語義動作

作用：在語法分析時，遇到帶有語義動作的花括號即執(zhí)行語義動作，執(zhí)行完后再進行下一步分析。10為了實現(xiàn)語法制導翻譯，對文法中終結符號和非終結符號引進一些屬性，例如，變量的數(shù)據(jù)類型、表達式的值以及存儲器中變量的地址等。以描述相應語言結構的語義值。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(chǎn)’)}/F{writecode(‘/’)}T’

b{writecode(‘b’)}

ε

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

指與文法符號相關信息,如它的類型、值、代碼序列、符號表內容等。

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

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

（2）屬性文法：

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

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

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

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

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

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

其它結點：表示運算符。

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

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

SV:=ExE-EaE*Ebc抽象語法樹的特點：結構緊湊、容易構造、結點數(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表示轉向某標號處

（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.循環(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,中間結果)例: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.

循環(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.轉向語句和條件語句的三元式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)點無需臨時變量占用空間少缺點沒有保存運算結果的屬性不利于修改、優(yōu)化377.3語法制導翻譯語法制導翻譯，直觀上說就是為每個文法規(guī)則確定相應的語義，編寫相應的翻譯程序。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ù)表達式的逆波蘭表示的語法制導翻譯

語法規(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ù)表達式到四元式的語法制導翻譯表達式文法：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、變量說明的翻譯程序設計語言中最簡單的說明語句是用一個基本字來定義一串名字的某種性質。Pascal語言中，變量說明部分冠以保留字VAR

作為標志，例如：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ù)說明的語法制導翻譯改寫如下：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ī)則相應的語義子程序如下：(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、語法制導翻譯技術其引進的四元式生成子程序表示形式為：Procedure

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