程序設計語言編譯原理第三版第7章-課件

1、1第七章語義分析和中間代碼產(chǎn)生優(yōu)化器語法分析器靜態(tài)檢查器中間代碼產(chǎn)生器中間代碼 一般情況下，在詞法分析程序和語法分析程序對源程序的語法結構進行分析之后，要么，由語法分析程序直接調用相應的語義子程序進行語義處理；要么，首先生成語法樹或該結構的某種表示，再進行語義處理。1第七章語義分析和中間代碼產(chǎn)生優(yōu)化器語法分析器靜態(tài)檢查器中2語義處理分兩步：1.靜態(tài)語義分析，即驗證語法結構合法的程序是否真正有意義。2.若靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯。 即要么生成程序的一種中間表示形式（中間代碼）， 要么生成實際的目標代碼。靜態(tài)語義檢查包括：（1）類型檢查；（2）控制流檢查；（3）一致性檢查；（4）相

2、關名字檢查。第七章語義分析和中間代碼產(chǎn)生2語義處理分兩步：靜態(tài)語義檢查包括：第七章語義分析和中間代3中間代碼：即中間語言，獨立于機器的，復雜性介于源語言和機器語言之間的一種表示形式。采用中間語言的好處：第七章語義分析和中間代碼產(chǎn)生（1）便于進行與機器無關的代碼優(yōu)化工作；（2）使編譯程序改變目標機更容易；（3）使編譯程序的結構在邏輯上更為簡單明確。3中間代碼：即中間語言，獨立于機器的，復雜性介于源采用中間語4 7.1 中間語言 7.2 說明語句 7.3 賦值語句的翻譯 7.4 布爾表達式的翻譯 7.5 控制語句的翻譯 7.6 過程調用的處理（略） 7.7 類型檢查 （略）第七章語義分析和中間代碼

