華東師范大學計算機科學技術系.ppt

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

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

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

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

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

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

6、。難點自然就集中在如何寫這些語義子程序了。 采用屬性翻譯文法（屬性文法），這是一種形式化的語義分析方法。,2020/7/29,華東師范大學計算機科學技術系,9,結論,語法制導的翻譯方法就是在語法分析的同時（制導下）插入一系列的語義動作（由語義子程序提供），將源程序（單詞形式）翻譯成等價的中間代碼。 主要考慮自底向上句法分析的方法（在歸約時調用語義子程序），設計翻譯方案（形成屬性文法）。,2020/7/29,華東師范大學計算機科學技術系,10,5.2 中間語言,常見的中間語言有很多種，一般可單獨或混合使用。 一、后綴表示（逆波蘭表示） 是由波蘭數(shù)學家盧卡西維奇(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,華東師范大學計算機科學技術系,11,后綴表示可以機械地計算。 中綴表示可以機械地轉換為后綴表示。（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,華東師范大學計算機科學技術系,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ù)組中的下標 i2是S2的尾符號在S數(shù)組中的下標加1 BZ是運算符表

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

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

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

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

13、返回語句為return y，其中y為返回值。,2020/7/29,華東師范大學計算機科學技術系,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,華東師范大學計算機科學技術系,42,例2. S-屬性翻譯文法的例子,將中綴表達式翻譯為抽象語法樹的翻譯文法。 簡單

14、算術表達式文法G ： 1+ .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的值是樹結點的地址，函數(shù)Node(x,y,z)的功能是：申請一塊空間，將x、y、z寫入，并返回該空間的首地址。,2020/7/29,華東師范大學計算機科學技術系,43,對單詞串（c.3+c.9)*(c.2+c.15)經過分析與翻譯后轉換為：,,,,,,,,,,*,+,+,c.3,c.9,c.2,c.15,2020/

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

16、，那么與該非結符有關的中間代碼已經生成” 。為什么？,2020/7/29,華東師范大學計算機科學技術系,46,習題,P129，習題5 5.1 5.2,2020/7/29,華東師范大學計算機科學技術系,47,5.4 說明語句,一、增加存儲地址分配的說明語句的翻譯方案 對說明語句a,b,c:real 語義為： 設編譯程序用于存儲地址分配的變量是offset，將標識符id的數(shù)據(jù)類型及由offset指出的存儲地址送入符號表相應的登記項中。 考慮文法G: ;|i:|i, int|real|arraynumof|,2020/7/29,華東師范大學計算機科學技術系,48,令屬性.type、.width分

