翻譯的任務(wù)首先是語義分析和正確性檢查

1、12 翻譯的任務(wù)：首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。 使用的方法稱作語法制導(dǎo)翻譯。基本思想是，根據(jù)翻譯的需要設(shè)置文法符號(hào)的屬性，以描述語法結(jié)構(gòu)的語義。例如，一個(gè)變量的屬性有類型，層次，存儲(chǔ)地址等。表達(dá)式的屬性有類型，值等。屬性值的計(jì)算和產(chǎn)生式相聯(lián)系。隨著語法分析的進(jìn)行，執(zhí)行屬性值的計(jì)算，完成語義分析和翻譯的任務(wù)。3 屬性值根據(jù)計(jì)算的依賴關(guān)系分成不相交的兩類：綜合屬性(synthesized attribute)和繼承屬性(inherited attribute)。在分析樹中，一個(gè)結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的屬性值計(jì)算出來的；而一個(gè)結(jié)點(diǎn)的繼承屬性值是由該結(jié)點(diǎn)兄第結(jié)

2、點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算出來的。 一般來說，語義翻譯可按圖5.1 的流程處理。實(shí)際上，編譯中語義翻譯的實(shí)現(xiàn)并不是按圖5.1 的流程處理的；而是隨語法分析的進(jìn)展，識(shí)別出一個(gè)語法結(jié)構(gòu)，就對(duì)它的語義進(jìn)行分析和翻譯。4 要求：隨著語法分析，分析樹逐步被構(gòu)造出來，進(jìn)展到每一步，定義的文法符號(hào)的屬性值是可以計(jì)算出來的。一個(gè)重要的屬性定義類稱作“L屬性”定義，滿足上述要求。5輸入符號(hào)串 分析樹依賴圖語義規(guī)則的計(jì)算圖5.1 語法制導(dǎo)翻譯的概觀6 5.1 語法制導(dǎo)定義(Syntax-directed definitions) 語法制導(dǎo)定義是對(duì)上下文無關(guān)文法的推廣 綜合屬性 繼承屬性 依賴圖 語義規(guī)則建立了屬性之間

3、的依賴關(guān)系，這些關(guān)系可以用圖來表示，這樣的圖稱為依賴圖。屬性75.1.1 語法制導(dǎo)定義的形式 在一個(gè)語法制導(dǎo)定義中，AP都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則形式為 b：= f（c1，c2，ck），f是一個(gè)函數(shù)，而且或者 1b是A的一個(gè)綜合屬性并且c1，c2，ck是中的符號(hào)的屬性，或者 2b是中的符號(hào)的一個(gè)繼承屬性并且c1，c2，ck是A或中的任何文法符號(hào)的屬性。 在兩種情況下，都說屬性b依賴于屬性c1，c2，ck。8例5.1 臺(tái)式計(jì)算器程序的語法制導(dǎo)定義（表5.1) 產(chǎn)生式 語義規(guī)則LEn print(Eval)E E1+T E val := E1 val+T valE T E val := T

4、 valT T1*F T val := T1 val+F valT F T val := F valF (E) F val := E valF digit F val := digitlexval9 每個(gè)文法符號(hào)和一個(gè)屬性值val 聯(lián)系，屬性值的設(shè)置和語法結(jié)構(gòu)的語義以及翻譯程序的需要有關(guān)。例如，把例5.1中的類型擴(kuò)充到 int和real。 5.1.2 綜合屬性 S-屬性定義 唯獨(dú)只使用綜合屬性的語法制導(dǎo)定義。 結(jié)點(diǎn)屬性值的計(jì)算正好和自底向上分析建立分析樹結(jié)點(diǎn)同步進(jìn)行。 例 5 .2 輸入：3*5+4n10digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fva

5、l:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln11 綜合屬性值的計(jì)算方法對(duì)于s-屬性定義，通常使用自底向上的分析方法，在建立每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則來計(jì)算綜合屬性值，即在 用哪個(gè)產(chǎn)生式進(jìn)行歸約后，就執(zhí)行那個(gè)產(chǎn)生式的s-屬性定義計(jì)算屬性的值，從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。 5.1.3 繼承屬性 繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和或兄弟結(jié)點(diǎn)的某些屬性值來決定的。 例5 . 3 變量說明的類性定義 int a,b,c12 表5.2 帶有繼承屬性L.in的語法制導(dǎo)定義 產(chǎn)生式 語義規(guī)則 DTL L in:=T type T int T