3、產(chǎn)生4 7.1 中間語言第七章語義分析和中間代碼產(chǎn)生57. 中間語言中間語言形式：后綴式三地址代碼 圖表示法三元式 四元式 間接三元式DAG抽象語法樹57. 中間語言中間語言形式：三元式 四元式 間接三元6一、后綴式逆波蘭式：規(guī)則：7. 中間語言(1)E常量變量： 后綴式為E本身(2)EE1 op E2： E1 E2 op(3)E(E1)： (E1)(4)Eop E1： E1 op6一、后綴式逆波蘭式：規(guī)則：7. 中間語言(1)E常77. 中間語言例子：a*(b+c)(a+b)*(c+d)abc+*x+yza0(8+z)3ab+cd+*xy+za08z+377. 中間語言例子：a*(b+c)(

4、a+b)*(c8二、圖表示法1.DAG(無循環(huán)有向圖) 與抽象語法樹對比 相同點:對表達式中的每個子表達式，它們都有一個結 點，一個內部結點代表一個操作符，它的孩子 代表操作數(shù)； 不同點:在一個DAG中代表公共子表達式的結點具有多個 父結點，而在一棵抽象語法樹中公共子表達式 被表示為重復的子樹。7. 中間語言8二、圖表示法1.DAG(無循環(huán)有向圖)7. 中間語言9例子：如圖所示，為a+a*(b-c)+(b-c)*d的DAG + * * d a- b c7. 中間語言9例子：如圖所示，為a+a*(b-c)+(b-c)*d的DA102.抽象語法樹例子：(1)a:=b*-c+b*-c的圖表示法ass

5、ign a+ * * b uminus b uminus c c語法樹assign a+ * b uminus cDAG7. 中間語言102.抽象語法樹例子：(1)a:=b*-c+b*-c的圖表11(2) a:=b*-c+b*-c 的抽象語法樹的兩種表示法assignida + *idbuminusidc *uminusidcidbidbIdcuminus1*02idbidcuminus5*46+37idaassign980123456789107. 中間語言11(2) a:=b*-c+b*-c 的抽象語法樹的兩種表示12三、三地址代碼1.三地址代碼:下面一般形式的語句構成的序列:x:=y o

6、p zT1:=y*z, T2:=x+T1稱為三地址代碼的原因: 每條語句通常包含三個地址,兩個用來表示操作數(shù),一個用來存放結果。7. 中間語言具體實現(xiàn):用記錄表示,其中包含運算符和操作數(shù)的域。x,y,z: 名字,常數(shù),編譯時產(chǎn)生的臨時變量 op: 運算符號(如定點運算符,浮點運算符,邏輯運算符等)12三、三地址代碼1.三地址代碼:下面一般形式的語句構成的序132.四元式：帶有四個域的記錄結構 內容均是指針,指向有關名字的符號表入口7. 中間語言(op，arg1，arg2，result)132.四元式：帶有四個域的記錄結構 內容均是指針,7.147. 中間語言例子: 三地址語句a:=b*-c+b

7、*-c的四元式表示 四元式表示Oparg1arg2result(0)(1)(2)(3)(4)(5)uminus*uminus*+:=cbcbT1T2T1T3T4T1T2T3T4T5a147. 中間語言例子: 三地址語句a:=b*-c+b*153.三元式： 為了避免把臨時變量填入符號表,可通過計算該臨時變量值的語句的位置來引用該臨時變量?；蚴侵赶蚍柋淼闹羔槍Τ绦蛑械拿侄曰蚴侵赶蛉奖淼闹羔槍εR時變量而言7. 中間語言（op，arg1，arg2）153.三元式：或是指向符號表的指針對程序中的名字而言716oparg1arg2(0)(1)(2)(3)(4)(5)uminus*umins*+a

8、ssigncbcb(1)a(0)(2)(3)(4)7. 中間語言例子: 三地址語句a:=b*-c+b*-c的三元式表示 16oparg1arg2(0)uminusc7. 中間語174.間接三元式：便于代碼優(yōu)化處理方法：間接碼表+三元式表按運算的先后順序列出有關三元式在三元表中的位置oparg1arg2(1)(2)(3)(4)(5)+*:=:=A(1)XDYBC(2)(1)(1)例: 語句X:=(A+B)*C;Y:=D(A+B)的間接三元式表示如下所示:間接代碼(1)(2)(3)(1)(4)(5)三元式表7. 中間語言174.間接三元式：便于代碼優(yōu)化處理按運算的先后順序列出有關187.2 說明語

9、句編譯過程中,對“說明語句”要做的工作:對一個過程或分程序的一系列說明語句,考察時:(1)需要為局部于該過程的名字分配存儲空間;(2)對每個局部名字,都需在符號表中建立相應的表項, 并填入有關的信息如類型、在存儲器中的相對地址 等。187.2 說明語句編譯過程中,對“說明語句”要做的工作19一、過程中的說明語句1. 產(chǎn)生“說明語句”的文法：PDDD;DDid: T TintegerTrealTarraynum of T1TT17.2 說明語句19一、過程中的說明語句1. 產(chǎn)生“說明語句”的文法：PD202.處理方式： 處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，則:

10、(1)將該名字填入符號表中,(2)置相對地址為當前offset之值，(3)使offset加上該名字所表示的數(shù)據(jù)對象的域寬。7.2 說明語句202.處理方式：7.2 說明語句213. 相應的翻譯模式：7.2 說明語句PDDD;DDid:T TintegerTrealTarraynum of T1TT1 offset:=0 enter (, T.type,offset); offset:=offset+t.width T.type:=integer; T.width:=4 T.type:=real; T.width:=8 T.type:=array(num.val,T1.type);

11、 T.width:=num.valT1.width T.type:=pointer(T1.type);T.width:=4 213. 相應的翻譯模式：7.2 說明語句PD22說明:(1) offset: 全程變量,代表變量在過程數(shù)據(jù)區(qū)中的相對地址, 用來跟蹤下一個可用的相對地址的位置.7.2 說明語句(2) enter(name,type,offset): 把名字name符號表,并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset.(3)綜合屬性: T.type名字的類型;T.width名字的域寬(即該類型名字所占用 的存儲單元個數(shù))22說明:7.2 說明語句(2) enter(n

12、ame,23二、保留作用域信息1.嵌套過程中的說明語句7.2 說明語句(1)相應的文法: PD DD;D | id: T | proc id; D; S(2)程序舉例: 23二、保留作用域信息1.嵌套過程中的說明語句7.2 說247.2 說明語句2.含嵌套說明的翻譯模式：PM D addwidth (top(tblptr), top(offset); pop (tblptr); pop(offset) M t:= mktable(nil); push(t,tblptr); push(0,offset) D D1; D2D proc id; N D1;S t:= top (tblptr); ad

13、dwidth (t,top(offset); pop(tblptr); pop(offset); enterproc ( top(tblptr), , t) N t:= mktable (top (tblptr); push(t,tblptr); push(0,offset) D id: T enter(top(tblptr), , T.type, top(offset); top(offset):= top(offset) +T.width 247.2 說明語句2.含嵌套說明的翻譯模式：PM D25(1)語義規(guī)則中的操作:7.2 說明語句2.含嵌套說明的翻譯模式：

14、Mktable (previous): 創(chuàng)建一張新符號表,并返回指向新表的一個指針;Enter (table, name, type, offset): 在指針table指示的符號表中為名字name建立一個新頂,并把類型type、相對地址offset填入到該項中;25(1)語義規(guī)則中的操作:7.2 說明語句2.含嵌套說267.2 說明語句(1)語義規(guī)則中的操作:Enterproc (table, name, newtable): 在指針table指示的符號表中為名字name的過程建立一個新頂。參數(shù)newtable指向過程name的符號表。Addwidth (table, width): 在指針

15、table指示的符號表表頭中記錄下該表中所有名字占用的總寬度;267.2 說明語句(1)語義規(guī)則中的操作:Enterp27(2)棧:tblptr:存放指向符號表的指針,棧頂為指向當前正在處理過 程的符號表指針.offset:存放變量在數(shù)據(jù)區(qū)中的相對地址,棧頂為當前正在處 理過程的下一個變量的相對地址。 (3) top():取當前棧頂元素 push(a,B):將a推進B棧棧頂 pop(A):將A棧棧頂元素出棧7.2 說明語句27(2)棧: (3) top():取當前棧頂元素7.2287.3 賦值語句的翻譯一、簡單算術表達式及賦值語句1.產(chǎn)生“賦值語句”三地址代碼的翻譯模式:Sid:=E p:=l

16、ookup(); if pnil then emit(p:=E.place) else error EE1+E2 E.place:=newtemp; emit(E.place:=E1.place+E2.place) EE1*E2 E.place:=newtemp; emit(E.place:=E1.place*E2.place) E-E1 E.place:=newtemp; emit(E.place:=uminusE1.place) E(E1) E.place:=E1.placeEid p:=lookup(); if pnil then E.place:=p els

17、e error287.3 賦值語句的翻譯一、簡單算術表達式及賦值語句1.292. 說明:id所代表的名字本身lookup()檢查符號表中是否存在相應此名字的入口nil:返回一個該表項的指針 =nil:未找到 emit()將生成的三地址語句發(fā)送到輸出文件中E.place存放E值的名字newtemp產(chǎn)生“臨時變量”7.3 賦值語句的翻譯292. 說明:7.3 賦值語句的翻譯303.例題：寫出下列代碼段中表達式的翻譯制導過 程及其所產(chǎn)生的四元式beginInteger：B、C、D、X;X:=-B*(C+D);endOparg1arg2result(1)(2)(3)(4)+

18、*:=T1T3T2T1T2T3符號表四元式7.3 賦值語句的翻譯303.例題：寫出下列代碼段中表達式的翻譯制導過Oparg131 已歸約串PLACE輸入串語義動作 # X:= -B*(C+D)# #X X := -B*(C+D)# # X:= X_ -B*(C+D)# # X:= - X_ B*(C+D)# # X:= -B X_B *(C+D)# # X:= -E X_B *(C+D)# E.place:=p= # X:= E1 X_T1 *(C+D)# E1.place:=newtemp=T1; 生成四元式(1) # X:=E*(C X_T1_C +D)# # X:=E*(E1X_T1_C

19、 +D)# E1.place:=p= 31 已歸約串PLACE輸入串語義動作32 已歸約串 PLACE 輸入串 語義動作 # X:=E*(E1+D X_T1_C_D )# # X:=E*(E1+E2 X_T1_C_D )# E2.place:=p= # X:=E*(E3X_T1_T2 )#E3.place:=newtemp=T2; 生成四元式(2) # X:=E*(E3) X_T1_T2_ # # X:=E*E4 X_T1_T2 # E4.place=E3.place=T2 # X:=E5X_T3 # E5.place=T3; 生成四元式(3) # S # p:=lookup(X.name);

20、 生成四元式(4)32 已歸約串 PLACE 輸入33二、數(shù)組元素的引用1.數(shù)組元素在存儲器中的存放:7.3 賦值語句的翻譯一維數(shù)組地址: 二維數(shù)組地址: Ai 的地址 = base + ( i - low) * w = i*w + ( base - low*w ) Ai1, i2 的地址 = base + ( ( i1 low1 ) * n2 +i1 - low2 ) * w = ( ( i1*n2 ) + i2 ) * w + ( base ( ( low1*n2 ) + low2 )*w )33二、數(shù)組元素的引用1.數(shù)組元素在存儲器中的存放:7.3347.3 賦值語句的翻譯1.數(shù)組元素在

21、存儲器中的存放:二、數(shù)組元素的引用k維數(shù)組地址: C = ( ( ( low1 n2+low2 ) n3 + low3 ) nk + lowk) * w變量部分：（( ( i1 n2+i2）n3 + i3）) nm + i m e1 = i1 , em = em-1*n m + imA i1, i2, , ik 的地址 =（i1 n2+i2）n3 + i3）) nk +ik )*w + base ( ( ( low1 n2+low2 ) n3 + low3 ) nk + lowk) * w 347.3 賦值語句的翻譯1.數(shù)組元素在存儲器中的存放:二35改寫產(chǎn)生式的原因： 使我們在整個下標表達式

22、串Elist的翻譯過程中隨時都能知道符號表中相應于數(shù)組名字id的符號表入口,從而隨時能了解登記在符號表中的有關數(shù)組id的全部信息。2.產(chǎn)生數(shù)組元素的產(chǎn)生式：LidElist | idLElist | idElistElist,E | E ElistElist,E | idE7.3 賦值語句的翻譯35改寫產(chǎn)生式的原因：2.產(chǎn)生數(shù)組元素的產(chǎn)生式：7.3 賦363.數(shù)組元素的翻譯模式：A.文法: (1) SL:=E (2) EE+E (3) E(E) (4) EL (5) LElist (6) Lid (7) ElistElist, E (8) Elistid E7.3 賦值語句的翻譯363.數(shù)組元

23、素的翻譯模式：7.3 賦值語句的翻譯37B.說明: id.placeid的符號表入口. E.place存放E的名字/值. L.offset = null , L為簡單名字; null, L為數(shù)組元素引用,存放臨時變量的值. (變量部分的值) L.place L簡單名字,則指向符號表中相應此名字表項的 指針,即此名字的符號表入口. L數(shù)組引用,則L.place存放臨時變量的值. (常量部分的值)7.3 賦值語句的翻譯37B.說明:7.3 賦值語句的翻譯387.3 賦值語句的翻譯B.說明: Elist.array用來記錄指向符號表中相應數(shù)組名字 表項的指針數(shù)組變量的符號表入口 Elist.plac

24、e表示臨時變量,用來臨時存放由Elist中的 下標表達式計算出的值。 Elist.ndim記錄Elist中的下標表達式的個數(shù),即 維數(shù)。Limit(array, j)返回nj,即由array所指示的數(shù)組的 第j維長度。387.3 賦值語句的翻譯B.說明: 397.3 賦值語句的翻譯C.翻譯模式 S L:=E if L.offset = null then emit ( L.place := E.place) else emit ( L.place L.offset := E.place) (2) E E1 + E2 E.place := newtemp; Emit ( E. place :=

25、E1.place + E2.place) (3) E ( E1 ) E.place := E1.place 397.3 賦值語句的翻譯C.翻譯模式 S L:407.3 賦值語句的翻譯 (4) EL if L. offset = null then E. place := L. place else begin E. place := newtemp; emit ( E. place:= L. place L. offset ) end (5) L Elist L. place := newtemp; emit ( L. place:= Elist. array - C ); L. offset

26、 := newtemp; emit ( L. offset := w* Elist. place ) (6) Lid L. place := id. place ; L. offset := null 407.3 賦值語句的翻譯 (4) EL 417.3 賦值語句的翻譯 (7) Elist Elist1, E t:= newtemp; m := Elist1.ndim +1 ; emit ( t:= Elist1.place * limit ( Elist1.array, m) ); emit ( t:= t + t. place ) Elist. array := Elist1.array;

27、 Elist. place := t; Elist. ndim := m (8) Elist id E Elist. place := E. place; Elist. ndim := 1; Elist. array := id. place 417.3 賦值語句的翻譯 (7) Elist E424.舉例已知:A為1020的數(shù)組,即n1=10,n2=20, 設w=4, x:=A y, zx:=Ay, z 其相應的三地址語句序列如下:(1) T1:=y*20(2) T1:=T1+z(3) T2:=A-84(4) T3:=4*T1(5) T4:=T2T3(6) x:=T47.3 賦值語句的翻譯42

28、4.舉例7.3 賦值語句的翻譯437.4 布爾表達式的翻譯前言:2.布爾表達式的組成及形式 組成:布爾運算符號、布爾變量、關系表達式 and, or, not (, ) 形式: E1 relop E21.布爾表達式的兩個基本作用 (1)用來計算邏輯值 (2)用作控制流語句的條件表達式437.4 布爾表達式的翻譯前言:2.布爾表達式的組成及形447.4 布爾表達式的翻譯3. 產(chǎn)生布爾表達式的文法:EE or EEE and EEnot EE(E)Eid relop idEid447.4 布爾表達式的翻譯3. 產(chǎn)生布爾表達式的文法:45一、數(shù)值表示法1.計算布爾表達式值的兩種方法：7.4 布爾表達

29、式的翻譯(1)逐步計算(與算術表達式計算類似)例：1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1(2)采取某種優(yōu)化措施 A or B if A then T else B A and Bif A then B else F not A if A then F elseT45一、數(shù)值表示法1.計算布爾表達式值的兩種方法：7.4 462.采取“逐步計算法”計算布爾表達式7.4 布爾表達式的翻譯(2)關系式a b if ab then 1 else 0分析: (1)布爾式a or b and not c T1:

30、=not c T2:=b and T1 T3:=a or T2 100: if ab goto 103 101: T:=0 102: goto 104 103: T:=1 104: 462.采取“逐步計算法”計算布爾表達式7.4 布爾表達式473.布爾表達式“逐步計算法”的翻譯模式： Emit(): 過程,將產(chǎn)生的三地址代碼送到輸出文件中. Nextstat: 給出輸出序列中下一條三地址語句的地址索引, 每產(chǎn)生一條三地址語句后,過程emit將nextstat加1.7.4 布爾表達式的翻譯473.布爾表達式“逐步計算法”的翻譯模式：7.4 布爾48關于布爾表達式的數(shù)值表示法的翻譯模式:EE1 o

31、r E2 E.place:=newtemp; emit (E.place:=E1.placeorE2.place) EE1 and E2 E.place:=newtemp; emit (E.place:=E1.placeandE2.place) Enot E1 E.place:=newtemp; emit (E.place:= notE1.place) E(E) E.place:=E1.placeEid1 relop id2 E.place:=newtemp; emit (if id1.place relop.op id2.place gotonextstat+3); emit (E.plac

32、e:= 0); emit (gotonextstat+2); emit (E.place:= 1);Eid E.place:=id.place 48關于布爾表達式的數(shù)值表示法的翻譯模式:EE1 and494.舉例：ab or cd and ef7.4 布爾表達式的翻譯 100: if ab goto 103 101: T1:=0 102: goto 104 103: T1:=1 104: if cd goto 107 105: T2:=0 106: goto 108 107: T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:

33、=1 112: T4:=T2 and T3 113: T5:=T1 or T4494.舉例：ab or cd and ec or bc goto L2goto L1 L1:if bc or bd then 553. 產(chǎn)生布爾表達式三地址代碼的語義規(guī)則 課本188頁表7.7 注意：利用表7.7中的語義規(guī)則翻譯的最容易方法是經(jīng)過 兩遍掃描。 （1）為給定的輸入串構造一顆語法樹； （2）對語法樹進行深度優(yōu)先遍歷，進行語義規(guī)則中 規(guī)定的翻譯。 553. 產(chǎn)生布爾表達式三地址代碼的語義規(guī)則 注意：利用表7564.實現(xiàn)一遍掃描翻譯 (1) 三地址代碼表示 四元式 ( jnz, a,p)if a goto

34、p ( jrop, x, y, p) if x rop y goto p ( j, p)goto p(2)一遍掃描的主要問題： 當生成某些轉移語句時我們可能還不知道該語句將要轉移到的標號究竟是什么？問題的解決：在生成形式分支的跳轉指令時暫時不確定跳轉 目標，而建立一個鏈表，把轉向這個目標的跳 轉指令的標號鍵入這個鏈表。一旦目標確定之 后再把它填入有關的跳轉指令中?；靥罴夹gE.truelist - E.falselist: 分別記錄布爾表達式E所對應的四元式中需回填“真”、“假”出口的四元式標號所構成的鏈表。 564.實現(xiàn)一遍掃描翻譯(2)一遍掃描的主要問題：問題的解決57變量nextquad指

35、向下一條將要產(chǎn)生但尚未形成的四元式的 地址,初值為1,執(zhí)行一次emit后,自動加1.函數(shù)makelist(i)將創(chuàng)建一個僅含i的新鏈表，其中i是四元式 數(shù)組的一個下標，函數(shù)返回指向這個鏈的指針。函數(shù)merge(p1,p2)把鏈首為p1和p2的兩條鏈合并為一,作為 函數(shù)值,回送合并后的鏈首.過程backpatch (p, t)功能是完成“回填”,把p所鏈接的每個 四元式的第四個區(qū)段都填為t.（3）變量和過程57變量nextquad指向下一條將要產(chǎn)生但尚未形成的四元58（4）翻譯模式: 課本190頁7.4 布爾表達式的翻譯(1)EE1 or M E2 backpatch (E1.falselist

36、, M.quad); E.truelist:=merge (E1.truelist, E2.truelist); E.falselist:=E2. falselist (2)EE1 and M E2 backpatch ( E1.truelist, M.quad); E.truelist:= E2. truelist ; E.falselist:= merge (E1.falselist, E2.falselist) (3)Enot E1 E.truelist:= E1. falselist ; E.falselist:= E1.truelist (4)E(E1) E.truelist:= E

37、1. truelist ; E.falselist:= E1.falselist 58（4）翻譯模式: 課本190頁7.4 布爾表達式的翻譯59(5) Eid1 relop id2 E.truelist:=makelist (nextquad); E.falselist:=makelist (nextquad+1) ; emit (jrelop.op ,id1.place,id2.place,0); emit (j,-，-，0) 7.4 布爾表達式的翻譯(6) Eid E.truelist:=makelist (nextquad); E.falselist:=makelist (nextqua

38、d+1) ; emit (jnz ,id.place,-,0 ); emit (j,-，-，0) (7) E M.quad:=nextquad; 59(5) Eid1 relop id2 E.tr605.例題：課本190頁例題7.4 ab or cd and ef7.4 布爾表達式的翻譯翻譯結果：100 ( j, a, b, 0)101 ( j, -, -, 102)102 ( j, c, d,104)103 ( j, -, -, 0)104 ( j L1: if ab goto L2 goto Lnext L2: if cd goto L3 goto L4 L3: T1:=y+z X:=T1 goto L1 L4: