華東師范大學(xué)計算機科學(xué)技術(shù)系.ppt

《華東師范大學(xué)計算機科學(xué)技術(shù)系.ppt》由會員分享，可在線閱讀，更多相關(guān)《華東師范大學(xué)計算機科學(xué)技術(shù)系.ppt（119頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,1,第五章 語法制導(dǎo)翻譯和中間代碼生成,5.1 概述 語義分析包含靜態(tài)語義檢查和語義識別，并在此基礎(chǔ)上對源程序（單詞串形式）進行等價轉(zhuǎn)換，轉(zhuǎn)換為中間代碼（目標(biāo)代碼）。 在后面的討論中總是認(rèn)為詞法、語法分析已經(jīng)完成，讀入的是（語法正確）句子！而不關(guān)心用什么方法進行語法分析的（以后主要討論自底向上的句法分析方法），關(guān)心的是如何在語法分析的同時正確地插入語義子程序進行翻譯（語法制導(dǎo)翻譯） 。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,2,一、靜態(tài)語義檢查,稱在編譯時刻進行的語義檢查為靜態(tài)語義檢查，通?？砂缦聝?nèi)容： 類型檢查。 檢查運算的合

2、法性和參與運算的運算分量類型的一致性（相容性）。必要時進行相應(yīng)的類型轉(zhuǎn)換。 (2) 控制流檢查。 以保證控制語句有合法的轉(zhuǎn)向點，如C語言中的break語句，需尋找包含它的最小的switch、while或for語句，方可找到轉(zhuǎn)向點，否則出錯。不允許循環(huán)外控制轉(zhuǎn)入循環(huán)內(nèi)。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,3,(3) 有關(guān)名字的匹配檢查。 可以對某些程序段命名，該名字出現(xiàn)在程序段的開始和結(jié)束處，如同語句括號一般，應(yīng)檢查它們的配對。 (4) 一致性檢查。 如在相同作用域中標(biāo)識符只能說明一次（重復(fù)定義），case語句的標(biāo)號不能相同，枚舉類型的元素不能重復(fù)，沒有定義數(shù)據(jù)類型等。,2020

3、/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,4,二、語法制導(dǎo)翻譯,例1：對算術(shù)表達式文法G的一個翻譯方案 +print “1” print “2” *print “3” print “4” ()print “5” iprint “6” 其中 括起的稱為該產(chǎn)生式的語義子程序。 對輸入串W=(i+i)*i則W是G的一個句子。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,5,若采用自底向上的句法分析，規(guī)定當(dāng)用產(chǎn)生式歸約時，調(diào)用相應(yīng)的語義子程序，則翻譯結(jié)束后輸出 64264154632。 若采用自頂向下的句法分析，規(guī)定當(dāng)用產(chǎn)生式推導(dǎo)時，調(diào)用相應(yīng)的語義子程序，則翻譯結(jié)束后輸出 23451246466

4、。 應(yīng)根據(jù)輸出（翻譯）目標(biāo)，配備適當(dāng)?shù)恼Z義子程序，這就是所要做的工作。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,6,三、翻譯要解決的問題,翻譯成什么樣的目標(biāo)語言的代碼？ 將源語言程序翻譯成中間語言的程序。中間語言與機器無關(guān)，而語句顆粒度又與機器語言相當(dāng)，于是帶來了諸多好處： 編譯邏輯結(jié)構(gòu)簡單明確，與機器相關(guān)的工作集中到目標(biāo)代碼生成階段，難度和工作量下降； 便于移植和維護。 利于優(yōu)化，代碼優(yōu)化將分成與機器無關(guān)的中間代碼優(yōu)化及與機器相關(guān)的目標(biāo)代碼優(yōu)化兩個階段，使優(yōu)化更有效。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,7,2. 何時進行這種翻譯？,如例1所示，如果作為句柄所對應(yīng)的產(chǎn)

5、生式，都配有一個相應(yīng)的翻譯子程序，則每當(dāng)按句柄歸約時，就調(diào)用相應(yīng)的翻譯子程序（語義子程序）完成局部的翻譯，則一個句子，一段代碼，按它們的歸約次序，將所有翻譯子程序依次執(zhí)行，就完成了這個句子、這段代碼的翻譯。這種翻譯與語法分析緊密相關(guān)，稱之為語法制導(dǎo)翻譯：每當(dāng)歸約時，調(diào)用相應(yīng)的語義子程序，這就是翻譯的時機。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,8,3. 如何實現(xiàn)這種翻譯？,語法制導(dǎo)翻譯的關(guān)鍵，是為每個產(chǎn)生式編寫翻譯子程序。例1中產(chǎn)生式所帶有的這種語義子程序只能輸出這類數(shù)字串?，F(xiàn)在，要對一個有窮表示的文法的無窮多個語句，按所給出的語義子程序要完成不同語句的翻譯任務(wù)，輸出各自的目標(biāo)代碼