17、別表示數(shù)據(jù)類型和該類型所需的存儲字節(jié)數(shù)，i.name表示變量名（地址），num.val表示數(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,華東師范大學計算機科學技術系,49,arraynumof1 .type:=array(num.val,1.type); .width:=num.val*1.w

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

19、單的形式，省略了維數(shù)、上下界等。后面將詳細討論。 如還要指出標識符的種類（如變量、常量、過程等，可以在產生式i:加入語義動作.kind:=VAR;及enter(i.name,.kind,）,,,i,:,,int,,:,i,,,,,int,及,,,,,,,,,,,,,,,,,,,2020/7/29,華東師范大學計算機科學技術系,52,二、嵌套過程中的說明語句,過程說明語句的翻譯 過程（分程序）嵌套是程序設計語言中常見的結構，一般有如下幾種形態(tài)： 過程嵌套、分程序嵌套，如ALGOL、Ada語言 過程嵌套、無分程序，如Pascal語言 過程不嵌套、分程序嵌套，如C語言 滿足不能交叉的原則，即只能平行

20、或嵌套。 滿足先調用后返回的棧式原則。 變量作用域最近嵌套原則。 平行過程（分程序）可使用相同的存儲區(qū)。,2020/7/29,華東師范大學計算機科學技術系,53,符號表的組織形式,對過程嵌套的語言，其符號表的組織（以過程為單位）應滿足： 對數(shù)據(jù)對象的說明，應核實該對象名是否已在當前程序中說明過，若無則進入，否則報錯。 對數(shù)據(jù)對象的使用，是與其聯(lián)系的最內層過程中說明的（不一定是當前的），因此應從本層逐層向外搜索。 進入過程應做好初始化工作：重置offset、建立新的符號表等。 退出過程應保證在本過程中的數(shù)據(jù)對象不會被訪問到。 因此：符號表組織的形式應是棧式管理。見P88、89,2020/7/29

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

22、top(offset)棧頂指針 語義函數(shù)mktable(x)的功能：創(chuàng)建新的符號表；指針參數(shù)x指向緊外層的符號表，返回值是新的符號表的地址。 語義過程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,華東師范大學計算機科學技術系,56,說明語句的翻譯方案,嵌套過程中說明語句的翻譯

23、方案： addwidth(top(tblptr),top(offset)); pop(tblptr);pop(offset); 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,華東師范大學計算機科學技術系,57, t:=mktable(top(tblptr)); push(t,tblptr);pu

24、sh(0,offset) i: enter(top(tbltop),i.name,.type,top(offset); top(offset):=top(offset)+.width ,2020/7/29,華東師范大學計算機科學技術系,58,5. 5 賦值語句,賦值語句的一般形式為a:=e;a是變量，e是表達式，即 a:= 一 簡單變量賦值語句的翻譯 考慮如下表達式文法G： 1 op 2 | -1 | (1)| i 其中op可以是+、-、*、/，增加了定義一目運算uminus的產生式 -1。若規(guī)定了優(yōu)先級、結合律，文法G是SLR（1）文法。 文法G的語義是十分清楚的。,2020/7/29

25、,華東師范大學計算機科學技術系,59,語義過程和屬性的說明,屬性i.name為簡單變量i的標識符字符串，.place為表達式的值所分配的存儲位置。 語義函數(shù)lookup（a）為名字a查符號表，若查到，返回a在符號表中的位置，若查不到，返回nil。 語義函數(shù)newtemp，每調用一次就返回一個可用的臨時變量地址。 語義過程emit（n1,n2,nm)，根據(jù)指定的參數(shù)，產生一個三地址語句并傳輸?shù)捷敵鑫募膎extq的位置，然后nextq自動加。 error( )是錯誤處理的語義過程.,2020/7/29,華東師范大學計算機科學技術系,60,簡單表達式翻譯方案, i := P:=lookup (i

26、.name); if Pnil then emit(P, :=,.place) else error( ) 1 op 2 .place:=newtemp; 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,華東師范大學計算機科學技

27、術系,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,2020/7/29,華東師范大學計算機科學技術系,62,二、類型轉換,上述翻譯方案沒有考慮運算對象的類型，在后面的討論時也往往忽略類型檢查與轉換，這兒簡單給予討論。 對賦值語句，可考慮： 引入屬性i.type與.type，記錄表達式的類型。 引入一些類型轉換運算符，如：itor等，對程序設計語言允許的相容的類型間進行轉換。 進行類型檢查，

28、若出現(xiàn)不允許的類型間的運算則報錯。 對語句 i := 翻譯時應注意以i的類型為主。,2020/7/29,華東師范大學計算機科學技術系,63,三、含數(shù)組元素的賦值語句的翻譯,在賦值語句和表達式中，如果除了簡單變量外還允許出現(xiàn)數(shù)組元素（即下標變量），則為了引用這些下標變量，必須先計算出數(shù)組元素的地址。 下標變量的地址計算 一般程序設計語言中數(shù)組定義有二類： 靜態(tài)數(shù)組：維數(shù)確定，上下界是常量，編譯時可以確定大小（體積）。如C、FORTRAN等 動態(tài)數(shù)組：維數(shù)確定，上下界是變量，運行時確定體積。 考慮較復雜的情況： 一個n維數(shù)組的一般形式為： array Al1: u1, l2:u2, , ln:un

29、: integer,2020/7/29,華東師范大學計算機科學技術系,64,一個物理的存儲空間是一個一維的線性空間，一個n維的數(shù)組必須存儲在A0開始的一片連續(xù)的存儲空間中。因此，就有按行存放和按列存放兩種選擇，有些語言如PL/1，規(guī)定按行存放，有些語言如FORTRAN，規(guī)定按列存放，不少語言則不作規(guī)定，由編譯程序決定取何種存儲方式。我們只討論按行存放。 一維數(shù)組 array al1:u1 設下標變量ai所在的地址用 if Pnil then begin .array:=P;//得到信息向量表首址傳下去 .place:=.place;//賦初值 .dim:=1 end else err

30、or ,2020/7/29,華東師范大學計算機科學技術系,72,1, t:=newtemp; k:=1.dim+1; emit(t:=1.place*limit(1.array,k)); emit(t:=t+.place); .array:=1.array; //傳下去 .place:=t; //傳下去 .dim:=k //傳下去 .place:=getc(.array); .offset:=.place ,2020/7/29,華東師范大學計算機科學技術系,73,注意：這兒數(shù)組元素的數(shù)據(jù)類型的寬度W=1，當 W 1時，還需要生成 .offset:=.place*W的三地址語句。即為：

31、.place:=getc(.array); .offset:=.place t:=newtemp emit(t, “ := ”,.offset,*,W) 例見P126 例2：對賦值語句a:=Ab,c+d的推導樹和三地址碼為：,2020/7/29,華東師范大學計算機科學技術系,74,,,,,,,,:=,,,,,,,+,,,,,,a,,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. 為什么要傳遞？如何傳

32、遞？ ii. 在歸約時，哪些屬性是可以使用的？為什么？,2020/7/29,華東師范大學計算機科學技術系,75,5.6 控制流語句,一、布爾表達式 考慮下列布爾表達式文法： and | or |not |()| id relop id|id|true|false 消除上述文法的二義性規(guī)則為： or、and為左結合的，優(yōu)先級為not，and，or。 relop是關系運算符，它們的優(yōu)先級均相同，不允許結合。 算術運算符優(yōu)先級最高，關系運算符其次，布爾運算符最低。,2020/7/29,華東師范大學計算機科學技術系,76,布爾表達式兩種基本作用： 參于邏輯運算，如 and 或not 。 作為控制語句的

33、條件表達式， 如if then 或 while do 。 布爾表達式的兩種翻譯方法 數(shù)值表示法：以0表示false，1(非零）表示true，采用計算算術表達式的方法計算表達式的邏輯值。 解釋法（優(yōu)化方法）：由于對布爾表達式E1 or E2，只要E1為true則不管E2的值如何布爾表達式肯定為true，只有E1為false時，E2的值即為布爾表達式E的值。 將A or B 解釋為 if 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,

34、華東師范大學計算機科學技術系,77,二、數(shù)值法翻譯方案,基本思想：像算術表達式那樣計算布爾表達式的值。 引入and、or、not等運算符 對關系運算符確定它們計算后的邏輯值 例3：a or b and not c 的三地址碼為： 100: t1:=not c 101: t2:=b and t1 102: t3:=a or t2 而 a

35、ce, “ :=”,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,華東師范大學計算機科學技術系,79,三、解釋法的翻譯方案,基本思想與采用的技術 由于按解釋法布爾表達式的最終結果是真、假二個出口。因此，將所有的子表達式的真出口組成真出口鏈，用屬性.true指出真

36、鏈鏈首，用屬性.false指出假鏈鏈首。 鏈的表示形式為： L1： goto 0; L2: goto L1; Ln: goto Ln-1,其中：Li為三地址語句序 號，0表示是鏈尾。,,2020/7/29,華東師范大學計算機科學技術系,80,語義函數(shù)makelist(x)的功能為：生成一根鏈，在第一個元素中填入x（x可以為空），并返回鏈首。,,1.code,,,to 1.false,to 1.true,2.code,,,.code,1.false:,to 2.false,to 2.true,to .true,to .false,,見P113 例如：對產生式 1 or 2,2020/7/

37、29,華東師范大學計算機科學技術系,81,按解釋法將所有的布爾運算解釋為轉移語句，為便于生成三地址碼，將if A then Tcode else Fcobe改寫為：if A goto Tcode goto Fcode 其中Tcode、Fcode是三地址語句序號，由nextq給出。特別地，序號0不存在。 采用“回填”技術 例如：對產生式 1 or 2,, 1 or 2,.true,.false,,,,,,2020/7/29,華東師范大學計算機科學技術系,82,子表達式1中的.true轉向語句已生成，但2的代碼尚未生成，而且2將生成多少個三地址語句不可能確定，所以無法確定轉向何處！ 因此，只有當確

38、定了轉向點后“回填”。這由語義過程backpatch(x,y)來完成，其功能為：將x指出的鏈首的鏈上所有的語句的轉向點都填上y。 可表示為： while x0 do begin t:=getL(x); L(x):=y; x:=t end,,getL(x)的功能取得x的轉向地址 L(x)是序號x的語句中goto后的位置,2020/7/29,華東師范大學計算機科學技術系,83,合并技術 將各子表達式的真、假鏈合并成一條鏈，這由語義函數(shù)merge(x,y)完成，其功能為：合并分別由x、y為鏈首的二條鏈，可描述為： T1:=y;T2:=getL(T1); while T2 0 do begin

39、 T1:=T2; T2:=getL(T1); end L(T2):=x；return(y);,2020/7/29,華東師范大學計算機科學技術系,84,插（拆）因子技術 對產生式 1 or 2 如1為假，則轉向點已經確定，是2的第一個三地址語句序號（即計算2)，若同時歸約，將無法完成回填假鏈的工作。,注意：采用教科書P115中的語義變量.bcode的 方法為：在 i 加入 .bcode=nextq; 在1 or 2 直接使用 .bcode=nextq,2020/7/29,華東師范大學計算機科學技術系,85,實現(xiàn),id .true:=makelist(nextq); emit(if id

40、.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,華東師范大學計算機科學技術系,86,拆因子方法： 1 or backpatch(1.false,nextq); .true:=1.true 2 .true:=merge(.true,2.true); .false:=2.false ,2020/7/29,華東師范大學計算機科學技術系,87

41、,例見P117 例4 用解釋法完成a

42、e; if not t then goto L1 1 goto L2; L1:2 L2:,2020/7/29,華東師范大學計算機科學技術系,89,由于布爾表達式可以按照數(shù)值法、解釋法來計算，因此，在控制結構中可以分別采用兩種方法來設計翻譯方案。 數(shù)值法 讓帶有屬性.place表示的值，.type表示的類型。 根據(jù).place的值決定轉向。 具體實現(xiàn)留給大家，后面的討論是針對解釋法的。,2020/7/29,華東師范大學計算機科學技術系,90,讓帶有屬性.true和.false分別指出 真、假鏈首。 為了正確、及時地生成回填地址，采用插（拆） 因子的方法。,插因子方法 (1)if then

43、 1 (2)if then 1 else (3) 2 (4) 拆因子方法 if then 1 else 2,2020/7/29,華東師范大學計算機科學技術系,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); .nextlist:=merge(1.nextlist,t); backpatch(.false,next

44、q) (3) 2 .nextlist:=merge(.nextlist,1.nextlist) (4) .code:=nextq,2020/7/29,華東師范大學計算機科學技術系,92,后續(xù)語句問題,控制流語句中有一個共同的問題，后續(xù)語句的轉向目標。一般 if-then語句中的 goto L1 if-then-else語句中的 goto L2 不一定是緊跟在這些語句中的三地址代碼后的語句 例如： if 1 then if 2 then S1 else S2 else S3 為解決該問題，引入語句出口鏈，讓屬性.nextlist指出的正確出口。由表示語句表的產生式 ; 歸約時完成。

45、,,goto L2,2020/7/29,華東師范大學計算機科學技術系,93, 1; backpatch(1.nextlist, .code); .nextlist:=.nextlist .nextlist:=.nextlist,2020/7/29,華東師范大學計算機科學技術系,94,不考慮后續(xù)語句(IF),if then 1 bakpatch(.true,.code); bakpatch(.false,nextq); (2) if then 1 else backpatch(.true,.code); .next:=nextq; emit(goto,0); backpatch(

46、.false,nextq) (3) 2 backpatch(.next,nextq (4) .code:=nextq,2020/7/29,華東師范大學計算機科學技術系,95,while語句的翻譯,產生式為： 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); .nextlist:=.false ,2020/

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

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

49、），否則報錯。標號的使用性出現(xiàn)可以有多次，因此要建立轉向鏈。 注意goto語句中L的特殊性，L一般不是nextq的值，而是符號表的入口地址。而將轉向點的三地址語句序號存放在L的符號表登記項中。 在討論了符號表的結構后將再仔細地討論轉向語句和語句標號的實現(xiàn)。,2020/7/29,華東師范大學計算機科學技術系,99,六、其他語句,僅討論for語句。 for語句的產生式為： 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:

50、=1,if iN goto .nextlist,1.code,L+2:,M:,i:=i+1,M+1:,goto L+1,2020/7/29,華東師范大學計算機科學技術系,100,采用“拆因子”、“傳遞”技術，產生式為： for i:=1 to N do 1 相應的屬性翻譯文法為： 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(g

51、oto, .again, nextq-2); backpatch(1.nextlist,); .nextlist:=.again,2020/7/29,華東師范大學計算機科學技術系,101,習題,P130 5.4 補充題 1. 對布爾表達式：（1）a OR b OR NOT c （2）（a OR NOT b） AND （NOT c OR d） 試分別用： 1）類似于算術表達式那樣求值的數(shù)值方案； 2）帶有真、假兩個出口的優(yōu)化方案； 給出三地址代碼的表示。 2. 寫出語句repeat1until的屬性翻譯文法。,2020/7/29,華東師范大學計算機科學技術系,102,3. 考察P

52、ascal語言中如下形式定義的for語句： for V:=1 to 2 do 1 若上述形式的for語句等價于： 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,華東師范大學計算機科學技術系,103,4.條件語句的產生式為： if then 1 else 2 語義可描述為: t:=; if t then goto L1; 1; goto L2; L1:2; L2: 1）讓帶有屬性.typ

53、e（值為Bool指明是布爾表達式）和.val（值為零表示假，非零為真）。 2）讓帶有屬性.type和屬性.false、.true（分別指出了假鏈與真鏈的鏈首地址）。 試分別給出符合上述語義規(guī)定的條件語句的屬性翻譯文法。,2020/7/29,華東師范大學計算機科學技術系,104,7 符號表,符號表是編譯程序的一個重要組成部分。在詞法分析階段，當識別出一個新的名字時，便將此名字登入符號表。與之關聯(lián)的其他屬性值，可在詞法分析、語法分析、語義分析及中間代碼生成等各階段陸續(xù)填入。而在編譯各階段將不斷地查詢、確認這些信息。因此，對符號表的訪問相當頻繁，所需的時間開銷占了編譯時間的不小的比例。如何組織好符號

54、表，為符號表上的操作選擇好的算法，是提高編譯效率的不可忽視的問題。,2020/7/29,華東師范大學計算機科學技術系,105,一、符號表的組織,抽象地看：符號表是一個對偶（實體名、實體描述）或（名字、信息）組成的集合。 名字：字符串（標識符），信息索引的關鍵字 信息：由一系列的登記項所組成，記錄該實體 的全部信息。 信息的來源： 源程序的說明與定義。 程序中該實體出現(xiàn)的位置（上下文）。 隱含的約定。,2020/7/29,華東師范大學計算機科學技術系,106,名字存儲形式：a)直接的、b)間接的,2020/7/29,華東師范大學計算機科學技術系,107,信息的主要內容：各數(shù)據(jù)實體運行時的特征

