第四章語法制導翻譯生成中間代碼

第四章語法制導翻譯生成中間代碼第一頁，共一百一十七頁，編輯于2023年，星期五24.1語法制導翻譯簡介語法與語義語法與語義的關系語法是指語言的結構、即語言的“樣子”；語義是指附著于語言結構上的實際含意，即語言的“意義”。語義不能離開語法獨立存在；語義遠比語法復雜；同一語言結構可包含多種含意，不同語言結構可表示相同含意；語法與語義之間沒有明確的界線。[例1]貓吃老鼠與老鼠吃貓，曬被子與曬太陽[例2]程序設計語言中的分情況結構第二頁，共一百一十七頁，編輯于2023年，星期五34.1語法制導翻譯簡介caseconditioniscase1:stat1;case2:stat2;...endcase;語義分析的兩個作用檢查是否結構正確的句子所表示的意思也合法；執(zhí)行規(guī)定的語義動作，如：表達式求值符號表填寫中間代碼生成等語義分析的方法 語法制導翻譯switch(condition){casecondition1:stat1;casecondition2:stat2; ...}

break;break;第三頁，共一百一十七頁，編輯于2023年，星期五44.1語法制導翻譯簡介屬性與語義規(guī)則語法制導翻譯的基本思想通俗地講，以語法分析為基礎，伴隨語法分析的各個步驟，執(zhí)行相應的語義動作。具體方法：將文法符號所代表的語言結構的意思，用附著于該文法符號的屬性表示；用語義規(guī)則規(guī)定產生式所代表的語言結構之間的關系（即屬性之間的關系），即用語義規(guī)則實現屬性計算。語義規(guī)則的執(zhí)行：在語法分析的適當時刻（如推導或歸約）執(zhí)行附著在對應產生式上的語義規(guī)則，以實現對語言結構語義的處理，如計算、查填符號表、生成中間代碼、發(fā)布出錯信息等。第四頁，共一百一十七頁，編輯于2023年，星期五54.1語法制導翻譯簡介屬性的抽象表示.attr如：E.val（值），E.type（類型），E.code（代碼序列），

E.place（存儲空間）對文法的約定 只關注語法分析基礎上的語義處理，忽略語法分析。為了簡單，討論的文法一般為二義文法。默認解決二義的方法是規(guī)定常規(guī)意義下的優(yōu)先級和結合性。屬性的定義 定義4.1

對于產生式A→α，其中α是由文法符號X1X2...Xn組成的序列，它的語義規(guī)則可以表示為(4.1)所示關于屬性的函數：

b:=f(c1,c2,...,ck) (4.1)第五頁，共一百一十七頁，編輯于2023年，星期五64.1語法制導翻譯簡介b:=f(c1,c2,...,ck) (4.1)語義規(guī)則中的屬性存在下述性質與關系。若b是A的屬性，c1,c2,...,ck是α中文法符號的屬性，或者A的其它屬性，則稱b是A的綜合屬性。若b是α中某文法符號Xi的屬性，c1,c2,...,ck是A的屬性，或者是α中其它文法符號的屬性，則稱b是Xi的繼承屬性。稱(4.1)中屬性b依賴于屬性c1,c2,...,ck。若語義規(guī)則的形式如下述(4.2)，則可將其想像為產生式左部文法符號A的一個虛擬屬性。屬性之間的依賴關系，在虛擬屬性上依然存在。

f(c1,c2,...,ck) (4.2)

(4.1)中屬性之間的依賴關系，實質上反映了屬性計算的先后次序，即所有屬性ci被計算之后才能計算屬性b。第六頁，共一百一十七頁，編輯于2023年，星期五74.1語法制導翻譯簡介語義規(guī)則的兩種形式語法制導定義 用抽象屬性和運算符號表示的語義規(guī)則(公式，做什么)翻譯方案 用具體屬性和運算表示的語義規(guī)則（程序段，如何做）語義規(guī)則也被習慣上稱為語義動作。忽略實現細節(jié)，二者作用等價。語法制導定義適用于設計階段，翻譯方案適用于實現階段。第七頁，共一百一十七頁，編輯于2023年，星期五84.1語法制導翻譯簡介[例4.1]將中綴形式的算術表達式轉換為后綴表示。其語法制導定義和翻譯方案可分別表示如下。其中print(E.post)是L的虛擬屬性，可以想象為L.p:=print(E.post)。翻譯方案中的.lexval表示詞法分析返回的記號num的值。產生式語法制導定義翻譯方案1翻譯方案2L→Eprint(E.post)print_post(post);E→E1+E2E.post:=E1.post||E2.post||'+';post(k):='+';k:=k+1;print(+);E→numE.post:=num.lexval;post(k):=lexval;k:=k+1;print(lexval);語法制導定義：算法

翻譯方案：程序實現，方法不唯一第八頁，共一百一十七頁，編輯于2023年，星期五94.1語法制導翻譯簡介翻譯方案中需要考慮的問題：采用什么樣的語法分析方法，不同的分析方法對語義處理的次序不同；為屬性分配存儲空間；考慮計算次序。翻譯方案1，自下而上計算，LR分析。以3+5+8為例，歸約時翻譯。產生式翻譯方案1L→Eprint_post(post);E→E1+E2post(k):='+';k:=k+1;E→numpost(k):=lexval;k:=k+1;post:(35+8+)第九頁，共一百一十七頁，編輯于2023年，星期五104.1語法制導翻譯簡介屬性作為分析樹的注釋 將屬性附著在分析樹對應文法符號上，形成注釋分析樹。[例4.2]3+5+8的分析樹和注釋分析樹：產生式語法制導定義翻譯方案2L→Eprint(E.post)E→E1+E2E.post:=E1.post||E2.post||'+';print(+);E→numE.post:=num.lexval;print(lexval);.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))第十頁，共一百一十七頁，編輯于2023年，星期五114.1語法制導翻譯簡介注釋分析樹上看繼承屬性與綜合屬性

繼承屬性是自上而下計算的綜合屬性是自下而上計算的提醒：除非特別提醒，本章討論的語法制導翻譯是綜合屬性。.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))第十一頁，共一百一十七頁，編輯于2023年，星期五12上次課總結語法制導翻譯的基本概念屬性與語義規(guī)則語義規(guī)則的兩種形式第十二頁，共一百一十七頁，編輯于2023年，星期五134.1語法制導翻譯簡介LR分析翻譯方案的設計LR分析中的語法制導翻譯實質上是對LR語法分析的擴充：擴充LR分析器的功能：當執(zhí)行歸約產生式的動作時，也執(zhí)行產生式對應的語義動作。由于是歸約時執(zhí)行語義動作，限制語義動作僅能放在產生式右部的最右邊；擴充分析棧：增加一個與分析棧并列的語義棧，用于存放分析棧中文法符號所對應的屬性值。例如：E→E1+E2val[top]:=val[top]+val[top+2];

對于表達式5+3

當歸約為左部E時 同時也得到了值8第十三頁，共一百一十七頁，編輯于2023年，星期五14[例4.3]3+5*8的語法制導翻譯。產生式L→EE→E1+E2E→E1*E2E→n分析棧 語義棧 輸入 語義動作# # 3+5*8# shift#n #3 +5*8# E→n,val[top]:=lexval#E #3 +5*8# shift#E+ #3? 5*8# shift#E+n #3?5 *8# E→n,val[top]:=lexval#E+E #3?5 *8# shift#E+E* #3?5? 8# shift#E+E*n#3?5?8 # E→n,val[top]:=lexval#E+E*E#3?5?8 # E→E1*E2,val[top]:=val[top]*val[top+2]#E+E #3?40 # E→E1+E2,val[top]:=val[top]+val[top+2]#E #43 # acc翻譯方案print(val[top]);val[top]:=val[top]+val[top+2];val[top]:=val[top]*val[top+2];val[top]:=lexval;語法制導定義print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;第十四頁，共一百一十七頁，編輯于2023年，星期五154.1語法制導翻譯簡介遞歸下降分析翻譯方案的設計遞歸下降方法是用程序實現對非終結符的展開和對終結符的匹配。翻譯方案的設計需要解決兩個問題：如何在遞歸下降子程序中嵌入語義動作？ 產生式右部的任何位置；如何為文法符號的屬性設計存儲空間？ 函數返回值、參數、變量等。例如在上機作業(yè)中，函數繪圖語言解釋器語法制導翻譯設計：遞歸子程序可以設計為函數，用于返回必要的屬性值；適當設計子程序中的臨時變量，用于保存屬性值；將語義動作嵌入在子程序的適當位置，正確計算屬性值。第十五頁，共一百一十七頁，編輯于2023年，星期五164.2中間代碼簡介編譯器各階段的完整輸出，均可以被認為是源程序的某種中間表示。本章討論的是中間代碼生成器輸出的中間表示，稱之為中間代碼。中間代碼實際上應起一個編譯器前端與后端分水嶺的作用。要求中間代碼具有如下特性，以便于編譯器的開發(fā)移植和代碼的優(yōu)化：便于語法制導翻譯；既與機器指令的結構相近，又與具體機器無關。中間代碼的主要形式：樹、后綴式、三地址碼等。第十六頁，共一百一十七頁，編輯于2023年，星期五174.2中間代碼簡介后綴式操作數在前，操作符緊隨其后，無需用括號限制運算的優(yōu)先級和結合性。算法4.1后綴式計算采用下述過程進行計算，最終結果留在棧中。

x:=first_token; whilenotend_of_exp

loop ifxinoperators then pushx; --操作數進棧

else pop(operators); --算符，彈出操作數

push(evaluate); --計算，將結果進棧

endif; next(x); endloop;第十七頁，共一百一十七頁，編輯于2023年，星期五184.2中間代碼簡介loop ifxinoperators then pushx; --操作數進棧

else pop(operators); --算符，彈出操作數

push(evaluate); --計算，將結果進棧

endif; next(x);endloop;算術表達式3+5+8的后綴式為35+8+。# 35+8+# push(3)#3 5+8+# push(3)#35 +8+# pop(3和5)，push(3+5)#8 8+# push(8)#88 +# pop(8和8)，push(8+8)#16 #第十八頁，共一百一十七頁，編輯于2023年，星期五194.2中間代碼簡介后綴式并不局限于二元運算的表達式，可以推廣到任何語句，遵守操作數在前，操作符緊跟其后的原則即可。對語句： ifethenxelsey后綴式可以寫為： exyif-then-else (1)此時e、x和y均需計算。實際上，根據條件e的取值，x和y不用都計算：

ep1jezxp2jumpp1:yp2: (2)其中：p1和p2分別是標號；

p1jez表示e的結果為0（假）則轉向p1；

p2jump表示無條件轉向p2。與(1)比較，(2)中的if-then-else被分解，首先計算e，根據e的結果是否為真，決定計算x還是計算y。第十九頁，共一百一十七頁，編輯于2023年，星期五204.2中間代碼簡介三地址碼三地址碼的直觀表示語法：result:=arg1oparg2或

result:=oparg1或

oparg1語義：結果存放在result中的二元運算arg1oparg2

結果存放在result中一元運算oparg1

一元運算oparg1賦值句x:=a+b*c的三地址碼序列：

T1:=b*c T2:=a+T1 x:=T2第二十頁，共一百一十七頁，編輯于2023年，星期五214.2中間代碼簡介三地址碼的種類序號 三地址碼 四元式（1） x:=yopz (op,y,z,x)（2） x:=opy (op,y,,x)（3） x:=y (:=,y,,x)（4） gotoL (j,,,L)（5） ifxgotoL (jnz,x,,L)（6） ifxrelopygotoL (jrelop,x,y,L)（7） paramx (param,,,x)（8） calln,P (call,n,,P)（9） returny (return,,,y)（10）x:=y[i] (=[],y[i],,x)（11）x[i]:=y ([]=,y,,x[i])（12）x:=&y (=&,y,,x)（13）x:=*y (=*,y,,x)（14）*x:=y (*=,y,,x)第二十一頁，共一百一十七頁，編輯于2023年，星期五224.2中間代碼簡介三地址碼的實現：三元式與四元式三元式 三元式(i)(op,arg1,arg2) 三地址碼(i):=arg1oparg2[例4.5]表達式x:=a+b*c的三元式：