6、。難點自然就集中在如何寫這些語義子程序了。 采用屬性翻譯文法（屬性文法），這是一種形式化的語義分析方法。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,9,結(jié)論,語法制導(dǎo)的翻譯方法就是在語法分析的同時（制導(dǎo)下）插入一系列的語義動作（由語義子程序提供），將源程序（單詞形式）翻譯成等價的中間代碼。 主要考慮自底向上句法分析的方法（在歸約時調(diào)用語義子程序），設(shè)計翻譯方案（形成屬性文法）。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,10,5.2 中間語言,常見的中間語言有很多種，一般可單獨或混合使用。 一、后綴表示（逆波蘭表示） 是由波蘭數(shù)學(xué)家盧卡西維奇(Lukasiewicz)提出的。它

7、是將a op b中運算量a、b依次寫在算符op之前，即a b op，可以形式地給出表達式E的后綴表示的遞歸定義： (1) 如果E是變量或常數(shù)，則E的后綴表示即E本身。 (2) 如果E為E1 op E2形式，則它的后綴表示為E1 E2 op， 其中op是二元算符，E1，E2分別是E的后綴表示(op為一元運算時E2為空)。 (3) 如果E為(E1)形式，則E1后綴表示即為E的后綴表示。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,11,后綴表示可以機械地計算。 中綴表示可以機械地轉(zhuǎn)換為后綴表示。（E.W.Dijkstra) 例2： (-a*b+c)-d的后綴表示為：a b* uminus c

8、+d- 其中uminus表示一元運算-。 后綴表示的推廣： O1，O2，On，其中是n元的運算符，Oi為運算對象 i=1,2n。 假定：后綴表示存放在一維數(shù)組S中，Si是一個單詞,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,12,例3：賦值語句 := 若V，E分別為、的后綴表示，賦值語句的后綴表示為：V E:= 如：A:=B*C+D則為ABC*D+:= 例4：條件語句 ifthenelse的后綴表示為：E i1 BZ S1 i2 BR S2 其中： E, S1, S2分別是，的后綴表示。 i1是S2的首符號在S數(shù)組中的下標(biāo) i2是S2的尾符號在S數(shù)組中的下標(biāo)加1 BZ是運算符表示“零轉(zhuǎn)”

9、 BR是運算符表示“無條件轉(zhuǎn)”,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,13,試將語句if x5 then x:=a;else x:=b;表示成逆波蘭表示 引入二元運算符BZ、一元運算符BR。逆波蘭表示 T,i,BZ的含義為若T的值為零，則轉(zhuǎn)到位置為i處執(zhí)行。i,BR的含義為無條件轉(zhuǎn)移到位置i處執(zhí)行。 假定上述語句的逆波蘭表示存放在一維數(shù)組S中，用數(shù)組的下標(biāo)表示轉(zhuǎn)向的位置。S數(shù)組可描述為：,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,14,二、圖(樹、抽象句法樹）表示,通過對分析樹的簡化得到 例5：對算術(shù)表達式文法G，輸入串W=(i+i)*i 的分析樹見前。而樹表示為： 反映了

10、一種運算順序 內(nèi)結(jié)點表示運算及運算結(jié)果 見P82。亦可以使用無環(huán)路有向圖dag(directed acyclic graph)。,*,+,i,i,i,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,15,三、三地址代碼,三地址代碼語句的一般形式為：x:=y op z 其中x、y和z為名字、常量或編譯時產(chǎn)生的臨時變量，op為運算符如定點運算符、浮點運算符、邏輯運算符等。由于三地址語句只含一個運算符，故多個算符組成的表達式必須用三地址語句序列表示。 例如表達式x+y*z的三地址代碼為： t1:=y*z t2:=x+t1 其中t1和t2是編譯時需要的臨時變量。,2020/7/29,華東師范大學(xué)計算

11、機科學(xué)技術(shù)系,16,三地址語句通常包含三個地址，兩個用來存放運算對象，一個用來存放運算結(jié)果。在實現(xiàn)時，用戶定義的名字將由指向符號表中該名字項的指針?biāo)妗?2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,17,四、三地址語句的種類,三地址語句有多種表示形式，常見的有： x:=y op z 賦值語句，其中op為二目的算術(shù)運算符或邏輯運算符。 (2) x:=op y 賦值語句，其中op為一目運算符，如一目減uminus，邏輯否定not，移位算符及將定點數(shù)轉(zhuǎn)換成浮點數(shù)的類型轉(zhuǎn)換符。 (3) x:=y復(fù)寫語句，將y的值賦給x。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,18,(4) goto

12、 L 無條件轉(zhuǎn)移語句，下一個將被執(zhí)行的語句是標(biāo)號為L的語句。 (5) if x relop y goto L 或 if x goto L 條件轉(zhuǎn)移語句, relop為關(guān)系運算符如、=等，若x和y滿足關(guān)系relop就轉(zhuǎn)而執(zhí)行標(biāo)號為L的語句，否則順序執(zhí)行本語句的下一語句。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,19,(6) param X 和 call P，n 過程調(diào)用語句，源程序中的過程調(diào)用語句 call P(x1, x2, , xn)可以用下列三地址代碼表示： param x1 param x2 param xn call P, n 其中整數(shù)n為實參個數(shù)。 過程返回語句為retur

13、n y，其中y為返回值。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,20,(7) 變址賦值： x:=yi，表示將從地址y開始的第i個地址單元的值賦給x。 xi:=y，表示將y的值賦給從地址x開始的第i個地址單元。 (8) 地址和指針賦值： x:= 1id, 2 2.dtype:=1.dtype; set_type(id.p, 1.dtype); id set_type(id.p, .dtype); 屬性.dtype是繼承屬性 。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,42,例2. S-屬性翻譯文法的例子,將中綴表達式翻譯為抽象語法樹的翻譯文法。 簡單算術(shù)表達式文法G ： 1

