編譯原理復(fù)習(xí)題目集答案

1、第4章 詞法分析重點內(nèi)容：正規(guī)式轉(zhuǎn)化為DFAa、 正規(guī)式->NFAb、 NFA -> DFA（子集法）c、 DFA化簡（分割法）題目1：課件例題：a、 為 R=(a|b)*(aa|bb)(a|b)*構(gòu)造 NFA b、 從NFA構(gòu)造DFA的算法c、 化簡題目2： 4.7 例1：構(gòu)造正規(guī)式相應(yīng)的DFA：1(0|1)*101按照以下三步：（1）由正規(guī)表達式構(gòu)造轉(zhuǎn)換系統(tǒng)（NFA）（2）由轉(zhuǎn)換系統(tǒng)（NFA）構(gòu)造確定的有窮自動機DFA（3）DFA的最小化答：（1）構(gòu)造與1(0|1)*101等價的 NFA(0|1)*111(0|1)*101XYXABCDY10XABCY11010,1（2）將NF

2、A轉(zhuǎn)換成DFA：采用子集法，即DFA的每個狀態(tài)對應(yīng)NFA的一個狀態(tài)集合：01XAAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態(tài)：01XAAABBCBCADDCB1、將M的狀態(tài)分成非終態(tài)和終態(tài)集X,A,B,C和D。2、尋找子集中不等價狀態(tài)X,A,B,C=>X，A,BC=>XABC，無需合并。最后生成DFA：XABCD110100101題目3：自習(xí)、書本練習(xí)4.7，參考答案見z4 書本練習(xí)4.7.doc 已知文法GS：SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b EaB|bF FbD|aE|b1、 構(gòu)由于不可到達，去除E、F相關(guān)的多余產(chǎn)生式

3、2、 由新的GS構(gòu)造NFA如下3、 NFA的轉(zhuǎn)換表：abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD4、子集法重命名狀態(tài)：（上標0：初態(tài)，*：終態(tài)）ab00131122*343354165*146345、使用分割法化簡以上DFA G：5.1 令G=(0,1,3,4,6),(2,5)/ 分別為非終態(tài)和終態(tài)集5.2 由0,1,3,4,6a=1,3，0,1,3,4,6b=3,2,5,6,4 將0,1,3,4,6劃分為 0,4,61,3，得G=(0,4,6),(1,3),(2,5)5.3 由0,4,6b=3,6,4，將之劃分為0,4,6，得G=(0),(4,6),(1,3),(2,5)

4、5.4 觀察后，G中狀態(tài)不可再分，為最小化DFA。6、分別用 0，4，1，2代表各狀態(tài)，DFA狀態(tài)轉(zhuǎn)換圖如下：造相應(yīng)的最小的DFA第5章 自頂向下的語法分析重點內(nèi)容：LL（1）文法a、 去除左遞歸b、 LL（1）文法的判定（first、follow、select集）c、 預(yù)測分析表d、 使用棧和預(yù)測分析表對輸入串的分析題目1：課件例題：消除左遞歸+判定+分析算術(shù)表達式文法G EE+TTTT*FFF(E)Id、分析輸入串i+i*i#（1）消除G的左遞歸得到文法 GETE ' E'+TE' TFT ' T'*FT'F(E)i（2）求出每個產(chǎn)

5、生式的select集,G是LL(1)文法 SELECT(ETE' ) = (,i SELECT(E'+TE' ) = + SELECT(E' ) = ),# SELECT(TFT' ) = (,i SELECT(T'*FT' ) = * SELECT(T' ) = +,),# SELECT(F(E) ) = ( SELECT(F i ) = i （3）依照選擇集合把產(chǎn)生式填入分析表注：表中空白處為出錯題目2：作業(yè)、習(xí)題5.1：消除左遞歸+判定+分析GS:S->a|(T) T->T,S|S d、分析輸入串（a,a）#文法

