【正文】 用自然語(yǔ)言描述輸入串的特征(i) 以任意個(gè)(包括0)b開(kāi)頭，中間有任意個(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開(kāi)頭,中間跟aa最后由一個(gè)a,b所組成的任意串結(jié)尾或者以任意個(gè)（包括0）b開(kāi)頭，中間跟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)生。最右推導(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+↑：充分性：當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語(yǔ)法樹(shù)。即設(shè)：α=aω；β=Aω’且 α=*β。αk+1可推導(dǎo)出b的一個(gè)后綴=b(不妨稱為b k+1)。（5）任何不是以0打頭的所有奇整數(shù)所組成的集合 5. 略 第二章 習(xí)題解答case char const 編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)言程序語(yǔ)句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。1.（1）答：26*26=676解：對(duì)應(yīng)文法為G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)解：本文法構(gòu)成的語(yǔ)言集為：L(G)={(10)nabma0n|n, m≥0}。解：本文法構(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。（5）S→aSSS→a由歸納假設(shè)，對(duì)于b39。由題意可知：α=aωT …T Aω’=β，由于文法是CFG，終結(jié)符a不可能被替換空串或非終結(jié)符，因此假設(shè)有誤。必要性：有唯一的語(yǔ)法樹(shù)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。11將右線性文法化為左線性文法的算法：o （1）對(duì)于G中每一個(gè)形如A→aB的產(chǎn)生式且A是開(kāi)始符，將其變?yōu)锽→a,否則若A不是開(kāi)始符，B→Aa。 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*bS=(ab*ab|b)ca+ab*ba +ab*=(ab*ab|b)ca| ab*ba| ab*20TWOreturn TW。char tmp[30]。if (c==HUNDRE)i+=100。case TWENT: i+=20。 由’和’括住的，中間由兩個(gè)’’或者非’和\n組成的任意次的字符串。yytext[i]。}30 從略。Function P:boolean。Function X:boolean。X:=false。End。Function A:boolean。BeignSave。Function C:boolean。BeginSave。Ep:=true。得證。 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)略 提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡(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）。反之，若xjxj+1...xi是句柄，由簡(jiǎn)單優(yōu)先關(guān)系的定義，必滿足上述條件。n=1時(shí)，STa,即S→a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。 文法為：E→E↑A | AA→A*T | A/T | TT→T+V | TV | VV→i | (E) 證：（1）對(duì)于a=…aU…是句型，必有ST*a(=…aU…) T+…ab….即在歸約過(guò)程中,b先于a被歸約,從而,a(2)的情況類似可以證明。 （2）、（3）類似可證。 解：用Floyd方法對(duì)已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為： zbMLa()f1567747g1654667aSbS→aScS→cAS→I4S→ccI7B→cccBB→aSSSS→cScaI4I2I3I4S→aSaSSbS→aSAaI1I2I3I1S’ →SSS→RS→aS(aI8I2I3I7R→) SS→SabS→, S→SSABS→r5I5S→aSaAB→SS→bSaS→aaI8I7S→aSbAA→cAdA→r3I11B→cBdq2q1→ACCI2q1→q2Sendq5→S。R3I11q4→q4。q5q5SI14I9I14q5→s。beginq2q3endq1beginI1I2I1q1’ →q1q3→I7I8I5q3→q4q4 解：識(shí)別活前綴的DFA及LR(0)分析表： 狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →aSAabcI0I6I5I4I3I1S’ →ScdA→ScA→I8A→SAScA→cAdS→I13S→AAdAA→A→I7B→aBA→Ab,a,bBabI6I5I4I6B→aBE→EE+T+/)E→E+T+/)E→a+/)(TaI8I13I12I12T→aT/+T→)/+/I4/I12T→a)+/)/E→EE→EE,+,*E→+E,+,*E→E事實(shí)上，從文法本身可以看出它是二義性的，因此不可能是LR（1）文法。E*E,+,*E→*E,+,*+*I3I4I2E→i+/)/LR(1)ACTIONGOTO+()aET0S5S4161S2ACC2S5S433R1R14R4R45S8S12796R2R27S11S108S8S121499R2R210R3R311S8S121312R4R413R1R114S11S1515R3R3可以看出，表中無(wú)沖突項(xiàng)，所以是LR(1)文法；LALR（1）分析表：LR(1)ACTIONGOTO+()aET0S5/S8S4/S1216/91S2/S11ACC2/11S5/S8S4/S123/133/13R1R1R14/12R4R4R45/8S5/S8S4/S127/146/96/9R2R2R210/15R3R3R37/14S2/S11S10/S15E)/+/）E→a/+ETaI1I6/I9I4/I12I1E’ →E)/+I14T→(E(E)+/)T→(E)+/)T→T/+T→（2）LR(1)分析法：狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0E’ →aB,a,bB→ 解： （1）求LR(1)項(xiàng)目集和狀態(tài)轉(zhuǎn)換圖：狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I0S’ →aB,a,bB→B→ACTIONGOTOabcdSA0s5s4s3161s2acc2r5r5r5r5r53s5s4s3s7894r3r3r3r3r35r7r7r7r7r76s5s4s37r6r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212r4r4r4r4r413r1r1r1r1r114r2r2r2r2r2SLR(1)分析法：FOLLOW(S)={c,b} FOLLOW(A)={a,b,c,d}ACTIONGOTOabcdSA0s5s4s3161s2acc2r5r5r5r53s5s4s3s7894r3r35r7r7r7r76s5s4s37r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212R4r4r4r413r1r1