1、編譯原理課程總復習賈棋詞法分析器詞法分析器記號（記號（token）流）流源代碼源代碼源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號記號非形式非形式化描述化描述形式化形式化描述描述正規式正規式字母字母串串語言語言字母表字母表名名字字n復雜的例子復雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001Pascal語言的標識符集合語言的標識符集合letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9id letter( (letter|

2、|digit) )* r+=rr*r?=r| a-z=a|b|c|z(1) abc=a|b|c源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號記號非形式非形式化描述化描述形式化形式化描述描述正規式正規式字母字母串串語言語言字母表字母表名名字字 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother正規式正規式狀態轉換圖狀態轉換圖12開始開始a0abb 12開始開始a0abbab子集構造法子集構

3、造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab6782345 子集構造法子集構造法19開始開始 0ab ab678234

4、5 子集構造法子集構造法19開始開始 0ab ab6782345 BD開始開始aAabbabCba19開始開始 0ab ab6782345 12開始開始a0abbabBD開始開始aAabbaa, bCbaEbBD開始開始aAabbabCbaBD開始開始aAabbabCbaBD開始開始aAabbabCbaBD開始開始aAabbabCba12開始開始a0abbab0123aabbabbbstart45aaa, b012bbbb4aastart最簡最簡DFA正規式正規式狀態轉換圖狀態轉換圖19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19開始開始 0a

5、b ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab12開始開始a0abb19開始開始 0ab ab67

6、82345 0123開始開始40123開始開始400123開始開始4100123開始開始41000123開始開始410010123開始開始4100100123開始開始41001010123開始開始410010100123開始開始4100101010123開始開始41001010100123開始開始410010101010123開始開始41001010101構造構造DFA, ,接受接受 0和和1的個數都是偶數的字符串的個數都是偶數的字符串312011110000開始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1正規式正規式狀態轉換圖狀態轉換圖第三章 語法分析器qE E A E | (E )

7、 | E | idqA + | * *qletter A-Za-zqdigit 0-9qid letter(letter|digit)* q串的特點串的特點 ba . . . aba . . . aA b b A A a a A | A abab1 | abab2A+Aa FIRST集、FOLLOW集！自下而上分析 S rm aABe rm aAde rm aAbcde rm abbcde句柄與某個產生式的右部符號串相同句柄與某個產生式的右部符號串相同句柄是句型的一個子串句柄是句型的一個子串把句柄歸約成非終結符代表了最右推導逆過程的一步把句柄歸約成非終結符代表了最右推導逆過程的一步n構造拓廣文

8、法n構造DFAq若是SLR直接構造即可q若是LR需要求取搜索符q若是LALR需要在LR的基礎上進行合并n根據DFA構造分析表判斷文法屬于哪類文法n證明文法 SA a | bAc | dc | bdan A dn是LALR(1)文法，但不是SLR(1)文法。：通過構造分析表來回答，如果表中不存在沖突則說明屬于某文法，否則不屬于該文法。：當文法很簡單時，可通過直觀分析。先說明該文法不是SLR(1)文法。從產生式很容易看出FoLLow(A) a，c。若輸入句子是dc，在d進棧后，面臨的是c，這時出現移進一歸約沖突。因為項目Sd.c要求移進，而項目A d.要求歸約(這兩個項目出現在同一項目集中)，因為

9、c在FOLLOW(A)中。n 而上面的移進一歸約沖突在規范LR(1)情況下不存在，因為只有在面臨a時才進行d到A的歸約。該文法還有另一個移進歸約沖突，在bd進棧后，面臨c的情況，其沖突的原因和上面的類似。該沖突在規范LR(1)情況下也不存在。這樣，該文法是LR(1)文法。n 顯然該文法的規范LR(1)項目集的集合中沒有同心項目集，因此該文法也是LALR(1)文法。id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry產產 生生 式式 語語 義義 規規 則則

10、 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 建立翻譯模式建立翻譯模式n如果既有如果既有綜合屬性綜合屬性又有又有繼承屬性繼承屬性，在建立翻譯模式，在建立翻譯模式時就必須保證：時就必須保證：1. 產生式右邊的符號的產生式右邊的符號的繼承屬性繼承屬性必須在先于這個符號必須在先于這個符號的動作中計算出來。的動作中計算出來。2. 一個動作不能引用這個動作右邊的符號的一個動作不能

11、引用這個動作右邊的符號的綜合屬性綜合屬性。3. 產生式左邊非終結符的產生式左邊非終結符的綜合屬性綜合屬性只有在它所引用的只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性所有屬性都計算出來以后才能計算。計算這種屬性的動作通常可放在產生式右端的的動作通常可放在產生式右端的末尾末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in)在寫語法制導定義之前，首先分析清楚需要為文在寫語法制導定義之前，首先分析清楚需要為文法符號定義一些什么屬性，然后看這些屬性的值法符號定義一些什么屬性，然后看這些屬性的值是否可以由文法符號本身所推出的串決定。若是，是否可以由文法符號本身

