編譯原理[張素琴]第2版-答案-清華大學(xué)出版社

1、編譯原理課后習(xí)題第 1 章引論第 1 題解釋下列術(shù)語(yǔ)：（1） 編譯程序：如果源語(yǔ)言為高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言為某臺(tái)計(jì)算機(jī)上的匯編語(yǔ)言或機(jī)器語(yǔ)言，則此翻譯程序稱(chēng)為編譯程序。（2） 源程序：源語(yǔ)言編寫(xiě)的程序稱(chēng)為源程序。（3） 目標(biāo)程序：目標(biāo)語(yǔ)言書(shū)寫(xiě)的程序稱(chēng)為目標(biāo)程序。（4） 編譯程序的前端：它由這樣一些階段組成：這些階段的工作主要依賴(lài)于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)。通常前端包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成這些階段，某些優(yōu)化工作也可在前端做，也包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符號(hào)表管理等工作。（5） 后端：指那些依賴(lài)于目標(biāo)機(jī)而一般不依賴(lài)源語(yǔ)言，只與中間代碼有關(guān)的那些階段，即目標(biāo)代碼生成，以及相

2、關(guān)出錯(cuò)處理和符號(hào)表操作。（6） 遍：是對(duì)源程序或其等價(jià)的中間語(yǔ)言程序從頭到尾掃視并完成規(guī)定任務(wù)的過(guò)程。第 2 題一個(gè)典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？并畫(huà)出編譯程序的總體結(jié)構(gòu)圖。答案：一個(gè)典型的編譯程序通常包含 8 個(gè)組成部分，它們是詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和錯(cuò)誤處理程序。其各部分的主要功能簡(jiǎn)述如下。詞法分析程序：輸人源程序，拼單詞、檢查單詞和分析單詞，輸出單詞的機(jī)內(nèi)表達(dá)形式。語(yǔ)法分析程序：檢查源程序中存在的形式語(yǔ)法錯(cuò)誤，輸出錯(cuò)誤處理信息。語(yǔ)義分析程序：進(jìn)行語(yǔ)義檢查和分析語(yǔ)義信息，并把分

3、析的結(jié)果保存到各類(lèi)語(yǔ)義信息表中。中間代碼生成程序：按照語(yǔ)義規(guī)則，將語(yǔ)法分析程序分析出的語(yǔ)法單位轉(zhuǎn)換成一定形式的中間語(yǔ)言代碼，如三元式或四元式。中間代碼優(yōu)化程序：為了產(chǎn)生高質(zhì)量的目標(biāo)代碼，對(duì)中間代碼進(jìn)行等價(jià)變換處理。目標(biāo)代碼生成程序：將優(yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。表格管理程序：負(fù)責(zé)建立、填寫(xiě)和查找等一系列表格工作。表格的作用是記錄源程序的各類(lèi)信息和編譯各階段的進(jìn)展情況，編譯的每個(gè)階段所需信息多數(shù)都從表格中讀取，產(chǎn)生的中間結(jié)果都記錄在相應(yīng)的表格中?？梢哉f(shuō)整個(gè)編譯過(guò)程就是造表、查表的工作過(guò)程。需要指出的是，這里的“表格管理程序”并不意味著它就是一個(gè)獨(dú)立的表格管理模塊，而是指編譯程序具有的

4、表格管理功能。錯(cuò)誤處理程序：處理和校正源程序中存在的詞法、語(yǔ)法和語(yǔ)義錯(cuò)誤。當(dāng)編譯程序發(fā)現(xiàn)源程序中的錯(cuò)誤時(shí)，錯(cuò)誤處理程序負(fù)責(zé)報(bào)告出錯(cuò)的位置和錯(cuò)誤性質(zhì)等信息，同時(shí)對(duì)發(fā)現(xiàn)的錯(cuò)誤進(jìn)行適當(dāng)?shù)男Ｕㄐ迯?fù)），目的是使編譯程序能夠繼續(xù)向下進(jìn)行分析和處理。第 3 題何謂翻譯程序、編譯程序和解釋程序？它們?nèi)咧g有何種關(guān)系？答案：翻譯程序是指將用某種語(yǔ)言編寫(xiě)的程序轉(zhuǎn)換成另一種語(yǔ)言形式的程序的程序，如編譯程序和匯編程序等。編譯程序是把用高級(jí)語(yǔ)言編寫(xiě)的源程序轉(zhuǎn)換（加工）成與之等價(jià)的另一種用低級(jí)語(yǔ)言編寫(xiě)的目標(biāo)程序的翻譯程序。解釋程序是解釋、執(zhí)行高級(jí)語(yǔ)言源程序的程序。解釋方式一般分為兩種：一種方式是，源程序功能的實(shí)現(xiàn)完全