(1)(*，b，c) (2)(+，a，(1)) (3)(:=，x，(2))序號的雙重含義：既代表此三元式，又代表三元式存放的結果存放方式：數組結構，三元式在數組中的位置由下標決定。弱點：給代碼的優(yōu)化帶來困難。因為代碼優(yōu)化常使用的方法是刪除某些代碼或移動某些代碼位置，而一旦進行了代碼的刪除或移動，則表示某三元式的序號會發(fā)生變化，從而使得其他三元式中對原序號的引用無效。第二十二頁，共一百一十七頁，編輯于2023年，星期五234.2中間代碼簡介語法制導翻譯設計的基本步驟文法符號屬性的設計必要的基本操作（函數等）的設計語義規(guī)則的設計三元式的語法制導翻譯屬性.code：三元式代碼，指示標識符的存儲單元或三元式表中的序號；屬性.name：標識符的名字；函數trip(op，arg1，arg2)：生成一個三元式，返回三元式的序號；函數entry()：返回標識符在符號表中的位置或存儲位置。第二十三頁，共一百一十七頁，編輯于2023年，星期五244.2中間代碼簡介產生式 語義規(guī)則(1)A→id:=E {A.code:=trip(:=，entry()，E.code)}(2)E→E1+E2 {E.code:=trip(+，E1.code，E2.code)}(3)E→E1*E2 {E.code:=trip(*，E1.code，E2.code)}(4)E→(E1) {E.code:=E1.code}(5)E→-E1 {E.code:=trip(@，E1.code，)}(6)E→id {E.code:=entry()}[例4.6]生成x:=a+b*c的三元式(LR分析)第二十四頁，共一百一十七頁，編輯于2023年，星期五254.2中間代碼簡介四元式四元式是對三元式的改進，將表示計算結果的三元式序號用一個顯式的變量表示，從而避免了三元式的值與三元式在三元組中的位置相關的弱點。四元式的語法：(op，arg1，arg2，result)所表示的計算：result:=arg1oparg2四元式的特點：四元式與三元式的唯一區(qū)別：將由序號所表示的運算結果改為由臨時變量來表示。此改進使得四元式的運算結果與其位置無關，為代碼優(yōu)化提供了極大方便：可以刪除或移動四元式而不影響運算結果。三地址碼與四元式形式的保持一致。四元式的種類三元式(i)(op,arg1,arg2)(i):=arg1oparg2第二十五頁，共一百一十七頁，編輯于2023年，星期五264.2中間代碼簡介四元式的語法制導翻譯屬性.code：表示存放運算結果的變量；函數newtemp：返回一個新的臨時變量，如T1，...等；過程emit(op，arg1，arg2,result)：生成一個四元式，若為一元運算，則arg2可空。產生式與語義規(guī)則：(1)A→id:=E {A.code:=newtemp;emit(:=,entry(),E.code, A.code)}(2)E→E1+E2 {E.code:=newtemp;emit(+,E1.code,E2.code,E.code)}(3)E→E1*E2 {E.code:=newtemp;emit(*,E1.code,E2.code,E.code)}(4)E→(E1) {E.code:=E1.code}(5)E→-E1 {E.code:=newtemp;emit(@,E1.code,,E.code)}(6)E→id {E.code:=entry()}第二十六頁，共一百一十七頁，編輯于2023年，星期五274.2中間代碼簡介圖形表示樹作為中間代碼 語法樹真實反映句子結構，對語法樹稍加修改(加入語義信息)，即可以作為中間代碼的一種形式(注釋語法樹)。[例4.8]賦值句x:=(a+b)*(a+b)的樹的中間代碼表示：三元式：(1)(+,a,b)(2)(+,a,b)(3)(*,(1),(2))(4)(:=,x,(3))四元式：(1)(+,a,b,T1)(2)(+,a,b,T2)(3)(*,T1,T2,T3)(4)(:=,x,T3,T4)第二十七頁，共一百一十七頁，編輯于2023年，星期五284.2中間代碼簡介樹的語法制導翻譯屬性.nptr：指向樹節(jié)點的指針；函數mknode(op，nptr1，nptr2)：生成一個根或內部節(jié)點，節(jié)點數據是op，nptr1和nptr2分別指向的左右孩子的子樹。若僅有一個孩子，則nptr2為空；函數mkleaf(node)：生成一個葉子節(jié)點。(1)A→id:=E {A.nptr:= mknode(:=,mkleaf(entry()),E.nptr)}(2)E→E1+E2 {E.nptr:=mknode(+,E1.nptr,E2.nptr)}(3)E→E1*E2 {E.nptr:=mknode(*,E1.nptr,E2.nptr)}(4)E→(E1) {E.nptr:=E1.nptr}(5)E→-E1 {E.nptr:=mknode(@,E1.nptr,)}(6)E→id {E.nptr:=mkleaf(entry(())}三元式、四元式與樹的語義規(guī)則設計是相似的。第二十八頁，共一百一十七頁，編輯于2023年，星期五294.2中間代碼簡介樹的優(yōu)化表示－DAG如果樹上若干個節(jié)點有完全相同的孩子，則這些節(jié)點可以指向同一個孩子，形成一個有向無環(huán)圖(DirectedAcyclicGraph,DAG)，與樹的唯一區(qū)別是多個父親可以共享同一個孩子，從而達到資源(運算、代碼等)共享的目的。DAG的語法制導翻譯與樹的語法制導翻譯相似，僅需要在mknode和mkleaf中增加相應的查詢功能：先查看所要構造的節(jié)點是否已經存在，若存在則無需構造新的節(jié)點，直接返回指向已存在節(jié)點的指針即可。第二十九頁，共一百一十七頁，編輯于2023年，星期五304.2中間代碼簡介樹與其他中間代碼的關系樹表示的中間代碼與后綴式和三地址碼之間有內在聯(lián)系：對樹進行深度優(yōu)先后序遍歷，得到的線性序列就是后綴式，或者說后綴式是樹的一個線性化序列；樹的每個內部節(jié)點和它的孩子對應一個三元式或四元式。[例4.9]賦值句x:=(a+b)*(a+b)的注釋語法樹：后綴式：xab+ab+*:=三元式：(1)(+,a,b) (2)(+,a,b)(3)(*,(1),(2)) (4)(:=,x,(3))四元式： (1)(+,a,b,T1) (2)(+,a,b,T2)(3)(*,T1,T2,T3) (4)(:=,x,T3,T4)現代的編譯器基礎架構均用語法樹作為中間表示。第三十頁，共一百一十七頁，編輯于2023年，星期五31上次課總結中間代碼后綴式三地址碼三元式四元式圖形表示第三十一頁，共一百一十七頁，編輯于2023年，星期五324.3符號表簡介符號表的作用：連接聲明與引用的橋梁，記住每個符號的相關信息，如作用域和綁定等，幫助編譯的各個階段正確有效地工作。符號表設計的基本要求：合理存放信息、快速準確查找。正確存儲各類信息；適應不同階段的需求；便于有效地進行查找、插入、刪除和修改等操作；空間可以動態(tài)擴充。第三十二頁，共一百一十七頁，編輯于2023年，星期五334.3符號表簡介符號表條目邏輯上講：每個聲明的名字在符號表中占據一欄，稱為一個條目，用于存放名字的相關信息。符號表中的內容：保留字、標識符、特殊符號(包括算符、分隔符等)等。多個子表：不同類別的符號可以存放在不同的子表中，如變量名表、過程名表、保留字表等。存放方式：關鍵字＋屬性。組合關鍵字：intx; {doublex; structx{floaty,z;}; }C符號表的組合關鍵字至少包括：名字＋作用域＋類型一個名字x在同一作用域中允許有多個的聲明，則引用時需要根據上下文確定x屬于哪個對象。為簡化編譯，大多數語言在語法上不允許這樣的聲明第三十三頁，共一百一十七頁，編輯于2023年，星期五344.3符號表簡介構成名字的字符串的存儲

定長數據采用直接存放，變長數據采用間接存放。

名字（直接存儲） 屬性

sort proc,... a int,... readarray proc,... draw_a_red_line_for_object_a boolean,...

名字（間接存儲） 屬性

101(或101/4) proc,... 106(或105/1) int,... 108(或106/9) proc,... 118(或115/28) boolean,... sort#a#readarray#draw_a_red_line_for_object_a# ↑101sortareadarraydraw_a_red_line_for_object_a↑101第三十四頁，共一百一十七頁，編輯于2023年，星期五354.3符號表簡介間接存儲的特點：間接存儲的方法實際上解決了復雜信息的存儲問題；將其推廣到屬性，則任何一個復雜的屬性，均可以為其另辟空間；空間本身可以是任何復雜結構，如數組的內情向量等。指向空間的指針存放于此屬性在符號表中的對應位置。關鍵字屬性x...任何復雜結構第三十五頁，共一百一十七頁，編輯于2023年，星期五364.3符號表簡介名字的作用域程序設計語言的名字可以出現在不同的范圍內，并且可以具有不同的意義。兩種劃分范圍的方式：并列的和嵌套的。不同的語言采用不同的方式：如Pascal的過程定義可以是嵌套的，而C的過程定義是并列的，但是C允許程序塊是嵌套的。（問題：過程與程序塊的主要區(qū)別？）名字的作用域：名字在哪個范圍內起作用。并列的兩個范圍內的名字作用域互不相干，但是分別在嵌套的兩個范圍內的名字，其作用域的問題就需要制定規(guī)則來限定，以使得任何一個名字在任何范圍內涵義都是無二義的。名字的作用域規(guī)則：規(guī)定一個名字在什么樣的范圍內應該表示什么意義。第三十六頁，共一百一十七頁，編輯于2023年，星期五374.3符號表簡介靜態(tài)作用域規(guī)則(static-scoperule)編譯時就可以確定名字的作用域，即僅從靜態(tài)讀程序就可確定名字的作用域。最近嵌套規(guī)則(mostcloselynested)以程序塊為例，也適用于過程。程序塊B中聲明的作用域包括B；如果名字x不在B中聲明，那么B中x的出現是在外圍程序塊B'的x聲明的作用域中，使得B'有x的聲明，并且B'比其它任何含x聲明的程序塊更接近被嵌套的B通俗地講，名字聲明在離其最近的內層起作用，即在名字引用處從內向外看，它處在所遇到的第一個該名字聲明的作用域。第三十七頁，共一百一十七頁，編輯于2023年，星期五38[例4.10]符合作用域規(guī)則的C++程序。voidmain(){ inta=0,b=0; /*B0層*/ { intb=1; /*B1層，被B0嵌套*/ { inta=2,c=4,d=5; /*B2層，被B1嵌套*/ printf("%d%d\n",a,b); /*結果為：2，1*/ } { intb=3; /*B3層，與B2并列*/ printf("%d%d\n",a,b); /*結果為：0，3*/ } printf("%d%d\n",a,b); /*結果為：0，1*/ }printf("%d%d\n",a,b); /*結果為：0，0*/}聲明 作用域inta=0 B0-B2intb=0 B0-B1intb=1 B1-B3inta=2 B2intb=3 B3第三十八頁，共一百一十七頁，編輯于2023年，星期五394.3符號表簡介線性表線性表應是一個棧，以正確反映名字的作用域，即符號的加入和刪除，均在線性表的一端進行。關鍵字：名字＋作用域；線性表上的操作：查找：從表頭(棧頂)開始，遇到的第一個名字；插入：先查找，再插入在表頭；1voidmain()2{inta=0,b=0; //B03{intb=1; //B14{inta=2,c=4,d=5; }//B27{intb=3; }//B311}}第三十九頁，共一百一十七頁，編輯于2023年，星期五404.3符號表簡介刪除：(a)暫時：將在同一作用域的名字同時摘走，適當保存；(b)永久：將在同一作用域的名字同時摘走，不再保存修改：與查找類似，修改第一個遇到的名字的信息。修改可以用刪除＋插入代替。線性表上操作的效率（n個條目） 成功查找(平均)：(n+1)/2；不成功查找：n+1

建立n個條目的符號表(最壞)：∑i

＝(n+1)n/2第四十頁，共一百一十七頁，編輯于2023年，星期五414.3符號表簡介散列表將線性表分成m個小表，構造hash函數，使名字均勻散布在子表中。若散列均勻，則時間復雜度會降到原線性表的1/m名字掛在兩個鏈上(便于刪除操作)：散列鏈(hashlink)：鏈接所有具有相同hash值的元素，表頭在表頭數組中；作用域鏈(scopelink)：鏈接所有在同一作用域中的元素，表頭在作用域鏈中。S1

S2

S4在同一作用域S3在另一作用域第四十一頁，共一百一十七頁，編輯于2023年，星期五424.3符號表簡介散列表上的操作查找：首先計算散列函數，然后從散列函數所指示的入口進入某個線性表，在線性表中沿hashlink，象查找單鏈表中的名字一樣查找。插入：首先查找，以確定要插入的名字是否已在表中，若不在，則要分別沿hashlink和scopelink插入到兩個鏈中，方法均是插在表頭，即兩個表均可看作是棧。刪除：把以作用域鏈連在一起的所有元素從當前符號表中刪除，保留作用域鏈所鏈的子表，為后繼工作使用(如果是臨時刪除，則下次使用時直接沿作用域鏈加入到散列鏈中即可)。第四十二頁，共一百一十七頁，編輯于2023年，星期五431voidmain()2{inta=0,b=0; //B03{intb=1; //B14{inta=2,c=4,d=5; }//B27{intb=3; }//B311}}設：hash(s)=ord(s)-ord('a')分析在B2中：退出B2進入B3：第四十三頁，共一百一十七頁，編輯于2023年，星期五44上次課總結符號表符號表的條目名字的存儲名字的作用域（靜態(tài)與最近嵌套原則）線性表散列表（作用域鏈與散列鏈）第四十四頁，共一百一十七頁，編輯于2023年，星期五454.3符號表簡介散列函數的計算 hash:string→integer減少沖突，分布均勻充分考慮程序設計語言的特點例：若有變量V001,V002,…,V300，且首字母的值作為hash值，會發(fā)生什么？一種可行的hash函數計算方法：從串s=c1c2…ck的字符ci確定正整數h： 令：h0=0,

計算：hi=αhi-1+ci,1≤i≤k,

得到：h=hk α=1或α是素數，如α=65599。取一素數m,令h=hmodm。第四十五頁，共一百一十七頁，編輯于2023年，星期五464.3符號表簡介思考題(P108)：對于下列函數

#include<iostream.h> constintPRIME=211; constintEOS='\0'; inthashpjw(char*s) { char*p;unsignedh=0,g; for(p=s;*p!=EOS;p++) { h=(h<<4)+(*p); if(g=h&0xf0000000) {h=h^(g>>24);h=h^g;} } returnh%PRIME; }(1)為每行語句寫注釋；(2)寫出此函數的計算公式；(3)若參數是"abcd"，試給出返回值。第四十六頁，共一百一十七頁，編輯于2023年，星期五474.4聲明語句的翻譯聲明語句的作用是為可執(zhí)行語句提供信息，以便于其執(zhí)行。對聲明語句的處理，主要是將所需要的信息正確地填寫進合理組織的符號表中。變量的聲明變量的類型定義與聲明

類型定義為編譯器提供存儲空間大小的信息，變量聲明為變量分配存儲空間。組合數據的類型定義和變量聲明有兩種情況：定義與聲明在一起，定義與聲明分離。定義確定存儲空間，聲明分配存儲空間簡單數據類型的存儲空間是已經確定的，如integer可以占4個字節(jié)，real可以占8個字節(jié)，char可以占1個字節(jié)等組合數據類型變量的存儲空間，需要編譯器根據程序員提供的信息計算而定第四十七頁，共一百一十七頁，編輯于2023年，星期五484.4聲明語句的翻譯例：在Pascal程序中的類型定義與變量聲明：

先定義后聲明

type player=array[1..2]ofinteger;

matrix=array[1..24]ofchar; varc,p:player; winner:boolean; display:matrix; movect:integer;

定義與聲明同時

varc,p:array[1..2]ofinteger; display:array[1..24]ofchar;強調：簡單變量聲明中類型是預定義的；組合變量聲明中類型需自己定義。（定義的兩種形式）第四十八頁，共一百一十七頁，編輯于2023年，星期五494.4聲明語句的翻譯變量聲明的語法制導翻譯變量聲明的文法：

D→D;D (1) |id:T (2) T→int (3) |real (4) |array[num]ofT (5) |^T (6)(5)是數組類型的聲明，其中的數組元素個數由num表示，如num可以是5或10等，它等價于1..5或1..10。(6)是指針類型的聲明，其寬度(大小)是一個常量。數組元素的類型和指針所指對象的類型可以是任意合法類型。聲明多維數組：A:array[d1]ofarray[d2]of...array[dn]ofint此多維數組以行為主存儲。因為第一維是有d1個元素的一維數組，每個元素又是一個n-1維的數組；依此類推。第四十九頁，共一百一十七頁，編輯于2023年，星期五504.4聲明語句的翻譯填寫符號表信息的語法制導翻譯全程量offset：記錄當前符號存儲的偏移量，初值設為0屬性.type和.width：變量的類型和所占據的存儲空間過程enter(name,type,offset)：為type類型的變量name建立符號表條目，并為其分配存儲空間(位置)offset(1)D→D;D(2)D→id:T {enter(,T.type,offset); offset:=offset+T.width;}(3)T→int {T.type:=integer;T.width:=4;}(4)T→real {T.type:=real;T.width:=8;}(5)T→array[num]ofT1 {T.type:=array(num.val,T1.type); T.width:=num.val*T1.width;}(6)T→^T1 {T.type:=pointer(T1.type);T.width:=4;}第五十頁，共一百一十七頁，編輯于2023年，星期五514.4聲明語句的翻譯例聲明的語法制導翻譯：a:array[10]ofint;x:int;(無分號)序號歸約使用的產生式 語義處理結果(1)T1→int T1.type=integer T1.width=4(2)T2→array[num]ofT1 T2.type=array(10,integer) T2.width=10*4=40(3)D1→id:T2 enter(a,array(10),0) offset=40(4)T3→int T3.type=integer T3.width=4(5)D2→id:T3 enter(x,integer,40) offset=44第五十一頁，共一百一十七頁，編輯于2023年，星期五52上次課總結變量聲明類型定義與變量聲明語法制導翻譯第五十二頁，共一百一十七頁，編輯于2023年，星期五534.4聲明語句的翻譯過程的定義與聲明過程（procedure）：過程頭＋過程體；函數；主程序過程的三種形式：過程定義、過程聲明和過程調用

Ada過程定義：

procedureswap(x,y:inoutinteger)is --規(guī)格說明

temp:integer; --體中的聲明

begintemp:=x;x:=y;y:=temp;endswap;--可執(zhí)行語句序列 聲明與引用：

procedureswap(x,y:inoutinteger); --過程聲明

swap(a,b); --過程調用先聲明后引用原則 過程定義可以寫在對它的引用之后或引用時看不到的地方。在這樣的情況下，引用前必須先聲明。而若引用前已定義，則聲明可省略，因為定義已包括了聲明。第五十三頁，共一百一十七頁，編輯于2023年，星期五544.4聲明語句的翻譯左值與右值形式上，出現在賦值號左邊和右邊的變量稱為左值和右值實質上，左值必須具有存儲空間，右值可以僅是一個值，而沒有存儲空間。形象地講，左值是容器，右值是內容。(1)consttwo=2; --聲明一個值為2的常量two(2)x:integer; --聲明一個類型為整型數的變量x(3)functionmax(a,b:integer)returninteger;

--聲明一個返回值類型是整型數的函數max(4)x:=two; --x當前值為2(5)x:=two+x; --x當前值變?yōu)?(6)x:=max(two,x)+x; --x當前值變?yōu)?(7)4:=x; --字面量不能作為左值(8)two:=x; --常量不能作為左值(9)max(two,x):=two; --函數返回值不能作為左值(10)x+two:=x+two; --表達式的值不能作為左值第五十四頁，共一百一十七頁，編輯于2023年，星期五554.4聲明語句的翻譯參數傳遞形參與實參定義時的參數稱為形參(parameter或formalparameter)引用時的參數稱為實參(argument或actualparameter)常見的參數傳遞形式：（不同的語言提供不同的形式）值調用（callbyvalue）引用調用（callbyreference）復寫－恢復（copy-in/copy-out）換名調用（callbyname）參數傳遞方法的實質：實參是代表左值、右值、還是實參本身的正文。第五十五頁，共一百一十七頁，編輯于2023年，星期五564.4聲明語句的翻譯值調用值調用的特點：過程內部對參數的修改，不影響作為實參的變量原來的值。實參的特點：任何可以作為右值的對象均可作為實參。參數傳遞和過程內對參數的使用原則：過程定義時形參被當作局部名看待，并在過程內部為形參分配存儲單元；調用過程前，首先計算實參并將值（實參的右值）放入形參的存儲單元；過程內部對形參單元中的數據直接訪問。第五十六頁，共一百一十七頁，編輯于2023年，星期五574.4聲明語句的翻譯值調用舉例：programreference(input,output);vara,b:integer;procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;begina:=1;b:=2;swap(a,b);writeln('a=',a);writeln('b=',b)end.運行結果：a=1 b=2//等價的C++程序#include<iostream.h>voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;}voidmain(){inta(1),b(2);swap(a,b);cout<<"a="<<a<<"b="<<b;}第五十七頁，共一百一十七頁，編輯于2023年，星期五584.4聲明語句的翻譯引用調用引用調用的特點：過程內部對形參的修改，等價于直接對實參的修改。實參的特點：必須是左值。參數傳遞和過程內對參數的使用原則：定義時形參被當作局部名看待，并在過程內部為形參分配存儲單元；調用過程前，將作為實參的變量的地址放進形參的存儲單元；過程內部把形參單元中的數據當作地址，進行間接訪問第五十八頁，共一百一十七頁，編輯于2023年，星期五594.4聲明語句的翻譯引用調用舉例：programreference(input,output);vara,b:integer;procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend;begina:=1;b:=2;swap(a,b);writeln('a=',a);writeln('b=',b)end.運行結果：a=2 b=1//等價的C++程序#include<iostream.h>voidswap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}voidmain(){inta(1),b(2);swap(a,b);cout<<"a="<<a<<"b="<<b;}第五十九頁，共一百一十七頁，編輯于2023年，星期五604.4聲明語句的翻譯值調用模擬引用調用#include<iostream.h>voidswap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}voidmain(){inta(1),b(2);swap(&a,&b);cout<<"a="<<a<<"b="<<b;}注意：