14、+ .ptr:=Node(+,1.ptr,.ptr .ptr:= .ptr 1*.ptr:=Node(*,1.ptr,.ptr .ptr:= .ptr ().ptr:= .ptr c .ptr:=Node(/,c.class,c.value 其中屬性X.ptr的值是樹結(jié)點的地址，函數(shù)Node(x,y,z)的功能是：申請一塊空間，將x、y、z寫入，并返回該空間的首地址。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,43,對單詞串（c.3+c.9)*(c.2+c.15)經(jīng)過分析與翻譯后轉(zhuǎn)換為：,*,+,+,c.3,c.9,c.2,c.15,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,4

15、4,說明,在本章的討論中，總使用S-屬性翻譯文法，采用自底向上的句法分析（不關(guān)心用哪種方法）。 主要的工作是： 設(shè)計文法符號帶有的綜合屬性；編制語義子程序。 翻譯的目標(biāo)是：三地址代碼。 2. 為了實現(xiàn)這種翻譯方法，要求： 詞法分析程序在返回所識別的單詞時，總帶有一個值（該值是數(shù)值或符號表中該單詞（標(biāo)識符）所在的地址或該單詞的內(nèi)部碼）。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,45,句法分析時遵循： i)將非終結(jié)符移入棧時，將其所帶的屬性一起入棧。 ii)使用產(chǎn)生式歸約后，調(diào)用與該產(chǎn)生式相關(guān)的語義子程序。 3. 注意：“當(dāng)非終結(jié)符出現(xiàn)在棧頂，那么與該非結(jié)符有關(guān)的中間代碼已經(jīng)生成” 。為

16、什么？,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,46,習(xí)題,P129，習(xí)題5 5.1 5.2,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,47,5.4 說明語句,一、增加存儲地址分配的說明語句的翻譯方案 對說明語句a,b,c:real 語義為： 設(shè)編譯程序用于存儲地址分配的變量是offset，將標(biāo)識符id的數(shù)據(jù)類型及由offset指出的存儲地址送入符號表相應(yīng)的登記項中。 考慮文法G: ;|i:|i, int|real|arraynumof|,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,48,令屬性.type、.width分別表示數(shù)據(jù)類型和該類型所需的存儲字節(jié)數(shù)，i.nam

17、e表示變量名（地址），num.val表示數(shù)值。 設(shè)過程enter(x,y,z)的功能為：將y,z送入x所指出的地址中。 屬性翻譯文法為： - offset:=0 ;- i:enter(i.name,.type,offset); offset:=offset+.width int.type:=int,.width:=4 real.type:=real,.width:=8,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,49,arraynumof1 .type:=array(num.val,1.type); .width:=num.val*1.width 1 .type:=pointer(1.t

18、ype); .width:=4,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,50,說明,這兒采用了“插因子”技術(shù)（以后還將討論“拆因子”）即將 改寫為等價的 的形式。為什么要這樣做呢？ 答案：為了在使用 歸約前插入語義動作offset:=0! 工作的原則是：歸約時調(diào)用相應(yīng)的語義子程序。 問題：采用教科書P115中的語義變量.bcode能夠解決嗎？ 例如：對句子a:int兩種方法的推導(dǎo)樹為：,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,51,如果不插入一個因子，則無法將offset初始化。 對數(shù)組arraynumof，這兒是一種最簡單的形式，省略了維數(shù)、上下界等。后面將詳細討論。 如