5、由解釋程序承擔(dān)和完成，即每讀出源程序的一條語(yǔ)句的第一個(gè)單詞，則依據(jù)這個(gè)單詞把控制轉(zhuǎn)移到實(shí)現(xiàn)這條語(yǔ)句功能的程序部分，該部分負(fù)責(zé)完成這條語(yǔ)句的功能的實(shí)現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀出源程序的一條語(yǔ)句，解釋程序就將其翻譯成一段機(jī)器指令并執(zhí)行之，然后再讀人下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。無(wú)論是哪種方式，其加工結(jié)果都是源程序的執(zhí)行結(jié)果。目前很多解釋程序采取上述兩種方式的綜合實(shí)現(xiàn)方案，即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序，然后集中解釋執(zhí)行中間代碼程序，最后得到運(yùn)行結(jié)果。廣義上講，編譯程序和解釋程序

6、都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是邊翻譯（解釋?zhuān)┻厛?zhí)行，不產(chǎn)生目標(biāo)代碼，輸出源程序的運(yùn)行結(jié)果。而編譯程序只負(fù)責(zé)把源程序翻譯成目標(biāo)程序，輸出與源程序等價(jià)的目標(biāo)程序，而目標(biāo)程序的執(zhí)行任務(wù)由操作系統(tǒng)來(lái)完成，即只翻譯不執(zhí)行。第 4 題對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段（詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成）報(bào)告的。（1） else 沒(méi)有匹配的if（2） 數(shù)組下標(biāo)越界（3） 使用的函數(shù)沒(méi)有定義（4） 在數(shù)中出現(xiàn)非數(shù)字字符答案：（1） 語(yǔ)法分析（2） 語(yǔ)義分析（3） 語(yǔ)法分析（4） 詞法分析第3 章 文法和語(yǔ)言第1 題文法G(A,B,S,a,b,c,P,S)其中P 為：SAc|aB

7、AabBbc寫(xiě)出L(GS)的全部元素。答案：L(GS)=abc第2 題文法GN為：ND|NDD0|1|2|3|4|5|6|7|8|9GN的語(yǔ)言是什么？答案:GN的語(yǔ)言是V+。V=0,1,2,3,4,5,6,7,8,9N=>ND=>NDD. =>NDDDD.D=>D.D第題為只包含數(shù)字、加號(hào)和減號(hào)的表達(dá)式，例如9-25，3-1，等構(gòu)造一個(gè)文法。答案：GS:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4 題已知文法GZ：ZaZb|ab 寫(xiě)出L(GZ)的全部元素。答案：Z=>aZb=>aaZbb=>aaa.Z.bbb=&

8、gt; aaa.ab.bbbL(GZ)=anbn|n>=1第5 題寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。 要求：(1) 允許0 打頭；(2)不允許0 打頭。答案：(1)允許0 開(kāi)頭的偶正整數(shù)集合的文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2)不允許0 開(kāi)頭的偶正整數(shù)集合的文法ENT|DTFT|GND|1|3|5|7|9D2|4|6|8FN|0GD|0第6 題已知文法G：<表達(dá)式>:=<項(xiàng)><表達(dá)式><項(xiàng)><項(xiàng)>:=<因子><項(xiàng)>*<因子><因子>:=（&l

9、t;表達(dá)式>）i試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹(shù)。（1）i（2）（i）（3）i*i （4）i*i +i （5）i+(i+i)（6）i+i*i第7 題證明下述文法G表達(dá)式是二義的。表達(dá)式=a|(表達(dá)式)|表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符=+|-|*|/答案：可為句子a+a*a 構(gòu)造兩個(gè)不同的最右推導(dǎo):最右推導(dǎo)1 表達(dá)式 =>表達(dá)式運(yùn)算符表達(dá)式=>表達(dá)式運(yùn)算符a=>表達(dá)式* a=>表達(dá)式運(yùn)算符表達(dá)式* a=>表達(dá)式運(yùn)算符a * a=>表達(dá)式+ a * a=>a + a * a最右推導(dǎo)2 表達(dá)式=>表達(dá)式運(yùn)算符表達(dá)式=>表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符表達(dá)式