C語言只有值調用因此：只能用值調用形式模擬引用調用的效果同樣：過程式程序設計語言可以模擬面向對象的繼承機制結論：語言與程序設計范型（方法）不是一一對應的關系第六十頁，共一百一十七頁，編輯于2023年，星期五614.4聲明語句的翻譯復寫－恢復引用調用的副作用inta=2;voidadd_one(int&x){a=x+1;x=x+1;}voidmain(){cout<<"before:a="<<a<<endl;add_one(a);cout<<"after:a="<<a<<endl;}本意：a=3 結果：a=4原因：實參與非本地量共用一個存儲空間，使得在過程內改變參數值的同時，也改變了非本地量的值。第六十一頁，共一百一十七頁，編輯于2023年，星期五624.4聲明語句的翻譯復寫-恢復的特點：(值調用和引用調用的結合)過程內部對參數的修改不直接影響實參，避免了副作用返回時將形參內容恢復給實參，實現了參數的返回。實參的特點：必須是左值。參數傳遞和過程內對參數的使用原則：過程定義時形參被當作局部名，在過程內部為形參分配單元(復寫)；調用過程前，計算實參并將右值放入形參的存儲單元；過程內部對形參單元中的數據直接訪問；過程返回前，將形參右值放回實參的存儲單元(恢復)。第六十二頁，共一百一十七頁，編輯于2023年，星期五634.4聲明語句的翻譯復寫-恢復舉例：proceduretestis --Ada源程序

