1、1nGoto 223 4一個語法上正確的句子，它所一個語法上正確的句子，它所代表的意義并不一定正確，例如代表的意義并不一定正確，例如“貓吃老鼠貓吃老鼠”和和“老鼠吃貓老鼠吃貓” 。 567894.1.2 屬性與語義規(guī)則（續(xù)1） 104.1.2 屬性與語義規(guī)則（續(xù)2） 114.1.2 屬性與語義規(guī)則（續(xù)2）12 134.1.3 語義規(guī)則的兩種形式（續(xù)1） 144.1.3 語義規(guī)則的兩種形式（續(xù)1）15 3+5*2/7(3+5)*(2/7)352*7/+35+27/*164.1.3 語義規(guī)則的兩種形式（續(xù)1） 174.1.3 語義規(guī)則的兩種形式（續(xù)2）LEE + E3 5E + E 8post:(

2、3 5 + 8 +)184.1.3 語義規(guī)則的兩種形式（續(xù)3） LEE + EE + E 83 5.LE(print(+)E(print(+) + E(print(8)E(print(3) + E(print(5) 83 5194.1.3 語義規(guī)則的兩種形式（續(xù)4） LEE + EE + E 83 5204.1.3 語義規(guī)則的兩種形式（續(xù)4） 21 驅(qū)動器輸入記號流輸出ip移進(jìn)-歸約分析表分析棧top 3 E ? + 5 Etop top8 E224.1.4 LR分析翻譯方案的設(shè)計（續(xù)1） 語法制導(dǎo)定義print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val

3、*E2.val;E.val:=n.lexval;print(valtop);valtop:=valtop+valtop+2;valtop:=valtop*valtop+2;valtop:=lexval; 234.1.4 LR分析翻譯方案的設(shè)計（續(xù)2）（格局的變化）（格局的變化）# # 3+5*8#shift 移進(jìn)#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

4、#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;#E #43 #acc 24 25n原理上講，源程序在語義分析完成之后，已經(jīng)具備了生成原理上講，源程序在語義分析完成之后，已經(jīng)具備了生成目標(biāo)代碼的條件，完全可以直接生成目標(biāo)代碼。目標(biāo)代碼的條件，完全可以直接生成目標(biāo)代碼。n但由于源代碼與目標(biāo)代碼的邏輯結(jié)構(gòu)往往差別很大，要使但由于源代碼與目標(biāo)代碼的邏輯結(jié)構(gòu)往往差別很大，要使翻譯一次到位很困難。翻譯一次到位很困

5、難。n在中間代碼的基礎(chǔ)上，再考慮對代碼的優(yōu)化和最終目標(biāo)代在中間代碼的基礎(chǔ)上，再考慮對代碼的優(yōu)化和最終目標(biāo)代碼的生成。碼的生成。n中間代碼實際上應(yīng)起一個編譯器前端與后端分水嶺的作用，中間代碼實際上應(yīng)起一個編譯器前端與后端分水嶺的作用，。26 27 也被稱為逆波蘭表示，它的典型特征是也被稱為逆波蘭表示，它的典型特征是3+5*2/7(3+5)*(2/7)352*7/+35+27/*28 x := first_token;第一個記號while not end_of_exp loop next(x);end loop; if x in operators如果是操作數(shù)then push x; - 操作數(shù)進(jìn)

6、棧else pop(operators); - 算符，彈出操作數(shù) push(evaluate); - 計算，并將結(jié)果進(jìn)棧end if;294.2.1 后綴式（續(xù)1）（#35+8+#push (3) ）（#3 5+8+#push (5) ）（#35 +8+#pop(3和5)，push(3+5)）（#8 8+#push (8) ）（#88 +#pop(8和8)，push(8+8) ）（#16 # ）304.2.1 后綴式（續(xù)2） 31 32n三地址碼與匯編指令在結(jié)構(gòu)上已經(jīng)十分接近，因此從三地三地址碼與匯編指令在結(jié)構(gòu)上已經(jīng)十分接近，因此從三地址碼生成目標(biāo)代碼比較容易。址碼生成目標(biāo)代碼比較容易。n但它

7、又不涉及與具體機(jī)器有關(guān)的實現(xiàn)細(xì)節(jié)，例如：地址但它又不涉及與具體機(jī)器有關(guān)的實現(xiàn)細(xì)節(jié)，例如：地址arg1、arg2、result在三地址碼中僅在三地址碼中僅，而，而它們到底是寄存器變量、內(nèi)存變量，還是常量并不被考慮，它們到底是寄存器變量、內(nèi)存變量，還是常量并不被考慮，因此便于對程序進(jìn)行與機(jī)器無關(guān)的優(yōu)化。因此便于對程序進(jìn)行與機(jī)器無關(guān)的優(yōu)化。n三地址碼是最終生成目標(biāo)代碼的理想中間代碼形式三地址碼是最終生成目標(biāo)代碼的理想中間代碼形式。n三地址碼與設(shè)計語言中的數(shù)學(xué)表達(dá)式或賦值句很相似。三地址碼與設(shè)計語言中的數(shù)學(xué)表達(dá)式或賦值句很相似。33 34產(chǎn)生式LEEE1+E2Enum 語法制導(dǎo)定義print(E.po

8、st)E.post:=E1.post |E2.post|+;E.post:=num.lexval; 翻譯方案1print_post(post);post(k):=+; k:=k+1;post(k):=lexval; k:=k+1; 中間代碼中間代碼 a. a. 后綴式后綴式b. b. 三地址碼三地址碼35 l 36 三地址碼的實現(xiàn)（續(xù)2） 37 三地址碼的實現(xiàn)（續(xù)3）3839 三地址碼的實現(xiàn)（續(xù)1）A.code:=trip(:=，entry()，E.code)E.code:=trip(+，E1.code，E2.code)E.code:=trip(*，E1.code，E2.code

9、)E.code:=E1.codeE.code:=trip(，E1.code， )E.code:=entry() 40【 例例4.25 】 41 三地址碼的實現(xiàn)（續(xù)2）Ax := E5E1 + E4aE2 * E3bc 42 三地址碼的實現(xiàn)（續(xù)2）A.code:=newtemp; emit(:= , entry()，E.code, A.code)E.code:=newtemp; emit(+，E1.code,E2.code,E.code)E.code:=newtemp; emit(*，E1.code,E2.code,E.code)E.code:=E1.codeE.co

10、de:=newtemp; emit(,E1.code, , E.code)E.code:=entry() 43 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）（:=, T3, T4, x)44 A.nptr:= mknode(:=,mkleaf(entry(),E.nptr)E.nptr:=mknode(+,E1.nptr,E2.nptr)E.nptr:=mknode(*,E1.

11、nptr,E2.nptr)E.nptr:=E1.nptrE.nptr:=mknode(,E1.nptr, )E.nptr:=mkleaf(entry() 45 x:=*+a b a bT1/(1)T2/(2)T3/(3)T4/(4)x:=*+a bT3/(3)T2/(2)T1/(1)46 47 樹與其他中間代碼的關(guān)系（續(xù)）x:=*+a b a bT1/(1)T2/(2)T3/(3)T4/(4) xab+ab+*:=(1)(+, a, b ) (2)(+, a, b ) (3)(*,(1),(2) (4)(:=,x, (3)(1)(+, a, b, T1) (2)(+, a, b,

12、 T2) (3)(*, T1,T2,T3) (4)(:=,T4,T3, x) 。48 49 50名字作用域類型.51（）sort proc, .a int, .readarray proc, .draw_a_red_line_for_object_aboolean, .52 名字（）屬性101 proc, .106 int, .108 proc, .118 boolean, . sort#a#readarray#draw_a_red_line_for_object_a#101 （將名字字符串統(tǒng)一存放在一個連續(xù)的空間中） 指針53 544.3.3 名字的作用域（續(xù)1） （most closely

13、 nested）：（static-scope rule）：554.3.3 名字的作用域（續(xù)2） void main() 564.4.4 線性表 a B0 0 #b B0 0b B1 1a B2 2c B2 4d B2 51 void main()2 int a=0, b=0; / B03 int b=1; / B14 int a=2, c=4, d=5; / B27 int b=3; / B3 11 574.3.4 線性表（續(xù)1）a B0 0 #b B0 0b B1 1a B2 2c B2 4d B2 5b B3 31 void main()2 int a=0, b=0;/ B03 int b

14、=1;/ B14 int a=2, c=4, d=5; / B27 int b=3; / B311 一個名字的查找：成功查找(平均)：(n+1)/2；不成功查找：n+1建立n個條目的符號表(最壞)： = (n+1)(n+2)/2nii1(a) 暫時：將在同一作用域的名字同時摘走，適當(dāng)保存；(b) 永久：將在同一作用域的名字同時摘走，不再保存。58 01ikm-1S1S2S3S4其中：hash(S1)=hash(S2)=i hash(S3)=hash(S4)=k59 其中： S1、S2、S4在同一作用域 S3在另一作用域01ikm-1S1S2S3S460 4.3.5 散列表（續(xù)1）614.3.5

15、 散列表（續(xù)2）設(shè)：hash(s)=ord(s)-ord(a)B0B0#B1B1#B2B2 #B3B3 #0123.a=2 B2a=0 B0b=1 B1b=0 B0c=3B2d=4 B2B2B1B001.a=0 B0b=1 B1b=0 B0B1B001.a=0 B0b=3B3b=1 B1b=0 B0B3B1B0d=4B2c=3B2a=2B2分析在B2中：62 hash: string integer63 散列函數(shù)的計算（續(xù)1）#include const int PRIME=211;const int EOS=0;int hashpjw(char *s) char *p; unsigned h

16、=0, g; for (p=s; *p!=EOS; p+) h=(h24); h=hg; return h%PRIME; 64 65 type player = array1.2 of integer; matrix = array1.24 of char;var c, p : player; winner : boolean; display : matrix; movect : integer;var c, p : array1.2 of integer; display : array1.24 of char;66 D D ; D (1) | id : T (2) T int (3) |

17、 real (4) | array num of T (5) | T (6) A : array d1 of array d2 of . array dn of int67 變量聲明的語法制導(dǎo)翻譯（續(xù)2）例例 聲明的語法制導(dǎo)翻譯：聲明的語法制導(dǎo)翻譯： D3D1 ; D2a : T2x : T3array 10 of T1intint a array(10,integer) 0 x integer 40.68 變量聲明的語法制導(dǎo)翻譯（續(xù)1）69 變量聲明的語法制導(dǎo)翻譯（續(xù)1）(1)DD;D(2)Did:T(3)Tint(4)Treal(5)Tarray num of T1(6)TT1語義規(guī)則：e

18、nter(, T.type, offset); /建立符號表 offset:=offset+T.width;T.type:=integer; T.width:=4;T.type:=real; T.width:=8;T.type:=array(num.val, T1.type); T.width:=num.val*T1.width; /寬度T.type:=pointer(T1.type); T.width:=4; D3D1 ; D2a : T2x : T3array 10 of T1intint a array(10,integer) 0 x integer 40.例例 聲明的語法制導(dǎo)翻