10、=>表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符 a=>表達(dá)式運(yùn)算符表達(dá)式 * a=>表達(dá)式運(yùn)算符a * a=>表達(dá)式+ a * a=>a + a * a第8 題文法GS為：SAc|aB Aab Bbc該文法是否為二義的？為什么？答案：對(duì)于串a(chǎn)bc(1)S=>Ac=>abc (2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。或者：對(duì)輸入字符串a(chǎn)bc，能構(gòu)造兩棵不同的語(yǔ)法樹(shù)，所以它是二義的。第9 題考慮下面上下文無(wú)關(guān)文法：SSS*|SS+|a(1)表明通過(guò)此文法如何生成串a(chǎn)a+a*，并為該串構(gòu)造語(yǔ)法樹(shù)。 (2)GS的語(yǔ)言是什么？答案：(1)

11、此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)該文法生成的語(yǔ)言是：*和+的后綴表達(dá)式，即逆波蘭式。第10 題文法SS(S)S| (1) 生成的語(yǔ)言是什么？(2) 該文法是二義的嗎？說(shuō)明理由。答案：（） 嵌套的括號(hào)（） 是二義的，因?yàn)閷?duì)于（）（）可以構(gòu)造兩棵不同的語(yǔ)法樹(shù)。第11 題令文法GE為：ET|E+T|E-T TF|T*F|T/F F(E)|i證明E+T*F 是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。答案：此句型對(duì)應(yīng)語(yǔ)法樹(shù)如右，故為此文法一個(gè)句型?；蛘撸阂?yàn)榇嬖谕茖?dǎo)序列:

12、 E=>E+T=>E+T*F，所以 E+T*F 句型此句型相對(duì)于E 的短語(yǔ)有:E+T*F；相對(duì)于T 的短語(yǔ)有T*F直接短語(yǔ)為：T*F 句柄為：T*F第13 題一個(gè)上下文無(wú)關(guān)文法生成句子abbaa 的推導(dǎo)樹(shù)如下：(1)給出串a(chǎn)bbaa 最左推導(dǎo)、最右推導(dǎo)。(2)該文法的產(chǎn)生式集合P 可能有哪些元素？(3)找出該句子的所有短語(yǔ)、直接短語(yǔ)、句柄。答案：(1)串a(chǎn)bbaa 最左推導(dǎo):S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推導(dǎo)：S=>ABS=>ABAa=>ABa

13、a=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)產(chǎn)生式有：SABS |Aa| Aa BSBB|b可能元素有： aa ab abbaa aaabbaa (3)該句子的短語(yǔ)有：a 是相對(duì)A 的短語(yǔ) 是相對(duì)S 的短語(yǔ)b 是相對(duì)B 的短語(yǔ)bb 是相對(duì)B 的短語(yǔ)aa 是相對(duì)S 的短語(yǔ)abbaa 是相對(duì)S 的短語(yǔ)直接短語(yǔ)有：a b句柄是：a第14 題給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：（1） anbnambm| n，m>=0（2） 1n0m 1m0n| n，m>=0（3）WaWr|W 屬于0|a*，Wr 表示W(wǎng)的逆答案：（）SAA

14、AaAb|（）S1S0|AA0A1|（）S0S0|1S1|第16 題給出生成下述語(yǔ)言的三型文法：(1)an|n >=0 (2) anbm|n,m>=1 (3)anbmck|n,m,k>=0 答案：(1) SaS|(2)SaAAaA|BBbB|b(3)AaA|BBbB|CCcC|第18 題解釋下列術(shù)語(yǔ)和概念：答案：（）字母表：是一個(gè)非空有窮集合。（）串：符號(hào)的有窮序列。字：字母表中的元素。句子：如果 Z-+ x , x V *T 則稱(chēng) x 是文法 G 的一個(gè)句子。 （）語(yǔ)言：它是由句子組成的集合，是由一組記號(hào)所構(gòu)成的集合。程序設(shè)計(jì)的語(yǔ)言就是所有該語(yǔ)言的程序的全體。語(yǔ)言可以看成在