a:integer; procedureadd_one(x:inoutinteger);--復寫-恢復調用

begina:=x+1;x:=x+1;endadd_one;begina:=2;a:=add_one(a);put_line('a=',a);endtest;//引用調用模擬復寫-恢復參數傳遞的演示程序inta=2;voidadd_one(int&x){ intlocal_x=x;a=local_x+1;local_x++;x=local_x;}voidmain(){ add_one(a); cout<<"after:a="<<a<<endl;}第六十三頁，共一百一十七頁，編輯于2023年，星期五644.4聲明語句的翻譯換名調用嚴格講，換名調用并不能算作真正的過程調用和參數傳遞。換名調用由Algol的復寫規(guī)則定義：過程被認為宏，每次對過程的調用，實質上是用過程體替換過程調用，替換中用實參的文字替換體中的形參。這樣的替換方式被稱為宏替換或宏展開；區(qū)分被調用過程的局部名和調用過程的名字。宏展開前被調用過程的每個局部名被重新命名成可區(qū)別的名字；當需要保持實參的完整性時，可為實參加括弧。換名調用的C++形式是宏定義(#define)，在預處理時進行宏替換，將過程體直接展開在它被調用的地方，消除了過程調用和參數傳遞，運行速度快。第六十四頁，共一百一十七頁，編輯于2023年，星期五654.4聲明語句的翻譯正文替換與函數調用的不一致性//換名調用副作用的演示程序#include<iostream.h>inttemp;#defineswap(x,y)temp=x;x=y;y=temp; //宏定義voidswap(int&x,int&y) //引用調用{inttemp;temp=x;x=y;y=temp;}voidmain(){inta(1),b[]={0,0};cout<<"before:a="<<a<<"b="<<b[0]<<""<<b[1]<<endl;swap(a,b[a]);cout<<"after:a="<<a<<"b="<<b[0]<<""<<b[1]<<endl;}第六十五頁，共一百一十七頁，編輯于2023年，星期五664.4聲明語句的翻譯一種折中的方法C++的內聯(lián)函數（inline）：與宏替換一樣高效（避免了函數調用）；消除了宏替換的副作用（模擬函數調用的效果）。//宏定義#definemacro_swap(x,y)temp=x;x=y;y=temp;//內聯(lián)函數inlinevoidinline_swap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}//引用調用voidprocedure_swap(int&x,int&y){inttemp;temp=x;x=y;y=temp;}第六十六頁，共一百一十七頁，編輯于2023年，星期五674.4聲明語句的翻譯作用域信息的保存過程的作用域與程序塊類似，在允許嵌套定義過程的程序設計語言中，相同的名字可以同時出現在不同的作用域中，因此有必要討論如何設計符號表來存放它們。此處討論的過程作用域，同樣遵守靜態(tài)作用域和最近嵌套原則。定義4.2