19、還要指出標(biāo)識符的種類（如變量、常量、過程等，可以在產(chǎn)生式i:加入語義動作.kind:=VAR;及enter(i.name,.kind,）,i,:,int,:,i,int,及,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,52,二、嵌套過程中的說明語句,過程說明語句的翻譯 過程（分程序）嵌套是程序設(shè)計語言中常見的結(jié)構(gòu)，一般有如下幾種形態(tài)： 過程嵌套、分程序嵌套，如ALGOL、Ada語言 過程嵌套、無分程序，如Pascal語言 過程不嵌套、分程序嵌套，如C語言 滿足不能交叉的原則，即只能平行或嵌套。 滿足先調(diào)用后返回的棧式原則。 變量作用域最近嵌套原則。 平行過程（分程序）可使用相同的存儲區(qū)。

20、,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,53,符號表的組織形式,對過程嵌套的語言，其符號表的組織（以過程為單位）應(yīng)滿足： 對數(shù)據(jù)對象的說明，應(yīng)核實該對象名是否已在當(dāng)前程序中說明過，若無則進入，否則報錯。 對數(shù)據(jù)對象的使用，是與其聯(lián)系的最內(nèi)層過程中說明的（不一定是當(dāng)前的），因此應(yīng)從本層逐層向外搜索。 進入過程應(yīng)做好初始化工作：重置offset、建立新的符號表等。 退出過程應(yīng)保證在本過程中的數(shù)據(jù)對象不會被訪問到。 因此：符號表組織的形式應(yīng)是棧式管理。見P88、89,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,54,過程說明的語義,在文法G中增加過程說明的產(chǎn)生式： proc i;1

21、; （注：省略了參數(shù)說明） 其語義為： 過程說明引入了新過程i,過程i局部于緊外層過程，因此i應(yīng)出現(xiàn)在緊外層過程的符號表中。 暫停緊外層過程的處理，為i過程創(chuàng)建新的符號表（初始化），將1中說明的數(shù)據(jù)對象登記在符號表中。 由于外層過程中的數(shù)據(jù)對象全局于i過程，因此i過程的符號表中有一指針指向緊外層過程符號表。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,55,編譯程序使用的數(shù)據(jù)結(jié)構(gòu)與語義過程： tblptr：棧式符號表，top(tblptr)棧頂指針 offset：棧式存儲區(qū)， top(offset)棧頂指針 語義函數(shù)mktable(x)的功能：創(chuàng)建新的符號表；指針參數(shù)x指向緊外層的符號表

22、，返回值是新的符號表的地址。 語義過程enter(t,n,ty,off)的功能：在t表的n地址中登記ty和off。 語義過程addwidth(t,w)的功能為：將w（該過程總的存儲量）記錄在t表的表頭。 語義過程enterproc(t,n,nt)的功能：將n、nt（過程名、符號表首址）登錄到t所指的緊外層過程符號表中。（彈出過程，返回到緊外層過程，使平行過程可使用相同的存儲區(qū)。 ）。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,56,說明語句的翻譯方案,嵌套過程中說明語句的翻譯方案： addwidth(top(tblptr),top(offset); pop(tblptr);pop(of

23、fset); t:=mktable(nil); push(t,tblptr);push(0,offset) ; proc i; t:=top(tblptr); addwidth(t,top(offset); pop(tblptr);pop(offset); enterproc(top(tblptr),i.name,t) ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,57, t:=mktable(top(tblptr); push(t,tblptr);push(0,offset) i: enter(top(tbltop),i.name,.type,top(offset); top(offs

24、et):=top(offset)+.width ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,58,5. 5 賦值語句,賦值語句的一般形式為a:=e;a是變量，e是表達式，即 a:= 一 簡單變量賦值語句的翻譯 考慮如下表達式文法G： 1 op 2 | -1 | (1)| i 其中op可以是+、-、*、/，增加了定義一目運算uminus的產(chǎn)生式 -1。若規(guī)定了優(yōu)先級、結(jié)合律，文法G是SLR（1）文法。 文法G的語義是十分清楚的。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,59,語義過程和屬性的說明,屬性i.name為簡單變量i的標(biāo)識符字符串，.place為表達式的值所分配的存儲位

25、置。 語義函數(shù)lookup（a）為名字a查符號表，若查到，返回a在符號表中的位置，若查不到，返回nil。 語義函數(shù)newtemp，每調(diào)用一次就返回一個可用的臨時變量地址。 語義過程emit（n1,n2,nm)，根據(jù)指定的參數(shù)，產(chǎn)生一個三地址語句并傳輸?shù)捷敵鑫募膎extq的位置，然后nextq自動加。 error( )是錯誤處理的語義過程.,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,60,簡單表達式翻譯方案, i := P:=lookup (i.name); if Pnil then emit(P, :=,.place) else error( ) 1 op 2 .place:=new

26、temp; emit(.place, :=,1.place, op,2.place) -1 .place:=newtemp; emit(.place,:=,uminus,1.place) (1) .place:=1.place i P:=lookup(i.name); if Pnil then .place:=P else error( ),2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,61,例1： 賦值語句 a:=-b*c+d 100：t1:=uminus b 101：t2:=t1*c 102：t3:=t2+d 103：a:=t3,:=,i.a,+,*,-,i.b,i.c,i.d,202

27、0/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,62,二、類型轉(zhuǎn)換,上述翻譯方案沒有考慮運算對象的類型，在后面的討論時也往往忽略類型檢查與轉(zhuǎn)換，這兒簡單給予討論。 對賦值語句，可考慮： 引入屬性i.type與.type，記錄表達式的類型。 引入一些類型轉(zhuǎn)換運算符，如：itor等，對程序設(shè)計語言允許的相容的類型間進行轉(zhuǎn)換。 進行類型檢查，若出現(xiàn)不允許的類型間的運算則報錯。 對語句 i := 翻譯時應(yīng)注意以i的類型為主。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,63,三、含數(shù)組元素的賦值語句的翻譯,在賦值語句和表達式中，如果除了簡單變量外還允許出現(xiàn)數(shù)組元素（即下標(biāo)變量），則為了引用這些下標(biāo)變

28、量，必須先計算出數(shù)組元素的地址。 下標(biāo)變量的地址計算 一般程序設(shè)計語言中數(shù)組定義有二類： 靜態(tài)數(shù)組：維數(shù)確定，上下界是常量，編譯時可以確定大小（體積）。如C、FORTRAN等 動態(tài)數(shù)組：維數(shù)確定，上下界是變量，運行時確定體積。 考慮較復(fù)雜的情況： 一個n維數(shù)組的一般形式為： array Al1: u1, l2:u2, , ln:un: integer,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,64,一個物理的存儲空間是一個一維的線性空間，一個n維的數(shù)組必須存儲在A0開始的一片連續(xù)的存儲空間中。因此，就有按行存放和按列存放兩種選擇，有些語言如PL/1，規(guī)定按行存放，有些語言如FORTRA

29、N，規(guī)定按列存放，不少語言則不作規(guī)定，由編譯程序決定取何種存儲方式。我們只討論按行存放。 一維數(shù)組 array al1:u1 設(shè)下標(biāo)變量ai所在的地址用 if Pnil then begin .array:=P;/得到信息向量表首址傳下去 .place:=.place;/賦初值 .dim:=1 end else error ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,72,1, t:=newtemp; k:=1.dim+1; emit(t:=1.place*limit(1.array,k); emit(t:=t+.place); .array:=1.array; /傳下去 .place

30、:=t; /傳下去 .dim:=k /傳下去 .place:=getc(.array); .offset:=.place ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,73,注意：這兒數(shù)組元素的數(shù)據(jù)類型的寬度W=1，當(dāng) W 1時，還需要生成 .offset:=.place*W的三地址語句。即為： .place:=getc(.array); .offset:=.place t:=newtemp emit(t, “ := ”,.offset,*,W) 例見P126 例2：對賦值語句a:=Ab,c+d的推導(dǎo)樹和三地址碼為：,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,74,:=,+,a,

31、d,c,A,b,100: t1:=b*20 101: t1:=t1+c 102: t2:=t1*4 103: t3:=a0t2 104: t4:=t3+d 105: a:=t4,問題： i. 為什么要傳遞？如何傳遞？ ii. 在歸約時，哪些屬性是可以使用的？為什么？,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,75,5.6 控制流語句,一、布爾表達式 考慮下列布爾表達式文法： and | or |not |()| id relop id|id|true|false 消除上述文法的二義性規(guī)則為： or、and為左結(jié)合的，優(yōu)先級為not，and，or。 relop是關(guān)系運算符，它們的優(yōu)先級均

32、相同，不允許結(jié)合。 算術(shù)運算符優(yōu)先級最高，關(guān)系運算符其次，布爾運算符最低。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,76,布爾表達式兩種基本作用： 參于邏輯運算，如 and 或not 。 作為控制語句的條件表達式， 如if then 或 while do 。 布爾表達式的兩種翻譯方法 數(shù)值表示法：以0表示false，1(非零）表示true，采用計算算術(shù)表達式的方法計算表達式的邏輯值。 解釋法（優(yōu)化方法）：由于對布爾表達式E1 or E2，只要E1為true則不管E2的值如何布爾表達式肯定為true，只有E1為false時，E2的值即為布爾表達式E的值。 將A or B 解釋為 if

33、A then true else B； 將A and B解釋為 if A then B else false； 將not A 解釋為 if A then false else true。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,77,二、數(shù)值法翻譯方案,基本思想：像算術(shù)表達式那樣計算布爾表達式的值。 引入and、or、not等運算符 對關(guān)系運算符確定它們計算后的邏輯值 例3：a or b and not c 的三地址碼為： 100: t1:=not c 101: t2:=b and t1 102: t3:=a or t2 而 ab 則為：100: if ab goto 103 101

34、: t:=0 102: goto 104 103: t:=1,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,78,翻譯方案為： 1 or 2 .place:=newtemp; emit(.place, “ :=”,1.place “or”,2.place) id1 relop id2 .place:=newtemp; emit(“if”,id1.place,relop.op,id2.place, “goto”,nextq+3); emit(.place, “ :=”,0); emit(“goto”, nextq+2); emit(.place, “ :=”,1) ,2020/7/29,華東

35、師范大學(xué)計算機科學(xué)技術(shù)系,79,三、解釋法的翻譯方案,基本思想與采用的技術(shù) 由于按解釋法布爾表達式的最終結(jié)果是真、假二個出口。因此，將所有的子表達式的真出口組成真出口鏈，用屬性.true指出真鏈鏈?zhǔn)?，用屬?false指出假鏈鏈?zhǔn)住?鏈的表示形式為： L1： goto 0; L2: goto L1; Ln: goto Ln-1,其中：Li為三地址語句序 號，0表示是鏈尾。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,80,語義函數(shù)makelist(x)的功能為：生成一根鏈，在第一個元素中填入x（x可以為空），并返回鏈?zhǔn)住?1.code,to 1.false,to 1.true,2.cod

36、e,.code,1.false:,to 2.false,to 2.true,to .true,to .false,見P113 例如：對產(chǎn)生式 1 or 2,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,81,按解釋法將所有的布爾運算解釋為轉(zhuǎn)移語句，為便于生成三地址碼，將if A then Tcode else Fcobe改寫為：if A goto Tcode goto Fcode 其中Tcode、Fcode是三地址語句序號，由nextq給出。特別地，序號0不存在。 采用“回填”技術(shù) 例如：對產(chǎn)生式 1 or 2, 1 or 2,.true,.false,2020/7/29,華東師范大學(xué)計算

37、機科學(xué)技術(shù)系,82,子表達式1中的.true轉(zhuǎn)向語句已生成，但2的代碼尚未生成，而且2將生成多少個三地址語句不可能確定，所以無法確定轉(zhuǎn)向何處！ 因此，只有當(dāng)確定了轉(zhuǎn)向點后“回填”。這由語義過程backpatch(x,y)來完成，其功能為：將x指出的鏈?zhǔn)椎逆溕纤械恼Z句的轉(zhuǎn)向點都填上y。 可表示為： while x0 do begin t:=getL(x); L(x):=y; x:=t end,getL(x)的功能取得x的轉(zhuǎn)向地址 L(x)是序號x的語句中g(shù)oto后的位置,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,83,合并技術(shù) 將各子表達式的真、假鏈合并成一條鏈，這由語義函數(shù)merge

38、(x,y)完成，其功能為：合并分別由x、y為鏈?zhǔn)椎亩l鏈，可描述為： T1:=y;T2:=getL(T1); while T2 0 do begin T1:=T2; T2:=getL(T1); end L(T2):=x；return(y);,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,84,插（拆）因子技術(shù) 對產(chǎn)生式 1 or 2 如1為假，則轉(zhuǎn)向點已經(jīng)確定，是2的第一個三地址語句序號（即計算2)，若同時歸約，將無法完成回填假鏈的工作。,注意：采用教科書P115中的語義變量.bcode的 方法為：在 i 加入 .bcode=nextq; 在1 or 2 直接使用 .bcode=nextq

