西安電子科技大學(xué)計(jì)算機(jī)考研編譯原理第四章 語法制導(dǎo)翻譯生成中間代碼

1第四章語法制導(dǎo)翻譯生成中間代碼語法制導(dǎo)翻譯是處理語義的基本方法，它以語法分析為基礎(chǔ)，在語法分析得到語言結(jié)構(gòu)的結(jié)果時(shí)，對(duì)附著于此結(jié)構(gòu)的語義進(jìn)行處理，如計(jì)算表達(dá)式的值、生成中間代碼等。與語法分析部分的討論不同，本章的內(nèi)容更注重于實(shí)際方法的討論。主要內(nèi)容包括：語法制導(dǎo)翻譯的基本概念中間代碼簡(jiǎn)介符號(hào)表簡(jiǎn)介典型聲明語句與可執(zhí)行語句的翻譯上機(jī)：DBMS的設(shè)計(jì)與實(shí)現(xiàn)—SQL的執(zhí)行24.1語法制導(dǎo)翻譯簡(jiǎn)介語法與語義語法與語義的關(guān)系語法是指語言的結(jié)構(gòu)、即語言的“樣子”；語義是指附著于語言結(jié)構(gòu)上的實(shí)際含意，即語言的“意義”。語義不能離開語法獨(dú)立存在；語義遠(yuǎn)比語法復(fù)雜；同一語言結(jié)構(gòu)可包含多種含意，不同語言結(jié)構(gòu)可表示相同含意；語法與語義之間沒有明確的界線。[例1]貓吃老鼠與老鼠吃貓，曬被子與曬太陽[例2]程序設(shè)計(jì)語言中的分情況結(jié)構(gòu)34.1語法制導(dǎo)翻譯簡(jiǎn)介caseconditioniscase1:stat1;case2:stat2;...endcase;語義分析的兩個(gè)作用檢查是否結(jié)構(gòu)正確的句子所表示的意思也合法；執(zhí)行規(guī)定的語義動(dòng)作，如：表達(dá)式求值符號(hào)表填寫中間代碼生成等語義分析的方法 語法制導(dǎo)翻譯switch(condition){casecondition1:stat1;casecondition2:stat2; ...}

break;break;44.1語法制導(dǎo)翻譯簡(jiǎn)介屬性與語義規(guī)則語法制導(dǎo)翻譯的基本思想通俗地講，以語法分析為基礎(chǔ)，伴隨語法分析的各個(gè)步驟，執(zhí)行相應(yīng)的語義動(dòng)作。具體方法：將文法符號(hào)所代表的語言結(jié)構(gòu)的意思，用附著于該文法符號(hào)的屬性表示；用語義規(guī)則規(guī)定產(chǎn)生式所代表的語言結(jié)構(gòu)之間的關(guān)系（即屬性之間的關(guān)系），即用語義規(guī)則實(shí)現(xiàn)屬性計(jì)算。語義規(guī)則的執(zhí)行：在語法分析的適當(dāng)時(shí)刻（如推導(dǎo)或歸約）執(zhí)行附著在對(duì)應(yīng)產(chǎn)生式上的語義規(guī)則，以實(shí)現(xiàn)對(duì)語言結(jié)構(gòu)語義的處理，如計(jì)算、查填符號(hào)表、生成中間代碼、發(fā)布出錯(cuò)信息等。54.1語法制導(dǎo)翻譯簡(jiǎn)介屬性的抽象表示.attr如：E.val（值），E.type（類型），E.code（代碼序列），

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

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

b:=f(c1,c2,...,ck) (4.1)64.1語法制導(dǎo)翻譯簡(jiǎn)介b:=f(c1,c2,...,ck) (4.1)語義規(guī)則中的屬性存在下述性質(zhì)與關(guān)系。若b是A的屬性，c1,c2,...,ck是α中文法符號(hào)的屬性，或者A的其它屬性，則稱b是A的綜合屬性。若b是α中某文法符號(hào)Xi的屬性，c1,c2,...,ck是A的屬性，或者是α中其它文法符號(hào)的屬性，則稱b是Xi的繼承屬性。稱(4.1)中屬性b依賴于屬性c1,c2,...,ck。若語義規(guī)則的形式如下述(4.2)，則可將其想像為產(chǎn)生式左部文法符號(hào)A的一個(gè)虛擬屬性。屬性之間的依賴關(guān)系，在虛擬屬性上依然存在。

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

(4.1)中屬性之間的依賴關(guān)系，實(shí)質(zhì)上反映了屬性計(jì)算的先后次序，即所有屬性ci被計(jì)算之后才能計(jì)算屬性b。74.1語法制導(dǎo)翻譯簡(jiǎn)介語義規(guī)則的兩種形式語法制導(dǎo)定義 用抽象屬性和運(yùn)算符號(hào)表示的語義規(guī)則(公式，做什么)翻譯方案 用具體屬性和運(yùn)算表示的語義規(guī)則（程序段，如何做）語義規(guī)則也被習(xí)慣上稱為語義動(dòng)作。忽略實(shí)現(xiàn)細(xì)節(jié)，二者作用等價(jià)。語法制導(dǎo)定義適用于設(shè)計(jì)階段，翻譯方案適用于實(shí)現(xiàn)階段。84.1語法制導(dǎo)翻譯簡(jiǎn)介[例4.1]將中綴形式的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表示。其語法制導(dǎo)定義和翻譯方案可分別表示如下。其中print(E.post)是L的虛擬屬性，可以想象為L(zhǎng).p:=print(E.post)。翻譯方案中的.lexval表示詞法分析返回的記號(hào)num的值。產(chǎn)生式語法制導(dǎo)定義翻譯方案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);語法制導(dǎo)定義：算法