15、一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。語(yǔ)法：表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。語(yǔ)義：表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。語(yǔ)言所代表的含義。第4 章 詞法分析第5 章 自頂向下語(yǔ)法分析方法第1 題對(duì)文法GSSa|(T)TT,S|S(1) 給出(a,(a,a)和(a,a),(a),a)的最左推導(dǎo)。(2) 對(duì)文法G，進(jìn)行改寫(xiě)，然后對(duì)每個(gè)非終結(jié)符寫(xiě)出不帶回溯的遞歸子程序。(3) 經(jīng)改寫(xiě)后的文法是否是LL(1)的?給出它的預(yù)測(cè)分析表。(4) 給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G 的句子。答案：(1) 對(duì)(a,(a,a)的最

16、左推導(dǎo)為：S=>（t）=> (T,S)=> (S,S)=> (a,S)=> (a,(T)=> (a,(T,S)=> (a,(S,S)=> (a,(a,S)=> (a,(a,a)對(duì)(a,a),(a),a) 的最左推導(dǎo)為：S => (T)=> (T,S)=> (S,S)=> (T),S)=> (T,S),S)=> (T,S,S),S)=> (S,S,S),S)=> (T),S,S),S)=> (T,S),S,S),S)=> (S,S),S,S),S)=> (a,S),S,S),S

17、)=> (a,a),S,S),S)=> (a,a),S),S)=> (a,a),(T),S)=> (a,a),(S),S) => (a,a),(a),S)=> (a,a),(a),a)(2) 改寫(xiě)文法為：0) Sa1) S2) S( T )3) TS N4) N, S N5) N非終結(jié)符 FIRST 集 FOLLOW 集S a,( #,)T a,( ).N , ).對(duì)左部為N 的產(chǎn)生式可知：FIRST （, S N）=，F(xiàn)IRST （）=FOLLOW （N）=)由于SELECT(N , S N)SELECT(N ) =， )= 所以文法是LL(1)的。預(yù)測(cè)分

18、析表（Predicting Analysis Table）也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。(3) 對(duì)輸入串（a,a）#的分析過(guò)程為：可見(jiàn)輸入串（a,a）#是文法的句子。第3 題已知文法GS：SMH|aHLSo|KdML|LeHfMK|bLM判斷G 是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。答案：文法展開(kāi)為：0） SM H1） Sa2） HL S o3） H4） Kd M L5） K6） Le H f7） MK8） Mb L M非終結(jié)符 FIRST 集 FOLLOW 集S a,d,b,e #,o M d,b e,#,o H ,e #,f,o L e a,d,b,e,

19、o,#K d, e,#,o 對(duì)相同左部的產(chǎn)生式可知：SELECT(SM H)SELECT(Sa) = d,b ,e，#,o a = SELECT(HL S o)SELECT(H) = e #,f,o = SELECT(Kd M L)SELECT(K) = d e,#,o = SELECT(MK)SELECT(Mb L M) = d，e,#,o b = 所以文法是LL(1)的。預(yù)測(cè)分析表：由預(yù)測(cè)分析表中無(wú)多重入口也可判定文法是LL(1)的。第7 題對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為L(zhǎng)L(1)文法?試對(duì)下面文法進(jìn)行改寫(xiě)，并對(duì)改寫(xiě)后的文法進(jìn)行判斷。()AbaB|BAbb|a(2

20、) AaABe|aBBb|d(3) SAa|bASBBab答案：()先改寫(xiě)文法為：0) AbaB1) A2) BbaBbb3) Bbb4) Ba再改寫(xiě)文法為：0) AbaB1) A2) BbN3) Ba4) NaBbb5) Nb預(yù)測(cè)分析表：由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。（2） 文法：AaABe|aBBb|d提取左公共因子和消除左遞歸后文法變?yōu)椋?) Aa N1) NA B e2) N3) Bd N14) N1b N15) N1非終結(jié)符 FIRST 集 FOLLOW 集A a #,dB d e N a, #,dN1 b, e 對(duì)相同左部的產(chǎn)生式可知：SELECT(NA B e)