39、,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,85,實現(xiàn),id .true:=makelist(nextq); emit(if id.place goto 0); .false:=makelist(nextq); emit(goto 0) 1 or 2 backpatch(1.false,.code); .true:=merge(1.true,2.true); .false:=2.false .code:=nextq,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,86,拆因子方法： 1 or backpatch(1.false,nextq); .true:=1.true 2 .tru

40、e:=merge(.true,2.true); .false:=2.false ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,87,例見P117 例4 用解釋法完成ab or cd and not ef 的翻譯，設(shè)nextq為100。,100: if ab goto 0 101: goto 102 102: if cd goto 104 103: goto 0 104:if ef goto 103 105: goto 100,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,88,四、控制流語句的翻譯,條件語句的翻譯 文法產(chǎn)生式為： (1) if then 1 (2) if then 1

41、 else 2 語義可描述為： (1) t:=e; if not t then goto L1 1 L1:,(2) t:=e; if not t then goto L1 1 goto L2; L1:2 L2:,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,89,由于布爾表達式可以按照數(shù)值法、解釋法來計算，因此，在控制結(jié)構(gòu)中可以分別采用兩種方法來設(shè)計翻譯方案。 數(shù)值法 讓帶有屬性.place表示的值，.type表示的類型。 根據(jù).place的值決定轉(zhuǎn)向。 具體實現(xiàn)留給大家，后面的討論是針對解釋法的。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,90,讓帶有屬性.true和.false