6、type :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype(id entry,L in)13TLLid3Lid2Did1real,1 entry2 entry3 entry4typein 56in 78in 91014 5.1.4 依賴圖 依賴圖的構(gòu)造方法 for 分析樹中每一結(jié)點(diǎn)n do for 結(jié)點(diǎn)n的文法符號(hào)的每一個(gè)屬性a do 為a在依賴圖中建立一個(gè)結(jié)點(diǎn)； for 分析樹中每一個(gè)結(jié)點(diǎn)n do for 結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一條 語義規(guī)則 b:f（c1，c2，c

7、k ) do for i:=1 to k do 從結(jié)點(diǎn)ci到結(jié)點(diǎn)b構(gòu)造一條有向邊；15 5.1.5 計(jì)算順序 拓?fù)渑判?一個(gè)有向非循環(huán)圖的拓?fù)渑判蚴菆D中 結(jié)點(diǎn)的任何順序m1，m2，mk，使得 邊必須是從序列中前面的結(jié)點(diǎn)指向后面的 結(jié)點(diǎn)，也就是說，如果mimj是mi到mj的 一條邊,那么在 序列中mi必須出現(xiàn)在mj的 前面。 若依賴圖中無環(huán)，則存在一個(gè)拓?fù)渑判?，它就是屬性值的?jì)算順序。16例5 . 6 圖5 . 5的拓?fù)渑判蚴牵?1， 2， 3，4，5，6，7，8，9，10 a4:=real; a5:=a4; addtype(id3entry,a5); a7:=a5; addtype(id2en

8、try,a7); a9:=a7; addtype(id1entry,a9);17 計(jì)算語義規(guī)則的方法 1 .分析樹法: 輸入串 分析樹 依賴圖 計(jì)算次序 2.基于規(guī)則的方法： 在構(gòu)造編譯器時(shí)，用 手工或?qū)ｉT的工具來分析語義規(guī)則,確定 屬性值的計(jì)算順序。 3. 忽略語義規(guī)則的方法：在分析過程中翻 譯，那么計(jì)算順序由分析方法來確定而 表面上與語義規(guī)則無關(guān)。實(shí)際上，限制 語法制導(dǎo)定義，使屬性值的計(jì)算順序能 和 語法分析過程同步進(jìn)行。18 5.2 語法樹（syntax tree）的構(gòu)造 抽象語法（abstract syntax） 從具體語法中抽象出語言結(jié)構(gòu)的本質(zhì)本質(zhì)性的東西，而不考慮語言的具體符號(hào)表示

9、，從而可簡(jiǎn)化語義的形式描述。 在不同的語言中賦值語句有不同的寫法： x=y; x:=y; yx 等等，可以用抽象形式 assignment(variable,expression)把前面各種具體形式統(tǒng)一起來。19語法樹 表示程序?qū)哟谓Y(jié)構(gòu)的樹，它 把分析樹中對(duì)語義無關(guān)緊要的成分去掉，是分析樹的抽象形 式 ， 也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。 語法樹是常用的一種中間表示形式。 C sg+ 把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點(diǎn)，但也有一些不足：1.適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)；2. 語法分析方法限制，對(duì)分析樹結(jié)點(diǎn)的訪問序和翻譯需要的訪問序不一致。205.2.1

10、 語法樹 產(chǎn)生式sif B then S1 else S2的語法樹 if-then-else | B S1 S2 賦值語句的語法樹 assignment variable expression 在語法樹中，運(yùn)算符號(hào)和關(guān)鍵字都不在葉結(jié)點(diǎn)，而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。21 5.2.2 建立表達(dá)式的語法樹 建立表達(dá)式的語法樹使用的函數(shù) 1. mknode(op,left,right) 建立一個(gè)運(yùn)算符號(hào)結(jié) 點(diǎn)，標(biāo)號(hào)是op,兩個(gè)域left和right指向運(yùn)算分 量結(jié)點(diǎn)的指針。 2mkleaf(id,entry) 建立一個(gè)標(biāo)識(shí)符結(jié)點(diǎn),由 標(biāo)號(hào)id標(biāo)識(shí)，一個(gè)域entry指向標(biāo)識(shí)符符號(hào) 表中相應(yīng)的項(xiàng)。 3. mkl

