大連理工大學(xué)編譯技術(shù)總復(fù)習(xí)

1、編譯原理課程總復(fù)習(xí)大連理工大學(xué)軟件學(xué)院23詞法分析器詞法分析器記號（記號（token）流）流源代碼源代碼源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號記號非形式非形式化描述化描述形式化形式化描述描述正規(guī)式正規(guī)式字母字母串串語言語言字母表字母表名名字字4n復(fù)雜的例子復(fù)雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110015Pascal語言的標(biāo)識符集合語言的標(biāo)識符集合letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9id lette

2、r( (letter| |digit) )* 6r+=rr*r?=r| a-z=a|b|c|z(1) abc=a|b|c7源程序源程序字符流字符流詞法詞法單元單元詞法詞法記號記號非形式非形式化描述化描述形式化形式化描述描述正規(guī)式正規(guī)式字母字母串串語言語言字母表字母表名名字字8 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother9正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖1012開始開始a0abb11 1

3、2開始開始a0abbab12子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 13子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 14子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 15子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 16子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 17子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 18子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 19子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 20子集構(gòu)造法子集構(gòu)造法19開始開始 0ab a

4、b6782345 21子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 22子集構(gòu)造法子集構(gòu)造法19開始開始 0ab ab6782345 23BD開始開始aAabbabCba19開始開始 0ab ab6782345 12開始開始a0abbab24BD開始開始aAabbaa, bCbaEbBD開始開始aAabbabCba25BD開始開始aAabbabCba26BD開始開始aAabbabCba27BD開始開始aAabbabCba12開始開始a0abbab28290123aabbabbbstart45aaa, b30012bbbb4aastart最簡最簡DFA3132正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換

5、圖狀態(tài)轉(zhuǎn)換圖3319開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3419開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab35 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3619開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3719開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3819開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|ba

6、b3919開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab4012開始開始a0abb19開始開始 0ab ab6782345 410123開始開始4420123開始開始40430123開始開始410440123開始開始4100450123開始開始41001460123開始開始410010470123開始開始4100101480123開始開始41001010490123開始開始410010101500123開始開始4100101010510123開始開始41001010101520123開始開始4100101010153構(gòu)造構(gòu)造DFA, ,接受接受 0和

7、和1的個(gè)數(shù)都是偶數(shù)的字符串的個(gè)數(shù)都是偶數(shù)的字符串312011110000開始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇154正規(guī)式正規(guī)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖55第三章 語法分析器56qE E A E | (E ) | E | idqA + | * *qletter A-Za-zqdigit 0-9qid letter(letter|digit)*57 q串的特點(diǎn)串的特點(diǎn) ba . . . aba . . . aA b b A A a a A | 58 59 60A abab1 | abab2A+Aa 61FIRST集、FOLLOW集626364656667686970717273747

8、57677787980！81自下而上分析 S rm aABe rm aAde rm aAbcde rm abbcde句柄與某個(gè)產(chǎn)生式的右部符號串相同句柄與某個(gè)產(chǎn)生式的右部符號串相同句柄是句型的一個(gè)子串句柄是句型的一個(gè)子串把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過程的一步把句柄歸約成非終結(jié)符代表了最右推導(dǎo)逆過程的一步828384858687888990919293拓廣文法G的LR(0)項(xiàng)目集規(guī)范族為：I0:SSSV=ESEV*EVidEVI1:SSI2:SV =EEV I3:SEI4:V*EEVV*EVidI5:VidI6:SV=EEVV*EVidI7:V*EI8:EVI9:SV=EidS SS V

9、=ES EV *EV idE VV id S V =EE V S S I0I1I2I5S E I3V * EE VV idV * EI4SV*idES V = EE VV *EV idI6=ES V=E E V VVI8idI3*V *E EI7I9識別產(chǎn)生式文法活前綴的DFAI1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R識別產(chǎn)生式文法活前綴的DFASLR(1)文法的弱點(diǎn)nSLR(1)文法描述能力有限98LR(1)分析練習(xí)題目LR(1)分析練習(xí)解答過程n解答：nStep 1. 拓廣文法 (添加產(chǎn)生式S-S)nStep 2: 構(gòu)造識別文法活前綴的DFALR(1

10、)分析練習(xí)解答過程102狀態(tài)狀態(tài)actiongoto= *id$SVE0s4s51231acc2s6r53r24s4s5875r4r46s12s111097r3r38r5r59r110r511r412s12s11101313r3103n拓廣文法n構(gòu)造DFAq若是SLR直接構(gòu)造即可q若是LR需要求取搜索符q若是LALR需要在LR的基礎(chǔ)上進(jìn)行合并n根據(jù)DFA構(gòu)造分析表104判斷文法屬于哪類文法n證明文法 SA a | bAc | dc | bdan A dn是LALR(1)文法，但不是SLR(1)文法。：通過構(gòu)造分析表來回答，如果表中不存在沖突則說明屬于某文法，否則不屬于該文法。：當(dāng)文法很簡單時(shí)，