42、分別指出 真、假鏈?zhǔn)住?為了正確、及時地生成回填地址，采用插（拆） 因子的方法。,插因子方法 (1)if then 1 (2)if then 1 else (3) 2 (4) 拆因子方法 if then 1 else 2,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,91,條件語句的屬性文法,if then 1 bakpatch(.true,.code); .nextlist:=merge(.false,1.nextlist) (2) if then 1 else backpatch(.truet,.code); t:=makelist(nextq); emit(goto,0); .nex

43、tlist:=merge(1.nextlist,t); backpatch(.false,nextq) (3) 2 .nextlist:=merge(.nextlist,1.nextlist) (4) .code:=nextq,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,92,后續(xù)語句問題,控制流語句中有一個共同的問題，后續(xù)語句的轉(zhuǎn)向目標(biāo)。一般 if-then語句中的 goto L1 if-then-else語句中的 goto L2 不一定是緊跟在這些語句中的三地址代碼后的語句 例如： if 1 then if 2 then S1 else S2 else S3 為解決該問題，引入語句出

44、口鏈，讓屬性.nextlist指出的正確出口。由表示語句表的產(chǎn)生式 ; 歸約時完成。,goto L2,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,93, 1; backpatch(1.nextlist, .code); .nextlist:=.nextlist .nextlist:=.nextlist,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,94,不考慮后續(xù)語句(IF),if then 1 bakpatch(.true,.code); bakpatch(.false,nextq); (2) if then 1 else backpatch(.true,.code); .next

45、:=nextq; emit(goto,0); backpatch(.false,nextq) (3) 2 backpatch(.next,nextq (4) .code:=nextq,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,95,while語句的翻譯,產(chǎn)生式為： while do 1 語義描述為：L1: t:=e; if not t then goto L2; 1； goto L1; L2: 屬性文法為： while 1 do 2 1 backpatch(.true,2.code); backpatch(1.nextlist,1.code); emit(goto, 1.code);

46、.nextlist:=.false ,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,96,注意：這兒1、2的值是不同的。 問題：a) 采用拆因子的方法，屬性文法如何給出？ b) 如不考慮后續(xù)語句，屬性文法如何給出？ 例1：給出語句while x10 do x:=x+1;的句法制導(dǎo) 的翻譯過程。,while,.100,T=100F=101,do,.102,.,x,10,.x,:=,.x,.x,+,.1,x,x,1,100：if x10 goto 102 104: goto 100 101: goto 0（105） 105: 102: t:=x+1 103: x:=t,2020/7/29,華東