21、SELECT(N) = a #,d = SELECT(N1b N1)SELECT(N1) = b e = 所以文法是LL(1)的。預(yù)測(cè)分析表（Predicting Analysis Table）也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。（3）文法：SAa|bASBBab第1 種改寫(xiě)：用A 的產(chǎn)生式右部代替S 的產(chǎn)生式右部的A 得：SSBa|bBab消除左遞歸后文法變?yōu)椋?) Sb N1) NB a N2) N3) Ba b非終結(jié)符 FIRST 集 FOLLOW 集S b #B a aN ,a #對(duì)相同左部的產(chǎn)生式可知：SELECT(NB a N)SELECT(N) = a # = 所

22、以文法是LL(1)的。預(yù)測(cè)分析表（Predicting Analysis Table）也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。第2 種改寫(xiě)：用S 的產(chǎn)生式右部代替A 的產(chǎn)生式右部的S 得：SAa|bAAaB|bBBab消除左遞歸后文法變?yōu)椋?) SA a1) Sb2) Ab B N3) Na B N4) N5) Ba b非終結(jié)符 FIRST 集 FOLLOW 集S b #A b aB a aN a, a對(duì)相同左部的產(chǎn)生式可知：SELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的

23、。預(yù)測(cè)分析表：也可由預(yù)測(cè)分析表中含有多重入口判定文法不是LL(1)的。第6 章 自底向上優(yōu)先分析第1 題已知文法GS為：Sa|(T)TT,S|S(1) 計(jì)算GS的FIRSTVT 和LASTVT。(2) 構(gòu)造GS的算符優(yōu)先關(guān)系表并說(shuō)明GS是否為算符優(yōu)先文法。(3) 計(jì)算GS的優(yōu)先函數(shù)。(4) 給出輸入串(a,a)#和(a,(a,a)#的算符優(yōu)先分析過(guò)程。答案：文法展開(kāi)為：SaSS(T)TT,STS(1) FIRSTVT - LASTVT 表：(2) 算符優(yōu)先關(guān)系表：(3)對(duì)應(yīng)的算符優(yōu)先函數(shù)為：（4）對(duì)輸入串（a,a）#的算符優(yōu)先分析過(guò)程為Success!對(duì)輸入串（a,(a,a)）# 的算符優(yōu)先分