11、可通過直觀分析。先說明該文法不是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)閏在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)目集，因此該文法也是LAL

12、R(1)文法。105106107108id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 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) 109110111112113114115116117

13、建立翻譯模式建立翻譯模式n如果既有如果既有綜合屬性綜合屬性又有又有繼承屬性繼承屬性，在建立翻譯模式，在建立翻譯模式時(shí)就必須保證：時(shí)就必須保證：1. 產(chǎn)生式右邊的符號的產(chǎn)生式右邊的符號的繼承屬性繼承屬性必須在先于這個(gè)符號必須在先于這個(gè)符號的動作中計(jì)算出來。的動作中計(jì)算出來。2. 一個(gè)動作不能引用這個(gè)動作右邊的符號的一個(gè)動作不能引用這個(gè)動作右邊的符號的綜合屬性綜合屬性。3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符的綜合屬性綜合屬性只有在它所引用的只有在它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的的動作通?？煞旁诋a(chǎn)生式

14、右端的末尾末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in)118119120121122123124在寫語法制導(dǎo)定義之前，首先分析清楚需要為文在寫語法制導(dǎo)定義之前，首先分析清楚需要為文法符號定義一些什么屬性，然后看這些屬性的值法符號定義一些什么屬性，然后看這些屬性的值是否可以由文法符號本身所推出的串決定。若是，是否可以由文法符號本身所推出的串決定。若是，則應(yīng)該只用綜合屬性就能解決。則應(yīng)該只用綜合屬性就能解決。125S S. depth := 0 SS L. depth := S. depth + 1 ( L ) S a print (S. depth) L L