11、eaf(num,val) 建立一個(gè)數(shù)結(jié)點(diǎn)，標(biāo)號(hào)為 num ，域val用于存放數(shù)的值。 返回新建立結(jié)點(diǎn)的指針。22idto entry anum 4 idto entry c +圖5.6 a-4+c的語法樹235.2.3 建立語法樹的語法制導(dǎo)定義 產(chǎn)生式 語義規(guī)則 EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mk

12、leaf(num,num.val)24idto entry anum 4 idto entry c +圖5.6 a-4+c的語法樹25 1 .每個(gè)非終結(jié)符號(hào)有一個(gè)語法樹結(jié)點(diǎn)的指針 屬性。 2 .非終結(jié)符號(hào)歸約未建立結(jié)點(diǎn)。5.2.4 關(guān)于表達(dá)式的有向非循環(huán)圖 有向非循環(huán)圖有向非循環(huán)圖 （Directed Acyclic Graph，簡(jiǎn) 稱dag) 用途：提取表達(dá)式中的公共子表達(dá)式，以取 得目標(biāo)程序的局部?jī)?yōu)化。 方法：執(zhí)行mknode和mkleaf時(shí)，檢查是否已有相同的結(jié)點(diǎn)，若有，則返回相應(yīng)結(jié)點(diǎn)的指針。26例5.9 表達(dá)式 aa*(b-c)+(b-c)*d 的DAG +*d+*acb275.3 S