24、析過(guò)程為：Success!第2 題已知文法GS為：Sa|(T)TT,S|S(1) 給出(a,(a,a)和(a,a)的最右推導(dǎo)，和規(guī)范歸約過(guò)程。(2) 將(1)和題1 中的(4)進(jìn)行比較給出算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。答案：（）(a,a)的最右推導(dǎo)過(guò)程為：S => (T)=> (T,S)=> (T,a)=> (S,a)=> (a,a)=>（a,(a,a)）的最右推導(dǎo)過(guò)程為：S=> (T)=> (T,S)=> (T,(T)=> (T,(T,S)=> (T,(T,a)=> (T,(S,a)=> (T,(a,a)=>

25、 (S,(a,a)=> (a,(a,a)(a,(a,a)的規(guī)范歸約過(guò)程：(a,a)的規(guī)范歸約過(guò)程：(2)算符優(yōu)先文法在歸約過(guò)程中只考慮終結(jié)符之間的優(yōu)先關(guān)系從而確定可歸約串，而與非終結(jié)符無(wú)關(guān)，只需知道把當(dāng)前可歸約串歸約為某一個(gè)非終結(jié)符，不必知道該非終結(jié)符的名字是什么，因此去掉了單非終結(jié)符的歸約。規(guī)范歸約的可歸約串是句柄，并且必須準(zhǔn)確寫(xiě)出可歸約串歸約為哪個(gè)非終結(jié)符。第題：有文法GS：S->VV->T|ViTT->F|T+FF->)V*|(1) 給出(+(i(的規(guī)范推導(dǎo)。(2) 指出句型 F+Fi(的短語(yǔ)，句柄，素短語(yǔ)。(3) GS是否為OPG？若是，給出(1)中句子的

26、分析過(guò)程。答案：(1)S=>V=>ViT=>ViF=>Vi(=>T i(=>T+F i(=>T+( i(=>F+( i(=>(+( i(2)句型F+Fi(的語(yǔ)法樹(shù)：短語(yǔ)：F，F(xiàn)+F，(，F(xiàn)+Fi( 句柄：F 素短語(yǔ)：(3)FIRSTVT 和LASTVT算符優(yōu)先關(guān)系因?yàn)樵撐姆ㄊ荗P，同時(shí)任意兩個(gè)終結(jié)符的優(yōu)先關(guān)系唯一，所以該文法為OPG。(+(i(的分析過(guò)程第題文法GS為：SS;GGGG(T)HHa(S)TT+SS（） 構(gòu)造GS的算符優(yōu)先關(guān)系表，并判斷GS是否為算符優(yōu)先文法。（） 給出句型a(T+S);H;(S)的短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)

27、。（） 給出a;(a+a)和(a+a)的分析過(guò)程，說(shuō)明它們是否為GS的句子。（） 給出（）中輸入串的最右推導(dǎo)，分別說(shuō)明兩輸入串是否為GS的句子。（） 由（）和（）說(shuō)明了算符優(yōu)先分析的哪些缺點(diǎn)。（） 算符優(yōu)先分析過(guò)程和規(guī)范歸約過(guò)程都是最右推導(dǎo)的逆過(guò)程嗎？答案：（1）構(gòu)造文法GS的算符優(yōu)先關(guān)系矩陣：在上表中可看出終結(jié)符之間的優(yōu)先關(guān)系是唯一的，或稱(chēng)GS的算符優(yōu)先關(guān)系矩陣不含多重入口，因此，GS是一個(gè)算符優(yōu)先文法。（）（3）對(duì)輸入串(a+a)的分析過(guò)程如下：說(shuō)明是它的句子。（）試用規(guī)范推導(dǎo)：S GH（S）由此往下S 不可能推導(dǎo)出a+a，所以 (a+a)不是GS的句子。（5）結(jié)果說(shuō)明：由于算符優(yōu)先分析法

28、去掉了單非終結(jié)符之間的歸約，盡管在分析過(guò)程中，當(dāng)決定是否為句柄時(shí)采取一些檢查措施，但仍難完全避免把錯(cuò)誤的句子得到正確的歸約。（）算符優(yōu)先分析過(guò)程不是最右推導(dǎo)的逆過(guò)程。規(guī)范歸約過(guò)程是最右推導(dǎo)的逆過(guò)程。 第7 章 LR 分析第1 題已知文法AaAd|aAb|判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。答案：文法：AaAd|aAb|拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序?yàn)椋? S' A1 A aAd2 A aAb3 A 由產(chǎn)生式知：First (S' ) = ,aFirst (A ) = ,aFollow(S' ) = #Follow

29、(A ) = d,b,#G的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示：在I0 中：A .aAd 和A .aAb 為移進(jìn)項(xiàng)目，A .為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2 中：Follow(A) a= d，b，# a=所以在I0、I2 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：題目1 的SLR(1)分析表題目1 對(duì)輸入串a(chǎn)b#的分析過(guò)程分析成功，說(shuō)明輸入串a(chǎn)b 是文法的句子。第2 題若有定義二進(jìn)制數(shù)的文法如下：SL·L|LLLB|BB0|1(1) 試為該文法構(gòu)造LR 分析表，并

30、說(shuō)明屬哪類(lèi)LR 分析表。(2) 給出輸入串101.110 的分析過(guò)程。答案：文法：SL.L|LLLB|BB0|1拓廣文法為G，增加產(chǎn)生式SS若產(chǎn)生式排序?yàn)椋? S' S1 S L.L2 S L3 L LB4 L B5 B 06 B 1由產(chǎn)生式知：First (S' ) = 0,1First (S ) = 0,1First (L ) = 0,1First (B ) = 0,1Follow(S' ) = #Follow(S ) = #Follow(L ) = .,0,1,#Follow(B ) = .,0,1,#G的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示：在I2

31、 中：B .0 和 B .1 為移進(jìn)項(xiàng)目，S L.為歸約項(xiàng)目，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I2、I8 中：Follow(s) 0，1= # 0，1=所以在I2 、I8 中的移進(jìn)-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：題目2 的SLR(1)分析表題目2 對(duì)輸入串101.110#的分析過(guò)程分析成功，說(shuō)明輸入串101.110 是題目2 文法的句子。題目3考慮文法S-> A S | bA -> S A | a（1）列出這個(gè)文法的所有LR(0)項(xiàng)目（2）按（1）列出的項(xiàng)目構(gòu)造識(shí)別這個(gè)文法活前綴的NFA，把這個(gè)N

32、FA 確定化為DFA，說(shuō)明這個(gè)DFA 的所有狀態(tài)全體構(gòu)成這個(gè)文法的LR(0)規(guī)范族（3）這個(gè)文法是SLR 的嗎？若是，構(gòu)造出它的SLR 分析表（4）這個(gè)文法是LALR 或LR(1)的嗎？答：（1）令拓廣文法G為(0) S -> S(1)S-> A S(2)S-> b(3)A -> S A(4)A -> a其LR(0)項(xiàng)目：(2) 識(shí)別這個(gè)文法活前綴的NFA 如上圖所示：確定化為DFA 如下圖所示：（3）因?yàn)镮5 中：FOLLOW（A）a，bI7 中：FOLLOW（S）a，b所以，該文法不是SLR（1）文法。（4）LR(1)項(xiàng)目集族為：I0 :S->·

33、;S, #S ->·AS, #S ->·b, #S ->·SA, a / bA ->·a, a / bI1 : S -> S·,#A -> S·A, a / bA ->·a, a / bA -> ·SA, a / bS ->·AS, a / bS ->·b, a / bI2 : S ->A·S, #S ->·b, #S ->·AS, #A ->·SA, a / bA A -

34、>·a, a / bI3 : S -> b·, #I4 : A -> a·, a / bI5 : A -> SA·, a / bS -> A·S, a / bS -> ·AS, a / bS ->·b, a/ bA ->·SA, a / bA ->·a, a / bI6 : A -> S·A,a/bA ->·SA, a / bA ->·a, a / bS->·AS, a / bS ->

35、;·b, a / bI7: S -> b·, a / bI8 : S -> AS·, #A -> S·A, a / bA ->·SA, a / bA ->·a, a / bS ->·AS, a / bS ->·b, a / bI9 :S ->A·S, #S ->·AS, #S ->·b, #S ->·SA, a / bA ->·a, a / bI10 :S ->AS·, a/bA

36、 ->S·A, a/bA ->·S A, a/bA ->·a, a / bS ->·b, a/bS ->·AS, a / bI11 :S ->A·S, a/bS ->·b, a/bS ->·AS, a / bA ->·S A, a/bA ->·a, a / bI12 :S ->SA·, a/bS ->A·S, a/bS ->·b, a/bS ->·AS, a / bA -&

37、gt;·S A, a/bA ->·a, a / b因?yàn)镮5 狀態(tài)集中存在“歸約移進(jìn)”沖突，所以不是LR(1)文法，也不是LALR文法。第6 題文法G=(U,T,S,a,b,c,d,e,P,S)其中P 為:SUTa|TbTS|Sc|dUUS|e(1) 判斷G 是LR(0)，SLR(1)，LALR(1)還是LR(1)，說(shuō)明理由。(2) 構(gòu)造相應(yīng)的分析表。答案：文法：SUTa|TbTS|Sc|dUUS|e拓廣文法為G'，增加產(chǎn)生式S'S若產(chǎn)生式排序?yàn)椋? S' S1 S UTa2 S Tb3 T S4 T Sc5 T d6 U US7 U e由產(chǎn)生式

38、知：First (S' ) = d,eFirst (S ) = d,eFirst (U ) = eFirst (T ) = d,eFollow(S' ) = #Follow(S ) = a,b,c,d,e,#Follow(U ) = d,eFollow(T ) = a,bG的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA 如下圖所示：在I1 中：S' S.為接受項(xiàng)目，T S. 為歸約項(xiàng)目，T S.c 為移進(jìn)項(xiàng)目，存在接受-歸約和移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I1 中：Follow(S') Follow(T)= # a ，b=Follow(T) c= a ，b c=在I8 中：Follow(U) Follow(T) c=d,e a ，b c=所以在I1 中的接受-歸約和移進(jìn)-歸約沖突與I8 中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow 集解決，所以G 是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：第8 題證明文法：SA$ABaBb|DbDaBD是LR(1)但不是SLR(1)。(其中'$'相當(dāng)于'#')答案：文法：ABaBb|DbDaBD拓廣文法為G，增加產(chǎn)生式SA若產(chǎn)生式排序?yàn)椋? S'A1 A BaBb2 A DbDa3 B 4 D 由產(chǎn)生式知：First (S' ) = a,b