翻譯方案：程序?qū)崿F(xiàn)，方法不唯一94.1語法制導(dǎo)翻譯簡(jiǎn)介翻譯方案中需要考慮的問題：采用什么樣的語法分析方法，不同的分析方法對(duì)語義處理的次序不同；為屬性分配存儲(chǔ)空間；考慮計(jì)算次序。翻譯方案1，自下而上計(jì)算，LR分析。以3+5+8為例，歸約時(shí)翻譯。產(chǎn)生式翻譯方案1L→Eprint_post(post);E→E1+E2post(k):='+';k:=k+1;E→numpost(k):=lexval;k:=k+1;post:(35+8+)104.1語法制導(dǎo)翻譯簡(jiǎn)介屬性作為分析樹的注釋 將屬性附著在分析樹對(duì)應(yīng)文法符號(hào)上，形成注釋分析樹。[例4.2]3+5+8的分析樹和注釋分析樹：產(chǎn)生式語法制導(dǎo)定義翻譯方案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+))114.1語法制導(dǎo)翻譯簡(jiǎn)介注釋分析樹上看繼承屬性與綜合屬性

繼承屬性是自上而下計(jì)算的綜合屬性是自下而上計(jì)算的提醒：除非特別提醒，本章討論的語法制導(dǎo)翻譯是綜合屬性。.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))12上次課總結(jié)語法制導(dǎo)翻譯的基本概念屬性與語義規(guī)則語義規(guī)則的兩種形式134.1語法制導(dǎo)翻譯簡(jiǎn)介L(zhǎng)R分析翻譯方案的設(shè)計(jì)LR分析中的語法制導(dǎo)翻譯實(shí)質(zhì)上是對(duì)LR語法分析的擴(kuò)充：擴(kuò)充LR分析器的功能：當(dāng)執(zhí)行歸約產(chǎn)生式的動(dòng)作時(shí)，也執(zhí)行產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。由于是歸約時(shí)執(zhí)行語義動(dòng)作，限制語義動(dòng)作僅能放在產(chǎn)生式右部的最右邊；擴(kuò)充分析棧：增加一個(gè)與分析棧并列的語義棧，用于存放分析棧中文法符號(hào)所對(duì)應(yīng)的屬性值。例如：E→E1+E2val[top]:=val[top]+val[top+2];

對(duì)于表達(dá)式5+3

當(dāng)歸約為左部E時(shí) 同時(shí)也得到了值814[例4.3]3+5*8的語法制導(dǎo)翻譯。產(chǎn)生式L→EE→E1+E2E→E1*E2E→n分析棧 語義棧 輸入 語義動(dòng)作# # 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;語法制導(dǎo)定義print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;154.1語法制導(dǎo)翻譯簡(jiǎn)介遞歸下降分析翻譯方案的設(shè)計(jì)遞歸下降方法是用程序?qū)崿F(xiàn)對(duì)非終結(jié)符的展開和對(duì)終結(jié)符的匹配。翻譯方案的設(shè)計(jì)需要解決兩個(gè)問題：如何在遞歸下降子程序中嵌入語義動(dòng)作？ 產(chǎn)生式右部的任何位置；如何為文法符號(hào)的屬性設(shè)計(jì)存儲(chǔ)空間？ 函數(shù)返回值、參數(shù)、變量等。例如在上機(jī)作業(yè)中，函數(shù)繪圖語言解釋器語法制導(dǎo)翻譯設(shè)計(jì)：遞歸子程序可以設(shè)計(jì)為函數(shù)，用于返回必要的屬性值；適當(dāng)設(shè)計(jì)子程序中的臨時(shí)變量，用于保存屬性值；將語義動(dòng)作嵌入在子程序的適當(dāng)位置，正確計(jì)算屬性值。164.2

中間代碼簡(jiǎn)介編譯器各階段的完整輸出，均可以被認(rèn)為是源程序的某種中間表示。本章討論的是中間代碼生成器輸出的中間表示，稱之為中間代碼。中間代碼實(shí)際上應(yīng)起一個(gè)編譯器前端與后端分水嶺的作用。要求中間代碼具有如下特性，以便于編譯器的開發(fā)移植和代碼的優(yōu)化：便于語法制導(dǎo)翻譯；既與機(jī)器指令的結(jié)構(gòu)相近，又與具體機(jī)器無關(guān)。中間代碼的主要形式：樹、后綴式、三地址碼等。174.2

中間代碼簡(jiǎn)介后綴式操作數(shù)在前，操作符緊隨其后，無需用括號(hào)限制運(yùn)算的優(yōu)先級(jí)和結(jié)合性。算法4.1后綴式計(jì)算采用下述過程進(jìn)行計(jì)算，最終結(jié)果留在棧中。

x:=first_token; whilenotend_of_exp

loop ifxinoperators then pushx; --操作數(shù)進(jìn)棧

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

push(evaluate); --計(jì)算，將結(jié)果進(jìn)棧

endif; next(x); endloop;184.2

中間代碼簡(jiǎn)介loop ifxinoperators then pushx; --操作數(shù)進(jìn)棧

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

push(evaluate); --計(jì)算，將結(jié)果進(jìn)棧

endif; next(x);endloop;算術(shù)表達(dá)式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 #194.2

中間代碼簡(jiǎn)介后綴式并不局限于二元運(yùn)算的表達(dá)式，可以推廣到任何語句，遵守操作數(shù)在前，操作符緊跟其后的原則即可。對(duì)語句： ifethenxelsey后綴式可以寫為： exyif-then-else (1)此時(shí)e、x和y均需計(jì)算。實(shí)際上，根據(jù)條件e的取值，x和y不用都計(jì)算：