15、1. depth := L. depth L1 , S. depth := L. depth SL S. depth := L. depth S126S 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.max127S S. in := 0 SS (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 :=

16、 L1. in + L1.num+1 S L.num := L1.num + S.num +1 L S. in := L. in S L. num := S.num 128n給出對表達(dá)式求導(dǎo)數(shù)的語法制導(dǎo)定義(習(xí)題4.5)產(chǎn)產(chǎn) 生生 式式語語 義義 規(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 := T.exp T T1* *F T.d := T1.d * *F.exp + T1.exp * *F.d; T.exp := T1.exp * *F.exp T

17、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:=num129P 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:TD.sum= 1D proc id; D1; SD.sum=D1.sum+1130P DD D;D | id:T | proc id; D; S(2)變量變量i

18、d的嵌套深度的嵌套深度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; S131n用用S的綜合屬性的綜合屬性val給出下面文法中給出下面文法中S產(chǎn)生的二產(chǎn)生的二進(jìn)制數(shù)的值。例如，輸入進(jìn)制數(shù)的值。例如，輸入101.101時(shí)，時(shí)，S.val5.625。nS L.L | L L L B | B B 0 | 1 1324.7 用用S的綜合屬性的綜合屬性val給出下面文法中給出下面文法中S產(chǎn)生的二進(jìn)產(chǎn)生的二進(jìn)制數(shù)的值

19、。例如，輸入制數(shù)的值。例如，輸入101.101時(shí)，時(shí)，S.val5.625。S L.L | LL L B | BB 0 | 1 (1) 僅使用僅使用綜合屬性綜合屬性決定決定S.val.如果只有整數(shù)部分，很顯然，可以定義如下：如果只有整數(shù)部分，很顯然，可以定義如下：S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val;L B L.val = B.val; B 0 B.val = 0;B 1 B.val = 1;133為了求小數(shù)部分的值，為了求小數(shù)部分的值，引入引入L的綜合屬性的綜合屬性b記錄記錄2的的L的位數(shù)次冪值的位數(shù)次冪值(2 length o

20、f L)S L1.L2 S.val = L1.val + L2.val / L2.b;S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val; L1.b = L.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;134SvalLv.LbvLvBvLb vBvBv0LbvBv11Bv01135SvalLv.LbvLvBvLb vBvBv0LbvBv11Bv01=1=1=0=2=1=1=0=1=2=5=2=4=8=2+5/8=2.625136nS L.L | L L L B | B B

21、 0 | 1（1）僅使用綜合屬性）僅使用綜合屬性（寫法二）（寫法二）S L1.L2 S.valL1.val+L2.val /2L2.lengthS L S.valL.valL L1B 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=1137nS L.L | L L L B | B B 0 | 1（2）用）用L屬性決定屬性決定S.val。B的唯一綜合屬性是的唯一綜合屬性是c，它給出由，它給出由B產(chǎn)生產(chǎn)生的位對最終值的貢獻(xiàn)。的位對最終值的貢獻(xiàn)。eg:101.101

22、最前和最后一位對最前和最后一位對5.625的的貢獻(xiàn)分別是貢獻(xiàn)分別是4和和0.125。（修改文法）（修改文法）S L.R S.valL1.val+R.valS L S.valL.valL B L1 B.i=L1.c * 2; L.c=L1.c * 2 ; L.val=L1.val+ B.c; L B B.i=1; L.c=1; L.val= B.cR R1 B B.i=R1.c / 2; R.c=R1.c /2 ; R.val=R1.val+ B.c; R B B.i=0.5; R.c=0.5; R.val= B.cB 0 B.c=0B 1 B.c=B.i138（2）試用一個(gè)語法制導(dǎo)定義來決定）

23、試用一個(gè)語法制導(dǎo)定義來決定S.val， 在這個(gè)定義中在這個(gè)定義中B僅有僅有綜合屬性綜合屬性c，給出由，給出由B生成的位對于最后的數(shù)值的分擔(dān)額。生成的位對于最后的數(shù)值的分擔(dān)額。引入引入B的繼承屬性的繼承屬性i，綜合屬性，綜合屬性c。（不修改文法）（不修改文法）S L1.L2 L1.i = 20; L2 .i = 2-1; S.val = L1.val +L2.valS L L.i = 20; S.val = L.val;L L1 B if L.i = 20 then begin L1.i = L.i *2 ; B.i = L.i end else begin L1.i = L.i ; L.s =

24、 L1.s/2; B.i = L1.s end L.val = L1.val +B.c L B B.i = L.i ; L.s= L.i/2; L.val = B.cB 0 B.c = B.i*0B 1 B.c = B.i*1139Sval Lv . Ls v Lv Bc Ls v Bc Bc 0 Ls v Bc 11 Bc 01=2=0*1=0.5=0*0.25=0.125=2.625140Sval iLv . iLs viLv iBciLs vi BciBc 0iLs v iBc 11i Bc 01141Sval iLv . iLs viLv iBciLs vi BciBc 0iLs v

25、iBc 11i Bc 01=20 =2-1 =21 =20 =21 =2-1 =2-1 =2-1 =2-2=2-2=2-3=2-3=2-4=2-1=0.5=0.5=2-2*0=0=2-3*1=0.125=0.5=0.5+0.125=0.625=2.6251421431441. 產(chǎn)生式右邊的符號的產(chǎn)生式右邊的符號的繼承屬性繼承屬性必須在先必須在先于這個(gè)符號的動作中計(jì)算出來。于這個(gè)符號的動作中計(jì)算出來。2. 一個(gè)動作不能引用這個(gè)動作右邊的符號一個(gè)動作不能引用這個(gè)動作右邊的符號的的綜合屬性綜合屬性。3. 產(chǎn)生式左邊非終結(jié)符的產(chǎn)生式左邊非終結(jié)符的綜合屬性綜合屬性只有在只有在它所引用的所有屬性都計(jì)算出來

26、以后才能它所引用的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動作通常放在產(chǎn)生計(jì)算。計(jì)算這種屬性的動作通常放在產(chǎn)生式右端的式右端的末尾末尾。145產(chǎn)產(chǎn) 生生 式式語語 義義 規(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.nptr F id F.nptr := mkleaf (id, id.entry) F num F.

27、nptr := mkleaf (num, num.val) 146E 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 + +147使用繼承屬性構(gòu)造使用繼承屬性構(gòu)造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.npt