設主程序(最外層過程)的嵌套深度dmain=1，則若過程A直接嵌套定義過程B，則dB=dA+1；變量聲明時所在過程的嵌套深度，被認為是該變量的嵌套深度。與程序塊相比，有兩點不同，使得過程聲明的處理復雜：過程頭(即界面)是一個名字，可象引用變量一樣被調用程序塊的執(zhí)行(控制流)與靜態(tài)一致，而過程不一致。第六十七頁，共一百一十七頁，編輯于2023年，星期五68例4.14快排序的Pascal程序：programsort(input,output); vara:array[0..10]ofinteger; x:integer;

procedurereadarray; vari:integer; beginfori:=1to9doread(a[i])end{readarray}; procedureexchange(i,j:integer); beginx:=a[i];a[i]:=a[j];a[j]:=x;end{exchange};

procedurequicksort(m,n:integer); vari,v:integer; functionpartition(y,z:integer):integer; vari,j:integer; begin...a...;...v...;...exchange(i,j);...end{partition};

beginif(n>m)then begini:=partition(m,n);quicksort(m,i-1);quicksort(i+1,n)end; end{quicksort};begina[0]:=-9999;a[10]:=9999;readarray;quicksort(1,9)end{sort}.過程變量深度sorta,x1readarrayi2exchange2quicksorti,v2partitioni,j3第六十八頁，共一百一十七頁，編輯于2023年，星期五694.4聲明語句的翻譯符號表中的作用域信息嵌套過程中的名字作用域信息，使用有嵌套結構的符號表保存。每個過程被認為是一個子符號表，或者是符號表中的一個節(jié)點。嵌套的節(jié)點之間用雙向鏈連接，正向鏈指示過程的嵌套關系，逆向鏈實現按作用域對名字進行訪問。參數如何處理?第六十九頁，共一百一十七頁，編輯于2023年，星期五70上次課總結過程的定義與聲明定義、聲明與引用左值與右值參數傳遞：值調用、引用調用、復寫－恢復、換名調用嵌套定義的過程中信息的存儲作用域信息的保存過程的作用域符號表中的作用域信息語法制導翻譯生成符號表第七十頁，共一百一十七頁，編輯于2023年，星期五714.4聲明語句的翻譯語法制導翻譯生成符號表簡化的過程定義文法(忽略了參數) P→D (1) D→D;D (2) |id:T (3) |procid;D;S (4)修改文法，在定義D之前生成符號表(LR分析) P→MD (1) D→D;D (2) |id:T (3) |procid;ND;S (4) M→ε (5) N→ε (6)問題：如何在處理產生式(1)和(4)的語言結構時正確地填寫符號表信息(雙向鏈表)？第七十一頁，共一百一十七頁，編輯于2023年，星期五724.4聲明語句的翻譯全程量、屬性與語義函數全程量：有序對棧(tblptr,offset) (符號表節(jié)點的指針,符號表節(jié)點所需寬度)棧上的操作：push(t,o)、pop、top(stack)語義函數與過程：函數mktable(previous)：建立一個新的節(jié)點，返回指向新節(jié)點的指針。previous是逆向鏈，指向該節(jié)點的前驅(外層)。過程enter(table,name,type,offset)：在table指向的節(jié)點中為名字name建立新的條目，包括名字的類型和存儲位置等。過程addwidth(table,width)：計算table節(jié)點中所有條目的累加寬度，并記錄在table的頭部信息中。過程enterproc(table,name,newtable)：為過程name在table指向的節(jié)點中建立一個新的條目。參數newtable是正向鏈，指向name過程自身的符號表節(jié)點。第七十二頁，共一百一十七頁，編輯于2023年，星期五734.4聲明語句的翻譯語義規(guī)則(1)P→MD {addwidth(top(tblptr),top(offset));pop;}(2)M→ε {t:=mktable(null);push(t,0,);}(3)D→D;D(4)D→id:T {enter(top(tblptr),,T.type,top(offset)); top(offset):=top(offset)+T.width;}(5)D→procid;ND1;S {t:=top(tblptr); addwidth(t,top(offset)); pop; enterproc(top(tblptr),,t);}(6)N→ε {t:=mktable(top(tblptr));push(t,0);}第七十三頁，共一百一十七頁，編輯于2023年，星期五744.4聲明語句的翻譯語法制導翻譯的過程procsort;a:array[10]ofint;x:int;procreadarry;i:int;read(a);readarray第七十四頁，共一百一十七頁，編輯于2023年，星期五75(1)M1→ε t1:=mktable(null);push(t1,0);(2)N1→ε t2:=mktable(top(tblptr));push(t2,0);(3)T1→int T1.type=integer,T1.width=4(4)T2→array[10]ofT1 T2.type=array(10,int),T2.width=40(5)D1→a:T2 (a,arr,0)填進t2所指節(jié)點，top(offset):=40(6)T3→int T2.type=integer,T2.width=4(7)D2→x:T3 (x,int,40)填進t2所指節(jié)點，top(offset):=44(8)N2→ε t3:=mktable(top(tblptr));push(t3,0);(9)T4→int T4.type=integer,T4.width=4(10)D3→i:T4 (i,int,0)填進t3所指節(jié)點，top(offset):=4(11)D4→procreadarrayN2D3;S t:=top(tblptr);addwidth(t,top(offset)); pop;enterproc(top(tblptr),readarray,t);(14)D7→procsortN1D6;S t:=top(tblptr);addwidth(t,top(offset)); pop;enterproc(top(tblptr),sort,t);(15)P→M1D7 addwidth(top(tblptr),top(offset));pop;第七十五頁，共一百一十七頁，編輯于2023年，星期五764.5簡單算術表達式與賦值句討論所基于的文法：A→id:=E E→E+E|E*E|-E|(E)|id簡單變量的語法制導翻譯屬性.place：存放E的變量名地址(符號表中地址或臨時變量)過程emit()：生成result:=arg1oparg2的三地址碼。(1)A→id:=E {emit(entry()':='E.place)}(2)E→E1+E2 {E.place:=newtemp；

emit(E.place':='E1.place'+'E2.place)}