ep1jezxp2jumpp1:yp2: (2)其中：p1和p2分別是標(biāo)號(hào)；

p1jez表示e的結(jié)果為0（假）則轉(zhuǎn)向p1；

p2jump表示無條件轉(zhuǎn)向p2。與(1)比較，(2)中的if-then-else被分解，首先計(jì)算e，根據(jù)e的結(jié)果是否為真，決定計(jì)算x還是計(jì)算y。204.2

中間代碼簡(jiǎn)介三地址碼三地址碼的直觀表示語法：result:=arg1oparg2或

result:=oparg1或

oparg1語義：結(jié)果存放在result中的二元運(yùn)算arg1oparg2

結(jié)果存放在result中一元運(yùn)算oparg1

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

T1:=b*c T2:=a+T1 x:=T2214.2

中間代碼簡(jiǎn)介三地址碼的種類序號(hào) 三地址碼 四元式（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)224.2

中間代碼簡(jiǎn)介三地址碼的實(shí)現(xiàn)：三元式與四元式三元式 三元式(i)(op,arg1,arg2) 三地址碼(i):=arg1oparg2[例4.5]表達(dá)式x:=a+b*c的三元式：

(1)(*，b，c) (2)(+，a，(1)) (3)(:=，x，(2))序號(hào)的雙重含義：既代表此三元式，又代表三元式存放的結(jié)果存放方式：數(shù)組結(jié)構(gòu)，三元式在數(shù)組中的位置由下標(biāo)決定。弱點(diǎn)：給代碼的優(yōu)化帶來困難。因?yàn)榇a優(yōu)化常使用的方法是刪除某些代碼或移動(dòng)某些代碼位置，而一旦進(jìn)行了代碼的刪除或移動(dòng)，則表示某三元式的序號(hào)會(huì)發(fā)生變化，從而使得其他三元式中對(duì)原序號(hào)的引用無效。234.2

中間代碼簡(jiǎn)介語法制導(dǎo)翻譯設(shè)計(jì)的基本步驟文法符號(hào)屬性的設(shè)計(jì)必要的基本操作（函數(shù)等）的設(shè)計(jì)語義規(guī)則的設(shè)計(jì)三元式的語法制導(dǎo)翻譯屬性.code：三元式代碼，指示標(biāo)識(shí)符的存儲(chǔ)單元或三元式表中的序號(hào)；屬性.name：標(biāo)識(shí)符的名字；函數(shù)trip(op，arg1，arg2)：生成一個(gè)三元式，返回三元式的序號(hào)；函數(shù)entry()：返回標(biāo)識(shí)符在符號(hào)表中的位置或存儲(chǔ)位置。244.2

中間代碼簡(jiǎn)介產(chǎn)生式 語義規(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分析)254.2

中間代碼簡(jiǎn)介四元式四元式是對(duì)三元式的改進(jìn)，將表示計(jì)算結(jié)果的三元式序號(hào)用一個(gè)顯式的變量表示，從而避免了三元式的值與三元式在三元組中的位置相關(guān)的弱點(diǎn)。四元式的語法：(op，arg1，arg2，result)所表示的計(jì)算：result:=arg1oparg2四元式的特點(diǎn)：四元式與三元式的唯一區(qū)別：將由序號(hào)所表示的運(yùn)算結(jié)果改為由臨時(shí)變量來表示。此改進(jìn)使得四元式的運(yùn)算結(jié)果與其位置無關(guān)，為代碼優(yōu)化提供了極大方便：可以刪除或移動(dòng)四元式而不影響運(yùn)算結(jié)果。三地址碼與四元式形式的保持一致。四元式的種類三元式(i)(op,arg1,arg2)(i):=arg1oparg2264.2

中間代碼簡(jiǎn)介四元式的語法制導(dǎo)翻譯屬性.code：表示存放運(yùn)算結(jié)果的變量；函數(shù)newtemp：返回一個(gè)新的臨時(shí)變量，如T1，...等；過程emit(op，arg1，arg2,result)：生成一個(gè)四元式，若為一元運(yùn)算，則arg2可空。產(chǎn)生式與語義規(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()}274.2

中間代碼簡(jiǎn)介圖形表示樹作為中間代碼 語法樹真實(shí)反映句子結(jié)構(gòu)，對(duì)語法樹稍加修改(加入語義信息)，即可以作為中間代碼的一種形式(注釋語法樹)。[例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)284.2

中間代碼簡(jiǎn)介樹的語法制導(dǎo)翻譯屬性.nptr：指向樹節(jié)點(diǎn)的指針；函數(shù)mknode(op，nptr1，nptr2)：生成一個(gè)根或內(nèi)部節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)是op，nptr1和nptr2分別指向的左右孩子的子樹。若僅有一個(gè)孩子，則nptr2為空；函數(shù)mkleaf(node)：生成一個(gè)葉子節(jié)點(diǎn)。(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ī)則設(shè)計(jì)是相似的。294.2

中間代碼簡(jiǎn)介樹的優(yōu)化表示－DAG如果樹上若干個(gè)節(jié)點(diǎn)有完全相同的孩子，則這些節(jié)點(diǎn)可以指向同一個(gè)孩子，形成一個(gè)有向無環(huán)圖(DirectedAcyclicGraph,DAG)，與樹的唯一區(qū)別是多個(gè)父親可以共享同一個(gè)孩子，從而達(dá)到資源(運(yùn)算、代碼等)共享的目的。DAG的語法制導(dǎo)翻譯與樹的語法制導(dǎo)翻譯相似，僅需要在mknode和mkleaf中增加相應(yīng)的查詢功能：先查看所要構(gòu)造的節(jié)點(diǎn)是否已經(jīng)存在，若存在則無需構(gòu)造新的節(jié)點(diǎn)，直接返回指向已存在節(jié)點(diǎn)的指針即可。304.2

