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

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

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

3、的依賴關系，這些關系可以用圖來表示，這樣的圖稱為依賴圖。屬性75.1.1 語法制導定義的形式 在一個語法制導定義中，AP都有與之相關聯(lián)的一套語義規(guī)則，規(guī)則形式為 b：= f（c1，c2，ck），f是一個函數(shù)，而且或者 1b是A的一個綜合屬性并且c1，c2，ck是中的符號的屬性，或者 2b是中的符號的一個繼承屬性并且c1，c2，ck是A或中的任何文法符號的屬性。 在兩種情況下，都說屬性b依賴于屬性c1，c2，ck。8例5.1 臺式計算器程序的語法制導定義（表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 每個文法符號和一個屬性值val 聯(lián)系，屬性值的設置和語法結構的語義以及翻譯程序的需要有關。例如，把例5.1中的類型擴充到 int和real。 5.1.2 綜合屬性 S-屬性定義 唯獨只使用綜合屬性的語法制導定義。 結點屬性值的計算正好和自底向上分析建立分析樹結點同步進行。 例 5 .2 輸入：3*5+4n10digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fva

5、l:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln11 綜合屬性值的計算方法對于s-屬性定義，通常使用自底向上的分析方法，在建立每一個結點處使用語義規(guī)則來計算綜合屬性值，即在 用哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計算屬性的值，從葉結點到根結點進行計算。 5.1.3 繼承屬性 繼承屬性值是由此結點的父結點和或兄弟結點的某些屬性值來決定的。 例5 . 3 變量說明的類性定義 int a,b,c12 表5.2 帶有繼承屬性L.in的語法制導定義 產(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 依賴圖 依賴圖的構造方法 for 分析樹中每一結點n do for 結點n的文法符號的每一個屬性a do 為a在依賴圖中建立一個結點； for 分析樹中每一個結點n do for 結點n所用產(chǎn)生式對應的每一條 語義規(guī)則 b:f（c1，c2，c

7、k ) do for i:=1 to k do 從結點ci到結點b構造一條有向邊；15 5.1.5 計算順序 拓撲排序 一個有向非循環(huán)圖的拓撲排序是圖中 結點的任何順序m1，m2，mk，使得 邊必須是從序列中前面的結點指向后面的 結點，也就是說，如果mimj是mi到mj的 一條邊,那么在 序列中mi必須出現(xiàn)在mj的 前面。 若依賴圖中無環(huán)，則存在一個拓撲排序，它就是屬性值的計算順序。16例5 . 6 圖5 . 5的拓撲排序是： 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 計算語義規(guī)則的方法 1 .分析樹法: 輸入串 分析樹 依賴圖 計算次序 2.基于規(guī)則的方法： 在構造編譯器時，用 手工或專門的工具來分析語義規(guī)則,確定 屬性值的計算順序。 3. 忽略語義規(guī)則的方法：在分析過程中翻 譯，那么計算順序由分析方法來確定而 表面上與語義規(guī)則無關。實際上，限制 語法制導定義，使屬性值的計算順序能 和 語法分析過程同步進行。18 5.2 語法樹（syntax tree）的構造 抽象語法（abstract syntax） 從具體語法中抽象出語言結構的本質本質性的東西，而不考慮語言的具體符號表示

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

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

11、eaf(num,val) 建立一個數(shù)結點，標號為 num ，域val用于存放數(shù)的值。 返回新建立結點的指針。22idto entry anum 4 idto entry c +圖5.6 a-4+c的語法樹235.2.3 建立語法樹的語法制導定義 產(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 .每個非終結符號有一個語法樹結點的指針 屬性。 2 .非終結符號歸約未建立結點。5.2.4 關于表達式的有向非循環(huán)圖 有向非循環(huán)圖有向非循環(huán)圖 （Directed Acyclic Graph，簡 稱dag) 用途：提取表達式中的公共子表達式，以取 得目標程序的局部優(yōu)化。 方法：執(zhí)行mknode和mkleaf時，檢查是否已有相同的結點，若有，則返回相應結點的指針。26例5.9 表達式 aa*(b-c)+(b-c)*d 的DAG +*d+*acb275.3 S

