編譯原理試題及答案.doc

編譯原理復(fù)習(xí)題一、填空題：1、編譯方式與解釋方式的根本區(qū)別在于（ 是否生成目標(biāo)代碼 ）。2、對編譯程序而言，輸入數(shù)據(jù)是（ 源程序 ），輸出結(jié)果是（ 目標(biāo)程序 ）。3、如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段：（編譯階段 ）和（ 運(yùn)行階段 ）。4、如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分成三個階段：（ 編譯階段）、（匯編階段）和（運(yùn)行階段）。5、自頂向下語法分析方法會遇到的主要問題有（ 回溯 ）和（ （左遞歸帶來的）無限循環(huán) ）。6、LL(k)分析法中，第一個L的含義是（ 從左到右進(jìn)行分析 ），第二個L的含義是（ 每次進(jìn)行最左推導(dǎo) ），“k”的含義是（向輸入串中查看K個輸入符號 ）。7、LL(1)分析法中，第一個L的含義是（從左到右進(jìn)行分析 ），第二個L的含義是（每次進(jìn)行最左推導(dǎo) ），“1”的含義是（向輸入串中查看1個輸入符號 ）。8、自頂向下語法分析方法的基本思想是：從（識別符號）出發(fā)，不斷建立（ 直接推導(dǎo) ），試圖構(gòu)造一個推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號相同的（ 符號串 ）。9、自底向上語法分析方法的基本思想是：從待輸入的符號串開始，利用文法的規(guī)則步步向上進(jìn)行（直接歸約），試圖（歸約）到文法的（ 識別符號|開始符號 ）。10、LR(0)分析法的名字中，“L”的含義是（從左到右進(jìn)行分析），“R”的含義是（ 采用最右推導(dǎo)的逆過程-最左歸約 ），“0”的含義是（向貌似句柄的符號串后查看0個輸入符號）。11、LR(1)分析法的名字中，“L”的含義是（從左到右進(jìn)行分析），“R”的含義是（采用最右推導(dǎo)的逆過程-最左歸約），“1”的含義是（向貌似句柄的符號串后查看1個輸入符號）。12、SLR(1)分析法的名字中，“S”的含義是（簡單的 ），“L”的含義是（從左到右進(jìn)行分析），“R”的含義是（采用最右推導(dǎo)的逆過程-最左歸約），“1”的含義是（向貌似句柄的符號串后查看1個輸入符號）。13、在編譯過程中，常見的中間語言形式有（逆波蘭表示 ）、（三元式 ）、（四元式）和（樹形表示）。14、在編譯程序中安排中間代碼生成的目的是（便于代碼優(yōu)化）和（便于目標(biāo)程序的移植）。15、表達(dá)式-a+b*(-c+d)的逆波蘭表示為（ a-bc-d+*+ ）。16、表達(dá)式a+b*(c+d/e)的逆波蘭表示為（abcde/+*+ ）。17、表達(dá)式a:=a+b*c(d/e)/f的逆波蘭表示為（ aabcde/*f/+:= ）。18、文法符號的屬性有（ 繼承屬性 ）和（ 綜合屬性 ）兩種。19、一個文法符號的繼承屬性是通過語法樹中它的（兄弟結(jié)點(diǎn)與父 ）結(jié)點(diǎn)的相應(yīng)文法符號的屬性來計(jì)算的。20、一個文法符號的綜合屬性是通過語法樹中它的（子 ）結(jié)點(diǎn)的屬性來計(jì)算的。21、語法制導(dǎo)的編譯程序能同時(shí)進(jìn)行（ 語法 ）分析和（ 語義 ）分析。22、編譯過程中掃描器所完成的任務(wù)是從（ 源程序 ）中識別出一個個具有（ 獨(dú)立語法意義的單詞 ）。23、確定的有窮自動機(jī)是一個（ 五元組 ），通常表示為（ DFA=（K，M，S，Z）。24、已知文法G(E): E-T|E+T|E-T T-F|T*F|T/F F-(E)|i 該文法的開始符號是（ E ），終結(jié)符號集合VT是（ +,-,*./,(,),i ），非終結(jié)符號集合VN是（ E,T,F ），句型T+T*F+i的短語有（ T+T*F+I ，T*F第一個T，i）。25、已知文法G(E): E-T|E+T|E-T T-F|T*F|T/F F-(E)|i 改寫該文法以消除直接左遞歸，改寫后的文法為：E-（+TE|-TE| ），T-（ FT ），（T- *FT|），F(xiàn)-（ （E）| i ）。26、已知文法G(Z): Z-U0|V1 U-Z1|1 V-Z0|0 請寫出全部由此文法描述的只含四個符號的句子：（ 0101，1010，1001，0110 ）。 該文法是Chomsky（ 3 ）型文法。27、Chomsky定義的四種形式語言文法分別為：（ 0型）文法-又稱（短語文法 ）文法，（1型）文法-又稱（上下文有關(guān)）文法，（2型 ）文法-又稱（上下文無關(guān) ）文法，（3型）文法-又稱（正則）文法。28、文法G(S): S-AB A-aAb|ab B-Bc|其描述的語言L(GS)=（ anbncm,n1，m0 ）。29、文法G(S): S-SAS|b|c A-aaA|a 其描述的語言L(GS)=（b,C,或者是以b開頭、以c結(jié)尾的、中間是任意個由b或c間隔開的奇數(shù)個a組成的符號串）。30、過程與過程引用中信息交換的方法是（全局變量的使用）和（參數(shù)傳遞 ）。31、形式參數(shù)和實(shí)在參數(shù)之間的對應(yīng)關(guān)系通常按（它們在源程序中的位置）來確定。32、按傳結(jié)果的方式進(jìn)行形實(shí)參數(shù)結(jié)合，是一種把（傳地址 ）和（傳值）的特點(diǎn)相結(jié)合的參數(shù)傳遞方式。33、在PASCAL中，由于允許用戶動態(tài)申請與釋放內(nèi)存空間，所以必須采用（ 堆 ）存儲分配方式。34、編譯程序進(jìn)行數(shù)據(jù)流分析的目的是（ 為了進(jìn)行全局優(yōu)化 ）。35、根據(jù)所涉及程序的范圍，優(yōu)化可分為（ 局部優(yōu)化 ）、（ 循環(huán)優(yōu)化 ）和（ 全局優(yōu)化 ）三種。36、局部優(yōu)化是局限于一個（ 基本塊 ）范圍內(nèi)的一種優(yōu)化。37、詞法分析階段的錯誤主要是（ 拼寫錯誤 ），可通過（ 最小距離匹配 ）的辦法去糾正錯誤。38、對錯誤的處理方法一般有（ 校正法 ）和（ 局部優(yōu)化法 ）。39、源程序中的錯誤一般有（ 詞法錯誤 ）、（ 語法錯誤 ）、（ 語義錯誤 ）和（ 違反環(huán)境限制的錯誤 ）四種。40、翻譯程序是這樣一種程序，它能夠?qū)ⅲ?用甲語言書寫的程序 ）轉(zhuǎn)換成與其等價(jià)的（ 用乙語言書寫的程序 ）。41、編譯程序的工作過程一般可以劃分成（ 詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化 ）等五個基本階段。42、編譯程序的工作過程還會伴有（ 表格處理 ）和（ 出錯處理 ）。二、選擇題：1、在使用高級語言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部（ A ）錯誤和部分（ B ）錯誤。 A、語法 B、語義 C、語用 D、運(yùn)行2、程序語言的處理程序是一種（ A ）。 A、系統(tǒng)軟件 B、應(yīng)用軟件 C、實(shí)時(shí)系統(tǒng) D、分布式系統(tǒng)3、（ B ）是兩類程序語言處理程序，它們的主要區(qū)別在于是否生成目標(biāo)代碼。 A、高級語言和低級語言 B、解釋程序和編譯程序 C、編譯程序和操作系統(tǒng) D、系統(tǒng)程序和應(yīng)用程序4、匯編語言是將（ A ）翻譯成（ B ）；編譯程序是將（ C ）翻譯成（ D ）。 A、匯編語言程序 B、機(jī)器語言程序 C、高級語言程序 D、匯編或機(jī)器語言程序 e、匯編或高級語言程序 F、機(jī)器或高級語言程序5、編譯程序與具體的機(jī)器（ A ），與具體的語言（ B ）。 A、有關(guān) B、無關(guān)6、編譯程序生成的目標(biāo)程序（ B ）是可執(zhí)行的程序。 A、一定 B、不一定7、編譯程序生成的目標(biāo)程序（ B ）是機(jī)器語言程序。 A、一定 B、不一定8、把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由（ B ）完成的。 A、編譯器 B、匯編器 C、解釋器 D、預(yù)處理器9、編譯過程中，語法分析器的任務(wù)是（ B ）。 (1)分析單詞是怎樣構(gòu)成的；(2)分析單詞串是如何構(gòu)成語句和說明的；(3)分析語句和說明是如何構(gòu)成程序的；(4)分析程序的結(jié)構(gòu) A、(2)(3) B、(2)(3)(4) C、(1)(2)(3) D、(1)(2)(3)(4) 10、文法G所描述的語言是（ D ）的集合 A、文法G的字母表V中所有符號組成的符號串； B、文法G的字母表V的閉包V*中的所有符號串； C、由文法的識別符號推出的所有符號串； D、由文法的識別符號推出的所有終結(jié)符符號串；11、描述語言L=ambn|nm1的文法為（D ）。 A、Z-Abb, A-aA|a, B-bB|b B、Z-ABb, A-Aa|a,B-aBb|b C、Z-Ab, A-aAb|a D、Z-aAb, A-Ab|aAb|12、一個句型中的最左（B ）稱為該句型的句柄。 A、短語 B、簡單短語 C、素短語 D、終結(jié)符號13、文法的二義性和語言的二義性是兩個（A）的概念。 A、不同 B、相同 C、無法判斷14、上下文無關(guān)文法（ A）產(chǎn)生語言L=ambnci|i1,n1 A、可以 B、不可以15、（B）正規(guī)文法能產(chǎn)生下面的語言：L=ambn|n1 A、存在一個 B、不存在任何c、無法判斷16、編譯程序中的語法分析器接受以（C）為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。 A、表達(dá)式 B、產(chǎn)生式C、單詞D、語句17、高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ B ）分析方法。 A、自左至右 B、自頂向下 C、自底向上 D、自右至左18、算符優(yōu)先分析法每次都是對（ E ）進(jìn)行歸約，簡單優(yōu)先分析法每次都是對（ C ）進(jìn)行歸約。 A、最左短語 B、簡單短語 C、句柄 D、素短語 E、最左素短語19、文法G(S)：SaTb|,，T-R，RR/S|S的句型aR/aSb/aTb,b的最左素短語為（ B ）。 A、aTb B、aSb C、S D、R/ E、,20、LR語法分析棧中存放的狀態(tài)是識別（ B ）的DFA狀態(tài)。 A、前綴 B、可歸前綴 C、項(xiàng)目 D、句柄21、已知文法GS：s-LaR|R，L-bR|c，R-L 該文法是（ B ）。 (1)LR(0)文法；(2)SLR(1)文法；(3)LR(1)文法；(4)LALR(1)文法；(5)都不是 A、(1)(2) B、(3)(4) C、(1)(2)(3)(4) D、(5) E、(6)22、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部（ B ）是該句型的句柄。 A、一定 B、不一定 23、LR(K)方法是（ D ）。 A、從左到右分析，每次走K步的一種編譯方法 B、從左到右分析，共經(jīng)過K步的一種編譯方法 C、從左到右分析，每次向前預(yù)測K步的一種編譯方法 D、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法24、文法GS：S-AA，A-Aa|a 不是LR(1)文法的理由是（ D ） A、FIRST(S)NFIRST(A) B、FIRST(A)NFOLLLOW(A) C、FIRST(Aa)NFIRST(a) D、都不是25、下列關(guān)于標(biāo)識符和名字的敘述中，正確的是（ C ）。 A、標(biāo)識符有一定的含義 B、名字是一個沒有意義的字符序列 C、名字有確切的屬性 D、都不對26、編譯程序在其工作過程中使用最多的數(shù)據(jù)結(jié)構(gòu)是（ C ）。它記錄著源程序中的各種信息，以便查詢或修改。 A、線性表 B、鏈表 C、表 D、符號表 27、在編譯程序在其工作過程中使用的各種表中，以（ D ）最重要，其生存期最長，使用也最頻繁。 A、線性表 B、鏈表 C、表 D、符號表28、編譯程序使用（ B ）區(qū)別標(biāo)識符的作用域。 A、說明標(biāo)識符的過程或函數(shù)名 B、說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次 C、說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 D、標(biāo)識符的行號29、動態(tài)存儲分配時(shí)，可以采用的分配方法有（ C ）。 (1)以過程為單位的棧式動態(tài)存儲分配；(2)堆存儲分配；(3)最佳分配方法 A、(1) B、(2) C、(1)(2) D、(1)(2)(3)30、過程調(diào)用時(shí)，參數(shù)的傳遞方法通常有（ D ）。 (1)傳值；(2)傳地址；(3)傳結(jié)果；(4)傳名 A、(1)(2) B、(1)(2)(3) C、(1)(2)(4) D、(1)(2)(3)(4)31、在編譯方法中，動態(tài)存儲分配的含義是（ A ）。 A、在運(yùn)行階段對源程序中的量進(jìn)行分配 B、在編譯階段對源程序中的量進(jìn)行分配 C、在編譯階段對源程序中的量進(jìn)行分配，在運(yùn)行時(shí)這些量的地址可以根據(jù)需要改變 D、以上都不對32、PASCAL中過程說明的局部量地址分配在（ B ）。 A、調(diào)用者的數(shù)據(jù)區(qū)中 B、被調(diào)用者的數(shù)據(jù)區(qū) C、主程序的數(shù)據(jù)區(qū) D、公共數(shù)據(jù)區(qū)33、表達(dá)式-a+b*c+d+(e*f)/d*e，如果優(yōu)先級由高到低依次為-、+、*、/，且均為左結(jié)合，則其后綴式為（ D ）。 A、abc*+d+ef*d/e*+- B、a-bc*def*d/e*+ C、a-bc*+def*d/e*+ D、a-b+cd+ef*+*de*/34、表達(dá)式a*b-c-d$e$f-g-h*i中，運(yùn)算符的優(yōu)先級由高到低依次為-、*、$，且均為右結(jié)合，則其后綴式為（ D ）。 A、ab*c-d-e$fg-h-i*$ B、$*a-b-cd$e*-f-ghi C、bcd-a*efgh-i*$ D、abcd-*efgh-i*$ E、ab*c-d-e$fg-h-i*$35、a:= a+b*c(d/e)/f的逆波蘭記號表示是（ C ）。A、aabc*+de/f/:= B、aabcde/*f/:= C、aabcde/*f/+:= D、以上都不對。三、簡答題：1、什么是語法制導(dǎo)翻譯？答：所謂語法制導(dǎo)翻譯，是指在語法規(guī)則的制導(dǎo)下，通過計(jì)算語義規(guī)則，完成對輸入符號的翻譯。由于使用屬性文法時(shí)把語法規(guī)則和語義規(guī)則分開，但在使用語法規(guī)則進(jìn)行推導(dǎo)或歸約的同時(shí)又使用這些語義規(guī)則來指導(dǎo)翻譯與最終產(chǎn)生目標(biāo)代碼，所以稱為語法制導(dǎo)翻譯。2、寫出算術(shù)表達(dá)式A+B*(C-D)+E/(C-D)*N 的三元式、四元式序列。答：四元式： 三元式：（-，C，D，T1） （1） （-，C，D）（*，B，T1，T2） （2）（*，B，（1）（+，A，T2，T3） （3） （+，A，（2）（-，C，D，T4） （4） （-，C，D）（*，T4，N，T5） （5） （*，（4），N）（/，E，T5，T6） （6）（/，E，（5）（+，T3，T6，T7） （7） （+，（3），（6）3、寫出條件語句 IF a，a，0，T1） （2） （BMZ，T1， ，（6） （3） （+，x，1，T2） （4） （：=，T2， ，x） （5） （BR， ， ，（9） （6） （-，x，1，T3） （7） （*，4，T3，T4） （8） （：=，T4， ，x） （9）4、把語句 IF AB3 do begin a:=a+3*b;b:=a+e-f*e; end; 的四元式序列。 答： （1） （+，x，y，T1） （2） （，T1，3，T2） （3） （BMZ，T2， ,(12)） （4） （*，3，b，T3） （5） （+，a ，T3，T4） （6） （：=，T4， ，a） （7） （+，a，e，T5） （8） （*，f，e，T6） （9） （-，T5，T6，T7） （10） （：=，T7， ，b） （11） （BR， ， ，（1） （12）8、將語句if A V B0 then while C0 do C:=C+D翻譯成四元式。答：100 (jnz， A， -， 104)101 (j， -， -， 102)102 (j， B， 0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1099、對下列文法G: S-#S# S-D(R) R-R;P|P P-S|i D-i （1）計(jì)算文法G中每個非終結(jié)符的FIRSTVT集； （2）計(jì)算文法G中每個非終結(jié)符的LASTVT集； 答：（1）各非終結(jié)符的FIRSTVT集合為：FIRSTVT（S）= # FIRSTVT（P）=（，i）FIRSTVT（S）=（，i） FIRSTVT（D）=i FIRSTVT（R）=；，（，i ） （2）各非終結(jié)符的LASTVT集合為：LASTVT（S）=# LASTVT（P）= ，iLASTVT（S）= LASTVT（D）= i LASTVT（R）=；，），i10、對下列文法G: S-#S# S-fStS S-i=E E-E+T|T T-PT|P P-(E)|i （1）計(jì)算文法G中每個非終結(jié)符的FIRSTVT集； （2）計(jì)算文法G中每個非終結(jié)符的LASTVT集；答：（1）各非終結(jié)符的FIRSTVT集合為：FIRSTVT（S）= # FIRSTVT（T）= ，（，i）FIRSTVT（S）=f，i FIRSTVT（E）=+，（，i ）FIRSTVT（P）=（，i ） （2）各非終結(jié)符的LASTVT集合為：LASTVT（S）=# LASTVT（T）= ，iLASTVT（S）= t，=，+，)，iLASTVT（E）= +，iLASTVT（P）= ，i11、文法G1：P-PaP|PbP|cP|Pe|f 證明文法G1是二義文法。答：因?yàn)槲姆ù嬖诰湫停篺bfbf ，此句型有兩棵不同的語法樹，所以文法是二義的。 或存在2種最右推導(dǎo)：A、 P=PbP=PbPbP=PbPbf=Pbfbf=fbfbfB、 P=PbP=Pbf=PbPbf=Pbfbf=fbfbf12、有文法GN：N-SE|ES-SD|DE-0|2|4|6|8|10D-0|1|2|3|4|5|6|7|8|9證明該文法是二義的；此文法描述的語言是什么？并試寫出另一文法，使L（G）=L（G），且G是無二義的。答：對于該文法，存在句型110，有兩棵不同的語法樹或兩種不同的最右推導(dǎo)，因此文法具有二義性。 A、 N=SE=S10=D10=110 B、 N=SE=S0=SD0=S10=D10=110該文法描述的語言是偶數(shù)集合。等價(jià)的無二義文法是：GN：N-SE|ES-SD|DE-0|2|4|6|8D-0|1|2|3|4|5|6|7|8|913、寫出不能被5整除的偶整數(shù)的文法。答：GZ:Z-(+|-)ABA-0|1|2|3|4|5|6|7|8|9|AAB-1|2|3|4|5|6|7|8|914、對于文法G=（VN，VT，S，P）： VN= S，A，B，；VT=a，b，開始符號為SP：S-aB|bAA-aS|bAA|aB-bS|aBB|b 給出串a(chǎn)aabbabbba的（1） 最左推導(dǎo)；（2）最右推導(dǎo)；（3）推導(dǎo)樹。答：最左推導(dǎo)： S=aB=aaBB=aaaBBB=aaabSBB=aaabbABB=aaabbaBB=aaabbabB=aaabbabbS=aaabbabbbA=aaabbabbba最右推導(dǎo)：S=aB=aaBB=aaBbS=aaBbbA=aaBbba=aaaBBbba=aaaBbbba=aaabSbbba=aaabbAbbba=aaabbabbba15、什么是句柄？答：一個句型德最左直接短語稱為句柄。16、什么是最左素短語？17、上下文無關(guān)文法答：若一個形式文法 G = (N, , P, S) 的產(chǎn)生式規(guī)則都取如下的形式：V - w，則稱之為上下文無關(guān)的，其中 VN ，w(N)* 。上下文無關(guān)文法取名為“上下文無關(guān)”的原因就是因?yàn)樽址?V 總可以被字串 w 自由替換，而無需考慮字符 V 出現(xiàn)的上下文。上下文無關(guān)文法重要的原因在于它們擁有足夠強(qiáng)的表達(dá)力來表示大多數(shù)程序設(shè)計(jì)語言的語法； 四、問答題：1、給出將賦值語句翻譯成四元式的語法制導(dǎo)定義，允許右部表達(dá)式含有加法、乘法、取負(fù)、括號運(yùn)算。生成賦值語句x:=b*(c+d)+a的四元式。2、出條件賦值語句 i:=if b then e1 else e2 的語義子程序。其中b是布爾表達(dá)式，e1和e2 是算術(shù)表達(dá)式，I代表與e1和e2類型相同的左部變量。按寫出的語義子程序生成條件賦值語句 z:=if ac then x+y else x-y+0.5 的四元式序列。3、試寫出PASCAL循環(huán)語句 for I:=1 to n do s的語義子程序，假定該語句的文法為： F1:=for i:=1 to n S:= F1 do S1 4、給出做為條件控制的布爾表達(dá)式翻譯為四元式的語法制導(dǎo)定義，允許布爾表達(dá)式中有與、或、非及括弧運(yùn)算。（如在翻譯過程中使用了自定義的函數(shù)，可以不寫函數(shù)過程，但請注明函數(shù)的功能和出入口的參數(shù)）。5、按語法制導(dǎo)的定義將下面的后綴表達(dá)式翻譯成中綴表達(dá)式。注意：不允許出現(xiàn)冗余括號。E-E1E2+E-E1E2*E-id6、某程序設(shè)計(jì)語言說明部分的語法制導(dǎo)定義如下所示：D-TLT-int|realL-L1,id|id給出其語法制導(dǎo)定義及自底向上的翻譯方案，并比較兩者的不同。7、設(shè)有文法GS：S-E(1)E-Aa(2)|Bb(3)A-cA(4)|d(5)B-cB(6)|d(7) 構(gòu)造其LR（0）分析表并利用此分析表判斷符號串a(chǎn)cccd是否是該文法的句子。8、對下列文法：S-SS-bRSTS-bR R-dSaR-eT-fRaT-f(1)出非終結(jié)符的FIRST和FOLLOW的集合。（2）構(gòu)造該文法的SLR（1）分析表。9、給定文法 GS ：S SaA | aA AbS | b 請構(gòu)造該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 。 請構(gòu)造該文法的 LR(0) 分析表。 什么是 LR(0) 文法？該文法是 LR(0) 文法嗎？為什么？ 什么是 SLR(1) 文法？該文法是 SLR(1) 文法嗎？為什么？ 10、構(gòu)造下列文法的LR（1）分析表，其中S 是文法的開始符號。S-SS-Aa|dAb|Bb|dBaA-cB-c11、對下面的文法G：S-bAAB|bAA-dSa|bB-cAa|c（1）判斷此文法是下列文法中的哪一種？并說明理由。 LR（0）、SLR（1）、LALR（1）、LR（1） （2）構(gòu)造相應(yīng)文法的項(xiàng)目集族和分析表。12、對下面的文法GS：S-aBc|bABA-aAb|bB-b|構(gòu)造其LL（1）分析表，并利用符號棧分析符號串baabbb是否是該文法的句子。13、對下面的文法G：E-E+T|TT-T*F|FF-(E)|I(1) 構(gòu)造其消除直接左遞歸后的文法G； （2）構(gòu)造文法G 的LL（1）分析表，并利用符號棧分析符號串i1*i2+i3是否是該文法的句子。14、對下面的文法G：P-begind;XendX-d;X|sYY-;sY|構(gòu)造文法G 的LL（1）分析表15、對下面的文法G：E-TEE-+E|T-FTT-T|F-PFF-*F|P-(E)|a|b| (1)計(jì)算這個文法的每個非終結(jié)符的FIRST和FOLLOW集合； （2）證明這個文法是LL（1）的； （3）構(gòu)造它的預(yù)測分析表； （4）構(gòu)造它的遞歸下降分析程序。16、對文法G(S)：S S a T | a T | a TT a T | a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。 17、設(shè)字母表= a，b，給出上的一個正則式b*abb*(abb*)。（1）構(gòu)造該正則式所對應(yīng)的NFA（畫出轉(zhuǎn)換圖）；（2）將所求的NFA確定化（畫出DFA的轉(zhuǎn)換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉(zhuǎn)換圖）；（4）該正則式所表示的正則集是什么？試用自然語言描述之。18、設(shè)字母表= a，b，給出上的一個正則式（a *|b*）b(ba)*。（1）構(gòu)造該正則式所對應(yīng)的NFA（畫出轉(zhuǎn)換圖）；（2）將所求的NFA確定化（畫出DFA的轉(zhuǎn)換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉(zhuǎn)換圖）；19、設(shè)有語言 L= | 0,1 + ，且不以 0 開頭，但以 00 結(jié)尾 。 試寫出描述 L 的正規(guī)表達(dá)式； 構(gòu)造識別 L 的 DFA （要求給出詳細(xì)過程，并畫出構(gòu)造過程中的 NDFA、DFA 的狀態(tài)轉(zhuǎn)換圖，以及 DFA 的形式化描述 ) 。 20、設(shè)字母表= a，b，給出上的一個正則式（a|b）*（aa|bb）（a|b）*。（1）構(gòu)造該正則式所對應(yīng)的NFA（畫出轉(zhuǎn)換圖）；（2）將所求的NFA確定化（畫出DFA的轉(zhuǎn)換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉(zhuǎn)換圖）；21、設(shè)字母表= a，b，給出上的一個正則式（a|b）*a（a|b）。（1）構(gòu)造該正則式所對應(yīng)的NFA（畫出轉(zhuǎn)換圖）；（2）將所求的NFA確定化（畫出DFA的轉(zhuǎn)換圖）；（3）將所求出的DFA最小化（畫出極小化后的轉(zhuǎn)換圖）；22、設(shè)有語言 L= | 0,1 + ，且不以 0 開頭，但以 00 結(jié)尾 。試寫出描述 L 的正規(guī)表達(dá)式；構(gòu)造識別 L 的 DFA （要求給出詳細(xì)過程，并畫出構(gòu)造過程中的 NDFA 、 DFA 的狀態(tài)轉(zhuǎn)換圖，以及 DFA 的形式化描述 ) 。答：（ 1 ）正規(guī)表達(dá)式： 1(0|1) * 00 （ 2 ）第一步：將正規(guī)表達(dá)式轉(zhuǎn)換為 NDFA 第二步：將 NDFA 確定化為 DFA ：造表法確定化（ 3 分） 確定化后 DFA M 的狀態(tài)轉(zhuǎn)換表 狀態(tài) 輸入I 0I 1t01SA,D,Bq 0q 1A,D,BD,B,CD,B重新命名q 1q 2q 3D,B,CD,B,C,ZD,Bq 2q 4q 3D,BD,B,CD,Bq 3q 2q 3D,B,C,ZD,B,C,ZD,Bq 4q 4q 3DFA 的狀態(tài)轉(zhuǎn)換圖第三步：給出 DFA 的形式化描述 DFA M = （ q 0 , q 1 , q 2 , q 3 , q 4 , 0,1, t, q 0 , q 4 ）t 的定義見 M 的狀態(tài)轉(zhuǎn)換表。23、給定文法 GS ：S SaA|aA AbS|b請構(gòu)造該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 。請構(gòu)造該文法的 LR(0) 分析表。什么是 LR(0) 文法？該文法是 LR(0) 文法嗎？為什么？什么是 SLR(1) 文法？該文法是 SLR(1) 文法嗎？為什么？ 答： （1）拓廣文法： GS: S S S SaA S a A AbS A b 該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA ： 該文法的 LR(0) 分析表： 狀態(tài)ACTIONGOTOab#SA0S 211S 3acc2r 3r 3r 33S 544r 2r 2 /S 6r 25r 5r 5r 56S 277r 4 /S 3r 4r 4 LR(0) 文法：該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 中沒有沖突狀態(tài)。該文法不是 LR(0) 文法，因?yàn)榇嬖跊_突狀態(tài)： I 4 和 I 7。 SLR(1) 文法：該文法的以 LR(0) 項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 中有沖突狀態(tài)，沖突可用 FOLLOW 集解決。該文法不是 SLR(1) 文法。因?yàn)?FOLLOW(S)=a,b,# ，所以無法解決沖突。24、對下面的文法G：S-aBc|bABA-aAb|bB-b| (1)計(jì)算這個文法的每個非終結(jié)符的FIRST和FOLLOW集合； （2）證明這個文法是LL（1）的；（3）構(gòu)造它的預(yù)測分析表。答：（1）first(B)=b, ,first(A)=a,b,first(S)=a,bFollow(S)=#,follow(A)=b,#,follow(B)=c,# (2)因?yàn)橹挥蠪IRST(B)含有e , 所以只考慮： FOLLOW(B)=FIRST(c) FOL