中間代碼簡(jiǎn)介樹與其他中間代碼的關(guān)系樹表示的中間代碼與后綴式和三地址碼之間有內(nèi)在聯(lián)系：對(duì)樹進(jìn)行深度優(yōu)先后序遍歷，得到的線性序列就是后綴式，或者說后綴式是樹的一個(gè)線性化序列；樹的每個(gè)內(nèi)部節(jié)點(diǎn)和它的孩子對(duì)應(yīng)一個(gè)三元式或四元式。[例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)現(xiàn)代的編譯器基礎(chǔ)架構(gòu)均用語法樹作為中間表示。31上次課總結(jié)中間代碼后綴式三地址碼三元式四元式圖形表示324.3

符號(hào)表簡(jiǎn)介符號(hào)表的作用：連接聲明與引用的橋梁，記住每個(gè)符號(hào)的相關(guān)信息，如作用域和綁定等，幫助編譯的各個(gè)階段正確有效地工作。符號(hào)表設(shè)計(jì)的基本要求：合理存放信息、快速準(zhǔn)確查找。正確存儲(chǔ)各類信息；適應(yīng)不同階段的需求；便于有效地進(jìn)行查找、插入、刪除和修改等操作；空間可以動(dòng)態(tài)擴(kuò)充。334.3

符號(hào)表簡(jiǎn)介符號(hào)表?xiàng)l目邏輯上講：每個(gè)聲明的名字在符號(hào)表中占據(jù)一欄，稱為一個(gè)條目，用于存放名字的相關(guān)信息。符號(hào)表中的內(nèi)容：保留字、標(biāo)識(shí)符、特殊符號(hào)(包括算符、分隔符等)等。多個(gè)子表：不同類別的符號(hào)可以存放在不同的子表中，如變量名表、過程名表、保留字表等。存放方式：關(guān)鍵字＋屬性。組合關(guān)鍵字：intx; {doublex; structx{floaty,z;}; }C符號(hào)表的組合關(guān)鍵字至少包括：名字＋作用域＋類型一個(gè)名字x在同一作用域中允許有多個(gè)的聲明，則引用時(shí)需要根據(jù)上下文確定x屬于哪個(gè)對(duì)象。為簡(jiǎn)化編譯，大多數(shù)語言在語法上不允許這樣的聲明344.3

符號(hào)表簡(jiǎn)介構(gòu)成名字的字符串的存儲(chǔ)

定長(zhǎng)數(shù)據(jù)采用直接存放，變長(zhǎng)數(shù)據(jù)采用間接存放。

名字（直接存儲(chǔ)） 屬性

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

名字（間接存儲(chǔ)） 屬性

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↑101354.3

符號(hào)表簡(jiǎn)介間接存儲(chǔ)的特點(diǎn)：間接存儲(chǔ)的方法實(shí)際上解決了復(fù)雜信息的存儲(chǔ)問題；將其推廣到屬性，則任何一個(gè)復(fù)雜的屬性，均可以為其另辟空間；空間本身可以是任何復(fù)雜結(jié)構(gòu)，如數(shù)組的內(nèi)情向量等。指向空間的指針存放于此屬性在符號(hào)表中的對(duì)應(yīng)位置。關(guān)鍵字屬性x...任何復(fù)雜結(jié)構(gòu)364.3

符號(hào)表簡(jiǎn)介名字的作用域程序設(shè)計(jì)語言的名字可以出現(xiàn)在不同的范圍內(nèi)，并且可以具有不同的意義。兩種劃分范圍的方式：并列的和嵌套的。不同的語言采用不同的方式：如Pascal的過程定義可以是嵌套的，而C的過程定義是并列的，但是C允許程序塊是嵌套的。（問題：過程與程序塊的主要區(qū)別？）名字的作用域：名字在哪個(gè)范圍內(nèi)起作用。并列的兩個(gè)范圍內(nèi)的名字作用域互不相干，但是分別在嵌套的兩個(gè)范圍內(nèi)的名字，其作用域的問題就需要制定規(guī)則來限定，以使得任何一個(gè)名字在任何范圍內(nèi)涵義都是無二義的。名字的作用域規(guī)則：規(guī)定一個(gè)名字在什么樣的范圍內(nèi)應(yīng)該表示什么意義。374.3

符號(hào)表簡(jiǎn)介靜態(tài)作用域規(guī)則(static-scoperule)編譯時(shí)就可以確定名字的作用域，即僅從靜態(tài)讀程序就可確定名字的作用域。最近嵌套規(guī)則(mostcloselynested)以程序塊為例，也適用于過程。程序塊B中聲明的作用域包括B；如果名字x不在B中聲明，那么B中x的出現(xiàn)是在外圍程序塊B'的x聲明的作用域中，使得B'有x的聲明，并且B'比其它任何含x聲明的程序塊更接近被嵌套的B通俗地講，名字聲明在離其最近的內(nèi)層起作用，即在名字引用處從內(nèi)向外看，它處在所遇到的第一個(gè)該名字聲明的作用域。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); /*結(jié)果為：2，1*/ } { intb=3; /*B3層，與B2并列*/ printf("%d%d\n",a,b); /*結(jié)果為：0，3*/ } printf("%d%d\n",a,b); /*結(jié)果為：0，1*/ }printf("%d%d\n",a,b); /*結(jié)果為：0，0*/}聲明 作用域inta=0 B0-B2intb=0 B0-B1intb=1 B1-B3inta=2 B2intb=3 B3394.3