47、師范大學(xué)計算機科學(xué)技術(shù)系,97,五、轉(zhuǎn)向語句和語句標(biāo)號,轉(zhuǎn)向語句的產(chǎn)生式為: goto L稱為標(biāo)號L的應(yīng)用性出現(xiàn) L： 稱為標(biāo)號L的定義性出現(xiàn) 標(biāo)號的定義性出現(xiàn)可以在使用性出現(xiàn)的前或后。 若標(biāo)號的定義性出現(xiàn)在前，應(yīng)用性出現(xiàn)在后，即先定值后引用(稱為向后引用)，則填入符號表在前，生成轉(zhuǎn)向目標(biāo)在后，是容易實現(xiàn)的。若標(biāo)號的應(yīng)用性出現(xiàn)在前，定義性出現(xiàn)在后，即先引用后定值(稱為向前引用)，則應(yīng)用時不能從符號表中獲得標(biāo)號的值，只能生成待轉(zhuǎn)指令，待標(biāo)號的定義性出現(xiàn)后，得到轉(zhuǎn)向目標(biāo)后回填。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,98,標(biāo)號定義性出現(xiàn)只能一次（在同一程序段中），否則報錯。標(biāo)號的使用性

48、出現(xiàn)可以有多次，因此要建立轉(zhuǎn)向鏈。 注意goto語句中L的特殊性，L一般不是nextq的值，而是符號表的入口地址。而將轉(zhuǎn)向點的三地址語句序號存放在L的符號表登記項中。 在討論了符號表的結(jié)構(gòu)后將再仔細地討論轉(zhuǎn)向語句和語句標(biāo)號的實現(xiàn)。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,99,六、其他語句,僅討論for語句。 for語句的產(chǎn)生式為： for i:=1 to N do 1 其中i為循環(huán)變量，它的循環(huán)初值和終值分別為和N，都是常量，其語義為： i:=1; again: if i1; i:=i+1; goto again end,L:,L+1:,i:=1,if iN goto .nextl

49、ist,1.code,L+2:,M:,i:=i+1,M+1:,goto L+1,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,100,采用“拆因子”、“傳遞”技術(shù)，產(chǎn)生式為： for i:=1 to N do 1 相應(yīng)的屬性翻譯文法為： for i:=1 to N do p:=lookup(i.name); emit(p, :=, 1); .again:=nextq; emit(if p, , N, goto 0); .place:=p 1 emit(.place,:=.place,+,1); emit(goto, .again, nextq-2); backpatch(1.nextlis

50、t,); .nextlist:=.again,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,101,習(xí)題,P130 5.4 補充題 1. 對布爾表達式：（1）a OR b OR NOT c （2）（a OR NOT b） AND （NOT c OR d） 試分別用： 1）類似于算術(shù)表達式那樣求值的數(shù)值方案； 2）帶有真、假兩個出口的優(yōu)化方案； 給出三地址代碼的表示。 2. 寫出語句repeat1until的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,102,3. 考察Pascal語言中如下形式定義的for語句： for V:=1 to 2 do 1 若上述形式的for

51、語句等價于： begin t1:=1；t2:=2； if t1t2 then begin V:=t1； L1: 1； V:=SUCC(V)；/V的后繼 if Vt2 then goto L1； end end 試寫出符合上述規(guī)定的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,103,4.條件語句的產(chǎn)生式為： if then 1 else 2 語義可描述為: t:=; if t then goto L1; 1; goto L2; L1:2; L2: 1）讓帶有屬性.type（值為Bool指明是布爾表達式）和.val（值為零表示假，非零為真）。 2）讓帶有屬性.type和屬性.

52、false、.true（分別指出了假鏈與真鏈的鏈?zhǔn)椎刂罚?試分別給出符合上述語義規(guī)定的條件語句的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,104,7 符號表,符號表是編譯程序的一個重要組成部分。在詞法分析階段，當(dāng)識別出一個新的名字時，便將此名字登入符號表。與之關(guān)聯(lián)的其他屬性值，可在詞法分析、語法分析、語義分析及中間代碼生成等各階段陸續(xù)填入。而在編譯各階段將不斷地查詢、確認(rèn)這些信息。因此，對符號表的訪問相當(dāng)頻繁，所需的時間開銷占了編譯時間的不小的比例。如何組織好符號表，為符號表上的操作選擇好的算法，是提高編譯效率的不可忽視的問題。,2020/7/29,華東師范大學(xué)計算機

53、科學(xué)技術(shù)系,105,一、符號表的組織,抽象地看：符號表是一個對偶（實體名、實體描述）或（名字、信息）組成的集合。 名字：字符串（標(biāo)識符），信息索引的關(guān)鍵字 信息：由一系列的登記項所組成，記錄該實體 的全部信息。 信息的來源： 源程序的說明與定義。 程序中該實體出現(xiàn)的位置（上下文）。 隱含的約定。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,106,名字存儲形式：a)直接的、b)間接的,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,107,信息的主要內(nèi)容：各數(shù)據(jù)實體運行時的特征 種屬用type1表示 如：變量、標(biāo)號、數(shù)組 數(shù)據(jù)類型 type如：整型、實型、字符型 存儲單元大小 stor

