【正文】 結(jié)符a，所以不可能出現(xiàn)…dc…這樣的句子。解：對(duì)應(yīng)文法為 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B（6）所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合解：G(S) = ({S,W,R},{0,1,}, {S→W, W→0W0|1W1| },S)（4）{wwr | w?{0,1}*,wr是w的逆序排列}解：對(duì)應(yīng)文法為G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（2）{anbmcp|n,m,p≥0}（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658個(gè)1.（1）答：26*26=676逗號(hào)在C語(yǔ)言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：(a,b,c,d)的值為d）。其中，{}用于語(yǔ)句括號(hào)；[]用于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達(dá)式運(yùn)算（改變運(yùn)算順序）。上述關(guān)鍵字在C語(yǔ)言中均為保留字。break 2. 解：一般說(shuō)來(lái)，編譯程序主要由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。編譯程序的特點(diǎn)是先將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序，將其保存到指定的空間中，在用戶需要時(shí)再執(zhí)行之。解釋程序的特點(diǎn)是并不先將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)言程序語(yǔ)句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。翻譯程序是將某種語(yǔ)言翻譯成另一種語(yǔ)言的程序的統(tǒng)稱。目錄第一章 習(xí)題解答 1第二章 習(xí)題解答 2 2 3： 5：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹（或最右推導(dǎo)）： 7： 7 10第三章 習(xí)題解答 10第四章 習(xí)題解答 24第四章習(xí)題參考答案 2435解： 3736解： 4037解： 4238解： 4339解：識(shí)別活前綴的DFA及LR(0)分析表： 5040解：求LR(1)項(xiàng)目集和狀態(tài)轉(zhuǎn)換表： 5441解： 5542解： 59第五章 習(xí)題解答 64 解： 65第一章 習(xí)題解答1. 解：源程序是指以某種程序設(shè)計(jì)語(yǔ)言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。即先翻譯、后執(zhí)行。 3. 解：C語(yǔ)言的關(guān)鍵字有：auto 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。 4. 解：C語(yǔ)言中括號(hào)有三種：{}，[]，（）。C語(yǔ)言中無(wú)END關(guān)鍵字。 5. 略 第二章 習(xí)題解答（2）答：26*10=260（1）{anbn|n≥0}解：對(duì)應(yīng)文法為G(S) = ({S},{a,b},{ S→ε| aSb },S) （3）{an bn|n≥0}∪{ dn|n≥0}解：對(duì)應(yīng)文法為G(S) = ({S,X,Y},{a,b,c,d,}, {S→X, S→Y,X→aXb|,Y→cYd| },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, J→1|3|5|7|9},S)（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+m0。（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(2n1)|n≥1}可知：奇數(shù)個(gè)a：此文法產(chǎn)生的語(yǔ)言是：以終結(jié)符a1 、a2 …an 為運(yùn)算對(duì)象，以∧、∨、~為運(yùn)算符，以[、]為分隔符的布爾表達(dá)式串5. ：由于此文法包含以下規(guī)則：AA→e，所以此文法是0型文法。：略：（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ǔ)句 endT 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ǔ)句；endT標(biāo)號(hào)：標(biāo)號(hào)：分程序首部；語(yǔ)句；s；endT標(biāo)號(hào)：標(biāo)號(hào)：分程序首部；s；s；endT標(biāo)號(hào)：標(biāo)號(hào)：分程序首部；說(shuō)明；s；s；endT標(biāo)號(hào)：標(biāo)號(hào)：分程序首部；d；s；s；endT標(biāo)號(hào)：標(biāo)號(hào)：begin 說(shuō)明；d；s；s；endT標(biāo)號(hào)：標(biāo)號(hào)：begin d；d；s；s；endT標(biāo)號(hào)： L：begin d；d；s；s；endTL：L：begin d；d；s；s；end（2）句子L：L：begin d；d；s；s end的相應(yīng)語(yǔ)法樹是：：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è)句子。（5）aacabcbcccaacbca不是文法G[S]中的句子由（1）可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能跟非終結(jié)符S，所以不可能出現(xiàn)…caacb…這樣的句子。設(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è)前綴b39。由歸納假設(shè)，對(duì)于b39。=β1β2...βk,使得αiT*bi成立，另外,我們有αk+1T*b(=b k+1）。證畢。假設(shè)α首符號(hào)為終結(jié)符時(shí)，β的首符號(hào)為非終結(jié)符。由題意可知：α=aωT …T Aω’=β，由于文法是CFG，終結(jié)符a不可能被替換空串或非終結(jié)符，因此假設(shè)有誤。即設(shè)：α=aω；β=Aω’且α=aωT …T Aω’=β，與（1）同理，得證。：(1) STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。（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ǔ)法樹略。必要性：有唯一的語(yǔ)法樹T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式（1）解：S→bCACdA→cSA| cCCC→cS | c（2）解：S→aAB | fA | gA→e | dDAD→eAB→f（3）解：S→ac（1）解：S→aAS | aS | bA→cS（2）解：S→aAA | aA | aA→bAc| bc | dAe| de（1）消除后的產(chǎn)生式如下：S→aB | BCB→DB | bC→bD→b | DB（2）消除后的產(chǎn)生式如下：S→SA | SB |（）|（S）|[] |[S]A→() |（S）|[]|[S]B224。1．從略2．3 假設(shè)W:表示載狐貍過(guò)河，G:表示載山羊過(guò)河，C:表示載白菜過(guò)河用到的狀態(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+)2）G的產(chǎn)生式A→αB，α∈VT+，因?yàn)棣潦亲址?，所以肯定存在著一個(gè)終結(jié)符a， 使A→aB可見兩者等價(jià)，所以由此文法產(chǎn)生的語(yǔ)言是正規(guī)語(yǔ)言。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→aG2等價(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)生。 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}=q714（1）從略(2)化簡(jiǎn)后S0和S1作為一個(gè)狀態(tài)，S5和S6作為一個(gè)狀態(tài)。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à)的。18 寫成方程組S=aT+aS(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*c 識(shí)別此語(yǔ)言的正規(guī)式是S=’LABEL’d(d|,d)*。 從略。22 構(gòu)造NFA其余從略。%{include include include define ON1define TW 2define THRE 3define TE 10define TWENT 20defin