(3)E→E1*E2 {E.place:=newtemp；

emit(E.place':='E1.place'*'E2.place)}(4)E→-E1 {E.place:=newtemp；

emit(E.place':=''-'E1.place)}

(5)E→(E1) {E.place:=E1.place}(6)E→id {E.place:=entry()}第七十六頁，共一百一十七頁，編輯于2023年，星期五774.5簡單算術表達式與賦值句變量的(內部)類型轉換強制(coercion)：按照一定的原則，將不同類型的變量在內部轉換為相同的類型，然后進行同類型變量的計算。屬性.mode：取值int或real表達式的類型判定樹：運算的轉換原則賦值的轉換原則第七十七頁，共一百一十七頁，編輯于2023年，星期五784.5簡單算術表達式與賦值句三地址碼：

T:=itrE：將E從整型變?yōu)閷嵭?，結果存放T中

T:=rtiE：將E從實型變?yōu)檎停Y果存放T中語義規(guī)則：A→id:=E {tmode:=entry().mode; iftmode=E.mode thenemit(entry()':='E.place); else T:=newtemp; iftmode=int thenemit(T':='rtiE.place); elseemit(T':='itrE.place); endif; emit(entry()':='T); endif; }第七十八頁，共一百一十七頁，編輯于2023年，星期五794.5簡單算術表達式與賦值句E→E1opE2{ T:=newtemp；E.mode:=real; ifE1.mode=int then ifE2.mode=int then emit(T':='E1.placeOPiE2.place);E.mode:=int; else U:=newtemp; emit(U':='itrE1.place);emit(T':='UOPrE2.place); endif; else ifE2.mode=int then U:=newtemp; emit(U':='itrE2.place);emit(T':='E1.placeOPrU); elseemit(T':='E1.placeOPrE2.place); endif; endif; E.place:=T;}其他語義規(guī)則看教材P128－129第七十九頁，共一百一十七頁，編輯于2023年，星期五804.5簡單算術表達式與賦值句[例4.17]x:=-a*b+c的語法制導翻譯，x、a、b是整型數，c是實型數。序號產生式 中間代碼(1)E1→a(2)E2→-E1 t1:=-a(3)E3→b(4)E4→E2*E3t2:=t1*i

b(5)E5→c(6)E6→E4+E5t4:=itrt2 t3:=t4+r

c(7)A→x:=E6t5:=rtit3 x:=t5.int.int.int.real.int(itor).real(rtoi)第八十頁，共一百一十七頁，編輯于2023年，星期五814.6數組元素的引用確定數組空間的存儲分配：以第一個元素地址為首地址，分配一個連續(xù)空間。多維到一維存儲空間的映射方法： 以行為主或以列為主三行三列的二維數組：a[0..2,2..4]以行為主存放時的元素排列：

a[0,2]a[0,3]a[0,4]a[1,2]a[1,3]a[1,4]a