13、-屬性定義及其自底向上的計(jì)算 在分析棧中使用一個(gè)附加的域來存放綜 合屬性值。 下圖為一個(gè)帶有綜合屬性值域的分析棧：stateval.XX.xY.Y.y.ZZ.ztop28 A b:=f(c1,c2,ck) b是A的綜合屬性，ci(1 ik)是中符號(hào)的屬性。綜合屬性的值在自底向上的分析過程中，每步歸約時(shí)，計(jì)算相應(yīng)的屬性值。 AXYZ Aa:=f(X x, Y y,Z z)A aX x Y y Z z29topstateval.XX.xYY.yZZ.zstateval.AA .atop 定義式 A .a:=f(X.x, Y.y, Z.z)（抽象）變成valntop:=f(valtop-2,valt

14、op-1,valtop)（具體可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行： ntop:=top-r+1 r是句柄的長(zhǎng)度執(zhí)行代碼段后執(zhí)行： top:=ntop;30例5.10 用LR分析器實(shí)現(xiàn)臺(tái)式計(jì)算器(表5.4） 產(chǎn)生式 代碼段(和表5.1對(duì)比）LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F valntop:=valtop-2*valtopT FF (E) valntop:=valtop-1F digit31表5.5 翻譯輸入3*5+4n所做的移動(dòng)輸入 state val 使用的產(chǎn)生式3*5+4n - - *5+4n 3 3 *5+4

15、n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3- +4n T* 5 3-5 +4n T* F 3-5 F digit 32 +4n T 15 T T*F +4n E 15 E T 4n E+ 15- n E+4 15-4 n E+F 15-4 F digit n E+T 15-4 T F n E 19 E E+T En 19 - L 19 L En33總結(jié)： 采用自底向上分析，例如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個(gè)“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個(gè)鉤子

16、上。這樣，隨著語法分析的進(jìn)行，歸約前調(diào)用相應(yīng)的語義子程序,完成翻譯的任務(wù)。345.4 L-屬性定義 在語法分析過程中進(jìn)行語義分析和翻譯，屬 性的計(jì)算順序受到語法分析建立分析樹結(jié)點(diǎn)順序的限制。 一種自然的計(jì)算屬性的順序是按深度優(yōu)先訪問分析樹結(jié)點(diǎn)的順序，它適應(yīng)多種自底向上和自頂向下的翻譯方法。 L-屬性定義 可用于按深度優(yōu)先順序計(jì)算屬性值。35深度優(yōu)先順序計(jì)算屬性PROCEDURE dfvisit(n:node); BEGIN FOR n 的每個(gè)子結(jié)點(diǎn)m,從左至右 DO BEGIN 計(jì)算m的繼承屬性； dfvisit(m) END; 計(jì)算n的綜合屬性 END;365.4.1 L-屬性定義 定義 一

17、個(gè)語法制導(dǎo)定義是L-屬性定義屬性定義，如果AX1X2XnP,其每一個(gè)語義規(guī)則中的每一個(gè)屬性都是一個(gè)綜合屬性，或是Xj(1j n)的一個(gè)繼承屬性，這個(gè)繼承屬性僅依賴于 1. 產(chǎn)生式中Xj的左邊符號(hào)X1，X2，Xj-1 的屬性； 2A的繼承屬性。 每一個(gè)S-屬性定義都是L-屬性定義。37表5.6 非L-屬性的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則ALMA QRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)表5.6的語法制導(dǎo)定義不是L-屬性定義文法符號(hào)Q的繼承屬性依賴于它右邊文法符號(hào)R的屬性385.4.2 翻譯模式 定義 翻譯

18、模式是語法制導(dǎo)定義的一種便于翻譯的書寫形式。其中屬性與文法符號(hào)相對(duì)應(yīng)，語義規(guī)則或語義動(dòng)作用花括號(hào) 括起來，可被插入到產(chǎn)生式右部的任何合適的位置上。 這是一種語法分析和語義動(dòng)作交錯(cuò)的表示法，他表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時(shí)執(zhí)行語義動(dòng)作。 翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序。可看成是分析過程中翻譯的注釋。39例5.12 一個(gè)簡(jiǎn)單的翻譯模式 ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 把語義動(dòng)作看成終結(jié)符號(hào)，輸入9-5+2,其分析樹如圖5. 10，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動(dòng)作，將輸出 9 5 - 2 +它

19、是輸入表達(dá)式9-5+2的后綴式。40ET9TPt(9)RPt(-)Pt(+)R-5Pt(5)+T2Pt(2)R圖5.10 9-5+2的帶語義動(dòng)作的分析樹41設(shè)計(jì)翻譯模式（根據(jù)語法制導(dǎo)定義）條件：語法制導(dǎo)定義是L-屬性定義 保證語義動(dòng)作不會(huì)引用還沒有計(jì)算的屬性值。1. 只需要綜合屬性的情況：為每一個(gè)語義規(guī)則建立一個(gè)包含賦值的動(dòng)作，并把這個(gè)動(dòng)作放在相應(yīng)的產(chǎn)生式右邊的末尾。 例如：TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val422. 既有綜合屬性又有繼承屬性產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來。 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右

20、邊符號(hào)的綜合屬性。 產(chǎn)生式左邊非終結(jié)符號(hào)的綜合屬性只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通?？煞旁诋a(chǎn)生式右端的未尾。43 下面的翻譯模式不滿足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 從L-屬性制導(dǎo)定義建立一個(gè)滿足上面 要求的翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學(xué)排版語言EQN E sub 1val編排結(jié)果E1val44 B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps B2.ps:=shrink(B.p

21、s) B.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B.ps SB B B1 B2 B B1 sub B2 B text產(chǎn)生式語義規(guī)則表5.7 盒子的大小和高度的語法制導(dǎo)定義45 B是編排單元； BBB表示倆個(gè)編排單元的并置； BBsubB表示第二個(gè)編排單元是第一個(gè)編 排 單元的下標(biāo)； ps是繼承屬性，影響編排單元的位置； texth可根據(jù)text的性質(zhì)查表得到； shrink把B2的尺寸縮小30%； disp把B2向下偏置。46 SB.ps:=10 BS.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2B.ht:=max(B1.ht

22、,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2B.ht:=disp(B1.ht,B2.ht) BtextB.ht:=text.h*Bps 圖5.12 從表5.7構(gòu)造的翻譯模式 475.5 自頂向下的翻譯 用翻譯模式構(gòu)造自頂向下翻譯。5.5.1 從翻譯模式中消除左遞歸 對(duì)于一個(gè)翻譯模式，若采用自頂向下分析，比須消除左遞歸和提取左公因子，在改寫基本文法時(shí)考慮屬性值的計(jì)算。例例5.14 圖5.13的帶左遞歸的文法的翻譯模式被轉(zhuǎn)換成圖5.14的帶右遞歸的文法的翻譯模式。48 EE1+T E val:=E1val+T val E E1-T E va

23、l:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val 圖5.13 帶左遞歸的文法的翻譯模式49 ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R. s:=R1 s R- TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val 圖5.14經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式50E val=6Tval=9R i=9; R s= 69T val=55R i=4; R

24、s= 6+ T val=2R i=6; R s= 62圖5.15 表達(dá)式9-5+2的計(jì)算51關(guān)于左遞歸翻譯模式更一般化的討論左遞歸翻譯模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （5.2） 每一個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫字母表示，g和f是任意函數(shù)。 消除左遞歸，文法轉(zhuǎn)換成 AX R RY R| （5.3） 52再考慮語義動(dòng)作，翻譯模式變?yōu)椋?AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i,Y y） R1 R s:=R1 s RR s:=R i （5.4） 經(jīng)過轉(zhuǎn)換的翻譯模式與圖5.14中一樣,使用R的繼承屬性i

25、和綜合屬性s。（5.2）和（5.4）的結(jié)果是一樣的,53A a=g(g(f(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)Y2Y1X(a)輸入：XY1Y254ARi=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)Y2Y1X(b)55例5. 15 表達(dá)式建立語法樹的翻譯模式： EE1+T Enptr :=mknode(+,E1 nptr,T nptr) EE1-T Enptr :=mknode(-,E1 nptr,T nptr)ET Enptr :=T nptr 從翻譯模式中消除左遞歸，變成圖5.17

26、的翻譯模式。56 ET Ri:=T nptr R E nptr:=R s R T R1 i:=mknode(+,R i,T nptr) R1 R s:=R1 s R- T R1 i:=mknode(-,R i,T nptr) R1 R s:=R1 s R R s:=R i T( E ) T nptr:=E nptr Tid T nptr:=mkleaf(id, id entry) Tnum T nptr:=mkleaf(num,num val) 57使用繼承屬性構(gòu)造語法樹EiRsTidR-TnumiRT+idid num 4 id - + to entry for ato entry for

27、cnptrnptrnptr58 5.5.2 預(yù)測(cè)翻譯器的設(shè)計(jì) 算法5.1 預(yù)測(cè)語法制導(dǎo)翻譯器的建立 輸入：一個(gè)帶有適合預(yù)測(cè)分析的基礎(chǔ)文法 的語法制導(dǎo)翻譯模式。 輸出：一個(gè)語法制導(dǎo)翻譯器的代碼。 方法：在預(yù)測(cè)分析器中加入語義動(dòng)作代碼。 1AVN,建立一個(gè)可遞歸調(diào)用的函數(shù)過程 A。為A的每一個(gè)繼承屬性都設(shè)置 一個(gè)形 式參數(shù)，函數(shù)的返回值是A的綜合屬性值。 2. 函數(shù)過程A的代碼（指用符號(hào)形式表示的 數(shù)據(jù)和程序）要根據(jù)當(dāng)前的輸入符號(hào)來決 定使用哪一個(gè)產(chǎn)生式。 593與每一個(gè)產(chǎn)生式有關(guān)的代碼，從左到右根 椐產(chǎn)生式右部是單詞符號(hào)、非終結(jié)符號(hào)還 是語義動(dòng)作，分別是：（a）對(duì)于帶有綜合屬性x的單詞符號(hào)X，x

28、存 放在X.x中，Match(X)。（b）對(duì)于BVN，編寫一個(gè)賦值語句 c：= B（b1, b2, ，bk) 其中， b1, b2, ，bk是繼承屬性， c是 綜合屬性。（c）對(duì)于每個(gè)動(dòng)作，動(dòng)作的代碼抄進(jìn)翻譯器 中，用代表屬性的變量來代替對(duì)屬性的 每一次引用。60例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 遞歸下降構(gòu)造語法樹遞歸下降構(gòu)造語法樹 function R（in: syntax-tree-node）： syntaX-tree-node； var nptr,i1,s1

29、,s： syntax-tree-node; addoplexeme:char； 61 IF lookahead=addop THEN /*產(chǎn)生式Raddop T R*/ addoplexeme:=lexval; match(addop); nptr:=T; i1:=mknode(addoplexeme,in,nptr); s1:=R(i1); s:=s1 ; ELSE s:=in; /*產(chǎn)生式R*/ return (s); 625.8 類型分析類型分析 每個(gè)程序設(shè)計(jì)語言都有自己的類型機(jī)制，包括類型說明和使用。 類型分析是編譯器語義分析的重要組成部分 。編譯器首先根據(jù)類型說明，確定每一個(gè)變量和常

30、量的類型 ，計(jì)算其使用存儲(chǔ)空間的大小，從而建立其到存儲(chǔ)空間的映射。進(jìn)而，編譯器要確定每個(gè)語言結(jié)構(gòu)的類型，以完成下面的主要任務(wù)： （1） 判定重載算符（函數(shù)）在程序中代表是那一個(gè)運(yùn)算；（2） 進(jìn)行類型轉(zhuǎn)換；（3） 對(duì)語言結(jié)構(gòu)進(jìn)行類型檢查。635.8.1 類型表達(dá)式類型表達(dá)式 5.8.1.1 類型表達(dá)式定義類型表達(dá)式定義 語言結(jié)構(gòu)的類型由類型表達(dá)式指稱，類型表達(dá)式依賴于程序語言的類型體制。類型表達(dá)式或者是簡(jiǎn)單類型表達(dá)式，或者是構(gòu)造符作用在類型表達(dá)式上得到的類型表達(dá)式。類型表達(dá)式的定義如下： （1） 類型名和基本類型是類型表達(dá)式。integer、char、real、boolean是基本類型，所以它們

31、是類型表達(dá)式。另外，void表示“無類型”，type_error表示“出錯(cuò)類型”，它們也是類型表達(dá)式。64 （2）類型構(gòu)造符作用于類型表達(dá)式的結(jié)果仍然是類型表達(dá)式。類型構(gòu)造符包括： （a）數(shù)組構(gòu)造符ARRAY：若T是類型表達(dá)式，則ARRAY（I,T）是類型表達(dá)式。 （b）笛卡兒乘積：若T1、T2是類型表達(dá)式，則T1 T2是類型表達(dá)式，且是左結(jié)合。 （c）記錄類型構(gòu)造符RECORD：若有標(biāo)識(shí)符N1、N2、Nn與類型表達(dá)式T1、T2、Tn， 則RECORD（N1 T1） （N2 T2） （Nn Tn）是一個(gè)類型表達(dá)式，它指稱一個(gè)記錄類型。 65 （d）指針類型構(gòu)造符POINTER：若T是類型 表達(dá)

32、式，則POINTER（T）是類型表達(dá)式，它指稱一個(gè)指針類型。 （e）函數(shù)類型構(gòu)造符：若D1、D2、Dn和R是類型表達(dá)式，則D1D2 DnR是類型表達(dá)式，其中優(yōu)先于，它指稱從定義域類型D1 D2 Dn到值域類型R的映射。 （3） 類型表達(dá)式中可出現(xiàn)類型變量，變量值是類型表達(dá)式。66例例5.23 設(shè)有Pascal 程序片段： TYPE stype=RECORD name:ARRAY 1.8 OF char; score:integer END; VAR table:ARRAY 1.50 OF stype; p: stype; 則stype代表的類型表達(dá)式 RECORD(nameARRAY(1.8,

33、char) (score integer) 和table綁定的類型表達(dá)式 ARRAY(1.50,stype) 和P綁定的類型表達(dá)式 POINTER(stype) 67例例5.24 設(shè)有下面的函數(shù)定義 FUNCTION f(P1:T1;P2:T2;，Pn:Tn):T; BEGIN END; 和f綁定的類型表達(dá)式 T1T2 TnT 例例5.25 在函數(shù)式語言中可如下定義恒等函數(shù) fun f(x)=x x可以是任何類型的語言結(jié)構(gòu)。因此x可以是任何類型。f的類型表達(dá)式為 為類型變量，其值是任何類型表達(dá)式。68 類型表達(dá)式的表達(dá)方法類型表達(dá)式的表達(dá)方法 1.樹:內(nèi)部結(jié)點(diǎn)是類型構(gòu)造符，葉結(jié)點(diǎn)是基本 類型，

34、類型名或類型變量。例如， FUNCTION f (a,b:char):integer: charcharpointer(integer)pointerintegercharchar692.位串(對(duì)類型表達(dá)式作某些限制) 例如，考慮由POINTER、和ARRAY 作為 構(gòu)造符的類型表達(dá)式。Pointer(t)表示指向類 型為t的指針，freturns(t)表示若干變?cè)暮?數(shù), 其中t為函數(shù)返回對(duì)象的類型, 而函數(shù)變 元的類型則存放在其它地方。ARRAY(t) 表 示元素類型為t 的數(shù)組，而數(shù)組元素的個(gè)數(shù) 保存在其它地方。這樣，構(gòu)造符都成為一元 算符，它們作用于 基本類型形成的類型表 達(dá)式有非常

35、統(tǒng)一的結(jié) 構(gòu)。70 類型構(gòu)造符 編碼 pointer 01 array 10 freturns 11 基本 類型 編碼 boolean 0000 char 0001 integer 0010 real 0011 類型 表達(dá)式 編碼 char 000000 0001 freturns(char) 000011 0001 pointer(freturns(char) 000111 0001 array(pointer(freturns(char) 100111 000171 5.8.1.2 類型表達(dá)式的等價(jià)類型表達(dá)式的等價(jià) 根據(jù)語言的類型體制和類型表達(dá)式的表示 方法，分結(jié)構(gòu)等價(jià)和名字等價(jià)。 結(jié)構(gòu)等

36、價(jià)結(jié)構(gòu)等價(jià) 兩個(gè)類型表達(dá)式結(jié)構(gòu)等價(jià)，當(dāng)且僅當(dāng)它們完全相同。圖5.30是測(cè)試兩個(gè)類型表達(dá)式結(jié)構(gòu)等價(jià)的算法，假設(shè)類型構(gòu)造符僅有 數(shù)組、笛卡兒積、指針和函數(shù)，這個(gè)算法遞歸地比較兩個(gè)類型表達(dá)式的結(jié)構(gòu)。 FUNCTION eq(s,t):boolean; BEGIN IF s 和 t 是相同的基本類型 THEN return(true)72ELSE IF (s=ARRAY(s1,s2) and (t=ARRAY(t1,t2) THEN return(eq(s1,t1) and eq(s2,t2) ELSE IF (s=s1s2) and (t=t1 t2) THEN return(eq(s1,t1) a

37、nd (eq(s2,t2) ELSE IF (s=POINTER(s1) and (t=POINTER(t1) THEN return(eq(s1,t1) ELSE IF (s=s1s2) and (t=t1t2) THEN return(eq(s1,t1) and eq(s2,t2) ELSE return(false) END 73 類型表達(dá)式中的名字類型表達(dá)式中的名字 類型可以命名。例如， TYPE Link=cell; VAR next: Link; (5.9） Last: Link; P: cell; q,r: cell; 所謂名字等價(jià)，是指兩個(gè)等價(jià)類型有同一個(gè)名字，也就是說，兩個(gè)類

38、型名表示不同的類型。在結(jié)構(gòu)等價(jià)中，在類型表達(dá)式中的所有名字被它們代表的類型表達(dá)式替換后，兩個(gè)類型表達(dá)式等價(jià)即是結(jié)構(gòu)等價(jià)。74 例例5.26 下面給出和聲明（5.9）中的5個(gè)變量相聯(lián)系的類型表達(dá)式。 變 量 類 型表 達(dá) 式 next Link last Link p Pointer(cell) q Pointer(cell) r Pointer(cell) 在名字等價(jià)下，變量next和last有同樣的類型; next和p的類型不相同。在結(jié)構(gòu)等價(jià)下，所有五個(gè)變量都有同樣的類型。 75 不同的語言中，通過聲明變量標(biāo)識(shí)符和類型聯(lián)系的規(guī)則是不同的，在解釋這些規(guī)則時(shí)，結(jié)構(gòu)等價(jià)和名字等價(jià)是兩個(gè)有用的概念。

39、 例例5.27 在一些Pascal的實(shí)現(xiàn)中，用隱含的類型名和每個(gè)聲明的變量標(biāo)識(shí)符相聯(lián)系，如果說明中出現(xiàn)沒有名字的類型表達(dá)式，就建立一個(gè)隱含的類型名。 TYPE VAR Link=cell; next : link; np=cell; last : link; nqr=cell; p : np; q,r : nqr; 76 典型的實(shí)現(xiàn)是構(gòu)造一張類型圖，每當(dāng)遇到類型構(gòu)造符和基本類型，就建立一個(gè)新結(jié)點(diǎn)，但要記住類型名所命名的類型表達(dá)式。在這種方法中，如果兩個(gè)類型表達(dá)式用類型圖中同樣的結(jié)點(diǎn)表示，那么，它們等價(jià)。link =pointerpointerpointercellnextlastpqr圖5.3

40、177類型表示中的環(huán)類型表示中的環(huán) 鏈表和樹結(jié)構(gòu)經(jīng)常是遞歸定義的。它們的結(jié)點(diǎn)通常定義成一個(gè)記錄，記錄中含有指向同類型記錄的指針。 設(shè)鏈表中的結(jié)點(diǎn)含有一個(gè)整型信息和一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針，實(shí)現(xiàn)鏈表的類型定義： TYPE link=node; node=RECORD info:integer; next: link END;78類型表達(dá)式用圖表示如下：Node=recordInfo integernext pointernodeNode=recordnextInfo integerpointera. 無環(huán)b. 有環(huán)795.8.2 類型分析類型分析5.8.2.1 變量標(biāo)識(shí)符和類型表達(dá)式的綁定變量標(biāo)

41、識(shí)符和類型表達(dá)式的綁定 程序說明部分建立計(jì)算環(huán)境,其中說明了每個(gè)變量標(biāo)識(shí)符以及與之綁定的類型。語法(5.10)是一個(gè)簡(jiǎn)單的程序語言語法，假設(shè)數(shù)組的下標(biāo)從1開始。 文法GP，產(chǎn)生式如下： (5 . 10) PD；E DD；D|id:T Tchar| integer| ARRAYnum OF T|T Enum |id| EMODE| EE| E（E）| E 80 語義分析程序首先處理類型說明，建立類型表達(dá)式，然后處理變量說明，建立變量和類型表達(dá)式的綁定。具體實(shí)現(xiàn)是把變量標(biāo)識(shí)符的類型信息記錄在其符號(hào)表的表項(xiàng)中，過程addtype（id.enery,T.type）完成這個(gè)任務(wù)，其翻譯模式由圖5.32給

42、出81 PD；E DD；D Did:Taddtype（id.enery，T.TYPE） TcharT.type:=char Tinteger T.type:=integer TT1 T.type:=POINTER(T1.type) TARRAYnum OF T1 T.type:=ARRAY(num.val,T1.type) 圖5.32 建立變量標(biāo)識(shí)符和類型屬性綁定 的翻譯模式 82 5.8.2.2 類型檢查類型檢查 借助于符號(hào)表中變量和類型屬性的綁定信息，分析確定每個(gè)語言結(jié)構(gòu)的類型表達(dá)式。類型檢查是在編譯時(shí)做的靜態(tài)類型檢查。 表達(dá)式的類型檢查表達(dá)式的類型檢查 檢查對(duì)象之間類型是否滿足相容條件,

43、函數(shù)lookup（e）取符號(hào)表中保存在條目e中的類型。 Enum E.type:=integer Eid E.type:=lookup(id.entry) EE1 MOD E2 E.type:= IF (E1.type=integer)AND(E2.type=integer) THEN integer ELSE type_error 83 EE1E2 E.type:=IF(E2.type=integer)AND(E1.type=ARRAY(s,t) THEN t ELSE type_error EE1 E.type:=IF E1.type=POINTER(t) THEN t ELSE type

44、_error 圖5.33 表達(dá)式的類型檢查的翻譯模式語句的類型檢查語句的類型檢查 指派給語句的類型是基本類型void，如果在語句中發(fā)現(xiàn)類型錯(cuò)誤， 指派給語句的類型是type_error。 84 Sid:=E S.type:=IF id.type=E.type THEN void ELSE type_error SIF E THEN S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_error SWHILE E DO S1 S.type:=IF E.type=boolean THEN S1.type ELSE type_error SS1;S2 S.type:=IF (S1.type=void)AND(S2.type=void) THEN void ELSE type_error 圖5.34 檢查語句類型的翻譯模式 85函數(shù)引用的類型檢查函數(shù)引用的類型檢查 對(duì)說明部分的分析，應(yīng)該能知道被引用函數(shù)的