55、 種屬用type1表示 如：變量、標號、數(shù)組 數(shù)據(jù)類型 type如：整型、實型、字符型 存儲單元大小 storage 以byte為單位 值 value 存儲地址 存儲區(qū)級別 storage-class 區(qū)分局部量、全局量等 已定義標志 define 所屬過程的靜態(tài)嵌套深度 P-level 其他信息 如過程：形實參數(shù) 記錄：域名、存儲區(qū)大小,2020/7/29,華東師范大學計算機科學技術系,108,二、符號表的操作,將符號表視為一個抽象數(shù)據(jù)類型，則對該ADT所進行的操作主要有： 初始化 Init生成表及表格的初始化 結束化 Exit 結束后的善后處理 插入與搜索lookup(symbol

56、) 在表中查找symbol，如存在，則返回地址，否則插入或報錯。 信息的登錄enter_desc(entry,desc) 在entry處登錄信息desc。 信息的讀取 get_desc(entry) 將entry處的信息讀取并回送。,2020/7/29,華東師范大學計算機科學技術系,109,實現(xiàn),符號表的結構： 可以組織成一張大表，或者分成若干張小表。不同的表可以以不同的數(shù)據(jù)結構組織。 數(shù)據(jù)結構 線性表 棧式、隊式、樹式表 散列（Hash)表,2020/7/29,華東師范大學計算機科學技術系,110,三、分程序結構語言的符號表,分程序語言又稱為塊結構語言，類ALGOL語言，其基本特征是：過程嵌

