1、編譯原理課程總復(fù)習(xí)賈棋詞法分析器詞法分析器記號(hào)（記號(hào)（token）流）流源代碼源代碼源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號(hào)記號(hào)非形式非形式化描述化描述形式化形式化描述描述正規(guī)式正規(guī)式字母字母串串語(yǔ)言語(yǔ)言字母表字母表名名字字n復(fù)雜的例子復(fù)雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001Pascal語(yǔ)言的標(biāo)識(shí)符集合語(yǔ)言的標(biāo)識(shí)符集合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源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號(hào)記號(hào)非形式非形式化描述化描述形式化形式化描述描述正規(guī)式正規(guī)式字母字母串串語(yǔ)言語(yǔ)言字母表字母表名名字字 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖12開始開始a0abb 12開始開始a0abbab子集構(gòu)造法子集構(gòu)

3、造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab678234

4、5 子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 BD開始開始aAabbabCba19開始開始 0ab ab6782345 12開始開始a0abbabBD開始開始aAabbaa, bCbaEbBD開始開始aAabbabCbaBD開始開始aAabbabCbaBD開始開始aAabbabCbaBD開始開始aAabbabCba12開始開始a0abbab0123aabbabbbstart45aaa, b012bbbb4aastart最簡(jiǎn)最簡(jiǎn)DFA正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖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構(gòu)造構(gòu)造DFA, ,接受接受 0和和1的個(gè)數(shù)都是偶數(shù)的字符串的個(gè)數(shù)都是偶數(shù)的字符串312011110000開始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖第三章 語(yǔ)法分析器qE E A E | (E )

7、 | E | idqA + | * *qletter A-Za-zqdigit 0-9qid letter(letter|digit)* q串的特點(diǎn)串的特點(diǎn) 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句柄與某個(gè)產(chǎn)生式的右部符號(hào)串相同句柄與某個(gè)產(chǎn)生式的右部符號(hào)串相同句柄是句型的一個(gè)子串句柄是句型的一個(gè)子串把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過(guò)程的一步把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過(guò)程的一步n構(gòu)造拓廣文

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

9、c在FOLLOW(A)中。n 而上面的移進(jìn)一歸約沖突在規(guī)范LR(1)情況下不存在，因?yàn)橹挥性诿媾Ra時(shí)才進(jìn)行d到A的歸約。該文法還有另一個(gè)移進(jìn)歸約沖突，在bd進(jìn)棧后，面臨c的情況，其沖突的原因和上面的類似。該沖突在規(guī)范LR(1)情況下也不存在。這樣，該文法是LR(1)文法。n 顯然該文法的規(guī)范LR(1)項(xiàng)目集的集合中沒有同心項(xiàng)目集，因此該文法也是LALR(1)文法。id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則

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如果既有如果既有綜合屬性綜合屬性又有又有繼承屬性繼承屬性，在建立翻譯模式，在建立翻譯模式時(shí)就必須保證：時(shí)就必須保證：1. 產(chǎn)生式右邊的符號(hào)的產(chǎn)生式右邊的符號(hào)的繼承屬性繼承屬性必須在先于這個(gè)符號(hào)必須在先于這個(gè)符號(hào)的動(dòng)作中計(jì)算出來(lái)。的動(dòng)作中計(jì)算出來(lái)。2. 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的一個(gè)動(dòng)作不能

11、引用這個(gè)動(dòng)作右邊的符號(hào)的綜合屬性綜合屬性。3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符的綜合屬性綜合屬性只有在它所引用的只有在它所引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常可放在產(chǎn)生式右端的的動(dòng)作通?？煞旁诋a(chǎn)生式右端的末尾末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in)在寫語(yǔ)法制導(dǎo)定義之前，首先分析清楚需要為文在寫語(yǔ)法制導(dǎo)定義之前，首先分析清楚需要為文法符號(hào)定義一些什么屬性，然后看這些屬性的值法符號(hào)定義一些什么屬性，然后看這些屬性的值是否可以由文法符號(hào)本身所推出的串決定。若是，是否可以由文法符號(hào)本身

12、所推出的串決定。若是，則應(yīng)該只用綜合屬性就能解決。則應(yīng)該只用綜合屬性就能解決。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 導(dǎo)數(shù)導(dǎo)數(shù)產(chǎn)產(chǎn) 生生 式式語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 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)一共聲明多少個(gè)一共聲明多少個(gè)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產(chǎn)生的二進(jìn)制數(shù)的值。例如，輸入101.101時(shí)，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. 產(chǎn)生式右邊的符號(hào)的產(chǎn)生式右邊的符號(hào)的繼承屬性繼承屬性必須在先必須在先于這個(gè)符號(hào)的動(dòng)作中計(jì)算出來(lái)。于這個(gè)符號(hào)的動(dòng)作中計(jì)算出來(lái)。2. 一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊的符號(hào)的的綜合屬性綜合

17、屬性。3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符的綜合屬性綜合屬性只有在只有在它所引用的所有屬性都計(jì)算出來(lái)以后才能它所引用的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常放在產(chǎn)生計(jì)算。計(jì)算這種屬性的動(dòng)作通常放在產(chǎn)生式右端的式右端的末尾末尾。產(chǎn)產(chǎn) 生生 式式語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 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 + +使用繼承屬性構(gòu)造使用繼承屬

19、性構(gòu)造a4c的抽象語(yǔ)法樹的抽象語(yǔ)法樹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產(chǎn)生的二進(jìn)制數(shù)的值。SL.L|LLLB|BB0|1(a)試用各有關(guān)綜合屬性決定S.val.如果只有整數(shù)部分，很顯然，可以定義如下：SLS.val = L.val;LL1BL.val = L1.val *2 + B.val;LBL.val = B.val; L.b =2;B0B.val =0;B1B.val =1;為了求小數(shù)部分的值，引入L的綜合屬性b記錄2的L的位數(shù)次冪值(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;訪問(wèn)鏈n訪問(wèn)鏈的使用及建立n動(dòng)態(tài)作用域和靜態(tài)作用域產(chǎn)生的不同輸出n值調(diào)用、引用調(diào)用、復(fù)寫恢復(fù)調(diào)用、換名調(diào)用例例 題題 n假定使