符號(hào)表簡(jiǎn)介線性表線性表應(yīng)是一個(gè)棧，以正確反映名字的作用域，即符號(hào)的加入和刪除，均在線性表的一端進(jìn)行。關(guān)鍵字：名字＋作用域；線性表上的操作：查找：從表頭(棧頂)開始，遇到的第一個(gè)名字；插入：先查找，再插入在表頭；1voidmain()2{inta=0,b=0; //B03{intb=1; //B14{inta=2,c=4,d=5; }//B27{intb=3; }//B311}}404.3

符號(hào)表簡(jiǎn)介刪除：(a)暫時(shí)：將在同一作用域的名字同時(shí)摘走，適當(dāng)保存；(b)永久：將在同一作用域的名字同時(shí)摘走，不再保存修改：與查找類似，修改第一個(gè)遇到的名字的信息。修改可以用刪除＋插入代替。線性表上操作的效率（n個(gè)條目） 成功查找(平均)：(n+1)/2；不成功查找：n+1

建立n個(gè)條目的符號(hào)表(最壞)：∑i

＝(n+1)n/2414.3

符號(hào)表簡(jiǎn)介散列表將線性表分成m個(gè)小表，構(gòu)造hash函數(shù)，使名字均勻散布在子表中。若散列均勻，則時(shí)間復(fù)雜度會(huì)降到原線性表的1/m名字掛在兩個(gè)鏈上(便于刪除操作)：散列鏈(hashlink)：鏈接所有具有相同hash值的元素，表頭在表頭數(shù)組中；作用域鏈(scopelink)：鏈接所有在同一作用域中的元素，表頭在作用域鏈中。S1

S2

S4在同一作用域S3在另一作用域424.3

符號(hào)表簡(jiǎn)介散列表上的操作查找：首先計(jì)算散列函數(shù)，然后從散列函數(shù)所指示的入口進(jìn)入某個(gè)線性表，在線性表中沿hashlink，象查找單鏈表中的名字一樣查找。插入：首先查找，以確定要插入的名字是否已在表中，若不在，則要分別沿hashlink和scopelink插入到兩個(gè)鏈中，方法均是插在表頭，即兩個(gè)表均可看作是棧。刪除：把以作用域鏈連在一起的所有元素從當(dāng)前符號(hào)表中刪除，保留作用域鏈所鏈的子表，為后繼工作使用(如果是臨時(shí)刪除，則下次使用時(shí)直接沿作用域鏈加入到散列鏈中即可)。431voidmain()2{inta=0,b=0; //B03{intb=1; //B14{inta=2,c=4,d=5; }//B27{intb=3; }//B311}}設(shè)：hash(s)=ord(s)-ord('a')分析在B2中：退出B2進(jìn)入B3：44上次課總結(jié)符號(hào)表符號(hào)表的條目名字的存儲(chǔ)名字的作用域（靜態(tài)與最近嵌套原則）線性表散列表（作用域鏈與散列鏈）454.3

符號(hào)表簡(jiǎn)介散列函數(shù)的計(jì)算 hash:string→integer減少?zèng)_突，分布均勻充分考慮程序設(shè)計(jì)語言的特點(diǎn)例：若有變量V001,V002,…,V300，且首字母的值作為hash值，會(huì)發(fā)生什么？一種可行的hash函數(shù)計(jì)算方法：從串s=c1c2…ck的字符ci確定正整數(shù)h： 令：h0=0,

計(jì)算：hi=αhi-1+ci,1≤i≤k,

得到：h=hk α=1或α是素?cái)?shù)，如α=65599。取一素?cái)?shù)m,令h=hmodm。464.3

符號(hào)表簡(jiǎn)介思考題(P108)：對(duì)于下列函數(shù)

#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)寫出此函數(shù)的計(jì)算公式；(3)若參數(shù)是"abcd"，試給出返回值。474.4聲明語句的翻譯聲明語句的作用是為可執(zhí)行語句提供信息，以便于其執(zhí)行。對(duì)聲明語句的處理，主要是將所需要的信息正確地填寫進(jìn)合理組織的符號(hào)表中。變量的聲明變量的類型定義與聲明

類型定義為編譯器提供存儲(chǔ)空間大小的信息，變量聲明為變量分配存儲(chǔ)空間。組合數(shù)據(jù)的類型定義和變量聲明有兩種情況：定義與聲明在一起，定義與聲明分離。定義確定存儲(chǔ)空間，聲明分配存儲(chǔ)空間簡(jiǎn)單數(shù)據(jù)類型的存儲(chǔ)空間是已經(jīng)確定的，如integer可以占4個(gè)字節(jié)，real可以占8個(gè)字節(jié)，char可以占1個(gè)字節(jié)等組合數(shù)據(jù)類型變量的存儲(chǔ)空間，需要編譯器根據(jù)程序員提供的信息計(jì)算而定484.4聲明語句的翻譯例：在Pascal程序中的類型定義與變量聲明：

先定義后聲明

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

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

定義與聲明同時(shí)

varc,p:array[1..2]ofinteger; display:array[1..24]ofchar;強(qiáng)調(diào)：簡(jiǎn)單變量聲明中類型是預(yù)定義的；組合變量聲明中類型需自己定義。（定義的兩種形式）494.4聲明語句的翻譯變量聲明的語法制導(dǎo)翻譯變量聲明的文法：