13、-屬性定義及其自底向上的計算 在分析棧中使用一個附加的域來存放綜 合屬性值。 下圖為一個帶有綜合屬性值域的分析棧：stateval.XX.xY.Y.y.ZZ.ztop28 A b:=f(c1,c2,ck) b是A的綜合屬性，ci(1 ik)是中符號的屬性。綜合屬性的值在自底向上的分析過程中，每步歸約時，計算相應的屬性值。 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í)行代碼段后執(zhí)行： top:=ntop;30例5.10 用LR分析器實現(xiàn)臺式計算器(表5.4） 產(chǎn)生式 代碼段(和表5.1對比）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所做的移動輸入 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總結： 采用自底向上分析，例如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執(zhí)行的代碼段，這就構成了翻譯程序。象一座建筑，語法分析是構架，歸約處有一個“掛鉤”，語義分析和翻譯的代碼段（語義子程序）就掛在這個鉤子

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

17、個語法制導定義是L-屬性定義屬性定義，如果AX1X2XnP,其每一個語義規(guī)則中的每一個屬性都是一個綜合屬性，或是Xj(1j n)的一個繼承屬性，這個繼承屬性僅依賴于 1. 產(chǎn)生式中Xj的左邊符號X1，X2，Xj-1 的屬性； 2A的繼承屬性。 每一個S-屬性定義都是L-屬性定義。37表5.6 非L-屬性的語法制導定義產(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的語法制導定義不是L-屬性定義文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性385.4.2 翻譯模式 定義 翻譯

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

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

20、邊符號的綜合屬性。 產(chǎn)生式左邊非終結符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的未尾。43 下面的翻譯模式不滿足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) 例5.13 從L-屬性制導定義建立一個滿足上面 要求的翻譯模式。 使用文法產(chǎn)生的語言是數(shù)學排版語言EQN E sub 1val編排結果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 盒子的大小和高度的語法制導定義45 B是編排單元； BBB表示倆個編排單元的并置； BBsubB表示第二個編排單元是第一個編 排 單元的下標； ps是繼承屬性，影響編排單元的位置； texth可根據(jù)text的性質查表得到； 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構造的翻譯模式 475.5 自頂向下的翻譯 用翻譯模式構造自頂向下翻譯。5.5.1 從翻譯模式中消除左遞歸 對于一個翻譯模式，若采用自頂向下分析，比須消除左遞歸和提取左公因子，在改寫基本文法時考慮屬性值的計算。例例5.14 圖5.13的帶左遞歸的文法的翻譯模式被轉換成圖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)過轉換的帶有右遞歸文法的翻譯模式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 表達式9-5+2的計算51關于左遞歸翻譯模式更一般化的討論左遞歸翻譯模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （5.2） 每一個文法符號都有一個綜合屬性，用相應的小寫字母表示，g和f是任意函數(shù)。 消除左遞歸，文法轉換成 AX R RY R| （5.3） 52再考慮語義動作，翻譯模式變?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)過轉換的翻譯模式與圖5.14中一樣,使用R的繼承屬性i

25、和綜合屬性s。（5.2）和（5.4）的結果是一樣的,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 表達式建立語法樹的翻譯模式： 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使用繼承屬性構造語法樹EiRsTidR-TnumiRT+idid num 4 id - + to entry for ato entry for

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

28、存 放在X.x中，Match(X)。（b）對于BVN，編寫一個賦值語句 c：= B（b1, b2, ，bk) 其中， b1, b2, ，bk是繼承屬性， c是 綜合屬性。（c）對于每個動作，動作的代碼抄進翻譯器 中，用代表屬性的變量來代替對屬性的 每一次引用。60例5.16 ： Raddop TR1i:=mknode（addop lexeme， R i， T nptr） R1R.s:=R1.s R R.s:=R.i （55） 遞歸下降構造語法樹遞歸下降構造語法樹 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 類型分析類型分析 每個程序設計語言都有自己的類型機制，包括類型說明和使用。 類型分析是編譯器語義分析的重要組成部分 。編譯器首先根據(jù)類型說明，確定每一個變量和常

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

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

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

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

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

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

36、價結構等價 兩個類型表達式結構等價，當且僅當它們完全相同。圖5.30是測試兩個類型表達式結構等價的算法，假設類型構造符僅有 數(shù)組、笛卡兒積、指針和函數(shù)，這個算法遞歸地比較兩個類型表達式的結構。 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 類型表達式中的名字類型表達式中的名字 類型可以命名。例如， TYPE Link=cell; VAR next: Link; (5.9） Last: Link; P: cell; q,r: cell; 所謂名字等價，是指兩個等價類型有同一個名字，也就是說，兩個類

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

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

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

41、識符和類型表達式的綁定 程序說明部分建立計算環(huán)境,其中說明了每個變量標識符以及與之綁定的類型。語法(5.10)是一個簡單的程序語言語法，假設數(shù)組的下標從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 語義分析程序首先處理類型說明，建立類型表達式，然后處理變量說明，建立變量和類型表達式的綁定。具體實現(xiàn)是把變量標識符的類型信息記錄在其符號表的表項中，過程addtype（id.enery,T.type）完成這個任務，其翻譯模式由圖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 建立變量標識符和類型屬性綁定 的翻譯模式 82 5.8.2.2 類型檢查類型檢查 借助于符號表中變量和類型屬性的綁定信息，分析確定每個語言結構的類型表達式。類型檢查是在編譯時做的靜態(tài)類型檢查。 表達式的類型檢查表達式的類型檢查 檢查對象之間類型是否滿足相容條件,

43、函數(shù)lookup（e）取符號表中保存在條目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 表達式的類型檢查的翻譯模式語句的類型檢查語句的類型檢查 指派給語句的類型是基本類型void，如果在語句中發(fā)現(xiàn)類型錯誤， 指派給語句的類型是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ù)引用的類型檢查 對說明部分的分析，應該能知道被引用函數(shù)的