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

2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,1,第五章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成,5.1 概述 語(yǔ)義分析包含靜態(tài)語(yǔ)義檢查和語(yǔ)義識(shí)別，并在此基礎(chǔ)上對(duì)源程序（單詞串形式）進(jìn)行等價(jià)轉(zhuǎn)換，轉(zhuǎn)換為中間代碼（目標(biāo)代碼）。 在后面的討論中總是認(rèn)為詞法、語(yǔ)法分析已經(jīng)完成，讀入的是（語(yǔ)法正確）句子！而不關(guān)心用什么方法進(jìn)行語(yǔ)法分析的（以后主要討論自底向上的句法分析方法），關(guān)心的是如何在語(yǔ)法分析的同時(shí)正確地插入語(yǔ)義子程序進(jìn)行翻譯（語(yǔ)法制導(dǎo)翻譯） 。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,2,一、靜態(tài)語(yǔ)義檢查,稱(chēng)在編譯時(shí)刻進(jìn)行的語(yǔ)義檢查為靜態(tài)語(yǔ)義檢查，通常可包含如下內(nèi)容： 類(lèi)型檢查。 檢查運(yùn)算的合法性和參與運(yùn)算的運(yùn)算分量類(lèi)型的一致性（相容性）。必要時(shí)進(jìn)行相應(yīng)的類(lèi)型轉(zhuǎn)換。 (2) 控制流檢查。 以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)，如C語(yǔ)言中的break語(yǔ)句，需尋找包含它的最小的switch、while或for語(yǔ)句，方可找到轉(zhuǎn)向點(diǎn)，否則出錯(cuò)。不允許循環(huán)外控制轉(zhuǎn)入循環(huán)內(nèi)。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,3,(3) 有關(guān)名字的匹配檢查。 可以對(duì)某些程序段命名，該名字出現(xiàn)在程序段的開(kāi)始和結(jié)束處，如同語(yǔ)句括號(hào)一般，應(yīng)檢查它們的配對(duì)。 (4) 一致性檢查。 如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次（重復(fù)定義），case語(yǔ)句的標(biāo)號(hào)不能相同，枚舉類(lèi)型的元素不能重復(fù)，沒(méi)有定義數(shù)據(jù)類(lèi)型等。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,4,二、語(yǔ)法制導(dǎo)翻譯,例1：對(duì)算術(shù)表達(dá)式文法G的一個(gè)翻譯方案 +print “1” print “2” *print “3” print “4” ()print “5” iprint “6” 其中 括起的稱(chēng)為該產(chǎn)生式的語(yǔ)義子程序。 對(duì)輸入串W=(i+i)*i則W是G的一個(gè)句子。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,5,若采用自底向上的句法分析，規(guī)定當(dāng)用產(chǎn)生式歸約時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序，則翻譯結(jié)束后輸出 64264154632。 若采用自頂向下的句法分析，規(guī)定當(dāng)用產(chǎn)生式推導(dǎo)時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序，則翻譯結(jié)束后輸出 23451246466。 應(yīng)根據(jù)輸出（翻譯）目標(biāo)，配備適當(dāng)?shù)恼Z(yǔ)義子程序，這就是所要做的工作。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,6,三、翻譯要解決的問(wèn)題,翻譯成什么樣的目標(biāo)語(yǔ)言的代碼？ 將源語(yǔ)言程序翻譯成中間語(yǔ)言的程序。中間語(yǔ)言與機(jī)器無(wú)關(guān)，而語(yǔ)句顆粒度又與機(jī)器語(yǔ)言相當(dāng)，于是帶來(lái)了諸多好處： 編譯邏輯結(jié)構(gòu)簡(jiǎn)單明確，與機(jī)器相關(guān)的工作集中到目標(biāo)代碼生成階段，難度和工作量下降； 便于移植和維護(hù)。 利于優(yōu)化，代碼優(yōu)化將分成與機(jī)器無(wú)關(guān)的中間代碼優(yōu)化及與機(jī)器相關(guān)的目標(biāo)代碼優(yōu)化兩個(gè)階段，使優(yōu)化更有效。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,7,2. 何時(shí)進(jìn)行這種翻譯？,如例1所示，如果作為句柄所對(duì)應(yīng)的產(chǎn)生式，都配有一個(gè)相應(yīng)的翻譯子程序，則每當(dāng)按句柄歸約時(shí)，就調(diào)用相應(yīng)的翻譯子程序（語(yǔ)義子程序）完成局部的翻譯，則一個(gè)句子，一段代碼，按它們的歸約次序，將所有翻譯子程序依次執(zhí)行，就完成了這個(gè)句子、這段代碼的翻譯。這種翻譯與語(yǔ)法分析緊密相關(guān)，稱(chēng)之為語(yǔ)法制導(dǎo)翻譯：每當(dāng)歸約時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序，這就是翻譯的時(shí)機(jī)。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,8,3. 如何實(shí)現(xiàn)這種翻譯？,語(yǔ)法制導(dǎo)翻譯的關(guān)鍵，是為每個(gè)產(chǎn)生式編寫(xiě)翻譯子程序。例1中產(chǎn)生式所帶有的這種語(yǔ)義子程序只能輸出這類(lèi)數(shù)字串?，F(xiàn)在，要對(duì)一個(gè)有窮表示的文法的無(wú)窮多個(gè)語(yǔ)句，按所給出的語(yǔ)義子程序要完成不同語(yǔ)句的翻譯任務(wù)，輸出各自的目標(biāo)代碼。難點(diǎn)自然就集中在如何寫(xiě)這些語(yǔ)義子程序了。 采用屬性翻譯文法（屬性文法），這是一種形式化的語(yǔ)義分析方法。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,9,結(jié)論,語(yǔ)法制導(dǎo)的翻譯方法就是在語(yǔ)法分析的同時(shí)（制導(dǎo)下）插入一系列的語(yǔ)義動(dòng)作（由語(yǔ)義子程序提供），將源程序（單詞形式）翻譯成等價(jià)的中間代碼。 主要考慮自底向上句法分析的方法（在歸約時(shí)調(diào)用語(yǔ)義子程序），設(shè)計(jì)翻譯方案（形成屬性文法）。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,10,5.2 中間語(yǔ)言,常見(jiàn)的中間語(yǔ)言有很多種，一般可單獨(dú)或混合使用。 一、后綴表示（逆波蘭表示） 是由波蘭數(shù)學(xué)家盧卡西維奇(Lukasiewicz)提出的。它是將a op b中運(yùn)算量a、b依次寫(xiě)在算符op之前，即a b op，可以形式地給出表達(dá)式E的后綴表示的遞歸定義： (1) 如果E是變量或常數(shù)，則E的后綴表示即E本身。 (2) 如果E為E1 op E2形式，則它的后綴表示為E1 E2 op， 其中op是二元算符，E1，E2分別是E的后綴表示(op為一元運(yùn)算時(shí)E2為空)。 (3) 如果E為(E1)形式，則E1后綴表示即為E的后綴表示。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,11,后綴表示可以機(jī)械地計(jì)算。 中綴表示可以機(jī)械地轉(zhuǎn)換為后綴表示。（E.W.Dijkstra) 例2： (-a*b+c)-d的后綴表示為：a b* uminus c+d- 其中uminus表示一元運(yùn)算-。 后綴表示的推廣： O1，O2，On，其中是n元的運(yùn)算符，Oi為運(yùn)算對(duì)象 i=1,2n。 假定：后綴表示存放在一維數(shù)組S中，Si是一個(gè)單詞,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,12,例3：賦值語(yǔ)句 := 若V，E分別為、的后綴表示，賦值語(yǔ)句的后綴表示為：V E:= 如：A:=B*C+D則為ABC*D+:= 例4：條件語(yǔ)句 ifthenelse的后綴表示為：E i1 BZ S1 i2 BR S2 其中： E, S1, S2分別是，的后綴表示。 i1是S2的首符號(hào)在S數(shù)組中的下標(biāo) i2是S2的尾符號(hào)在S數(shù)組中的下標(biāo)加1 BZ是運(yùn)算符表示“零轉(zhuǎn)” BR是運(yùn)算符表示“無(wú)條件轉(zhuǎn)”,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,13,試將語(yǔ)句if x5 then x:=a;else x:=b;表示成逆波蘭表示 引入二元運(yùn)算符BZ、一元運(yùn)算符BR。逆波蘭表示 T,i,BZ的含義為若T的值為零，則轉(zhuǎn)到位置為i處執(zhí)行。i,BR的含義為無(wú)條件轉(zhuǎn)移到位置i處執(zhí)行。 假定上述語(yǔ)句的逆波蘭表示存放在一維數(shù)組S中，用數(shù)組的下標(biāo)表示轉(zhuǎn)向的位置。S數(shù)組可描述為：,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,14,二、圖(樹(shù)、抽象句法樹(shù)）表示,通過(guò)對(duì)分析樹(shù)的簡(jiǎn)化得到 例5：對(duì)算術(shù)表達(dá)式文法G，輸入串W=(i+i)*i 的分析樹(shù)見(jiàn)前。而樹(shù)表示為： 反映了一種運(yùn)算順序 內(nèi)結(jié)點(diǎn)表示運(yùn)算及運(yùn)算結(jié)果 見(jiàn)P82。亦可以使用無(wú)環(huán)路有向圖dag(directed acyclic graph)。,*,+,i,i,i,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,15,三、三地址代碼,三地址代碼語(yǔ)句的一般形式為：x:=y op z 其中x、y和z為名字、常量或編譯時(shí)產(chǎn)生的臨時(shí)變量，op為運(yùn)算符如定點(diǎn)運(yùn)算符、浮點(diǎn)運(yùn)算符、邏輯運(yùn)算符等。由于三地址語(yǔ)句只含一個(gè)運(yùn)算符，故多個(gè)算符組成的表達(dá)式必須用三地址語(yǔ)句序列表示。 例如表達(dá)式x+y*z的三地址代碼為： t1:=y*z t2:=x+t1 其中t1和t2是編譯時(shí)需要的臨時(shí)變量。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,16,三地址語(yǔ)句通常包含三個(gè)地址，兩個(gè)用來(lái)存放運(yùn)算對(duì)象，一個(gè)用來(lái)存放運(yùn)算結(jié)果。在實(shí)現(xiàn)時(shí)，用戶(hù)定義的名字將由指向符號(hào)表中該名字項(xiàng)的指針?biāo)妗?2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,17,四、三地址語(yǔ)句的種類(lèi),三地址語(yǔ)句有多種表示形式，常見(jiàn)的有： x:=y op z 賦值語(yǔ)句，其中op為二目的算術(shù)運(yùn)算符或邏輯運(yùn)算符。 (2) x:=op y 賦值語(yǔ)句，其中op為一目運(yùn)算符，如一目減uminus，邏輯否定not，移位算符及將定點(diǎn)數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)的類(lèi)型轉(zhuǎn)換符。 (3) x:=y復(fù)寫(xiě)語(yǔ)句，將y的值賦給x。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,18,(4) goto L 無(wú)條件轉(zhuǎn)移語(yǔ)句，下一個(gè)將被執(zhí)行的語(yǔ)句是標(biāo)號(hào)為L(zhǎng)的語(yǔ)句。 (5) if x relop y goto L 或 if x goto L 條件轉(zhuǎn)移語(yǔ)句, relop為關(guān)系運(yùn)算符如、=等，若x和y滿(mǎn)足關(guān)系relop就轉(zhuǎn)而執(zhí)行標(biāo)號(hào)為L(zhǎng)的語(yǔ)句，否則順序執(zhí)行本語(yǔ)句的下一語(yǔ)句。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,19,(6) param X 和 call P，n 過(guò)程調(diào)用語(yǔ)句，源程序中的過(guò)程調(diào)用語(yǔ)句 call P(x1, x2, , xn)可以用下列三地址代碼表示： param x1 param x2 param xn call P, n 其中整數(shù)n為實(shí)參個(gè)數(shù)。 過(guò)程返回語(yǔ)句為return y，其中y為返回值。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,20,(7) 變址賦值： x:=yi，表示將從地址y開(kāi)始的第i個(gè)地址單元的值賦給x。 xi:=y，表示將y的值賦給從地址x開(kāi)始的第i個(gè)地址單元。 (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é)計(jì)算機(jī)科學(xué)技術(shù)系,42,例2. S-屬性翻譯文法的例子,將中綴表達(dá)式翻譯為抽象語(yǔ)法樹(shù)的翻譯文法。 簡(jiǎn)單算術(shù)表達(dá)式文法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ù)結(jié)點(diǎn)的地址，函數(shù)Node(x,y,z)的功能是：申請(qǐng)一塊空間，將x、y、z寫(xiě)入，并返回該空間的首地址。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,43,對(duì)單詞串（c.3+c.9)*(c.2+c.15)經(jīng)過(guò)分析與翻譯后轉(zhuǎn)換為：,*,+,+,c.3,c.9,c.2,c.15,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,44,說(shuō)明,在本章的討論中，總使用S-屬性翻譯文法，采用自底向上的句法分析（不關(guān)心用哪種方法）。 主要的工作是： 設(shè)計(jì)文法符號(hào)帶有的綜合屬性；編制語(yǔ)義子程序。 翻譯的目標(biāo)是：三地址代碼。 2. 為了實(shí)現(xiàn)這種翻譯方法，要求： 詞法分析程序在返回所識(shí)別的單詞時(shí)，總帶有一個(gè)值（該值是數(shù)值或符號(hào)表中該單詞（標(biāo)識(shí)符）所在的地址或該單詞的內(nèi)部碼）。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,45,句法分析時(shí)遵循： i)將非終結(jié)符移入棧時(shí)，將其所帶的屬性一起入棧。 ii)使用產(chǎn)生式歸約后，調(diào)用與該產(chǎn)生式相關(guān)的語(yǔ)義子程序。 3. 注意：“當(dāng)非終結(jié)符出現(xiàn)在棧頂，那么與該非結(jié)符有關(guān)的中間代碼已經(jīng)生成” 。為什么？,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,46,習(xí)題,P129，習(xí)題5 5.1 5.2,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,47,5.4 說(shuō)明語(yǔ)句,一、增加存儲(chǔ)地址分配的說(shuō)明語(yǔ)句的翻譯方案 對(duì)說(shuō)明語(yǔ)句a,b,c:real 語(yǔ)義為： 設(shè)編譯程序用于存儲(chǔ)地址分配的變量是offset，將標(biāo)識(shí)符id的數(shù)據(jù)類(lèi)型及由offset指出的存儲(chǔ)地址送入符號(hào)表相應(yīng)的登記項(xiàng)中。 考慮文法G: ;|i:|i, int|real|arraynumof|,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,48,令屬性.type、.width分別表示數(shù)據(jù)類(lèi)型和該類(lèi)型所需的存儲(chǔ)字節(jié)數(shù)，i.name表示變量名（地址），num.val表示數(shù)值。 設(shè)過(guò)程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é)計(jì)算機(jī)科學(xué)技術(shù)系,49,arraynumof1 .type:=array(num.val,1.type); .width:=num.val*1.width 1 .type:=pointer(1.type); .width:=4,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,50,說(shuō)明,這兒采用了“插因子”技術(shù)（以后還將討論“拆因子”）即將 改寫(xiě)為等價(jià)的 的形式。為什么要這樣做呢？ 答案：為了在使用 歸約前插入語(yǔ)義動(dòng)作offset:=0! 工作的原則是：歸約時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序。 問(wèn)題：采用教科書(shū)P115中的語(yǔ)義變量.bcode能夠解決嗎？ 例如：對(duì)句子a:int兩種方法的推導(dǎo)樹(shù)為：,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,51,如果不插入一個(gè)因子，則無(wú)法將offset初始化。 對(duì)數(shù)組arraynumof，這兒是一種最簡(jiǎn)單的形式，省略了維數(shù)、上下界等。后面將詳細(xì)討論。 如還要指出標(biāo)識(shí)符的種類(lèi)（如變量、常量、過(guò)程等，可以在產(chǎn)生式i:加入語(yǔ)義動(dòng)作.kind:=VAR;及enter(i.name,.kind,）,i,:,int,:,i,int,及,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,52,二、嵌套過(guò)程中的說(shuō)明語(yǔ)句,過(guò)程說(shuō)明語(yǔ)句的翻譯 過(guò)程（分程序）嵌套是程序設(shè)計(jì)語(yǔ)言中常見(jiàn)的結(jié)構(gòu)，一般有如下幾種形態(tài)： 過(guò)程嵌套、分程序嵌套，如ALGOL、Ada語(yǔ)言 過(guò)程嵌套、無(wú)分程序，如Pascal語(yǔ)言 過(guò)程不嵌套、分程序嵌套，如C語(yǔ)言 滿(mǎn)足不能交叉的原則，即只能平行或嵌套。 滿(mǎn)足先調(diào)用后返回的棧式原則。 變量作用域最近嵌套原則。 平行過(guò)程（分程序）可使用相同的存儲(chǔ)區(qū)。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,53,符號(hào)表的組織形式,對(duì)過(guò)程嵌套的語(yǔ)言，其符號(hào)表的組織（以過(guò)程為單位）應(yīng)滿(mǎn)足： 對(duì)數(shù)據(jù)對(duì)象的說(shuō)明，應(yīng)核實(shí)該對(duì)象名是否已在當(dāng)前程序中說(shuō)明過(guò)，若無(wú)則進(jìn)入，否則報(bào)錯(cuò)。 對(duì)數(shù)據(jù)對(duì)象的使用，是與其聯(lián)系的最內(nèi)層過(guò)程中說(shuō)明的（不一定是當(dāng)前的），因此應(yīng)從本層逐層向外搜索。 進(jìn)入過(guò)程應(yīng)做好初始化工作：重置offset、建立新的符號(hào)表等。 退出過(guò)程應(yīng)保證在本過(guò)程中的數(shù)據(jù)對(duì)象不會(huì)被訪(fǎng)問(wèn)到。 因此：符號(hào)表組織的形式應(yīng)是棧式管理。見(jiàn)P88、89,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,54,過(guò)程說(shuō)明的語(yǔ)義,在文法G中增加過(guò)程說(shuō)明的產(chǎn)生式： proc i;1; （注：省略了參數(shù)說(shuō)明） 其語(yǔ)義為： 過(guò)程說(shuō)明引入了新過(guò)程i,過(guò)程i局部于緊外層過(guò)程，因此i應(yīng)出現(xiàn)在緊外層過(guò)程的符號(hào)表中。 暫停緊外層過(guò)程的處理，為i過(guò)程創(chuàng)建新的符號(hào)表（初始化），將1中說(shuō)明的數(shù)據(jù)對(duì)象登記在符號(hào)表中。 由于外層過(guò)程中的數(shù)據(jù)對(duì)象全局于i過(guò)程，因此i過(guò)程的符號(hào)表中有一指針指向緊外層過(guò)程符號(hào)表。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,55,編譯程序使用的數(shù)據(jù)結(jié)構(gòu)與語(yǔ)義過(guò)程： tblptr：棧式符號(hào)表，top(tblptr)棧頂指針 offset：棧式存儲(chǔ)區(qū)， top(offset)棧頂指針 語(yǔ)義函數(shù)mktable(x)的功能：創(chuàng)建新的符號(hào)表；指針參數(shù)x指向緊外層的符號(hào)表，返回值是新的符號(hào)表的地址。 語(yǔ)義過(guò)程enter(t,n,ty,off)的功能：在t表的n地址中登記ty和off。 語(yǔ)義過(guò)程addwidth(t,w)的功能為：將w（該過(guò)程總的存儲(chǔ)量）記錄在t表的表頭。 語(yǔ)義過(guò)程enterproc(t,n,nt)的功能：將n、nt（過(guò)程名、符號(hào)表首址）登錄到t所指的緊外層過(guò)程符號(hào)表中。（彈出過(guò)程，返回到緊外層過(guò)程，使平行過(guò)程可使用相同的存儲(chǔ)區(qū)。 ）。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,56,說(shuō)明語(yǔ)句的翻譯方案,嵌套過(guò)程中說(shuō)明語(yǔ)句的翻譯方案： 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,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,57, t:=mktable(top(tblptr); push(t,tblptr);push(0,offset) i: enter(top(tbltop),i.name,.type,top(offset); top(offset):=top(offset)+.width ,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,58,5. 5 賦值語(yǔ)句,賦值語(yǔ)句的一般形式為a:=e;a是變量，e是表達(dá)式，即 a:= 一 簡(jiǎn)單變量賦值語(yǔ)句的翻譯 考慮如下表達(dá)式文法G： 1 op 2 | -1 | (1)| i 其中op可以是+、-、*、/，增加了定義一目運(yùn)算uminus的產(chǎn)生式 -1。若規(guī)定了優(yōu)先級(jí)、結(jié)合律，文法G是SLR（1）文法。 文法G的語(yǔ)義是十分清楚的。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,59,語(yǔ)義過(guò)程和屬性的說(shuō)明,屬性i.name為簡(jiǎn)單變量i的標(biāo)識(shí)符字符串，.place為表達(dá)式的值所分配的存儲(chǔ)位置。 語(yǔ)義函數(shù)lookup（a）為名字a查符號(hào)表，若查到，返回a在符號(hào)表中的位置，若查不到，返回nil。 語(yǔ)義函數(shù)newtemp，每調(diào)用一次就返回一個(gè)可用的臨時(shí)變量地址。 語(yǔ)義過(guò)程emit（n1,n2,nm)，根據(jù)指定的參數(shù)，產(chǎn)生一個(gè)三地址語(yǔ)句并傳輸?shù)捷敵鑫募膎extq的位置，然后nextq自動(dòng)加。 error( )是錯(cuò)誤處理的語(yǔ)義過(guò)程.,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,60,簡(jiǎn)單表達(dá)式翻譯方案, i := P:=lookup (i.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,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,61,例1： 賦值語(yǔ)句 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,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,62,二、類(lèi)型轉(zhuǎn)換,上述翻譯方案沒(méi)有考慮運(yùn)算對(duì)象的類(lèi)型，在后面的討論時(shí)也往往忽略類(lèi)型檢查與轉(zhuǎn)換，這兒簡(jiǎn)單給予討論。 對(duì)賦值語(yǔ)句，可考慮： 引入屬性i.type與.type，記錄表達(dá)式的類(lèi)型。 引入一些類(lèi)型轉(zhuǎn)換運(yùn)算符，如：itor等，對(duì)程序設(shè)計(jì)語(yǔ)言允許的相容的類(lèi)型間進(jìn)行轉(zhuǎn)換。 進(jìn)行類(lèi)型檢查，若出現(xiàn)不允許的類(lèi)型間的運(yùn)算則報(bào)錯(cuò)。 對(duì)語(yǔ)句 i := 翻譯時(shí)應(yīng)注意以i的類(lèi)型為主。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,63,三、含數(shù)組元素的賦值語(yǔ)句的翻譯,在賦值語(yǔ)句和表達(dá)式中，如果除了簡(jiǎn)單變量外還允許出現(xiàn)數(shù)組元素（即下標(biāo)變量），則為了引用這些下標(biāo)變量，必須先計(jì)算出數(shù)組元素的地址。 下標(biāo)變量的地址計(jì)算 一般程序設(shè)計(jì)語(yǔ)言中數(shù)組定義有二類(lèi)： 靜態(tài)數(shù)組：維數(shù)確定，上下界是常量，編譯時(shí)可以確定大?。w積）。如C、FORTRAN等 動(dòng)態(tài)數(shù)組：維數(shù)確定，上下界是變量，運(yùn)行時(shí)確定體積。 考慮較復(fù)雜的情況： 一個(gè)n維數(shù)組的一般形式為： array Al1: u1, l2:u2, , ln:un: integer,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,64,一個(gè)物理的存儲(chǔ)空間是一個(gè)一維的線(xiàn)性空間，一個(gè)n維的數(shù)組必須存儲(chǔ)在A0開(kāi)始的一片連續(xù)的存儲(chǔ)空間中。因此，就有按行存放和按列存放兩種選擇，有些語(yǔ)言如PL/1，規(guī)定按行存放，有些語(yǔ)言如FORTRAN，規(guī)定按列存放，不少語(yǔ)言則不作規(guī)定，由編譯程序決定取何種存儲(chǔ)方式。我們只討論按行存放。 一維數(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é)計(jì)算機(jī)科學(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:=t; /傳下去 .dim:=k /傳下去 .place:=getc(.array); .offset:=.place ,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,73,注意：這兒數(shù)組元素的數(shù)據(jù)類(lèi)型的寬度W=1，當(dāng) W 1時(shí)，還需要生成 .offset:=.place*W的三地址語(yǔ)句。即為： .place:=getc(.array); .offset:=.place t:=newtemp emit(t, “ := ”,.offset,*,W) 例見(jiàn)P126 例2：對(duì)賦值語(yǔ)句a:=Ab,c+d的推導(dǎo)樹(shù)和三地址碼為：,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,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,問(wèn)題： i. 為什么要傳遞？如何傳遞？ ii. 在歸約時(shí)，哪些屬性是可以使用的？為什么？,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,75,5.6 控制流語(yǔ)句,一、布爾表達(dá)式 考慮下列布爾表達(dá)式文法： and | or |not |()| id relop id|id|true|false 消除上述文法的二義性規(guī)則為： or、and為左結(jié)合的，優(yōu)先級(jí)為not，and，or。 relop是關(guān)系運(yùn)算符，它們的優(yōu)先級(jí)均相同，不允許結(jié)合。 算術(shù)運(yùn)算符優(yōu)先級(jí)最高，關(guān)系運(yùn)算符其次，布爾運(yùn)算符最低。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,76,布爾表達(dá)式兩種基本作用： 參于邏輯運(yùn)算，如 and 或not 。 作為控制語(yǔ)句的條件表達(dá)式， 如if then 或 while do 。 布爾表達(dá)式的兩種翻譯方法 數(shù)值表示法：以0表示false，1(非零）表示true，采用計(jì)算算術(shù)表達(dá)式的方法計(jì)算表達(dá)式的邏輯值。 解釋法（優(yōu)化方法）：由于對(duì)布爾表達(dá)式E1 or E2，只要E1為true則不管E2的值如何布爾表達(dá)式肯定為true，只有E1為false時(shí)，E2的值即為布爾表達(dá)式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,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,77,二、數(shù)值法翻譯方案,基本思想：像算術(shù)表達(dá)式那樣計(jì)算布爾表達(dá)式的值。 引入and、or、not等運(yùn)算符 對(duì)關(guān)系運(yùn)算符確定它們計(jì)算后的邏輯值 例3：a or b and not c 的三地址碼為： 100: t1:=not c 101: t2:=b and t1 102: t3:=a or t2 而 a<b 則為：100: if a<b goto 103 101: t:=0 102: goto 104 103: t:=1,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(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,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,79,三、解釋法的翻譯方案,基本思想與采用的技術(shù) 由于按解釋法布爾表達(dá)式的最終結(jié)果是真、假二個(gè)出口。因此，將所有的子表達(dá)式的真出口組成真出口鏈，用屬性.true指出真鏈鏈?zhǔn)?，用屬?false指出假鏈鏈?zhǔn)住?鏈的表示形式為： L1： goto 0; L2: goto L1; Ln: goto Ln-1,其中：Li為三地址語(yǔ)句序 號(hào)，0表示是鏈尾。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,80,語(yǔ)義函數(shù)makelist(x)的功能為：生成一根鏈，在第一個(gè)元素中填入x（x可以為空），并返回鏈?zhǔn)住?1.code,to 1.false,to 1.true,2.code,.code,1.false:,to 2.false,to 2.true,to .true,to .false,見(jiàn)P113 例如：對(duì)產(chǎn)生式 1 or 2,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,81,按解釋法將所有的布爾運(yùn)算解釋為轉(zhuǎn)移語(yǔ)句，為便于生成三地址碼，將if A then Tcode else Fcobe改寫(xiě)為：if A goto Tcode goto Fcode 其中Tcode、Fcode是三地址語(yǔ)句序號(hào)，由nextq給出。特別地，序號(hào)0不存在。 采用“回填”技術(shù) 例如：對(duì)產(chǎn)生式 1 or 2, 1 or 2,.true,.false,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,82,子表達(dá)式1中的.true轉(zhuǎn)向語(yǔ)句已生成，但2的代碼尚未生成，而且2將生成多少個(gè)三地址語(yǔ)句不可能確定，所以無(wú)法確定轉(zhuǎn)向何處！ 因此，只有當(dāng)確定了轉(zhuǎn)向點(diǎn)后“回填”。這由語(yǔ)義過(guò)程backpatch(x,y)來(lái)完成，其功能為：將x指出的鏈?zhǔn)椎逆溕纤械恼Z(yǔ)句的轉(zhuǎn)向點(diǎn)都填上y。 可表示為： while x0 do begin t:=getL(x); L(x):=y; x:=t end,getL(x)的功能取得x的轉(zhuǎn)向地址 L(x)是序號(hào)x的語(yǔ)句中g(shù)oto后的位置,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,83,合并技術(shù) 將各子表達(dá)式的真、假鏈合并成一條鏈，這由語(yǔ)義函數(shù)merge(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é)計(jì)算機(jī)科學(xué)技術(shù)系,84,插（拆）因子技術(shù) 對(duì)產(chǎn)生式 1 or 2 如1為假，則轉(zhuǎn)向點(diǎn)已經(jīng)確定，是2的第一個(gè)三地址語(yǔ)句序號(hào)（即計(jì)算2)，若同時(shí)歸約，將無(wú)法完成回填假鏈的工作。,注意：采用教科書(shū)P115中的語(yǔ)義變量.bcode的 方法為：在 i 加入 .bcode=nextq; 在1 or 2 直接使用 .bcode=nextq,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,85,實(shí)現(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é)計(jì)算機(jī)科學(xué)技術(shù)系,86,拆因子方法： 1 or backpatch(1.false,nextq); .true:=1.true 2 .true:=merge(.true,2.true); .false:=2.false ,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,87,例見(jiàn)P117 例4 用解釋法完成a<b or c<d and not e<f 的翻譯，設(shè)nextq為100。,100: if a<b goto 0 101: goto 102 102: if c<d goto 104 103: goto 0 104:if e<f goto 103 105: goto 100,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,88,四、控制流語(yǔ)句的翻譯,條件語(yǔ)句的翻譯 文法產(chǎn)生式為： (1) if then 1 (2) if then 1 else 2 語(yǔ)義可描述為： (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é)計(jì)算機(jī)科學(xué)技術(shù)系,89,由于布爾表達(dá)式可以按照數(shù)值法、解釋法來(lái)計(jì)算，因此，在控制結(jié)構(gòu)中可以分別采用兩種方法來(lái)設(shè)計(jì)翻譯方案。 數(shù)值法 讓帶有屬性.place表示的值，.type表示的類(lèi)型。 根據(jù).place的值決定轉(zhuǎn)向。 具體實(shí)現(xiàn)留給大家，后面的討論是針對(duì)解釋法的。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,90,讓帶有屬性.true和.false分別指出 真、假鏈?zhǔn)住?為了正確、及時(shí)地生成回填地址，采用插（拆） 因子的方法。,插因子方法 (1)if then 1 (2)if then 1 else (3) 2 (4) 拆因子方法 if then 1 else 2,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,91,條件語(yǔ)句的屬性文法,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,nextq) (3) 2 .nextlist:=merge(.nextlist,1.nextlist) (4) .code:=nextq,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,92,后續(xù)語(yǔ)句問(wèn)題,控制流語(yǔ)句中有一個(gè)共同的問(wèn)題，后續(xù)語(yǔ)句的轉(zhuǎn)向目標(biāo)。一般 if-then語(yǔ)句中的 goto L1 if-then-else語(yǔ)句中的 goto L2 不一定是緊跟在這些語(yǔ)句中的三地址代碼后的語(yǔ)句 例如： if 1 then if 2 then S1 else S2 else S3 為解決該問(wèn)題，引入語(yǔ)句出口鏈，讓屬性.nextlist指出的正確出口。由表示語(yǔ)句表的產(chǎn)生式 ; 歸約時(shí)完成。,goto L2,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,93, 1; backpatch(1.nextlist, .code); .nextlist:=.nextlist .nextlist:=.nextlist,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,94,不考慮后續(xù)語(yǔ)句(IF),if then 1 bakpatch(.true,.code); bakpatch(.false,nextq); (2) if then 1 else backpatch(.true,.code); .next:=nextq; emit(goto,0); backpatch(.false,nextq) (3) 2 backpatch(.next,nextq (4) .code:=nextq,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,95,while語(yǔ)句的翻譯,產(chǎn)生式為： while do 1 語(yǔ)義描述為：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/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,96,注意：這兒1、2的值是不同的。 問(wèn)題：a) 采用拆因子的方法，屬性文法如何給出？ b) 如不考慮后續(xù)語(yǔ)句，屬性文法如何給出？ 例1：給出語(yǔ)句while x<10 do x:=x+1;的句法制導(dǎo) 的翻譯過(guò)程。,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,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,97,五、轉(zhuǎn)向語(yǔ)句和語(yǔ)句標(biāo)號(hào),轉(zhuǎn)向語(yǔ)句的產(chǎn)生式為: goto L稱(chēng)為標(biāo)號(hào)L的應(yīng)用性出現(xiàn) L： 稱(chēng)為標(biāo)號(hào)L的定義性出現(xiàn) 標(biāo)號(hào)的定義性出現(xiàn)可以在使用性出現(xiàn)的前或后。 若標(biāo)號(hào)的定義性出現(xiàn)在前，應(yīng)用性出現(xiàn)在后，即先定值后引用(稱(chēng)為向后引用)，則填入符號(hào)表在前，生成轉(zhuǎn)向目標(biāo)在后，是容易實(shí)現(xiàn)的。若標(biāo)號(hào)的應(yīng)用性出現(xiàn)在前，定義性出現(xiàn)在后，即先引用后定值(稱(chēng)為向前引用)，則應(yīng)用時(shí)不能從符號(hào)表中獲得標(biāo)號(hào)的值，只能生成待轉(zhuǎn)指令，待標(biāo)號(hào)的定義性出現(xiàn)后，得到轉(zhuǎn)向目標(biāo)后回填。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,98,標(biāo)號(hào)定義性出現(xiàn)只能一次（在同一程序段中），否則報(bào)錯(cuò)。標(biāo)號(hào)的使用性出現(xiàn)可以有多次，因此要建立轉(zhuǎn)向鏈。 注意goto語(yǔ)句中L的特殊性，L一般不是nextq的值，而是符號(hào)表的入口地址。而將轉(zhuǎn)向點(diǎn)的三地址語(yǔ)句序號(hào)存放在L的符號(hào)表登記項(xiàng)中。 在討論了符號(hào)表的結(jié)構(gòu)后將再仔細(xì)地討論轉(zhuǎn)向語(yǔ)句和語(yǔ)句標(biāo)號(hào)的實(shí)現(xiàn)。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,99,六、其他語(yǔ)句,僅討論for語(yǔ)句。 for語(yǔ)句的產(chǎn)生式為： for i:=1 to N do 1 其中i為循環(huán)變量，它的循環(huán)初值和終值分別為和N，都是常量，其語(yǔ)義為： i:=1; again: if i1; i:=i+1; goto again end,L:,L+1:,i:=1,if iN goto .nextlist,1.code,L+2:,M:,i:=i+1,M+1:,goto L+1,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(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.nextlist,); .nextlist:=.again,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,101,習(xí)題,P130 5.4 補(bǔ)充題 1. 對(duì)布爾表達(dá)式：（1）a OR b OR NOT c （2）（a OR NOT b） AND （NOT c OR d） 試分別用： 1）類(lèi)似于算術(shù)表達(dá)式那樣求值的數(shù)值方案； 2）帶有真、假兩個(gè)出口的優(yōu)化方案； 給出三地址代碼的表示。 2. 寫(xiě)出語(yǔ)句repeat1until的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,102,3. 考察Pascal語(yǔ)言中如下形式定義的for語(yǔ)句： for V:=1 to 2 do 1 若上述形式的for語(yǔ)句等價(jià)于： begin t1:=1；t2:=2； if t1t2 then begin V:=t1； L1: 1； V:=SUCC(V)；/V的后繼 if Vt2 then goto L1； end end 試寫(xiě)出符合上述規(guī)定的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,103,4.條件語(yǔ)句的產(chǎn)生式為： if then 1 else 2 語(yǔ)義可描述為: t:=; if t then goto L1; 1; goto L2; L1:2; L2: 1）讓帶有屬性.type（值為Bool指明是布爾表達(dá)式）和.val（值為零表示假，非零為真）。 2）讓帶有屬性.type和屬性.false、.true（分別指出了假鏈與真鏈的鏈?zhǔn)椎刂罚?試分別給出符合上述語(yǔ)義規(guī)定的條件語(yǔ)句的屬性翻譯文法。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,104,7 符號(hào)表,符號(hào)表是編譯程序的一個(gè)重要組成部分。在詞法分析階段，當(dāng)識(shí)別出一個(gè)新的名字時(shí)，便將此名字登入符號(hào)表。與之關(guān)聯(lián)的其他屬性值，可在詞法分析、語(yǔ)法分析、語(yǔ)義分析及中間代碼生成等各階段陸續(xù)填入。而在編譯各階段將不斷地查詢(xún)、確認(rèn)這些信息。因此，對(duì)符號(hào)表的訪(fǎng)問(wèn)相當(dāng)頻繁，所需的時(shí)間開(kāi)銷(xiāo)占了編譯時(shí)間的不小的比例。如何組織好符號(hào)表，為符號(hào)表上的操作選擇好的算法，是提高編譯效率的不可忽視的問(wèn)題。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,105,一、符號(hào)表的組織,抽象地看：符號(hào)表是一個(gè)對(duì)偶（實(shí)體名、實(shí)體描述）或（名字、信息）組成的集合。 名字：字符串（標(biāo)識(shí)符），信息索引的關(guān)鍵字 信息：由一系列的登記項(xiàng)所組成，記錄該實(shí)體 的全部信息。 信息的來(lái)源： 源程序的說(shuō)明與定義。 程序中該實(shí)體出現(xiàn)的位置（上下文）。 隱含的約定。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,106,名字存儲(chǔ)形式：a)直接的、b)間接的,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,107,信息的主要內(nèi)容：各數(shù)據(jù)實(shí)體運(yùn)行時(shí)的特征 種屬用type1表示 如：變量、標(biāo)號(hào)、數(shù)組 數(shù)據(jù)類(lèi)型 type如：整型、實(shí)型、字符型 存儲(chǔ)單元大小 storage 以byte為單位 值 value 存儲(chǔ)地址 存儲(chǔ)區(qū)級(jí)別 storage-class 區(qū)分局部量、全局量等 已定義標(biāo)志 define 所屬過(guò)程的靜態(tài)嵌套深度 P-level 其他信息 如過(guò)程：形實(shí)參數(shù) 記錄：域名、存儲(chǔ)區(qū)大小,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,108,二、符號(hào)表的操作,將符號(hào)表視為一個(gè)抽象數(shù)據(jù)類(lèi)型，則對(duì)該ADT所進(jìn)行的操作主要有： 初始化 Init生成表及表格的初始化 結(jié)束化 Exit 結(jié)束后的善后處理 插入與搜索lookup(symbol) 在表中查找symbol，如存在，則返回地址，否則插入或報(bào)錯(cuò)。 信息的登錄enter_desc(entry,desc) 在entry處登錄信息desc。 信息的讀取 get_desc(entry) 將entry處的信息讀取并回送。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,109,實(shí)現(xiàn),符號(hào)表的結(jié)構(gòu)： 可以組織成一張大表，或者分成若干張小表。不同的表可以以不同的數(shù)據(jù)結(jié)構(gòu)組織。 數(shù)據(jù)結(jié)構(gòu) 線(xiàn)性表 棧式、隊(duì)式、樹(shù)式表 散列（Hash)表,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,110,三、分程序結(jié)構(gòu)語(yǔ)言的符號(hào)表,分程序語(yǔ)言又稱(chēng)為塊結(jié)構(gòu)語(yǔ)言，類(lèi)ALGOL語(yǔ)言，其基本特征是：過(guò)程嵌套、分程序嵌套。 滿(mǎn)足： 只能嵌套，不能交叉原則 分程序中可以定義、說(shuō)明數(shù)據(jù)實(shí)體 最近嵌套規(guī)則 靜態(tài)作用域規(guī)則和嵌套樹(shù)規(guī)則 對(duì)符號(hào)表及其操作的要求： 見(jiàn)前（第54張）,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,111,實(shí)現(xiàn) 采用棧式數(shù)據(jù)結(jié)構(gòu)組織符號(hào)表，對(duì)應(yīng)的操作為： Newlookup(symbol) 功能為54的i. Oldlookup(symbol) 功能為54的ii. Unitentry( ) 記錄緊外層最后一個(gè)地址，表示新一層的開(kāi)始。 Unitexit( ) 根據(jù)保存的緊外層分程序地址，把本層彈出。 記：tabletop(tt)為符號(hào)表?xiàng)ｍ數(shù)刂?unittop(ut)為分程序表?xiàng)ｍ數(shù)刂?2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,112,例1： Unit A; a1,a2:int; Unit B; a3,a4:int; end B; Unit C; a5,a6; end C; end A;,a) 進(jìn)入B之前為：,tt,ut,b) 退出B之前為：,tt,ut,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,113,c) 退出C之前為：,tt,ut,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,114,如何計(jì)算、保存與存儲(chǔ)分配有關(guān)的信息 在分程序表中除保存tabletop外，還應(yīng)保存與存儲(chǔ)分配有關(guān)的信息，至少應(yīng)有： offset的當(dāng)時(shí)值（分配地址的工作單元） unitlevel(該分程序的靜態(tài)層號(hào)） 若存儲(chǔ)分配以過(guò)程為單位，即offset的值為0。則需要完成兩件事： 計(jì)算各過(guò)程所需的最大存儲(chǔ)量pstorage值（所有局部于該過(guò)程的變量，數(shù)組是其信息向量表的大小） 平行分程序中定義的實(shí)體可以分配在同一存儲(chǔ)空間。如例1中的a5,a6與a3,a4。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,115,工作過(guò)程： 在過(guò)程的登記項(xiàng)中設(shè)立plevel、offset、tabletop、pstorage、unitlevel等內(nèi)容。 初始時(shí)置offset,pstorage,unitlevel為零。 進(jìn)入分程序，保存當(dāng)時(shí)的tabletop,pstorage,offset, unitlevel+1的值。 退出分程序時(shí)，計(jì)算pstorage:=Max(pstorage,offset);恢復(fù)保存的tabletop,offset,unitlevel-1的值。 這樣，在結(jié)束分析，退出過(guò)程時(shí)，pstorage的值即為該過(guò)程的最大的存儲(chǔ)量。,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,116,例2：以過(guò)程為單位 存儲(chǔ)分配概況： 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 offset=0,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,117,轉(zhuǎn)向語(yǔ)句、標(biāo)號(hào)的處理 問(wèn)題：分程序結(jié)構(gòu)語(yǔ)言，標(biāo)號(hào)不僅可以先使用，后定義，而且可以從分程序中轉(zhuǎn)出，如何確定l：在哪一層？ 例如：Unit A; Unit B; goto l； end B; l: end A;,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,118,解決方法： 在標(biāo)號(hào)使用性出現(xiàn)（goto l;)時(shí)，調(diào)用newlookup(symbol);這樣只查當(dāng)前分程序，若未查到，則進(jìn)入符號(hào)表。（不報(bào)錯(cuò)） 在標(biāo)號(hào)的登記項(xiàng)中設(shè)立二個(gè)域declared和referenced用于指出標(biāo)號(hào)的定義和引用。初始時(shí)都為“No”，當(dāng)遇到goto l;時(shí)在ref中填“Yes”，當(dāng)遇到l：時(shí)在del中填“Yes”。 在退出分程序時(shí)，ref和del二個(gè)域中可能的情形為： del=“Yes”ref=“No” 表明：l在本層中定義，但未使用，報(bào)錯(cuò)。 因?yàn)椴辉试S轉(zhuǎn)入本層！,2020/7/29,華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系,119,del=“No”ref=“Yes” 表明：本層無(wú)定義，但使用了l，goto l;應(yīng)轉(zhuǎn)至外層同名標(biāo)號(hào)，處理過(guò)程為： 將該登記項(xiàng)（可能有多個(gè)）勾鏈在緊外層分程序的符號(hào)表中。 若緊外層有同名標(biāo)號(hào)，則轉(zhuǎn)向確定，否則繼續(xù)1)。 del=“Yes”ref=“Yes” 本層定義，本層使用。,