57、套、分程序嵌套。 滿足： 只能嵌套，不能交叉原則 分程序中可以定義、說明數(shù)據(jù)實體 最近嵌套規(guī)則 靜態(tài)作用域規(guī)則和嵌套樹規(guī)則 對符號表及其操作的要求： 見前（第54張）,2020/7/29,華東師范大學計算機科學技術系,111,實現(xiàn) 采用棧式數(shù)據(jù)結構組織符號表，對應的操作為： Newlookup(symbol) 功能為54的i. Oldlookup(symbol) 功能為54的ii. Unitentry( ) 記錄緊外層最后一個地址，表示新一層的開始。 Unitexit( ) 根據(jù)保存的緊外層分程序地址，把本層彈出。 記：tabletop(tt)為符號表棧頂?shù)刂?unittop(ut)為分程序表

58、棧頂?shù)刂?2020/7/29,華東師范大學計算機科學技術系,112,例1： Unit A; a1,a2:int; Unit 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,華東師范大學計算機科學技術系,113,c) 退出C之前為：,,,,,,,tt,,,ut,,2020/7/29,華東師范大學計算機科學技術系,114,如何計算、保存與存儲分配有關的信息 在分程序表中除保存tabletop外，還應保存與存儲分配有關的信息，至少應有

59、： offset的當時值（分配地址的工作單元） unitlevel(該分程序的靜態(tài)層號） 若存儲分配以過程為單位，即offset的值為0。則需要完成兩件事： 計算各過程所需的最大存儲量pstorage值（所有局部于該過程的變量，數(shù)組是其信息向量表的大小） 平行分程序中定義的實體可以分配在同一存儲空間。如例1中的a5,a6與a3,a4。,2020/7/29,華東師范大學計算機科學技術系,115,工作過程： 在過程的登記項中設立plevel、offset、tabletop、pstorage、unitlevel等內容。 初始時置offset,pstorage,unitlevel為零。 進入分程序，保

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

61、 L2 0,R3 L3 L1,Ps=R3 offset=L3 Ps=R2 offset=L3=L2 Ps=R2 offset=L2 Ps=0 offset=L2 Ps=0 offset=0,2020/7/29,華東師范大學計算機科學技術系,117,轉向語句、標號的處理 問題：分程序結構語言，標號不僅可以先使用，后定義，而且可以從分程序中轉出，如何確定l：在哪一層？ 例如：Unit A; Unit B; goto l； end B; l: end A;,2020/7/29,華東師范大學計算機科學技術系,118,解決方法： 在標號使用性出現(xiàn)（goto l;)時，調用newlookup(

62、symbol);這樣只查當前分程序，若未查到，則進入符號表。（不報錯） 在標號的登記項中設立二個域declared和referenced用于指出標號的定義和引用。初始時都為“No”，當遇到goto l;時在ref中填“Yes”，當遇到l：時在del中填“Yes”。 在退出分程序時，ref和del二個域中可能的情形為： del=“Yes”ref=“No” 表明：l在本層中定義，但未使用，報錯。 因為不允許轉入本層！,2020/7/29,華東師范大學計算機科學技術系,119,del=“No”ref=“Yes” 表明：本層無定義，但使用了l，goto l;應轉至外層同名標號，處理過程為： 將該登記項（可能有多個）勾鏈在緊外層分程序的符號表中。 若緊外層有同名標號，則轉向確定，否則繼續(xù)1)。 del=“Yes”ref=“Yes” 本層定義，本層使用。,