6、GS:S->a|(T)，T->T,S|S (1) 給出對(a,(a,a)的最左推導(dǎo)(2) 改寫文法，去除左遞歸(3) 判斷新文法是否LL1文法，如是，給出其預(yù)測分析表 (4) 給出輸入串（a,a）#的分析過程，判斷其是否文法G的句子 。答：（1）對(a,(a,a)的最左推導(dǎo)為： S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=>(a,(T,S)=>(a,(S,S)=>(a,(a,S)=>(a,(a,a)（2） 改寫文法為： 0)Sa 1) S 2) S(T) 3) TSN 4) N,SN 5) N非終結(jié)符

7、FIRST集FOLLOW集Sa,(#,)Ta,()N,)對左部為N的產(chǎn)生式可知：FIRST (,S N) = , FIRST () =FOLLOW (N) =)由于SELECT(N,S N)SELECT(N)=, )=所以文法是LL(1)的。（3）預(yù)測分析表：a(),#Sa(T)TSNSNSNN,SN可由預(yù)測分析表中，無多重入口判定文法是LL（1）的。（4）對輸入串（a,a）#的分析過程為：棧當(dāng)前輸入符剩余輸入符所用產(chǎn)生式#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#(aaa,aa)#a,a)#a,a)#,a)#,a)#,a)#a)#a)#)#)#S(T)TSN

8、SaN,SNSaN可見輸入串（a,a）#是文法的句子。題目3：復(fù)習(xí)、書本5.6例1：判定+分析GS：SaH，HaMd|d，MAb|，AaM|ed、分析輸入串a(chǎn)aabd#（1）判斷GS是否為LL（1）文法；若是，構(gòu)造其預(yù)測分析表；Select(HaMd)=a , Select(Hd)= d ；Select(MAb)= a,e, Select(M)= d,b；Select(AaM)= a , Select(Ae)= e相同左部產(chǎn)生式的select集的交集均為空，所以GS是LL（1）文法。預(yù)測分析表：（2）分析aaabd#是否GS的句子。 使用棧和預(yù)測分析表對輸入串的分析：第6章 自底向上的語法分析

9、重點內(nèi)容：算符優(yōu)先文法a、 非終結(jié)符的firstvt集和lastvt集的計算b、 算符優(yōu)先關(guān)系表c、 使用棧和算符優(yōu)先關(guān)系表對輸入串的歸約題目1：課件例題：文法：EE+T|TTT×F|FF(E)|Ic、算符優(yōu)先歸約輸入串i+i#（1）求各非終結(jié)符的FIRSTVT集與LASTVT集（2）計算算符優(yōu)先關(guān)系表并說明此文法是否算符優(yōu)先文法（3）給出輸入串i+i#的算符優(yōu)先分析過程 （1）FIRSTVT-LASTVT表：非終結(jié)符FIRSTVTLASTVTE+ × i (+ × ) iTx i (× ) i Fi () i（2）算符優(yōu)先關(guān)系表：+x()i#+>

10、<<><>x>><><>(<<<=<)>>>>i>>>>#<<<<=優(yōu)先關(guān)系表中無多重定義，此文法是算符優(yōu)先文法（3）對輸入串i+i#的算符優(yōu)先分析過程為：題目2：作業(yè)、習(xí)題6.1、復(fù)習(xí)：文法GS:S->a|(T) T->T,S|S c、算符優(yōu)先歸約輸入串（a,a）#文法GS:S->a|(T)，T->T,S|S (1) 計算GS的FIRSTVT、LASTVT(2) 改造算符優(yōu)先關(guān)系表并說明GS是否算符優(yōu)先文法

11、(3) 給出輸入串（a,a）#的算符優(yōu)先分析過程，判斷其是否文法G的句子 。答：文法展開為：SaSS(T)TT,STS（1）FIRSTVT-LASTVT表：非終結(jié)符FIRSTVTLASTVTSa (a )T, a (, a )（2）算符優(yōu)先關(guān)系表：a(),#a>>>>>>(<<<=<)>>>,<<<>>#<<<=表中無多重入口，所以是算符優(yōu)先（OPG）文法。（3）對輸入串（a,a）#的算符優(yōu)先分析過程為：棧當(dāng)前輸入字符剩余輸入串動作#(#(a#(N#(N,#(N,a#(

12、N,N#(N#(N)#N(a,a)#a,a)#,a)#a) #a) #)#Move inMove inReduce:SaMove inMove inReduce:SaReduce:TT,SMove inReduce:S(T)可見輸入串（a,a）#是文法的句子。題目3：自習(xí)、書本練習(xí)6.4，參考答案見z6 書本練習(xí)6.4.doc 已知文法GS：SàS;G SàG GàG(T) GàH Hàa Hà(S) TàT+S TàSc、算符優(yōu)先歸約輸入串a(chǎn);(a+a)#（1）構(gòu)造算符優(yōu)先關(guān)系表FIRSTVT(S)=;FIRST

13、VT(G) = ; , a , ( FIRSTVT(G)= ( FIRSTVT(H) = a , ( FIRSTCT(H)=a , ( FIRSTVT(T) = + FIRSTVT(S) = + , ; , a , ( LASTVT(S) = ; LASTVT(G) = ; , a , )LASTVT(G) = ) LASTVT(H) = a , )LASTVT(H) = a, LASTVT(T) = + LASTVT(S) = + , ; , a , 即：FIRSTVTLASTVTS; , a , (; , a , )Ga , (a , )Ha , (a , )T+ , ; , a , (+

14、 , ; , a ,)由SàS;GLASTVT（S） > ; < FIRSTVT（G）由GàG(TLASTVT（G） > ( < FIRSTVT（T）由GàT)LASTVT（T） > )由Gà(T)( = )由TàT+SLASTVT（T） > + < FIRSTVT（S）由Hà(S)( < FIRSTVT（S）LASTVT（S） > )( = )由S-> #S#< FIRSTVT（S）LASTVT（S） > # = #;()a+#;><><>>(<<<<)>>>>>a>>>>>+<<><>#<<<由優(yōu)先關(guān)系表中所有符號對的關(guān)系唯一，可判定文法GS是算符優(yōu)先文法。 (2) 分析a;(aa) / SàS;G |G GàG(T) |H Hàa |(S) TàT+S |S分析棧優(yōu)先關(guān)系當(dāng)前字符剩余輸入串動作1#<a;(aa)#移進2#a>(a