D→D;D (1) |id:T (2) T→int (3) |real (4) |array[num]ofT (5) |^T (6)(5)是數(shù)組類型的聲明，其中的數(shù)組元素個(gè)數(shù)由num表示，如num可以是5或10等，它等價(jià)于1..5或1..10。(6)是指針類型的聲明，其寬度(大小)是一個(gè)常量。數(shù)組元素的類型和指針?biāo)笇?duì)象的類型可以是任意合法類型。聲明多維數(shù)組：A:array[d1]ofarray[d2]of...array[dn]ofint此多維數(shù)組以行為主存儲(chǔ)。因?yàn)榈谝痪S是有d1個(gè)元素的一維數(shù)組，每個(gè)元素又是一個(gè)n-1維的數(shù)組；依此類推。504.4聲明語句的翻譯填寫符號(hào)表信息的語法制導(dǎo)翻譯全程量offset：記錄當(dāng)前符號(hào)存儲(chǔ)的偏移量，初值設(shè)為0屬性.type和.width：變量的類型和所占據(jù)的存儲(chǔ)空間過程enter(name,type,offset)：為type類型的變量name建立符號(hào)表?xiàng)l目，并為其分配存儲(chǔ)空間(位置)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;}514.4聲明語句的翻譯例聲明的語法制導(dǎo)翻譯：a:array[10]ofint;x:int;(無分號(hào))序號(hào)歸約使用的產(chǎn)生式 語義處理結(jié)果(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=4452上次課總結(jié)變量聲明類型定義與變量聲明語法制導(dǎo)翻譯534.4聲明語句的翻譯過程的定義與聲明過程（procedure）：過程頭＋過程體；函數(shù)；主程序過程的三種形式：過程定義、過程聲明和過程調(diào)用

Ada過程定義：

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

temp:integer; --體中的聲明

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

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

swap(a,b); --過程調(diào)用先聲明后引用原則 過程定義可以寫在對(duì)它的引用之后或引用時(shí)看不到的地方。在這樣的情況下，引用前必須先聲明。而若引用前已定義，則聲明可省略，因?yàn)槎x已包括了聲明。544.4聲明語句的翻譯左值與右值形式上，出現(xiàn)在賦值號(hào)左邊和右邊的變量稱為左值和右值實(shí)質(zhì)上，左值必須具有存儲(chǔ)空間，右值可以僅是一個(gè)值，而沒有存儲(chǔ)空間。形象地講，左值是容器，右值是內(nèi)容。(1)consttwo=2; --聲明一個(gè)值為2的常量two(2)x:integer; --聲明一個(gè)類型為整型數(shù)的變量x(3)functionmax(a,b:integer)returninteger;

--聲明一個(gè)返回值類型是整型數(shù)的函數(shù)max(4)x:=two; --x當(dāng)前值為2(5)x:=two+x; --x當(dāng)前值變?yōu)?(6)x:=max(two,x)+x; --x當(dāng)前值變?yōu)?(7)4:=x; --字面量不能作為左值(8)two:=x; --常量不能作為左值(9)max(two,x):=two; --函數(shù)返回值不能作為左值(10)x+two:=x+two; --表達(dá)式的值不能作為左值554.4聲明語句的翻譯參數(shù)傳遞形參與實(shí)參定義時(shí)的參數(shù)稱為形參(parameter或formalparameter)引用時(shí)的參數(shù)稱為實(shí)參(argument或actualparameter)常見的參數(shù)傳遞形式：（不同的語言提供不同的形式）值調(diào)用（callbyvalue）引用調(diào)用（callbyreference）復(fù)寫－恢復(fù)（copy-in/copy-out）換名調(diào)用（callbyname）參數(shù)傳遞方法的實(shí)質(zhì)：實(shí)參是代表左值、右值、還是實(shí)參本身的正文。564.4聲明語句的翻譯值調(diào)用值調(diào)用的特點(diǎn)：過程內(nèi)部對(duì)參數(shù)的修改，不影響作為實(shí)參的變量原來的值。實(shí)參的特點(diǎn)：任何可以作為右值的對(duì)象均可作為實(shí)參。參數(shù)傳遞和過程內(nèi)對(duì)參數(shù)的使用原則：過程定義時(shí)形參被當(dāng)作局部名看待，并在過程內(nèi)部為形參分配存儲(chǔ)單元；調(diào)用過程前，首先計(jì)算實(shí)參并將值（實(shí)參的右值）放入形參的存儲(chǔ)單元；過程內(nèi)部對(duì)形參單元中的數(shù)據(jù)直接訪問。574.4聲明語句的翻譯值調(diào)用舉例：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.運(yùn)行結(jié)果：a=1 b=2//等價(jià)的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;}584.4聲明語句的翻譯引用調(diào)用引用調(diào)用的特點(diǎn)：過程內(nèi)部對(duì)形參的修改，等價(jià)于直接對(duì)實(shí)參的修改。實(shí)參的特點(diǎn)：必須是左值。參數(shù)傳遞和過程內(nèi)對(duì)參數(shù)的使用原則：定義時(shí)形參被當(dāng)作局部名看待，并在過程內(nèi)部為形參分配存儲(chǔ)單元；調(diào)用過程前，將作為實(shí)參的變量的地址放進(jìn)形參的存儲(chǔ)單元；過程內(nèi)部把形參單元中的數(shù)據(jù)當(dāng)作地址，進(jìn)行間接訪問594.4聲明語句的翻譯引用調(diào)用舉例：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.運(yùn)行結(jié)果：a=2 b=1//等價(jià)的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;}604.4聲明語句的翻譯值調(diào)用模擬引用調(diào)用#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語言只有值調(diào)用因此：只能用值調(diào)用形式模擬引用調(diào)用的效果同樣：過程式程序設(shè)計(jì)語言可以模擬面向?qū)ο蟮睦^承機(jī)制結(jié)論：語言與程序設(shè)計(jì)范型（方法）不是一一對(duì)應(yīng)的關(guān)系614.4聲明語句的翻譯復(fù)寫－恢復(fù)引用調(diào)用的副作用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 結(jié)果：a=4原因：實(shí)參與非本地量共用一個(gè)存儲(chǔ)空間，使得在過程內(nèi)改變參數(shù)值的同時(shí)，也改變了非本地量的值。624.4聲明語句的翻譯復(fù)寫-恢復(fù)的特點(diǎn)：(值調(diào)用和引用調(diào)用的結(jié)合)過程內(nèi)部對(duì)參數(shù)的修改不直接影響實(shí)參，避免了副作用返回時(shí)將形參內(nèi)容恢復(fù)給實(shí)參，實(shí)現(xiàn)了參數(shù)的返回。實(shí)參的特點(diǎn)：必須是左值。參數(shù)傳遞和過程內(nèi)對(duì)參數(shù)的使用原則：過程定義時(shí)形參被當(dāng)作局部名，在過程內(nèi)部為形參分配單元(復(fù)寫)；調(diào)用過程前，計(jì)算實(shí)參并將右值放入形參的存儲(chǔ)單元；過程內(nèi)部對(duì)形參單元中的數(shù)據(jù)直接訪問；過程返回前，將形參右值放回實(shí)參的存儲(chǔ)單元(恢復(fù))。634.4聲明語句的翻譯復(fù)寫-恢復(fù)舉例：proceduretestis --Ada源程序