54、age 以byte為單位 值 value 存儲地址 存儲區(qū)級別 storage-class 區(qū)分局部量、全局量等 已定義標(biāo)志 define 所屬過程的靜態(tài)嵌套深度 P-level 其他信息 如過程：形實參數(shù) 記錄：域名、存儲區(qū)大小,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,108,二、符號表的操作,將符號表視為一個抽象數(shù)據(jù)類型，則對該ADT所進行的操作主要有： 初始化 Init生成表及表格的初始化 結(jié)束化 Exit 結(jié)束后的善后處理 插入與搜索lookup(symbol) 在表中查找symbol，如存在，則返回地址，否則插入或報錯。 信息的登錄enter_desc(entry,desc

55、) 在entry處登錄信息desc。 信息的讀取 get_desc(entry) 將entry處的信息讀取并回送。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,109,實現(xiàn),符號表的結(jié)構(gòu)： 可以組織成一張大表，或者分成若干張小表。不同的表可以以不同的數(shù)據(jù)結(jié)構(gòu)組織。 數(shù)據(jù)結(jié)構(gòu) 線性表 棧式、隊式、樹式表 散列（Hash)表,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,110,三、分程序結(jié)構(gòu)語言的符號表,分程序語言又稱為塊結(jié)構(gòu)語言，類ALGOL語言，其基本特征是：過程嵌套、分程序嵌套。 滿足： 只能嵌套，不能交叉原則 分程序中可以定義、說明數(shù)據(jù)實體 最近嵌套規(guī)則 靜態(tài)作用域規(guī)則和嵌套樹

56、規(guī)則 對符號表及其操作的要求： 見前（第54張）,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,111,實現(xiàn) 采用棧式數(shù)據(jù)結(jié)構(gòu)組織符號表，對應(yīng)的操作為： Newlookup(symbol) 功能為54的i. Oldlookup(symbol) 功能為54的ii. Unitentry( ) 記錄緊外層最后一個地址，表示新一層的開始。 Unitexit( ) 根據(jù)保存的緊外層分程序地址，把本層彈出。 記：tabletop(tt)為符號表棧頂?shù)刂?unittop(ut)為分程序表棧頂?shù)刂?2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,112,例1： Unit A; a1,a2:int; Un

57、it B; a3,a4:int; end B; Unit C; a5,a6; end C; end A;,a) 進入B之前為：,tt,ut,b) 退出B之前為：,tt,ut,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,113,c) 退出C之前為：,tt,ut,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,114,如何計算、保存與存儲分配有關(guān)的信息 在分程序表中除保存tabletop外，還應(yīng)保存與存儲分配有關(guān)的信息，至少應(yīng)有： offset的當(dāng)時值（分配地址的工作單元） unitlevel(該分程序的靜態(tài)層號） 若存儲分配以過程為單位，即offset的值為0。則需要完成兩件事： 計算各

58、過程所需的最大存儲量pstorage值（所有局部于該過程的變量，數(shù)組是其信息向量表的大小） 平行分程序中定義的實體可以分配在同一存儲空間。如例1中的a5,a6與a3,a4。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,115,工作過程： 在過程的登記項中設(shè)立plevel、offset、tabletop、pstorage、unitlevel等內(nèi)容。 初始時置offset,pstorage,unitlevel為零。 進入分程序，保存當(dāng)時的tabletop,pstorage,offset, unitlevel+1的值。 退出分程序時，計算pstorage:=Max(pstorage,offse

59、t);恢復(fù)保存的tabletop,offset,unitlevel-1的值。 這樣，在結(jié)束分析，退出過程時，pstorage的值即為該過程的最大的存儲量。,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,116,例2：以過程為單位 存儲分配概況： procedure A Unit A1; L1 Unit A2; L2 end A2; R2 Unit A3; L3 end A3; R3 end A1; R1.,R2 L2 0,R3 L3 L1,Ps=R3 offset=L3 Ps=R2 offset=L3=L2 Ps=R2 offset=L2 Ps=0 offset=L2 Ps=0 offse

60、t=0,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,117,轉(zhuǎn)向語句、標(biāo)號的處理 問題：分程序結(jié)構(gòu)語言，標(biāo)號不僅可以先使用，后定義，而且可以從分程序中轉(zhuǎn)出，如何確定l：在哪一層？ 例如：Unit A; Unit B; goto l； end B; l: end A;,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,118,解決方法： 在標(biāo)號使用性出現(xiàn)（goto l;)時，調(diào)用newlookup(symbol);這樣只查當(dāng)前分程序，若未查到，則進入符號表。（不報錯） 在標(biāo)號的登記項中設(shè)立二個域declared和referenced用于指出標(biāo)號的定義和引用。初始時都為“No”，當(dāng)遇到goto l;時在ref中填“Yes”，當(dāng)遇到l：時在del中填“Yes”。 在退出分程序時，ref和del二個域中可能的情形為： del=“Yes”ref=“No” 表明：l在本層中定義，但未使用，報錯。 因為不允許轉(zhuǎn)入本層！,2020/7/29,華東師范大學(xué)計算機科學(xué)技術(shù)系,119,del=“No”ref=“Yes” 表明：本層無定義，但使用了l，goto l;應(yīng)轉(zhuǎn)至外層同名標(biāo)號，處理過程為： 將該登記項（可能有多個）勾鏈在緊外層分程序的符號表中。 若緊外層有同名標(biāo)號，則轉(zhuǎn)向確定，否則繼續(xù)1)。 del=“Yes”ref=“Yes” 本層定義，本層使用。,