《西安電子科技大學(xué)《編譯原理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)《編譯原理.ppt（41頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、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ī)作業(yè)第三部分：語法制導(dǎo)翻譯繪制函數(shù)圖形,2,4.1 語法制導(dǎo)翻譯簡(jiǎn)介4.1.1 語法與語義, 語法與語義的關(guān)系 語法是指語言的結(jié)構(gòu)、即語言的“樣子”；語義是指附著于語言結(jié)構(gòu)上的實(shí)際含意 ，即語言的“意義”。 對(duì)于語法和語義： 語義不能離開
2、語法獨(dú)立存在； 語義遠(yuǎn)比語法復(fù)雜； 同一語言結(jié)構(gòu)可以包含多種含意，不同語言結(jié)構(gòu)表示相同含意； 語法與語義之間沒有明確的界線。,例1：貓吃老鼠與老鼠吃貓 例2：程序設(shè)計(jì)語言中的分情況結(jié)構(gòu)：,1case condition is case1: stat1; case2: stat2; ... end case;,2switch (condition) case condition1:stat1; case condition2:stat2; ... ,break; break;,3,4.1.1 語法與語義（續(xù)1）, 語義分析的兩個(gè)作用 檢查是否結(jié)構(gòu)正確的句子所表示的意思也合法；
3、執(zhí)行規(guī)定的語義動(dòng)作，如： 表達(dá)式求值 符號(hào)表填寫 中間代碼生成等 語義分析的方法 語法制導(dǎo)翻譯,（2004年3月31日在此結(jié)束）,4,4.1.2 屬性與語義規(guī)則, 語法制導(dǎo)翻譯的基本思想 通俗地講： 以語法分析為基礎(chǔ)，伴隨語法分析的各個(gè)步驟，執(zhí)行相應(yīng)的語義動(dòng)作。 具體方法： 1將文法符號(hào)所代表的語言結(jié)構(gòu)的意思，用附著于該文法符號(hào)的屬性表示； 2用語義規(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ì)算、查填符
4、號(hào)表、生成中間代碼、發(fā)布出錯(cuò)信息等。,5,4.1.2 屬性與語義規(guī)則（續(xù)1）, 屬性的抽象表示 .attr 例如：E.val（值） E.type（類型） E.code（代碼序列） E.place（存儲(chǔ)空間） 對(duì)文法的約定 本章關(guān)注的是語法分析的基礎(chǔ)上的語義處理，忽略語法分析。 為了簡(jiǎn)單，本章的文法一般為二義文法。默認(rèn)解決二義的方法是規(guī)定常規(guī)意義下的優(yōu)先級(jí)和結(jié)合性。,6,4.1.2 屬性與語義規(guī)則（續(xù)2）, 屬性的定義** 定義4.1 對(duì)于產(chǎn)生式A，其中是由文法符號(hào)X1X2...Xn組成的序列，它的語義規(guī)則可以表示為(4.1)所示關(guān)于屬性的函數(shù)： b := f(c1, c2, ...
5、, ck) (4.1) 語義規(guī)則中的屬性存在下述性質(zhì)與關(guān)系。 (1) 若b是A的屬性，c1, c2, ..., ck是中文法符號(hào)的屬性，或者A的其它屬性，則稱b是A的綜合屬性。 (2) 若b是中某文法符號(hào)Xi的屬性，c1, c2, ..., ck是A的屬性，或者是中其它文法符號(hào)的屬性，則稱b是Xi的繼承屬性。 (3) 稱(4.1)中屬性b依賴于屬性c1, c2, ..., ck。 (4) 若語義規(guī)則的形式如下述(4.2)，則可將其想像為產(chǎn)生式左部文法符號(hào)A的一個(gè)虛擬屬性。屬性之間的依賴關(guān)系，在虛擬屬性上依然存在。 f(c1, c2, ..., ck) (4.2
6、) ,(4.1)中屬性之間的依賴關(guān)系，實(shí)質(zhì)上反映了屬性計(jì)算的先后次序，即所有屬性ci被計(jì)算之后才能計(jì)算屬性b。,EE1+E2 E.val:=E1.val+E2.val,EE1+E2 print(E.val),7,4.1.3 語義規(guī)則的兩種形式, 語法制導(dǎo)定義 用抽象的屬性和運(yùn)算符號(hào)表示的語義規(guī)則；（公式，做什么） 翻譯方案 用具體屬性和運(yùn)算表示的語義規(guī)則。（程序段，如何做） 語義規(guī)則也被習(xí)慣上稱為語義動(dòng)作。 忽略實(shí)現(xiàn)細(xì)節(jié)，二者作用等價(jià)。（設(shè)計(jì)與實(shí)現(xiàn)）,8,4.1.3 語義規(guī)則的兩種形式（續(xù)1）,例4.1 將中綴形式的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表示的語法制導(dǎo)定義和翻譯方案。虛擬屬性print(E.
7、post)可想象為L(zhǎng).p:=print(E.post)。,產(chǎn)生式 LE EE1+E2 Enum,語法制導(dǎo)定義 print(E.post) E.post:=E1.post ||E2.post||+; E.post:=num.lexval;,翻譯方案1 print_post(post); post(k):=+; k:=k+1; post(k):=lexval; k:=k+1;,翻譯方案中需要考慮的問題： 1采用什么樣的語法分析方法； 2為屬性分配存儲(chǔ)空間； 3考慮計(jì)算次序。,產(chǎn)生式 翻譯方案2 LE EE1+E2 print(+); Enum print(lexval);,語法制導(dǎo)定義算法
8、翻譯方案程序?qū)崿F(xiàn)，多種方法,翻譯方案1，自下而上計(jì)算，LR分析。 （以3+5+8為例，歸約時(shí)翻譯）,post:(3 5 + 8 +),9,4.1.3 語義規(guī)則的兩種形式（續(xù)2）, 屬性作為分析樹的注釋 將屬性附著在分析樹對(duì)應(yīng)文法符號(hào)上，形成注釋分析樹。,產(chǎn)生式 語法制導(dǎo)定義 翻譯方案 LE print(E.post); EE1+E2 E.post:=E1.post print(+); ||E2.post||+; Enum E.post:=num.lexval; print(lexval);,例4.2 3+5+8的分析樹和注釋分析樹：,.post=3,.post=5,.post
9、=8,.post=35+,.post=35+8+,(print(35+8+)),10,4.1.3 語義規(guī)則的兩種形式（續(xù)3）, 注釋分析樹上看繼承屬性與綜合屬性 繼承屬性是自上而下計(jì)算的 綜合屬性是自下而上計(jì)算的 提醒：除非特別提醒，本章討論的語法制導(dǎo)翻譯是綜合屬性。,11,4.1.4 LR分析翻譯方案的設(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)的屬性值
10、。,例如： EE1+E2 valtop:=valtop+valtop+2;,對(duì)于表達(dá)式： 5+3,當(dāng)歸約為左部E時(shí)， 同時(shí)也得到了值8。,12,4.1.4 LR分析翻譯方案的設(shè)計(jì)（續(xù)1）,例4.3 3+5*8的語法制導(dǎo)翻譯。,語法制導(dǎo)定義 print(E.val) E.val:=E1.val+E2.val; E.val:=E1.val*E2.val; E.val:=n.lexval;,翻譯方案 print(valtop); valtop:=valtop+valtop+2; valtop:=valtop*valtop+2; valtop:=lexval;,產(chǎn)生式 LE EE1+E2 EE1*E
11、2 En,分析棧 語義棧輸入 語義動(dòng)作 # # 3+5*8#shift #n #3 +5*8#En，valtop:=lexval #E #3 +5*8#shift #E+ #3? 5*8#shift #E+n #3?5 *8#En，valtop:=lexval #E+E #3?5 *8#shift #E+E* #3?5? 8# shift #E+E*n #3?5?8 # En，valtop:=lexval #E+E*E #3?5?8 # EE1*E2; valtop:=valtop*valtop+2; #E+E #3?40 # EE1+E2，valtop:=valtop+valtop+2; #
12、E #43 #acc,13,4.1.5 遞歸下降分析翻譯方案的設(shè)計(jì),遞歸下降方法是用程序?qū)崿F(xiàn)對(duì)非終結(jié)符的展開和對(duì)終結(jié)符的匹配。翻譯方案的設(shè)計(jì)需要解決兩個(gè)問題： 1如何在遞歸下降子程序中嵌入語義動(dòng)作： 產(chǎn)生式右部的任何位置； 2如何為文法符號(hào)的屬性設(shè)計(jì)存儲(chǔ)空間： 函數(shù)返回值、參數(shù)、變量等。,例 函數(shù)繪圖語言的解釋器中語法制導(dǎo)翻譯的設(shè)計(jì)： 1遞歸子程序可以設(shè)計(jì)為函數(shù)，用于返回必要的屬性值； 2適當(dāng)設(shè)計(jì)子程序中的臨時(shí)變量，用于保存屬性值； 3將語義動(dòng)作嵌入在子程序的適位置，正確計(jì)算屬性值。 （第三次上機(jī)課介紹）,閱讀：95頁的例4.4,14,4.2. 中間代碼簡(jiǎn)介,編譯器各階段的完整輸出，均可以
13、被認(rèn)為是源程序的某種中間表示。 本章討論的是中間代碼生成器輸出的中間表示，稱之為中間代碼。 中間代碼實(shí)際上應(yīng)起一個(gè)編譯器前端與后端分水嶺的作用。 要求中間代碼具有如下特性，以便于編譯器的開發(fā)移植和代碼的優(yōu)化： 1便于語法制導(dǎo)翻譯； 2既與機(jī)器指令的結(jié)構(gòu)相近，又與具體機(jī)器無關(guān)。 中間代碼的主要形式：樹、后綴式、三地址碼等。,15,4.2.1 后綴式, 后綴式的特征 操作符在前，操作數(shù)緊隨其后，無需用括號(hào)限制運(yùn)算的優(yōu)先級(jí)和結(jié)合性。 計(jì)算后綴式的虛擬機(jī),算法4.1 后綴式計(jì)算 輸入 后綴式 輸出 計(jì)算結(jié)果 方法 采用下述過程進(jìn)行計(jì)算，最終結(jié)果留在棧中。,x := first_token; whi
14、le not end_of_exp loop if x in operators then push x; -- 操作數(shù)進(jìn)棧 else pop(operators); -- 算符，彈出操作數(shù) push(evaluate); -- 計(jì)算，并將結(jié)果進(jìn)棧 end if; next(x); end loop; ,16, 后綴式計(jì)算 4.2.1 后綴式（續(xù)1）,算術(shù)表達(dá)式3+5+8的后綴式為35+8+。 算法4.1的計(jì)算： （#35+8+#進(jìn)棧） （#3 5+8+#進(jìn)棧） （#35 +8+#彈出3和5，計(jì)算3+5，結(jié)果進(jìn)棧） （#8 8+#進(jìn)棧） （#88 +#彈出8和8，
15、計(jì)算8+8，結(jié)果進(jìn)棧） （#16 # ）,x := first_token; while not end_of_exp loop if x in operators then push x; -- 操作數(shù)進(jìn)棧 else pop(operators); -- 算符，彈出操作數(shù) push(evaluate); -- 計(jì)算，并將結(jié)果進(jìn)棧 end if; next(x); end loop;,17, 將后綴式推廣到其他語句 4.2.1 后綴式（續(xù)2）,后綴式并不局限于二元運(yùn)算的表達(dá)式，可以推廣到任何語句，只要遵守操作數(shù)在前，操作符緊跟其后的原則即可。 語句：if e
16、 then x else y 它的后綴式可以寫為： e x y if-then-else(1) 上述表示中，e、x和y均需計(jì)算。 而實(shí)際上，根據(jù)條件e的取值，x和y不能都計(jì)算： e p1 jez x p2 jump p1: y p2:(2) 其中： p1和p2分別是標(biāo)號(hào)； p1 jez表示e的結(jié)果為0（假）則轉(zhuǎn)向p1； p2 jump表示無條件轉(zhuǎn)向p2。 與 (1)比較，(2)中的if-then-else被分解，首先計(jì)算e，根據(jù)e的結(jié)果是否為真，決定計(jì)算x還是計(jì)算y。,18,4.2.2 三地址碼, 三地址碼的直觀表示 語法： 語義：,例如： 賦值句x := a + b * c的三地址碼
17、序列： T1 := b * c T2 := a + T1 x := T2 注意：直觀表示與源程序中賦值句的區(qū)別。,result := arg1 op arg2 或 result := op arg1 或 op arg1,結(jié)果存放在result中的二元運(yùn)算arg1 op arg2 結(jié)果存放在result中一元運(yùn)算op arg1 一元運(yùn)算op arg1,19, 三地址碼的種類,序號(hào) 三地址碼四元式 （1） x := y op z(op, y, z, x) （2） x := op y(op, y, , x) （3） x := y(:=, y, , x) （4） goto L(j, , , L) （5
18、） if x goto L(jnz, x, , L) （6） if x relop y goto L(jrelop, x, y, L) （7） param x(param, , , x) （8） call n, P(call, n, , P) （9） return y(return, , , y) （10） x := yi(=, yi, , x) （11） xi := y(=, y, , xi) （12） x := emit(:=，E.code, , A.code) emit(:=，E.code, , entry(id.name)) E.code:=newtemp; emit(+，E1.co
19、de,E2.code,E.code) E.code:=newtemp; emit(*，E1.code,E2.code,E.code) E.code:=E1.code E.code:=newtemp; emit(,E1.code, , E.code) E.code:=entry(id.name),25,4.2.3 圖形表示, 樹作為中間代碼 語法樹真實(shí)反映句子結(jié)構(gòu)，對(duì)語法樹稍加修改（加入語義信息），即可以作為中間代碼的一種形式（注釋語法樹）。 例4.8 賦值句x:=(a+b)*(a+b)的樹的中間代碼表示：,T1/(1),T2/(2),T3/(3),T4/(4),26, 樹的語法制導(dǎo)翻譯,(
20、1) A id := E (2) E E1 + E2 (3) E E1 * E2 (4) E ( E1 ) (5) E - E1 (6) E id,A.nptr:= mknode(:=,mkleaf(entry(id.name)),E.nptr) E.nptr:=mknode(+,E1.nptr,E2.nptr) E.nptr:=mknode(*,E1.nptr,E2.nptr) E.nptr:=E1.nptr E.nptr:=mknode(,E1.nptr, ) E.nptr:=mkleaf(entry((id.name)),屬性.nptr：指向樹節(jié)點(diǎn)的指針； 函數(shù)mknode(op，npt
21、r1，nptr2)： 生成一個(gè)根或內(nèi)部節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)是op， nptr1和nptr2分別指向的左右孩子的子樹。若僅有一個(gè)孩子，則nptr2為空； 函數(shù)mkleaf(node)： 生成一個(gè)葉子節(jié)點(diǎn)。,27, 樹的優(yōu)化表示DAG,如果樹上若干個(gè)節(jié)點(diǎn)有完全相同的孩子，則這些節(jié)點(diǎn)可以指向同一個(gè)孩子，形成一個(gè)有向無環(huán)圖（Directed Acyclic Graph, DAG）。 DAG與樹的唯一區(qū)別是多個(gè)父親可以共享同一個(gè)孩子，從而達(dá)到資源（運(yùn)算、代碼等）共享的目的。,DAG的語法制導(dǎo)翻譯與樹的語法制導(dǎo)翻譯相似，僅需要在mknode和mkleaf中增加相應(yīng)的查詢功能。 首先查看所要構(gòu)造的節(jié)點(diǎn)是否已
22、經(jīng)存在，若存在則無需構(gòu)造新的節(jié)點(diǎn)，直接返回指向已存在節(jié)點(diǎn)的指針即可。,28, 樹與其他中間代碼的關(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
23、)(*, T1,T2,T3) (4)(:=,x, T3,T4),因此，現(xiàn)代的編譯器基礎(chǔ)架構(gòu)均用語法樹作為中間表示。,29,4.3 符號(hào)表簡(jiǎn)介,符號(hào)表的作用：連接聲明與引用的橋梁，記住每個(gè)符號(hào)的相關(guān)信息，如作用域和綁定等，幫助編譯的各個(gè)階段正確有效地工作。 符號(hào)表設(shè)計(jì)的基本要求：目標(biāo)是合理存放信息和快速準(zhǔn)確查找。 正確存儲(chǔ)各類信息。 適應(yīng)不同階段的需求； 便于有效地進(jìn)行查找、插入、刪除和修改等操作； 空間可以動(dòng)態(tài)擴(kuò)充；,30,,4.3.1 符號(hào)表?xiàng)l目,邏輯上講：每個(gè)聲明的名字在符號(hào)表中占據(jù)一欄，稱為一個(gè)條目，用于存放名字的相關(guān)信息。 符號(hào)表中的內(nèi)容：保留字、標(biāo)識(shí)符、特殊符號(hào)（包括算符、分隔符等
24、）等等。不同類別的符號(hào)存放在不同的子表中，如變量名表、過程名表、保留字表等。 存放方式：關(guān)鍵字屬性。 關(guān)于組合關(guān)鍵字：,...... int x; double x; struct x float y, z; ; ,為C++構(gòu)造的符號(hào)表中，組合關(guān)鍵字至少應(yīng)該包括三項(xiàng)：名字作用域類型。 當(dāng)一個(gè)名字x在同一作用域中允許有多于一個(gè)的聲明，則對(duì)x的引用時(shí)需要根據(jù)上下文確定x到底屬于哪個(gè)對(duì)象。 因此程序設(shè)計(jì)語言在語法上規(guī)定了不允許這樣的聲明，以簡(jiǎn)化編譯時(shí)的處理。,31,4.3.2構(gòu)成名字的字符串的存儲(chǔ),定長(zhǎng)數(shù)據(jù)變長(zhǎng)數(shù)據(jù) 直接存放間接存放,名字（直接存儲(chǔ)）屬性 sort proc, ... a int
25、, ... readarray proc, ... draw_a_red_line_for_object_aboolean, ...,名字（間接存儲(chǔ)）屬性 101 (或101/4) proc, ... 106 (或105/1)int, ... 108 (或106/9)proc, ... 118 (或105/28)boolean, ...,sort#a#readarray#draw_a_red_line_for_object_a# 101,sortareadarraydraw_a_red_line_for_object_a 101,間接存儲(chǔ)的方法實(shí)際上解決了復(fù)雜信息的存儲(chǔ)問題，將其推廣到屬性，則
26、任何一個(gè)復(fù)雜的屬性，均可以為其另辟空間（空間本身可以是復(fù)雜結(jié)構(gòu)，如數(shù)組的內(nèi)情向量等），而僅需要將指向此空間的指針放在此屬性在符號(hào)表中的對(duì)應(yīng)位置即可。,32,4.3.3 名字的作用域,程序設(shè)計(jì)語言的名字可以出現(xiàn)在不同的范圍內(nèi)，并且可以具有不同的意義。 兩種劃分范圍的方式：并列的和嵌套的。 不同的語言采用不同的方式：如Pascal的過程定義可以是嵌套的，而C的過程定義是并列的，但是C允許程序塊是嵌套的。,名字的作用域：名字在哪個(gè)范圍內(nèi)起作用。并列的兩個(gè)范圍內(nèi)的名字作用域互不相干，但是分別在嵌套的兩個(gè)范圍內(nèi)的名字，其作用域的問題就需要制定規(guī)則來限定，以使得任何一個(gè)名字在任何范圍內(nèi)涵義都是無二義的。,
27、名字的作用域規(guī)則：規(guī)定一個(gè)名字在什么樣的范圍內(nèi)應(yīng)該表示什么意義。,33,4.3.3 名字的作用域（續(xù)1）, 靜態(tài)作用域原則（static-scope rule）： 編譯時(shí)就可以確定名字的作用域，也可以說，僅從靜態(tài)讀程序就可確定名字的作用域。 最近嵌套原則（most closely nested）： 以程序塊為例，也適用于過程。 程序塊B中聲明的作用域包括B； 如果名字x不在B中聲明，那么B中x的出現(xiàn)是在外圍程序塊B的x聲明的作用域中，使得 (a) B有x的聲明，并且 (b) B比其它任何含x聲明的程序塊更接近被嵌套的B。,通俗地講，名字的聲明在離其最近的內(nèi)層起作用，即在名字引用處從
28、內(nèi)向外看， 它處在所遇到的第一個(gè)該名字聲明的作用域。 例子：找人 張三；軟件學(xué)院的張三；計(jì)算機(jī)學(xué)院的張三；西電軟件學(xué)院的張三,34,4.3.3 名字的作用域（續(xù)2）,例4.10 說明符合作用域規(guī)則的C++程序。 void main() int a=0, b=0;/* B0層 */ int b=1;/* B1層，被B0嵌套 */ int a=2, c=4, d=5;/* B2層，被B1嵌套 */ printf(%d %dn, a, b);/* 結(jié)果為：2，1 */ int b=3; /* B3層，與B2并列 */ printf(%d %dn, a, b); /* 結(jié)果為：0
29、，3 */ printf(%d %dn, a, b);/* 結(jié)果為：0，1 */ printf(%d %dn, a, b); /* 結(jié)果為：0，0 */ ,聲明與作用域：,聲 明作用域 int a=0 B0-B2 int b=0 B0-B1 int b=1B1-B3 int a=2 B2 int b=3B3,35,4.3.4 線性表,線性表應(yīng)是一個(gè)棧，以正確反映名字的作用域，即符號(hào)的加入和刪除，均在線性表的一端進(jìn)行。,線性表上的操作：關(guān)鍵字：名字作用域； 查找：從表頭(棧頂)開始，遇到的第一個(gè)名字； 插入：先查找，再插入在表頭；,1 void main() 2 int a=0, b=
30、0; // B0 3 int b=1; // B1 4 int a=2, c=4, d=5; // B2 7 int b=3; // B3 11 ,36,4.3.4 線性表（續(xù)1）,1 void main() 2 int a=0, b=0;// B0 3 int b=1;// B1 4 int a=2, c=4, d=5; // B2 7 int b=3; // B3 11 ,線性表上操作的效率（n個(gè)條目）： 一個(gè)名字的查找：成功查找(平均)：(n+1)/2；不成功查找：n+1 建立n個(gè)條目的符號(hào)表(最壞)： = (n+1)(n+2)/2,刪除： (a) 暫時(shí)：將在同
31、一作用域的名字同時(shí)摘走，適當(dāng)保存； (b) 永久：將在同一作用域的名字同時(shí)摘走，不再保存。 修改：與查找類似，修改第一個(gè)遇到的名字的信息。 修改可以用插入刪除代替。,37,4.3.5 散列表, 散列表的構(gòu)成 將線性表分成m個(gè)小表。構(gòu)造hash函數(shù)，使名字均勻地散布在m個(gè)子表中。如果散列均勻，則時(shí)間復(fù)雜度會(huì)降到原線性表的1/m。,每個(gè)名字掛在兩個(gè)鏈上(便于刪除操作)： 哈希鏈(hash link)： 鏈接所有具有相同hash值的元素，表頭在表頭數(shù)組中； 作用域鏈(scope link)：鏈接所有在同一作用域中的元素，表頭在作用域鏈中。,其中： S1、S2、S4在同一作用域 S3在另一作用
32、域,38, 散列表上的操作 4.3.5 散列表（續(xù)1）,1查找：首先計(jì)算散列函數(shù)，然后從散列函數(shù)所指示的入口進(jìn)入某個(gè)線性表，在線性表中沿hash link，象查找單鏈表中的名字一樣進(jìn)行查找。 2插入：首先查找，以確定要插入的名字是否已在表中，若不在，則要分別沿hash link和scope link插入到兩個(gè)鏈中，方法均是插在表頭，即兩個(gè)表均可看作是棧。 3刪除：把以作用域鏈連在一起的所有元素從當(dāng)前符號(hào)表中刪除，保留作用域鏈所鏈的子表，為后繼工作使用（如果是臨時(shí)刪除，則下次使用時(shí)直接沿作用域鏈加入到散列鏈中即可）。,39,4.3.5 散列表（續(xù)2）,設(shè)：hash(s)=
33、ord(s)-ord(a),1 void main() 2 int a=0, b=0; // B0 3 int b=1; // B1 4 int a=2, c=4, d=5; // B2 7 int b=3; // B3 11 ,分析在B2中：,退出B2進(jìn)入B3：,40, 散列函數(shù)的計(jì)算 hash: string integer,減少?zèng)_突，分布均勻 充分考慮程序設(shè)計(jì)語言的特點(diǎn) 若有變量：V001,V002,,V300，且首字母的值作為hash值。 會(huì)發(fā)生什么？,一種可行的hash函數(shù)計(jì)算方法： 從串s=c1c2ck的字符ci確定正整數(shù)h： 令： h0=0, 計(jì)算：hi=hi
34、-1+ci, 1ik, 得到：h=hk =1或是素?cái)?shù)，如=65599。,思考題：根據(jù)上述方法，設(shè)計(jì)一個(gè)hash函數(shù)并測(cè)試之。根據(jù)測(cè)試結(jié)果討論各參數(shù)值對(duì)函數(shù)結(jié)果的影響。, 取一素?cái)?shù)m, 令 h=h mod m。,41, 散列函數(shù)的計(jì)算（續(xù)1）,思考題（P108）：對(duì)于下列函數(shù)： #include const int PRIME=211; const int EOS=0; int hashpjw(char *s) char *p; unsigned h=0, g; for (p=s; *p!=EOS; p++) h=(h24); h=hg; return h%PRIME; (1) 為每行語句寫注釋； (2) 寫出此函數(shù)的計(jì)算公式； (3) 若參數(shù)是abcd，試給出返回值。,結(jié) 束,
西安電子科技大學(xué)《編譯原理.ppt