12、所推出的串決定。若是，則應該只用綜合屬性就能解決。則應該只用綜合屬性就能解決。S S. depth := 0 SS L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth := L. depth L1 , S. depth := L. depth SL S. depth := L. depth SS S print(S.max)S ( L ) S.max:=L.max+1S a S.max=0 L L1 , S L.max:=max(L1.max, S.max)L S L.max:=S.maxS S. in := 0 SS

13、 (L. in := S. in + 1 L ) S. num:= L.num+ 2 S a S. num := 1; print (S. in+1) L L1. in := L. in L1 , S. in := L1. in + L1.num+1 S L.num := L1.num + S.num +1 L S. in := L. in S L. num := S.num 導數導數產產 生生 式式語語 義義 規規 則則 E E print(E.d) E E1 + T E.d := E1.d+T.d; E.exp := E1.exp + T.exp E T E.d := T.d; E.exp

14、 := T.exp T T1* *F T.d := T1.d * *F.exp + T1.exp * *F.d; T.exp := T1.exp * *F.exp T F T.d := F.d ; T.exp := F.exp F (E) F.d := E.d ; F.exp := (E.exp) F x F.d := 1; F.exp := x F num F.d := 0; F.exp:=numP DD D;D | id:T | proc id; D; S(1)一共聲明多少個一共聲明多少個idP D print(D.sum)D D1;D2 D.sum= D1.sum+D2.sumD id:

15、TD.sum= 1D proc id; D1; SD.sum=D1.sum+1P DD D;D | id:T | proc id; D; S(2)變量變量id的嵌套深度的嵌套深度P D.depth= 1D D D1.depth= D.depthD1; D2.depth= D.depthD2D id:T print(, D.depth)D proc id; D1.depth= D.depth+1D1; Sn用S的綜合屬性val給出下面文法中S產生的二進制數的值。例如，輸入101.101時，S.val5.625。nS L.L | L L L B | B B 0 | 1 nS L.L

16、| L L L B | B B 0 | 1n(1)僅使用綜合屬性僅使用綜合屬性S L1.L2 S.valL1.val+L2.val /2L2.lengthS L S.valL.valL L B L.val=L1.val * 2+B.val; L.length=L1.length+1L B L.val=B.val; L.length=1B 0 B.val=0B 1 B.val=11. 產生式右邊的符號的產生式右邊的符號的繼承屬性繼承屬性必須在先必須在先于這個符號的動作中計算出來。于這個符號的動作中計算出來。2. 一個動作不能引用這個動作右邊的符號一個動作不能引用這個動作右邊的符號的的綜合屬性綜合

17、屬性。3. 產生式左邊非終結符的產生式左邊非終結符的綜合屬性綜合屬性只有在只有在它所引用的所有屬性都計算出來以后才能它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通常放在產生計算。計算這種屬性的動作通常放在產生式右端的式右端的末尾末尾。產產 生生 式式語語 義義 規規 則則 E E1 + T E.nptr := mknode( +, E1.nptr, T.nptr) E T E.nptr := T.nptr T T1* *F T.nptr := mknode( * *, T1.nptr, F.nptr) T F T.nptr := F.nptr F (E) F.nptr := E

18、.nptr F id F.nptr := mkleaf (id, id.entry) F num F.nptr := mkleaf (num, num.val) E T R.i := T.nptr T + T + T + RE.nptr := R.sR +TR1.i := mknode ( +, R.i, T.nptr)R1R.s := R1.sR R.s := R.i T F W.i := F.nptrWT.nptr := W.sW * *FW1.i := mknode ( * *, W.i, F.nptr)W1W.s := W1.sW W.s := W.i + +使用繼承屬性構造使用繼承屬

19、性構造a4c的抽象語法樹的抽象語法樹ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R. sR. sR. sE.nptrE T R.i:=T.nptr R E.nptr:=R.sR + T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR - T R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.sR R.s:=R.iT ( E ) T.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entr

20、y)T num T.nptr:=mkleaf(num,num.val)4.7令綜合屬性val表示S產生的二進制數的值。SL.L|LLLB|BB0|1(a)試用各有關綜合屬性決定S.val.如果只有整數部分，很顯然，可以定義如下：SLS.val = L.val;LL1BL.val = L1.val *2 + B.val;LBL.val = B.val; L.b =2;B0B.val =0;B1B.val =1;為了求小數部分的值，引入L的綜合屬性b記錄2的L的位數次冪值(2lengthofL)SL1.L2S.val =L1.val +L2.val /L2.b;SLS.val =L.val;LL1BL.val = L1.val *2 + B.val; L.b =L.b*2;LBL.val = B.val; L.b =2;B0B.val =0;B1B.val =1;訪問鏈n訪問鏈的使用及建立n動態作用域和靜態作用域產生的不同輸出n值調用、引用調用、復寫恢復調用、換名調用例例 題題 n假定使