a:integer; procedureadd_one(x:inoutinteger);--復(fù)寫-恢復(fù)調(diào)用

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

設(shè)主程序(最外層過程)的嵌套深度dmain=1，則若過程A直接嵌套定義過程B，則dB=dA+1；變量聲明時(shí)所在過程的嵌套深度，被認(rèn)為是該變量的嵌套深度。與程序塊相比，有兩點(diǎn)不同，使得過程聲明的處理復(fù)雜：過程頭(即界面)是一個(gè)名字，可象引用變量一樣被調(diào)用程序塊的執(zhí)行(控制流)與靜態(tài)一致，而過程不一致。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,j3694.4聲明語句的翻譯符號(hào)表中的作用域信息嵌套過程中的名字作用域信息，使用有嵌套結(jié)構(gòu)的符號(hào)表保存。每個(gè)過程被認(rèn)為是一個(gè)子符號(hào)表，或者是符號(hào)表中的一個(gè)節(jié)點(diǎn)。嵌套的節(jié)點(diǎn)之間用雙向鏈連接，正向鏈指示過程的嵌套關(guān)系，逆向鏈實(shí)現(xiàn)按作用域?qū)γ诌M(jìn)行訪問。參數(shù)如何處理?70上次課總結(jié)過程的定義與聲明定義、聲明與引用左值與右值參數(shù)傳遞：值調(diào)用、引用調(diào)用、復(fù)寫－恢復(fù)、換名調(diào)用嵌套定義的過程中信息的存儲(chǔ)作用域信息的保存過程的作用域符號(hào)表中的作用域信息語法制導(dǎo)翻譯生成符號(hào)表714.4聲明語句的翻譯語法制導(dǎo)翻譯生成符號(hào)表簡(jiǎn)化的過程定義文法(忽略了參數(shù)) P→D (1) D→D;D (2) |id:T (3) |procid;D;S (4)修改文法，在定義D之前生成符號(hào)表(LR分析) P→MD (1) D→D;D (2) |id:T (3) |procid;ND;S (4) M→ε (5) N→ε (6)問題：如何在處理產(chǎn)生式(1)和(4)的語言結(jié)構(gòu)時(shí)正確地填寫符號(hào)表信息(雙向鏈表)？724.4聲明語句的翻譯全程量、屬性與語義函數(shù)全程量：有序?qū)?tblptr,offset) (符號(hào)表節(jié)點(diǎn)的指針,符號(hào)表節(jié)點(diǎn)所需寬度)棧上的操作：push(t,o)、pop、top(stack)語義函數(shù)與過程：函數(shù)mktable(previous)：建立一個(gè)新的節(jié)點(diǎn)，返回指向新節(jié)點(diǎn)的指針。previous是逆向鏈，指向該節(jié)點(diǎn)的前驅(qū)(外層)。過程enter(table,name,type,offset)：在table指向的節(jié)點(diǎn)中為名字name建立新的條目，包括名字的類型和存儲(chǔ)位置等。過程addwidth(table,width)：計(jì)算table節(jié)點(diǎn)中所有條目的累加寬度，并記錄在table的頭部信息中。過程enterproc(table,name,newtable)：為過程name在table指向的節(jié)點(diǎn)中建立一個(gè)新的條目。參數(shù)newtable是正向鏈，指向name過程自身的符號(hào)表節(jié)點(diǎn)。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);}744.4聲明語句的翻譯語法制導(dǎo)翻譯的過程procsort;a:array[10]ofint;x:int;procreadarry;i:int;read(a);readarray75(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)填進(jìn)t2所指節(jié)點(diǎn)，top(offset):=40(6)T3→int T2.type=integer,T2.width=4(7)D2→x:T3 (x,int,40)填進(jìn)t2所指節(jié)點(diǎn)，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)填進(jìn)t3所指節(jié)點(diǎn)，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;764.5簡(jiǎn)單算術(shù)表達(dá)式與賦值句討論所基于的文法：A→id:=E E→E+E|E*E|-E|(E)|id簡(jiǎn)單變量的語法制導(dǎo)翻譯屬性.place：存放E的變量名地址(符號(hào)表中地址或臨時(shí)變量)過程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()}774.5簡(jiǎn)單算術(shù)表達(dá)式與賦值句變量的(內(nèi)部)類型轉(zhuǎn)換強(qiáng)制(coercion)：按照一定的原則，將不同類型的變量在內(nèi)部轉(zhuǎn)換為相同的類型，然后進(jìn)行同類型變量的計(jì)算。屬性.mode：取值int或real表達(dá)式的類型判定樹：運(yùn)算的轉(zhuǎn)換原則賦值的轉(zhuǎn)換原則784.5簡(jiǎn)單算術(shù)表達(dá)式與賦值句三地址碼：

