蔣立源《編譯原理》西北工業(yè)大學(xué)出版社第3版課后答案.docx

《蔣立源《編譯原理》西北工業(yè)大學(xué)出版社第3版課后答案.docx》由會(huì)員分享，可在線閱讀，更多相關(guān)《蔣立源《編譯原理》西北工業(yè)大學(xué)出版社第3版課后答案.docx（98頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

《編譯原理》課后習(xí)題答案 第一章 1. 解：源程序是指以某種程序設(shè)計(jì)語(yǔ)言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序。翻譯程序是將某種語(yǔ)言翻譯成另一種語(yǔ)言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)言程序語(yǔ)句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序，將其保存到指定的空間中，在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。 2. 解：一般說(shuō)來(lái)，編譯程序主要由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。 3. 解：C語(yǔ)言的關(guān)鍵字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述關(guān)鍵字在C語(yǔ)言中均為保留字。 4. 解：C語(yǔ)言中括號(hào)有三種：{}，[]，（）。其中，{}用于語(yǔ)句括號(hào)；[]用于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達(dá)式運(yùn)算（改變運(yùn)算順序）。C語(yǔ)言中無(wú)END關(guān)鍵字。逗號(hào)在C語(yǔ)言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：(a,b,c,d)的值為d）。 5. 略 第二章 1.（1）答：26*26=676 （2）答：26*10=260 （3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658個(gè) 2.構(gòu)造產(chǎn)生下列語(yǔ)言的文法 （1）{anbn|n≥0} 解：對(duì)應(yīng)文法為G(S) = ({S},{a,b},{ S→ε| aSb },S) （2）{anbmcp|n,m,p≥0} 解：對(duì)應(yīng)文法為G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S) （3）{an # bn|n≥0}∪{cn # dn|n≥0} 解：對(duì)應(yīng)文法為G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y→cYd|# },S) （4）{w#wr# | w?{0,1}*,wr是w的逆序排列} 解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S) （5）任何不是以0打頭的所有奇整數(shù)所組成的集合 解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, J1|3|5|7|9},S) （6）所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合 解：對(duì)應(yīng)文法為 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B 3.描述語(yǔ)言特點(diǎn) （1）S→10S0S→aAA→bAA→a 解：本文法構(gòu)成的語(yǔ)言集為：L(G)={(10)nabma0n|n, m≥0}。 （2）S→SS S→1A0A→1A0A→ε 解：L(G)={1n10n11n20n2 … 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm不全為零}該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，0、1個(gè)數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同連續(xù)的0。 （3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε 解：本文法構(gòu)成的語(yǔ)言集為：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特點(diǎn)是具有1p1n0n 或1n0n0q形式，進(jìn)一步，可知其具有形式1n0mn,m≥0,且n+m>0。 （4）S→bAdcA→AGSG→εA→a 解：可知，S=>…=>baSndc n≥0 該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，是以ba開頭dc結(jié)尾的串,且ba、dc個(gè)數(shù)相同。 （5）S→aSSS→a 解：L(G)={a(2n-1)|n≥1}可知：奇數(shù)個(gè)a 4.解：此文法產(chǎn)生的語(yǔ)言是：以終結(jié)符a1 、a2 …an 為運(yùn)算對(duì)象，以∧、∨、~為運(yùn)算符，以[、]為分隔符的布爾表達(dá)式串 5. 5.1解：由于此文法包含以下規(guī)則：AA→e，所以此文法是0型文法。 5.2證明：略 6.解： （1）最左推導(dǎo)： <程序>T<分程序>T<標(biāo)號(hào)>：<分程序>TL：<分程序> TL：<標(biāo)號(hào)>：<分程序> T L：L：<分程序> T L：L：<無(wú)標(biāo)號(hào)分程序> T L：L：<分程序首部>；<復(fù)合尾部> T L：L：<分程序首部>；<說(shuō)明>；<復(fù)合尾部> T L：L：begin<說(shuō)明>；<說(shuō)明>；<復(fù)合尾部> T L：L：begin d；<說(shuō)明>；<復(fù)合尾部> T L：L：begin d；d；<復(fù)合尾部> T L：L：begin d；d；<語(yǔ)句>；<復(fù)合尾部> T L：L：begin d；d；s；<復(fù)合尾部. T L：L：begin d；d；s；<語(yǔ)句> end T L：L：begin d；d；s；s end 最右推導(dǎo)： <程序>T<分程序>T<標(biāo)號(hào)>：<分程序> T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序> T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<無(wú)標(biāo)號(hào)分程序> T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<復(fù)合尾部> T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語(yǔ)句>；<復(fù)合尾部> T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語(yǔ)句>；<語(yǔ)句>；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語(yǔ)句>；s；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；s；s；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；說(shuō)明；s；s；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；d；s；s；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：begin 說(shuō)明；d；s；s；end T<標(biāo)號(hào)>：<標(biāo)號(hào)>：begin d；d；s；s；end T<標(biāo)號(hào)>： L：begin d；d；s；s；end TL：L：begin d；d；s；s；end （2）句子L：L：begin d；d；s；s end的相應(yīng)語(yǔ)法樹是： 7.解： aacb是文法G[S]中的句子，相應(yīng)語(yǔ)法樹是： 最右推導(dǎo)：S=>aAcB=>aAcb=>aacb 最左推導(dǎo)：S=>aAcB=>aacB=>aacb （2）aabacbadcd不是文法G[S]中的句子 因?yàn)槲姆ㄖ械木渥硬豢赡芤苑墙K結(jié)符d結(jié)尾 （3）aacbccb不是文法G[S]中的句子 可知，aacbccb僅是文法G[S]的一個(gè)句型的一部分，而不是一個(gè)句子。 （4）aacabcbcccaacdca不是文法G[S]中的句子 因?yàn)榻K結(jié)符d后必然要跟終結(jié)符a，所以不可能出現(xiàn)…dc…這樣的句子。 （5）aacabcbcccaacbca不是文法G[S]中的句子 由（1）可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能跟非終結(jié)符S，所以不可能出現(xiàn)…caacb…這樣的句子。 8.證明：用歸納法于n，n=1時(shí)，結(jié)論顯然成立。設(shè)n=k時(shí)，對(duì)于α1α2...αkT*b,存在βi：i=1,2,..,k，αiT*bi成立，現(xiàn)在設(shè) α1α2... αkαk+1T*b，因文法是前后文無(wú)關(guān)的，所以α1α2... αk可推導(dǎo)出b的一個(gè)前綴b，αk+1可推導(dǎo)出b的一個(gè)后綴=b"(不妨稱為b k+1)。由歸納假設(shè)，對(duì)于b，存在βi ：i=1,2,..,k，b=β1β2...βk,使得 αiT*bi成立，另外,我們有αk+1T*b"(=b k+1）。即n=k+1時(shí)亦成立。證畢。 9.證明：(1)用反證法。假設(shè)α首符號(hào)為終結(jié)符時(shí)，β的首符號(hào)為非終結(jié)符。即設(shè)：α=aω；β=Aω’且 α=>*β。 由題意可知：α=aωT …T Aω’=β，由于文法是CFG，終結(jié)符a不可能被替換空串或非終結(jié)符，因此假設(shè)有誤。得證； （2）同（1），假設(shè)：β的首符號(hào)為非終結(jié)符時(shí)，α首符號(hào)為終結(jié)符。即設(shè)：α=aω；β=Aω’且α=aωT …T Aω’=β，與（1）同理，得證。 10.證明：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹（或最右推導(dǎo)）： STABTAbcTabc STDCTDcTabc 所以，本文法具有二義性。 11.解： (1) STABTAaSbTAacbTbAacbTbbAacbTbbaacb 上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對(duì)應(yīng)的語(yǔ)法樹為： 全部的短語(yǔ)： 第一個(gè)a (a1)是句子bbaacb相對(duì)于非終結(jié)符A (A1) (產(chǎn)生式A?a）的短語(yǔ)（直接短語(yǔ)）； b1a1是句子bbaacb相對(duì)于非終結(jié)符A2的短語(yǔ)； b2b1a1是句子bbaacb相對(duì)于非終結(jié)符A3的短語(yǔ)； c是句子bbaacb相對(duì)于非終結(jié)符S1（產(chǎn)生式S?c）的短語(yǔ)（直接短語(yǔ)）； a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語(yǔ)； b2b1a1a2cb3是句子bbaacb相對(duì)于非終結(jié)符S2的短語(yǔ)； 注：符號(hào)的下標(biāo)是為了描述方便加上去的。 （2）句子（（（b）a（a））（b））的最右推導(dǎo)： ST（AS）T（A（b））T（（SaA）（b））T（（Sa（a））（b）） T（（（b）a（a））（b）） 相應(yīng)的語(yǔ)法樹是： （3）解：iii*i+↑對(duì)應(yīng)的語(yǔ)法樹略。 最右推導(dǎo)：E TT=>F=>FP↑T FE↑T FET+↑T FEF+↑T FEP+↑T FEi+↑ TFTi+↑T FTF*i+↑TFTP*i+↑T FTi*i+↑TFFi*i+↑T FPi*i+↑ TFii*i+↑T Pii*i+↑Tiii*i+↑ 12.證明： 充分性：當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語(yǔ)法樹。 必要性：有唯一的語(yǔ)法樹T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式 13.化簡(jiǎn)下列各個(gè)文法 （1）解：S→bCACdA→cSA| cCCC→cS | c （2）解：S→aAB | fA | gA→e | dDAD→eAB→f （3）解：S→ac 14.消除下列文法中的ε產(chǎn)生式 （1）解：S→aAS | aS | bA→cS （2）解：S→aAA | aA | aA→bAc| bc | dAe| de 15.消除下列文法中的無(wú)用產(chǎn)生式和單產(chǎn)生式 （1）消除后的產(chǎn)生式如下： S→aB | BC B→DB | b C→b D→b | DB （2）消除后的產(chǎn)生式如下： S→SA | SB |（）|（S）|[] |[S] A→() |（S）|[]|[S] B[] |[S] （3）消除后的產(chǎn)生式如下： E→E+T | T*F | (E) | P↑F | i T→T*F | (E) | P↑F | i F→P↑F | (E) | i P→(E) | i 第三章 1．從略 2． 3 假設(shè)W:表示載狐貍過河，G:表示載山羊過河，C:表示載白菜過河 用到的狀態(tài)1：狐貍和山羊在左岸2：狐貍和白菜載左岸3:羊和白菜在左岸 4:狐貍和山羊在右岸5:狐貍和白菜在右岸 6:山羊和白菜在右岸F:全在右岸 4 證明：只須證明文法G:A→αB 或A→α （A,B∈VN, α∈VT+） 等價(jià)于G1:A→aB 或A→a (a∈VT+) G1的產(chǎn)生式中 A→aB, 則B也有B→bC ,C→cD …. 所以有 A →abc…B’,a,b,c…∈VT,B’∈VN 所以與G等價(jià)。 2）G的產(chǎn)生式A→αB，α∈VT+，因?yàn)棣潦亲址?，所以肯定存在著一個(gè)終結(jié)符a， 使A→aB 可見兩者等價(jià)，所以由此文法產(chǎn)生的語(yǔ)言是正規(guī)語(yǔ)言。 5 6 根據(jù)文法知其產(chǎn)生的語(yǔ)言是 L={ambnci| m,n,i≧1} 可以構(gòu)造如下的文法VN={S,A,B,C}, VT={a,b,c} P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其狀態(tài)轉(zhuǎn)換圖如下: 7 (1) 其對(duì)應(yīng)的右線性文法是: A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B (2) 最短輸入串011 (3) 任意接受的四個(gè)串 011,0110,0011,000011 (4) 任意以1打頭的串. 8 從略。 9 （2）相應(yīng)的3型文法 (i) S →aAS→bS A→aA A→bB B→a|aB B→b|bB (ii) S→aA|a S→bB B→aB | bB A→aB A→b|bA (iii) S→aA S→bB A→bA A→aC B→aB B→bC C→a|aC C→b|bC (iv) S→bS S→aA A→aC A→bB B→aB B→bC C→a|aC C→b|bC （3）用自然語(yǔ)言描述輸入串的特征 (i) 以任意個(gè)(包括0)b開頭，中間有任意個(gè)（大于1）a，跟一個(gè)b,還可以有一個(gè)由a,b組成的任意字符串 (ii) 以a打頭，后跟任意個(gè)（包括0）b (iii)以a打頭，中間有任意個(gè)（包括0）b,再跟a,最后由一個(gè)a,b所組成的任意串結(jié)尾或者 以b打頭，中間有任意個(gè)（包括0）a,再跟b,最后由一個(gè)a,b所組成的任意串結(jié)尾 (iv)以任意個(gè)（包括0）b開頭,中間跟aa最后由一個(gè)a,b所組成的任意串結(jié)尾或者 以任意個(gè)（包括0）b開頭，中間跟ab后再接任意（包括0）a再接b，最后由一個(gè)a,b所組成的任意串結(jié)尾 10 （1）G1的狀態(tài)轉(zhuǎn)換圖： G2的狀態(tài)轉(zhuǎn)換圖： (2) G1等價(jià)的左線性文法： S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→a G2等價(jià)的右線性文法： S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a （3）對(duì)G1文法,abb的推導(dǎo)序列是： S=>aA=>abB=>abb 對(duì)G1’文法，abb的推導(dǎo)序列是： S=>Bb=>Abb=>abb 對(duì)G2文法，aabca的推導(dǎo)序列是： S=>Aa=>Cca=>Babca=>aabca 對(duì)G2’文法，aabca的推導(dǎo)序列是： S=>aB=>aabC=>aabcA=>aabca （4）對(duì)串a(chǎn)cbd來(lái)說(shuō)，G1,G1’文法都不能產(chǎn)生。 11將右線性文法化為左線性文法的算法： o （1）對(duì)于G中每一個(gè)形如A→aB的產(chǎn)生式且A是開始符，將其變?yōu)锽→a,否則若A不是開始符，B→Aa; o （2）對(duì)于G中每一個(gè)形如A→a的產(chǎn)生式,將其變?yōu)镾→Aa 12 (1) 狀態(tài)矩陣是： 記[S]=q0 [B]=q1 [A B]=q2 [S A]=q3 ,最小化和確定化后如圖 （2）記 [S]=q0, [A]=q1,[B S]=q2 最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下 13 （1）將具有ε動(dòng)作的NFA確定化后，其狀態(tài)轉(zhuǎn)換圖如圖： 記 { S0,S1,S3}=q0 {S1}=q1 {S2 S3}=q2 {S3}=q3 (2) 記{S}=q0 {Z}=q1 {U R}=q2 {S X}=q3 {Y U R}=q4 {X S U}=q5 {Y U R Z}=q6 {Z S}=q7 14（1）從略 (2)化簡(jiǎn)后S0和S1作為一個(gè)狀態(tài)，S5和S6作為一個(gè)狀態(tài)。 狀態(tài)轉(zhuǎn)換圖如圖 15從略。 16從略。 (1) r*表示的正規(guī)式集是{ε,r,rr,rrr,…} (ε|r)*表示的正規(guī)式集是{ε, εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…} ε|rr*表示的正規(guī)式集是{ε,r,rr,rrr,…} (r*)*=r*={ε,r,rr,rrr,…} 所以四者是等價(jià)的。 (2)（rs）*r表示的正規(guī)式集是{ε,rs,rsrs,rsrsrs,…}r ={r,rsr,rsrsr,rsrsrsr,…} r(sr)* 表示的正規(guī)式集是r{ε,sr,srsr,srsrsr,…} ={ r,rsr,rsrsr,rsrsrsr,…} 所以兩者等價(jià)。 18 寫成方程組 S=aT+aS(1) B=cB+c(2) T=bT+bB(3) 所以B=c*cT=b*bc*c S=a*ab*bc*c G1: S=aA+B(1) B=cC+b(2) A=abS+bB (3) C=D(4) D=bB+d(5) 把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得 A=abS+b(cb)*(cd|b)把它打入（1）得 S=a(abS+b(cb)*(cd|b))+ (cb)*(cd|b) =aabS+ab(cb)*(cd|b) + (cb)*(cd|b) =(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b)) G2: S=Aa+B (1) A=Cc+Bb (2) B=Bb+a(3) C=D+Bab(4) D=d(5) 可得 D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*b S=(ab*ab|b)ca+ab*ba +ab* =(ab*ab|b)ca| ab*ba| ab* 20 識(shí)別此語(yǔ)言的正規(guī)式是S=’LABEL’d(d|,d)*; 從略。 21 從略。 22 構(gòu)造NFA 其余從略。 23 下面舉一個(gè)能夠識(shí)別1,2,3,10,20,100的例子，讀者可以推而廣之。 %{ #include #include #include #define ON1 #define TW 2 #define THRE 3 #define TE 10 #define TWENT 20 #define HUNDRE 100 #define WHITE9999 %} upper[A-Z] %% ONEreturn ON; TWOreturn TW; THREEreturn THRE; TENreturn TE; TWENTYreturn TWENT; HUNDREDreturn HUNDRE; " "+|\treturn WHITE; \nreturn0; %% main(int argc,char *argv[]) { int c,i=0; char tmp[30]; if (argc==2) { if ((yyin=fopen(argv[1],"r"))==NULL) { printf("cant open %s\n",argv[1]);exit(0); } } while ((c=yylex())!=0) { switch(c) { case ON: c=yylex(); if (c==0) goto {i+=1;label;} c=yylex(); if (c==HUNDRE) i+=100; else i+=1; break; case TW:c=yylex(); c=yylex(); if (c==HUNDRE) i+=200; else i+=2; break; case TWENT: i+=20; break; case TE:i+=10; break; default:break; } }/*while*/ label: printf("%d\n",i); return; } 24 （1）Dn表示的正規(guī)集是長(zhǎng)度為2n任意a和b組成的字符串。 此正規(guī)式的長(zhǎng)度是2n 用來(lái)識(shí)別Dn的DFA至多需要2n＋1個(gè)狀態(tài)。 25 從略。 26（1）由{}括住的,中間由任意個(gè)非{組成的字符串, 如{},{}},{a},{defg}等等。 （2）匹配一行僅由一個(gè)大寫字母和一個(gè)數(shù)字組成的串，如A1,F8,Z2等。 （3）識(shí)別\r\n和除數(shù)字字符外的任何字符。 由’和’括住的，中間由兩個(gè)’’或者非’和\n組成的任意次的字符串。如’’’’, ‘a(chǎn)’,’bb’,’def’，’’’’’’等等 27O[Xx][0-9]*[a-fA-F]*|[0-9]+|(\’([a-zA-Z]|\\[Xx][0-7][0-7a-fA-F]|\\0[01][0-7][0-7]|\\[a-z])\’) 28^[a-zA-Z_]+[0-9]*[a-zA-Z_]* 29 參考程序如下： %{ #include #include #include #define UPPER2 #define WHITE3 %} upper[A-Z] %% {upper}+returnUPPER; \t|" "+returnWHITE; %% main(int argc,char *argv[]) { int c,i; if (argc==2) { if ((yyin=fopen(argv[1],"r"))==NULL) { printf("cant open %s\n",argv[1]);exit(0); } } while ((c=yylex())!=EOF) { if (c==2) { for (i=0;yytext[i];i++) printf("%c",tolower(yytext[i])); yytext[0]=\000; } if (c==3) printf(" "); else printf("%s",yytext); } return; } yywrap() { return ; } 30 從略。 第四章 1.解： (1)S→(S)Z21|()Z21|[S]Z31|[]Z31 A→(S)Z22|()Z22|[S]Z32|[]Z32 B→(S)Z23|()Z23|[S]Z33|[]Z33 Z11→ε|AZ11|BZ21 Z12→AZ12|BZ22Z13→AZ13|BZ23 Z21→Z11Z22→ε|Z12 Z23→Z13Z31→Z21 Z32→Z22Z33→ε|Z23 (2)S→bZ11|aZ21A→bZ12|aZ22 Z11→ε| AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22 (3)S→(T)Z11 | aZ11 | Z11S→(T)Z12 | aZ12 | Z12 Z11→ε| Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ22 2.解： SAbB1,1.1(表示第1步，用產(chǎn)生式1.1推導(dǎo),以下同) CAbbB2,2.1 edAbbB3,4.1 edCAbbB4,2.1 ededAbbbB5,4.1 edaAbbbB5，4.2 (不符合，改寫第5步，用4.2) edBfbbB4,2.2 edCSdfbbB5,3.1 ededSdfbbB6,4.1 edaSdfbbB6,4.2 eddfbbB5,3.2 eddfbbCSd6,3.1 eddfbbedSd7,4.1 eddfbbaSd7,4.2 eddfbbd6,3.2 3.解：以下Save表示save token_pointer value, Restore表示restore token_pointer value。 (1)文法沒有左遞歸。 Function P:boolean; Begin Save; P:=true; If next_token=”begin” then If next_token=’d’ then If next_token=’;’ then If X then If next_token=”end” then return; Restore; P:=false; End; Function X:boolean; Begin Save; X:=true; If next_token=’d’ then If next_token=’;’ then If X then return; Restore; If next_token=’s’ then If Y then return; Restore; X:=false; End; Function Y:boolean; Begin Save; Y=true; If next_token=’;’ then If next_token=’s’ then If Y then return; Restore; End; (2)消去文法左遞歸，并記為： P→begin S endS→A|CA→V:=EC→ if E then S E→VE’E’ →+VE’|εV→I Function P:boolean; Begin Save; P:=true; If next_token=”begin” then If S then If next_token=”end” then return;; Restore; P:=false; End; Function A:boolean; Beign Save; A:=true; If V then If next_token=”:=” then If E then return; Restore; A:=flase; End; Function S:boolean; Beign Save; S:=true; If A then return; Restore; If C then return; Restore; S:=false; End; Function C:boolean; Begin Save; C:=true; If next_token=”if” then If E then If next_token=”then” then If S then return; Restore; C:=false; End; Function E:boolean; Begin Save; E:=true; If V then If Ep then return; Restore; E:=false; End; Function Ep:boolean; Being Save; Ep:=true; If next_token=’+’ then If V then If E’ then return; Return; End; 4.解： 5.證：因?yàn)槭亲筮f歸文法，所以必存在左遞歸的非終結(jié)符A，及形如A→α|β的產(chǎn)生式,且αT* Ad. 則first(Ad) ∩first(β)≠φ,從而 first(α) ∩first(β)≠φ，即文法不滿足LL（1）文法條件。得證。 6.證：LL（1）文法的分析句子過程的每一步，永遠(yuǎn)只有唯一的分析動(dòng)作可進(jìn)行。現(xiàn)在，假設(shè)LL(1)文法G是二義性文法，則存在句子α，它有兩個(gè)不同的語(yǔ)法樹。即存在著句子α有兩個(gè)不同的最左推導(dǎo)。從而可知，用LL（1）方法進(jìn)行句子α的分析過程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進(jìn)行語(yǔ)法分析，即LL（1）分析動(dòng)作存在不確定性。與LL（1）性質(zhì)矛盾。所以，G不是LL(1)文法。 7.解： (1)D產(chǎn)生式兩個(gè)候選式fD和f的first集交集不為空，所以不是LL(1)的。 (2)此文法具有左遞歸性，據(jù)第5題結(jié)論，不是LL(1)的。 8.解： (1)消除左遞歸性,得： S→bZ11|aZ21A→bZ12|aZ22Z11→bZ11|εZ12→bZ12 Z21→bZ11|aZ21Z22→bZ12|aZ22|ε 消除無(wú)用產(chǎn)生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21 此文法已滿足LL(1)文法的三個(gè)條件， 所以　G’[S]: S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21 (2) G’文法的各非終結(jié)符的FIRST 集和FOLLOW集： 產(chǎn)生式 FIRST 集 FOLLOW集 S→bZ11 →aZ21  {a} {#} Z11→bZ11 →ε  {ε} {#} Z21→bZ11 →aZ21  {a} {#} LL(1)分析表為： a b # S aZ21 bZ11 Z11 bZ11 ε Z21 aZ21 bZ11 9.解： (1) 產(chǎn)生式 first集 follow集 S→SaB →bB   {#,a,c} A→S →a {a} {c} B→Ac {a,b} {#,a,c} (2)將S→SaB | bB改寫為S→bBS’,S’ →aBS’|ω,可驗(yàn)證，新文法是LL(1)的。 10.解： 1）為方便書寫，記：<布爾表達(dá)式>為A，<布爾因子>為B，<布爾二次量>為C，<布爾初等量>為D，原文法可以簡(jiǎn)化為： A→A∨B | B B→B∧C | CC→┐D | DD→(A) | true | false, 顯然，文法含有左遞歸，消去后等價(jià)LL(1)文法為： A→BA’ A’ →∨BA’|ω B→CB’, B’ →∧CB’|ωC→┐D|DD→(A)| true|false (2)略 證：若LL（1）文法G有形如B→aAAb的產(chǎn)生式，且AT+ε及AT*ag,根據(jù)FIRST集FOLLOW集的構(gòu)造算法可知，F(xiàn)IRST(A)中一切非ε加到FOLLOW(A)中，則a∈FOLLOW(A)；又因?yàn)閍∈FIRST(ag),所以兩集合相交非空，因此，G不是LL(1)文法；與前提矛盾，假設(shè)不成立，得證。 12。解： (1) S A ( a ) b S = = A = < = < ( = = < < < a > = < > < > > ) > > > > > b > > 不是簡(jiǎn)單優(yōu)先文法。 (2) S R T ( ) ∧ a , S > = R = T > ( < = < < < < ) > > ∧ > > a > > , < = < < < 是簡(jiǎn)單優(yōu)先文法。 (3) S R ( a , ) S = < < R > > ( = < < a > > , = < < ) > > 是簡(jiǎn)單優(yōu)先文法。 o 首先消去無(wú)用產(chǎn)生式Z→E, Z→E+T S Z T # i ( ) S Z = = T > > # = < < < I > > ( = < < < ) > > 化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法； 13.解： S A / A S > > A = < = < = / > > a > > A和/之間同時(shí)有關(guān)系=和<,所以不是簡(jiǎn)單優(yōu)先文法； 提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡(jiǎn)單），使得對(duì)文法的輸入比較簡(jiǎn)單的同時(shí)(需要把輸入轉(zhuǎn)化為計(jì)算機(jī)語(yǔ)言表示，這種轉(zhuǎn)化應(yīng)該盡量簡(jiǎn)單)，能夠比較簡(jiǎn)單地構(gòu)造3個(gè)基本關(guān)系矩陣（=，LEAD和LAST）。 證明：設(shè)xjxj+1...xi是滿足條件xj-1xi+1的最左子串。由=關(guān)系的定義，可知xjxj+1...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj-1,L=<變量表>, V= <變量>,T=<類型>，a=VAR,則消去V，并采用分層法改寫文法，得到：D→aW:T;W→LL→L,i|iT→r|n|b|c 其全部簡(jiǎn)單優(yōu)先關(guān)系是： D W T L a : ; , i r|n|b|c D W = T = L > = a = < < : = < ; , > > > = i r|n|b|c > 是簡(jiǎn)單優(yōu)先文法。 證：設(shè)STna,我們對(duì)n用歸納法，證明a不含兩個(gè)非終結(jié)符相鄰情況。n=1時(shí)，STa,即S→a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。設(shè)n=k時(shí)，上述結(jié)論成立，且設(shè)STkdAb，由歸納假設(shè)，A兩側(cè)必為終結(jié)符。我們?cè)龠M(jìn)行一步推導(dǎo)，得STkdAbTdub, 其中，A→u是文法中的產(chǎn)生式，由定義，u中不含兩個(gè)非終結(jié)符相鄰情況，從而dub兩個(gè)非終結(jié)符相鄰情況。得證。 證：由于G不是算符文法，G中至少有一個(gè)產(chǎn)生式，其右部含有兩個(gè)非終結(jié)符相鄰的情況。不失一般性，設(shè)其形為U→xABy,x,y∈V*,由于文法不含無(wú)用產(chǎn)生式，則必存在含有U的句型dUb，即存在推導(dǎo)ST*dUbTdxAByb.得證。 文法為：E→E↑A | AA→A*T | A/T | TT→T+V | T-V | VV→i | (E) 20.解： （1）構(gòu)造算符優(yōu)先矩陣： - * （ ） i # - > < > < < > < > * > < > < > < ( < < < = < ) > > > > I > > > > # < < < < （2）在（-，-）、（-，*）和（*，-）處有多重定義元素，不是算符優(yōu)先文法； （3）改寫方法： 將E→E-T中的減號(hào)與F→-P中的賦值運(yùn)算符強(qiáng)制規(guī)定優(yōu)先關(guān)系； 或者將F-P中的賦值運(yùn)算符改為別的符號(hào)來(lái)表示； (1)證明：由設(shè)句型a =…Ua…中含a的短語(yǔ)不含U，即存在A，A=>*ay,則a可歸約為a =…Ua…*…UA…=b，b是G的一個(gè)句型，這與G是算符文法矛盾，所以，a中含有a的短語(yǔ)必含U。 （2）的證明與（1）類似，略。 證：（1）對(duì)于a=…aU…是句型，必有ST*a(=…aU…) T+…ab….即在歸約過程中,b先于a被歸約,從而,aby+1，與bx-1=bx及 by=by+1矛盾，得證。 提示：根據(jù)27題的結(jié)論，只要證u是句型α的短語(yǔ)，根據(jù)=關(guān)系的定義容易知道u是句型α的素短語(yǔ)。 證：與28題的不同點(diǎn)只是a0,an+1可以是’#’,不影響結(jié)論。 證：設(shè)不能含有素短語(yǔ)，則只能是含有短語(yǔ)（不能含有終結(jié)符號(hào)），則該短語(yǔ)只能含有一個(gè)非終結(jié)符號(hào)，否則不符合算符文法定義，得證。 31.解： （1）算符優(yōu)先矩陣： + * ↑ （ ） i # + > < < < > < > * > > < < > < > ↑ > > < < > < > ( < < < < = < ) > > > > > I > > > > > # < < < < < （2）用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為： + * ↑ ( ) i # F 3 5 5 1 7 7 1 G 2 4 6 6 1 6 1 32.解：用Floyd方法對(duì)已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為： z b M L a ( ) f 1 5 6 7 7 4 7 g 1 6 5 4 6 6 7 33.解： （1）優(yōu)先矩陣如下： [ ] a # [ > = ] > > a < > < > < # < < < （2）用Bell方法求優(yōu)先函數(shù)的過程如下： [ ] a # f 5 7 5 1 g 5 5 6 1 （3）顯然，文法不是算符優(yōu)先文法, 所以不能線性化。 略。 35解： （1）識(shí)別全部活前綴的DFA如下：（以表格的形式來(lái)表示，很容易可以轉(zhuǎn)化為圖的形式，本章中其余的題目也是采用這種形式表示。） 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→aSb S→aSc S→ab S a I1 I2 I1 S’ →S I2 S→aSb S→aSc S→ab S→aSb S→aSc S→ab S a b I3 I2 I4 I3 S→aSb S→aSc b c I5 I6 I4 S→ab I5 S→aSb I6 S→aSc （2）識(shí)別全部活前綴的DFA如下： 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→cA S→ccB S c I1 I I1 S’ →S I2 S→cA S→ccB A→cA A→a A c a I3 I4 I5 I3 S→cA I4 S→ccB A→cA B→ccB B→b A→cA A→a B A c b a I6 I5 I7 I8 I5 I5 A→a I6 S→ccB I7 B→ccB A→cA A→cA A→a C A a I9 I10 I5 I8 B→b I9 B→ccB A→cA B→ccB B→b A→cA A→a B A c b a I11 I10 I7 I8 I5 I10 A→cA I11 B→ccB 所求的LR(0)項(xiàng)目規(guī)范族C={I0,I1,…,I11} （3） 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→aSSb S→aSSS S→c S c a I1 I2 I3 I1 S’ →S I2 S→c I3 S→aSSb S→aSSS S→aSSb S→aSSS S→c S c a I4 I2 I3 I4 S→aSSb S→aSSS S→aSSb S→aSSS S→c S c a I5 I2 I3 I5 S→aSSb S→aSSS S→aSSb S→aSSS S→c S a b c I7 I3 I6 I2 I6 S→aSSb I7 S→aSSS （4） 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→A A→Ab A→a S A a I1 I2 I3 I1 S’ →S I2 S→A S→Ab b I4 I3 A→a I4 S→Ab 36解： （1）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,b,c} ACTION GOTO a b c # S 0 S2 1 1 ACC 2 S2 S4 3 3 S5 S6 4 R3 R3 R3 5 R1 R1 R1 6 R2 R2 R2 （2）是LR(0)文法，其SLR(1)分析表如下： FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#} ACTION GOTO a b c # S A B 0 S2 1 1 ACC 2 S5 S4 3 3 R1 4 S5 S8 S7 3 6 5 R4 6 R2 7 S5 S9 10 8 R6 9 S5 S8 S7 10 11 10 R3 11 R5 （3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,a,b,c} ACTION GOTO a b c # S 0 S3 S2 1 1 ACC 2 R3 R3 R3 R3 3 S3 S2 4 4 S3 S2 5 5 S3 S6 S2 7 6 R1 R1 R1 R1 7 R2 R2 R2 R2 （4）因?yàn)镮2中含有沖突項(xiàng)目，所以不是LR(0)文法，其SLR(1)分析表如下： FOLLOW(S)={#}∩=φ(所以可以用SLR(1)規(guī)則解決沖突), FOLLOW(A)={b,#} ACTION GOTO a b # S A 0 S3 1 2 1 ACC 2 S4 R1 3 R3 R3 4 R2 R2 37解： 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→(SR S→a S ( a I1 I2 I3 I1 S’ →S I2 S→(SR S→(SR S→a S ( a I4 I2 I3 I3 S→a I4 S→(SR S→(SR S→a R→,SR R→) a ( R , ) I3 I2 I5 I6 I7 I5 S→(SR I6 R→, SR S→(SR S→a S ( a I8 I2 I3 I7 R→) I8 R→,SR R→,SR R→) ) , R I7 I6 I9 I9 R→,SR LR(0)分析表如下： ACTION GOTO a ( ) , # S R 0 S3 S2 1 1 ACC 2 S3 S2 4 3 R2 R2 R2 R2 R2 4 S3 S2 S7 S6 5 5 R1 R1 R1 R1 R1 6 S3 S2 8 7 R4 R4 R4 R4 R4 8 S7 S6 9 9 R3 R3 R3 R3 R3 可見是LR(0)文法。 38解： （1） 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→Sab S→bR S b I1 I2 I1 (沖突項(xiàng)目) S’ →S S→Sab a acc I3 I2 S→bR R→S R→a S→Sab S→bR R S a b I4 I5 I6 I2 I3 S→Sab b I7 I4 S→bR r2 I5 (沖突項(xiàng)目) R→S S→Sab a I3 I6 R→a I7 S→Sab 項(xiàng)目I1,I5同時(shí)具有移進(jìn)和歸約項(xiàng)目，對(duì)于I5={ R→S, S→Sab },follow(R)={a},follow(R) ∩{a}={a},所以SLR(1)規(guī)則不能解決沖突，從而該文法不是SLR(1)文法。 （2） 狀態(tài) 項(xiàng)目集 經(jīng)過的符號(hào) 到達(dá)的狀態(tài) I0 S’ →S S→aSAB S→BA B→b S a B b I1 I2 I3 I4 I1 S’→S I2 S→aSAB S→aSAB S→BA B→b S a B b I5 I2 I3 I4 I3 S