T:=itrE：將E從整型變?yōu)閷?shí)型，結(jié)果存放T中

T:=rtiE：將E從實(shí)型變?yōu)檎?，結(jié)果存放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; }794.5簡(jiǎn)單算術(shù)表達(dá)式與賦值句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－129804.5簡(jiǎn)單算術(shù)表達(dá)式與賦值句[例4.17]x:=-a*b+c的語法制導(dǎo)翻譯，x、a、b是整型數(shù)，c是實(shí)型數(shù)。序號(hào)產(chǎn)生式 中間代碼(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)814.6數(shù)組元素的引用確定數(shù)組空間的存儲(chǔ)分配：以第一個(gè)元素地址為首地址，分配一個(gè)連續(xù)空間。多維到一維存儲(chǔ)空間的映射方法： 以行為主或以列為主三行三列的二維數(shù)組：a[0..2,2..4]以行為主存放時(shí)的元素排列：

a[0,2]a[0,3]a[0,4]a[1,2]a[1,3]a[1,4]a[2,2]a[2,3]a[2,4]以列為主存放時(shí)的元素排列：

a[0,2]a[1,2]a[2,2]a[0,3]a[1,3]a[2,3]a[0,4]a[1,4]a[2,4]確定數(shù)組元素地址的兩個(gè)要素：首地址和相對(duì)首地址的偏移量。不同的映射方式，使得同一個(gè)數(shù)組元素相對(duì)首地址的偏移量不同。a[0,2]a[0,3]a[0,4]a[1,2]a[1,3]a[1,4]a[2,2]a[2,3]a[2,4]824.6數(shù)組元素的引用確定映射方式的兩種方法由聲明時(shí)的語法確定映射方式：

a:array[d1]ofarray[d2]of...array[dn]ofinteger;

引用方式：a[i1,i2,...,in]或a[i1][i2]...[in]由編譯器確定映射方式：

a:array[d1,d2,...,dn]ofinteger;

引用方式：a[i1,i2,...,in]數(shù)組元素引用時(shí)地址的確定：根據(jù)映射方式求出計(jì)算公式；根據(jù)計(jì)算公式設(shè)計(jì)語義規(guī)則。834.6數(shù)組元素的引用數(shù)組元素的地址計(jì)算三個(gè)假設(shè)條件：以行為主存放，推廣到n維，就是數(shù)組的第i維中每個(gè)成員是di個(gè)n-i維的數(shù)組，其中di是第i維成員的個(gè)數(shù)；數(shù)組每維的下界均為1；每個(gè)元素占一個(gè)標(biāo)準(zhǔn)存貯單元(認(rèn)為是一個(gè)字或者字節(jié))。數(shù)組的聲明： A[d1,d2,..,dn]數(shù)組元素的引用： A[i1,i2,..,in]假設(shè)首地址為a，一個(gè)元素占w個(gè)單元一維數(shù)組地址計(jì)算：addr(A[i])=a+(i-1)*w二維數(shù)組地址計(jì)算：addr(A[i1,i2])=a+((i1-1)*d2+(i2-1))*w844.6數(shù)組元素的引用n維數(shù)組地址計(jì)算addr(A[i1，i2，...，in])=a+((i1-1)*d2*d3*...*dn+(i2-1)*d3*d4*...*dn+...+(in-1))*w=a-(d2*d3*...*dn+d3*d4*...*dn+...+dn+1)*w+(i1*d2*d3*...*dn+i2*d3*d4*...*dn+...+in-1*dn+in)*w=a–c*w+v*w根據(jù)假設(shè)條件③w=1:addr(A[i1，i2，...，in])=a–c+v數(shù)組元素引用的語法制導(dǎo)翻譯基本方法：求c和v的遞推計(jì)算公式；修改文法以適應(yīng)遞推計(jì)算；85上次課總結(jié)作用域信息的保存過程的作用域符號(hào)表中的作用域信息語法制導(dǎo)翻譯生成符號(hào)表簡(jiǎn)單算術(shù)表達(dá)式與賦值句的語法制導(dǎo)翻譯內(nèi)部類型轉(zhuǎn)換數(shù)組元素的引用地址兩要素：首地址、偏移量地址計(jì)算公式：a-c+v864.7布爾表達(dá)式布爾表達(dá)式的作用與結(jié)構(gòu)布爾表達(dá)式的應(yīng)用：邏輯運(yùn)算，如：x:=aorb控制語句的控制條件，如ifCthen...，whileCdo...等布爾表達(dá)式與其他表達(dá)式的關(guān)系：

BE→BEorBE|BEandBE|notBE|(BE)|RE|true|falseRE→RErelopRE|(RE)|EE→EopE|-E|(E)|id|num約定的優(yōu)先級(jí)與結(jié)合性：從高到低，notandor簡(jiǎn)化的布爾表達(dá)式文法：

E→EorE|EandE|notE|(E)|idrelopid|id|true|false874.7布爾表達(dá)式布爾表達(dá)式的計(jì)算方法數(shù)值表示的直接計(jì)算可以用1表示true，0表示falseor、and、not與+、*、-(一元)對(duì)應(yīng)例如AorBandnotC的三地址碼：T1:=notCT2:=BandT1T3:=AorT2關(guān)系運(yùn)算表達(dá)式a<b的計(jì)算，翻譯成如下的三地址碼序列：(1)ifa<bgoto(4)(2)t1:=0(3)goto(5)(4)t1:=1884