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

《編譯原理》課后習(xí)題答案第一章解：源程序是指以某種程序設(shè)計(jì)語言所編寫的程序。目標(biāo)程序是指編譯程序〔或解釋程序〕將源程序處理加工而得的另一種語言〔目標(biāo)語言〕的程序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語言程序語句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語言程序翻譯成機(jī)器語言程序，將其保存到指定的空間中，在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。解：C語言的關(guān)鍵字有：auto

break

casecharconst

continuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述關(guān)鍵字在C語言中均為保存字。解：C語言中括號(hào)有三種：{}，[]，〔〕。其中，{}用于語句括號(hào)；[]用于數(shù)組；〔〕用于函數(shù)〔定義與調(diào)用〕及表達(dá)式運(yùn)算〔改變運(yùn)算順序〕。C語言中無END關(guān)鍵字。逗號(hào)在C語言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值〔如：(a,b,c,d)的值為d〕。略第二章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)生以下語言的文法

〔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,Jà1|3|5|7|9},S)

〔6〕所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合

解：對(duì)應(yīng)文法為S→0A|1B|e，A→0S|1CB→0C|1SC→1A|0B3.描述語言特點(diǎn)

〔1〕S→10S0S→aAA→bAA→a

解：本文法構(gòu)成的語言集為：L(G)={(10)nabma0n|n,m≥0}。

〔2〕S→SSS→1A0A→1A

解：L(G)={1n10n11n20n2…1nm0nm|n1,n2,…,nm≥0；且n1,n2,…nm不全為零}該語言特點(diǎn)是：產(chǎn)生的句子中，0、1個(gè)數(shù)相同，并且假設(shè)干相接的1后必然緊接數(shù)量相同連續(xù)的0。

〔3〕S→1AS→B0A→1AA→CB→B0B→CC→1C0C

解：本文法構(gòu)成的語言集為：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=>…=>baSndcn≥0

該語言特點(diǎn)是：產(chǎn)生的句子中，是以ba開頭dc結(jié)尾的串,且ba、dc個(gè)數(shù)相同。

〔5〕S→aSSS→a

解：L(G)={a(2n-1)|n≥1}可知：奇數(shù)個(gè)a4.解：此文法產(chǎn)生的語言是：以終結(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)>：<分程序>TL：L：<分程序>TL：L：<無標(biāo)號(hào)分程序>TL：L：<分程序首部>；<復(fù)合尾部>TL：L：<分程序首部>；<說明>；<復(fù)合尾部>TL：L：begin<說明>；<說明>；<復(fù)合尾部>TL：L：begind；<說明>；<復(fù)合尾部>TL：L：begind；d；<復(fù)合尾部>TL：L：begind；d；<語句>；<復(fù)合尾部>TL：L：begind；d；s；<復(fù)合尾部.TL：L：begind；d；s；<語句>endTL：L：begind；d；s；send最右推導(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)>：<無標(biāo)號(hào)分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；<語句>；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語句>；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；說明；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；d；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：begin說明；d；s；s；endT<標(biāo)號(hào)>：<標(biāo)號(hào)>：begind；d；s；s；endT<標(biāo)號(hào)>：L：begind；d；s；s；endTL：L：begind；d；s；s；end〔2〕句子L：L：begind；d；s；send的相應(yīng)語法樹是：7.解：aacb是文法G[S]中的句子，相應(yīng)語法樹是：最右推導(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…這樣的句子?！?〕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，因文法是前后文無關(guān)的，所以α1α2...αk可推導(dǎo)出b的一個(gè)前綴b'，αk+1可推導(dǎo)出b的一個(gè)后綴=b"(不妨稱為bk+1)。由歸納假設(shè)，對(duì)于b'，存在βi：i=1,2,..,k，b'=β1β2...βk,使得αiT*bi成立，另外,我們有αk+1T*b"(=bk+1〕。即n=k+1時(shí)亦成立。證畢。9.證明：(1)用反證法。假設(shè)α首符號(hào)為終結(jié)符時(shí)，β的首符號(hào)為非終結(jié)符。即設(shè)：α=aω；β=Aω’且α=>*β。由題意可知：α=aωT…TAω’=β，由于文法是CFG，終結(jié)符a不可能被替換空串或非終結(jié)符，因此假設(shè)有誤。得證；〔2〕同〔1〕，假設(shè)：β的首符號(hào)為非終結(jié)符時(shí)，α首符號(hào)為終結(jié)符。即設(shè)：α=aω；β=Aω’且α=aωT…TAω’=β，與〔1〕同理，得證。10.證明：因?yàn)榇嬖诰渥樱篴bc，它對(duì)應(yīng)有兩個(gè)語法樹〔或最右推導(dǎo)〕：STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。11.解：(1)STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導(dǎo)中，下劃線局部為當(dāng)前句型的句柄。對(duì)應(yīng)的語法樹為：全部的短語：第一個(gè)a(a1)是句子bbaacb相對(duì)于非終結(jié)符A(A1)(產(chǎn)生式A?a〕的短語〔直接短語〕；b1a1是句子bbaacb相對(duì)于非終結(jié)符A2的短語；b2b1a1是句子bbaacb相對(duì)于非終結(jié)符A3的短語；c是句子bbaacb相對(duì)于非終結(jié)符S1〔產(chǎn)生式S?c〕的短語〔直接短語〕；a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語；b2b1a1a2cb3是句子bbaacb相對(duì)于非終結(jié)符S2注：符號(hào)的下標(biāo)是為了描述方便加上去的?！?〕句子〔〔〔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)的語法樹是：〔3〕解：iii*i+↑對(duì)應(yīng)的語法樹略。最右推導(dǎo)：ETT=>F=>FP↑TFE↑TFET+↑TFEF+↑TFEP+↑TFEi+↑TFTi+↑TFTF*i+↑TFTP*i+↑TFTi*i+↑TFFi*i+↑TFPi*i+↑TFii*i+↑TPii*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有唯一的語法樹。必要性：有唯一的語法樹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→ac14.消除以下文法中的ε產(chǎn)生式〔1〕解：S→aAS|aS|bA→cS〔2〕解：S→aAA|aA|aA→bAc|bc|dAe|de15.消除以下文法中的無用產(chǎn)生式和單產(chǎn)生式〔1〕消除后的產(chǎn)生式如下：S→aB|BCB→DB|bC→bD→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|iT→T*F|(E)|P↑F|iF→P↑F|(E)|iP→(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)生的語言是正規(guī)語言。56根據(jù)文法知其產(chǎn)生的語言是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→bSA→aAA→bBB→a|aBB→b|bB(ii)S→aA|aS→bBB→aB|bBA→aBA→b|bA(iii)S→aAS→bBA→bAA→aCB→aBB→bCC→a|aCC→b|bC(iv)S→bSS→aAA→aCA→bBB→aBB→bCC→a|aCC→b|bC〔3〕用自然語言描述輸入串的特征(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來說，G1,G1’文法都不能產(chǎn)生。11將右線性文法化為左線性文法的算法：〔1〕對(duì)于G中每一個(gè)形如A→aB的產(chǎn)生式且A是開始符，將其變?yōu)锽→a,否則假設(shè)A不是開始符，B→Aa;〔2〕對(duì)于G中每一個(gè)形如A→a的產(chǎn)生式,將其變?yōu)镾→Aa12(1)狀態(tài)矩陣是：記[S]=q0[B]=q1[AB]=q2[SA]=q3,最小化和確定化后如圖〔2〕記[S]=q0,[A]=q1,[BS]=q2最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下13〔1〕將具有ε動(dòng)作的NFA確定化后，其狀態(tài)轉(zhuǎn)換圖如圖：記{S0,S1,S3}=q0{S1}=q1{S2S3}=q2{S3}=q3(2)記{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q714〔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*cS=a*ab*bc*cG1: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*20識(shí)別此語言的正規(guī)式是S=’LABEL’d(d|,d)*;從略。21從略。22構(gòu)造NFA其余從略。23下面舉一個(gè)能夠識(shí)別1,2,3,10,20,100的例子，讀者可以推而廣之。%{#include<stdio.h>#include<string.h>#include<ctype.h>#defineON1#defineTW2#defineTHRE3#defineTE10#defineTWENT20#defineHUNDRE100#defineWHITE9999%}upper[A-Z]%%ONEreturnTWOreturnTW;THREEreturnTHRE;TENreturnTE;TWENTYreturnTWENT;HUNDREDreturnHUNDRE;""+|\treturnWHITE;\nreturn0;%%main(intargc,char*argv[]){intc,i=0;chartmp[30];if(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can'topen%s\n",argv[1]);exit(0);}}while((c=yylex())!=0){switch(c){caseON:c=yylex();if(c==0)goto{i+=1;label;}c=yylex();if(c==HUNDRE)i+=100;elsei+=1;break;caseTW:c=yylex();c=yylex();if(c==HUNDRE)i+=200;elsei+=2;break;caseTWENT:i+=20;break;caseTE: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用來識(shí)別Dn的DFA至多需要2n＋1個(gè)狀態(tài)。25從略。26〔1〕由{}括住的,中間由任意個(gè)非{組成的字符串,如{},{}},{a},{defg}等等?！?〕匹配一行僅由一個(gè)大寫字母和一個(gè)數(shù)字組成的串，如A1,F8,Z2等?！?〕識(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<stdio.h>#include<string.h>#include<ctype.h>#defineUPPER2#defineWHITE3%}upper[A-Z]%%{upper}+returnUPPER;\t|""+returnWHITE;%%main(intargc,char*argv[]){intc,i;if(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can'topen%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("");elseprintf("%s",yytext);}return;}yywrap(){return;}從略。第四章1.解：(1)S→(S)Z21|()Z21|[S]Z31|[]Z31A→(S)Z22|()Z22|[S]Z32|[]Z32B→(S)Z23|()Z23|[S]Z33|[]Z33Z11→ε|AZ11|BZ21Z12→AZ12|BZ22Z13→AZ13|BZ23Z21→Z11Z22→ε|Z12Z23→Z13Z31→Z21Z32→Z22Z33→ε|Z23(2)S→bZ11|aZ21A→bZ12|aZ22Z11→ε|AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22(3)S→(T)Z11|aZ11|Z11S→(T)Z12|aZ12|Z12Z11→ε|Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ222.解：SAbB1,1.1(表示第1步，用產(chǎn)生式1.1推導(dǎo),以下同)CAbbB2,2.1edAbbB3,4.1edCAbbB4,2.1ededAbbbB5,4.1edaAbbbB5，4.2(不符合，改寫第5步，用4.2)edBfbbB4,2.2edCSdfbbB5,3.1ededSdfbbB6,4.1edaSdfbbB6,4.2eddfbbB5,3.2eddfbbCSd6,3.1eddfbbedSd7,4.1eddfbbaSd7,4.2eddfbbd6,3.23.解：以下Save表示savetoken_pointervalue,Restore表示restoretoken_pointervalue。(1)文法沒有左遞歸。FunctionP:boolean;BeginSave;P:=true;Ifnext_token=〞begin〞thenIfnext_token=’d’thenIfnext_token=’;’thenIfXthenIfnext_token=〞end〞thenreturn;Restore;P:=false;End;FunctionX:boolean;BeginSave;X:=true;Ifnext_token=’d’thenIfnext_token=’;’thenIfXthenreturn;Restore;Ifnext_token=’s’thenIfYthenreturn;Restore;X:=false;End;FunctionY:boolean;BeginSave;Y=true;Ifnext_token=’;’thenIfnext_token=’s’thenIfYthenreturn;Restore;End;(2)消去文法左遞歸，并記為：P→beginSendS→A|CA→V:=EC→ifEthenSE→VE’E’→+VE’|εV→IFunctionP:boolean;BeginSave;P:=true;Ifnext_token=〞begin〞thenIfSthenIfnext_token=〞end〞thenreturn;;Restore;P:=false;End;FunctionA:boolean;BeignSave;A:=true;IfVthenIfnext_token=〞:=〞thenIfEthenreturn;Restore;A:=flase;End;FunctionS:boolean;BeignSave;S:=true;IfAthenreturn;Restore;IfCthenreturn;Restore;S:=false;End;FunctionC:boolean;BeginSave;C:=true;Ifnext_token=〞if〞thenIfEthenIfnext_token=〞then〞thenIfSthenreturn;Restore;C:=false;End;FunctionE:boolean;BeginSave;E:=true;IfVthenIfEpthenreturn;Restore;E:=false;End;FunctionEp:boolean;BeingSave;Ep:=true;Ifnext_token=’+’thenIfVthenIfE’thenreturn;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è)不同的語法樹。即存在著句子α有兩個(gè)不同的最左推導(dǎo)。從而可知，用LL〔1〕方法進(jìn)行句子α的分析過程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進(jìn)行語法分析，即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→bZ12Z21→bZ11|aZ21Z22→bZ12|aZ22|ε消除無用產(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)分析表為：ab#SaZ21bZ11Z11bZ11εZ21aZ21bZ119.解：(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|BB→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)略證：假設(shè)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)SA(a)bS==A=<=<(==<<<a>=<><>>)>>>>>b>>不是簡(jiǎn)單優(yōu)先文法。(2)SRT()∧a,S>=R=T>(<=<<<<)>>∧>>a>>,<=<<<是簡(jiǎn)單優(yōu)先文法。(3)SR(a,)S=<<R>>(=<<a>>,=<<)>>是簡(jiǎn)單優(yōu)先文法。首先消去無用產(chǎn)生式Z→E,Z→E+TSZT#i()SZ==T>>#=<<<I>>(=<<<)>>化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法；13.解：SA/AS>>A=<=<=/>>a>>A和/之間同時(shí)有關(guān)系=和<,所以不是簡(jiǎn)單優(yōu)先文法；提示：分析教材中給出的算法，選擇一種適宜的表示給定文法的方法〔盡量簡(jiǎn)單〕，使得對(duì)文法的輸入比擬簡(jiǎn)單的同時(shí)(需要把輸入轉(zhuǎn)化為計(jì)算機(jī)語言表示，這種轉(zhuǎn)化應(yīng)該盡量簡(jiǎn)單)，能夠比擬簡(jiǎn)單地構(gòu)造3個(gè)根本關(guān)系矩陣〔=，LEAD和LAST〕。證明：設(shè)xjxj+1...xi是滿足條件xj-1<xj=xj+1=...=xi>xi+1的最左子串。由=關(guān)系的定義，可知xjxj+1...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj-1<xj可知xj-1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。同理，xi為某產(chǎn)生式的尾符號(hào)。即存在產(chǎn)生式U→xjxj+1...xi設(shè)ST*aUb其中，aT*...xj-1,bT*xi+1...對(duì)于aUb可構(gòu)造一語法樹，并通過對(duì)其剪枝〔歸約〕，直到U出現(xiàn)在句柄中。從而xjxj+1...xi必為句柄。反之，假設(shè)xjxj+1...xi是句柄，由簡(jiǎn)單優(yōu)先關(guān)系的定義，必滿足上述條件。解：為描述方便，用符號(hào)表示各非終結(jié)符：D=<變量說明>,L=<變量表>,V=<變量>,T=<類型>，a=VAR,則消去V，并采用分層法改寫文法，得到：D→aW:T;W→LL→L,i|iT→r|n|b|c其全部簡(jiǎn)單優(yōu)先關(guān)系是：DWTLa:;,ir|n|b|cDW=T=L>=a=<<:=<;,>>>=ir|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*,由于文法不含無用產(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)來表示；(1)證明：由設(shè)句型a=…Ua…中含a的短語不含U，即存在A，A=>*ay,則a可歸約為a=…Ua…ü*…UA…=b，b是G的一個(gè)句型，這與G是算符文法矛盾，所以，a中含有a的短語必含U?！?〕的證明與〔1〕類似，略。證：〔1〕對(duì)于a=…aU…是句型，必有ST*a(=…aU…)T+…ab….即在歸約過程中,b先于a被歸約,從而,a<b.對(duì)于(2)的情況類似可以證明。證明略.證明略.證明略。證：(1)用反證法。設(shè)沒有短語包含b但是不包含a，則a,b一定同時(shí)位于某個(gè)短語中，從而必使得a,b同時(shí)位于同一產(chǎn)生式的右部，所以a=b，與G是算符優(yōu)先文法〔=與<不能并存〕矛盾。〔2〕、〔3〕類似可證。證：只要證u中不含有除自身以外的素短語。設(shè)有這樣的素短語存在，即存在bx···by是素短語，其中1<x或者y<n之一成立。因素短語是短語，根據(jù)短語定義，則必有：1<xTbx-1<bx或y<nTby>by+1，與bx-1=bx及by=by+1矛盾，得證。提示：根據(jù)27題的結(jié)論，只要證u是句型α的短語，根據(jù)=關(guān)系的定義容易知道u是句型α的素短語。證：與28題的不同點(diǎn)只是a0,an+1可以是’#’,不影響結(jié)論。證：設(shè)不能含有素短語，則只能是含有短語〔不能含有終結(jié)符號(hào)〕，則該短語只能含有一個(gè)非終結(jié)符號(hào)，否則不符合算符文法定義，得證。31.解：〔1〕算符優(yōu)先矩陣：+*↑〔〕i#+><<<><>*>><<><>↑>><<><>(<<<<=<)>>>>>I>>>>>#<<<<<〔2〕用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為：+*↑()i#F3551771G246616132.解：用Floyd方法對(duì)的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為：zbMLa()f1567747g165466733.解：〔1〕優(yōu)先矩陣如下：[]a#[>=]>>a<><><#<<<〔2〕用Bell方法求優(yōu)先函數(shù)的過程如下：[]a#f5751g5561〔3〕顯然，文法不是算符優(yōu)先文法,所以不能線性化。略。35解：〔1〕識(shí)別全部活前綴的DFA如下：〔以表格的形式來表示，很容易可以轉(zhuǎn)化為圖的形式，本章中其余的題目也是采用這種形式表示?！碃顟B(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·aSbS→·aScS→·abSaI1I2I1S’→S·I2S→a·SbS→a·ScS→a·bS→·aSbS→·aScS→·abSabI3I2I4I3S→aS·bS→aS·cbcI5I6I4S→ab·I5S→aSb·I6S→aSc·〔2〕識(shí)別全部活前綴的DFA如下：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·cAS→·ccBSc·I1II1S’→S·I2S→c·AS→c·cBA→·cAA→·aAcaI3I4I5I3S→cA·I4S→cc·BA→c·AB→·ccBB→·bA→·cAA→·aBAcbaI6I5I7I8I5I5A→a·I6S→ccB·I7B→c·cBA→c·AA→·cAA→·aCAaI9I10I5I8B→b·I9B→cc·BA→c·AB→·ccBB→·bA→·cAA→·aBAcbaI11I10I7I8I5I10A→cA·I11B→ccB·所求的LR(0)工程標(biāo)準(zhǔn)族C={I0,I1,…,I11}〔3〕狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·aSSbS→·aSSSS→·cScaI1I2I3I1S’→S·I2S→c·I3S→a·SSbS→a·SSSS→·aSSbS→·aSSSS→·cScaI4I2I3I4S→aS·SbS→aS·SSS→·aSSbS→·aSSSS→·cScaI5I2I3I5S→aSS·bS→aSS·SS→·aSSbS→·aSSSS→·cSabcI7I3I6I2I6S→aSSb·I7S→aSSS·〔4〕狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·AA→·AbA→·aSAaI1I2I3I1S’→S·I2S→A·S→A·bbI4I3A→a·I4S→Ab·36解：〔1〕是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,b,c}ACTIONGOTOabc#S0S211ACC2S2S433S5S64R3R3R35R1R1R16R2R2R2〔2〕是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#}ACTIONGOTOabc#SAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5〔3〕是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,a,b,c}ACTIONGOTOabc#S0S3S211ACC2R3R3R3R33S3S244S3S255S3S6S276R1R1R1R17R2R2R2R2〔4〕因?yàn)镮2中含有沖突工程，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#}∩=φ(所以可以用SLR(1)規(guī)則解決沖突),FOLLOW(A)={b,#}ACTIONGOTOab#SA0S3121ACC2S4R13R3R34R2R237解：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·(SRS→·aS(aI1I2I3I1S’→S·I2S→(·SRS→·(SRS→·aS(aI4I2I3I3S→a·I4S→(S·RS→·(SRS→·aR→·,SRR→·)a(R,)I3I2I5I6I7I5S→(SR·I6R→,·SRS→·(SRS→·aS(aI8I2I3I7R→)·I8R→,S·RR→·,SRR→·)),RI7I6I9I9R→,SR·LR(0)分析表如下：ACTIONGOTOa(),#SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可見是LR(0)文法。38解：〔1〕狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·SabS→·bRSbI1I2I1(沖突工程)S’→S·S→S·abaaccI3I2S→b·RR→·SR→·aS→·SabS→·bRRSabI4I5I6I2I3S→Sa·bbI7I4S→bR·r2I5(沖突工程)R→S·S→S·abaI3I6R→a·I7S→Sab·工程I1,I5同時(shí)具有移進(jìn)和歸約工程，對(duì)于I5={R→S·,S→S·ab},follow(R)={a},follow(R)∩{a}={a},所以SLR(1)規(guī)則不能解決沖突，從而該文法不是SLR(1)文法?！?〕狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·aSABS→·BAB→·bSaBbI1I2I3I4I1S’→S·I2S→a·SABS→·aSABS→·BAB→·bSaBbI5I2I3I4I3S→B·AA→·aAA→·BB→·bAaBbI6I7I8I4I4B→b·r5I5S→aS·ABA→·aAA→·BB→·bAaBbI9I7I8I4I6S→BA·r2I7A→a·AA→·BA→·aAB→·bABabI10I8I7I4I8A→B·r4I9S→aSA·BB→·bBbI11I4I10A→aA·r3I11S→aSAB·r1不存在沖突工程，故該文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#SAB0S2S4131ACC2S2S4533S7S4684R5R5R55S7S4986R2R2R27S7S41088R4R4R49S41110R3R3R311R1R1R1〔3〕先求識(shí)別全部活前綴的DFA：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·aSbS→·bSaS→·abSabI1I2I3I1S’→S·accI2S→a·SBS→a·bS→·aSbS→·bSaS→·abSbaI4I5I2I3S→b·SaS→·aSbS→·bSaS→·abSabI6I2I3I4S→aS·bbI7I5S→ab·r3I6S→bS·aaI8I7S→aSb·r1I8S→bSa·r2不存在沖突工程，故該文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#S0S2S311ACC2S2S543S2S364S75R3R3R36S87R1R1R18R2R2R2〔4〕先求識(shí)別全部活前綴的DFA：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·aAS→·bBSabI1I2I3I1S’→S·accI2(沖突)S→a·AA→·cAdA→·AcI4I5r4I3(沖突)S→b·BB→·cBddB→·BcI6I7r6I4S→aA·r1I5(沖突)A→c·AdA→·cAdA→·AcI8I5r4I6S→bB·r2I7(沖突)B→c·BddB→c·BddB→·BcI9I7r6I8A→cA·ddI10I9B→cB·dddI11I10A→cAd·r3I11B→cBd·ddI12I12B→cBdd·r5因?yàn)閒ollow(A)=follow(B)={#,d},所以沖突工程I2,I3,I5,I7可以用SLR(1)規(guī)則得以解決，從而該文法為SLR(1)文法。其SLR(1)分析表如下：ACTIONGOTOabcd#SAB0S2S311Acc2S5R4R443S7R6R664R15S5R4R486R27S7R6R698S109S1110R3R311S1212R5R5〔5〕解：原文法等價(jià)化為q1→q2,q1→q3,q2→q4;q5,q4→beginD,q4→q4;D,q5→Send,q5→S;q5,q3→beginq5,先求識(shí)別全部活前綴的DFA：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0q1’→·q1q1→·q2q1→·q3q2→·q4;q5q3→·beginq5q4→·beginDq4→·q4;Dq1q2q3q4beginI1I2I3I4I5I1q1’→q1·ACCI2q1→q2·R1I3q1→q3·R2I4q2→q4·;q5q4→q4·;D;DI6I5q3→begin·q5q3→begin·Dq5→·Sendq5→·S;q5q5DSI7I8I9I6q2→q4;·q5q4→q4;·Dq5→·Sendq5→·S;q5q5DSI10I11I9I7q3→beginq5·R8I8q3→beginD·R4I9q5→S·endq5→S·;q5end;I12I13I10q2→q4;q5·R3I11q4→q4;D·R5I12q5→Send·R6I13q5→s;·q5q5→·Sendq5→·S;q5q5SI14I9I14q5→s;q5·R7不存在沖突工程，故該文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTO;beginDSend#q1q2q3q4q5012341Acc2R13R24S65S8S976S7S9107R88R49S13S1210R311R512R613S91414R7〔6〕解：原文法可化為等價(jià)形式：q1→beginq2q3end,q2→q2d;,q2→ε,q3→q3;q4,q3→q4,q4→S,q4→ε,先求識(shí)別全部活前綴的DFA：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0q1’→·q1q1→·beginq2q3endq1beginI1I2I1q1’→q1·ACCI2q1→begin·q2q3endq2→·q2d;q2→·q2q2I3R3I3(沖突工程)Q1→beginq2·q3endq2→q2·d;q3→·q3;q4q3→·q4q4→·Sq4→·q3Ddq4SI4I10I5I6R7I4q1→beginq2q3·endq3→q3·;q4end;I7I8I5q3→q4·R5I6q4→S·R6I7q1→beginq2q3end·R1I8(沖突工程)q3→q3;·q4q4→·Sq4→·q4SI9I6R7I9q3→q3;q4·R4I10q2→q2d·;;I11I11q2→q2d;·R2因?yàn)閒ollow(q4)={end,#}，故沖突工程可以通過SLR(1)規(guī)則來解決，從而文法為SLR(1)文法。SLR(1)分析表如下：actiongotobeginendd;S#q1q2q3q40S2112R3R3R3R333R7S10R7S6454S7S85R5R56R6R67R18R7R7S699R4R41011R2R2R2R239解：識(shí)別活前綴的DFA及LR(0)分析表：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·SS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcI0I6I5I4I3I1S’→S·A→S·bbI2I2A→Sb·I3S→c·AdA→c·dA→·AScA→·SbA→·cdA→·aS→·AAdS→·cAdS→·bSAabcdI8I9I5I4I3I7I4S→b·I5A→a·I6S→A·AdA→A·ScA→·AScA→·SbA→·cdA→·aS→·AAdS→·cAdS→·bSAabcI11I10I5I4I3I7A→cd·I8A→S·bbI2I9S→cA·dA→A·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcdI11I10I5I4I3I14I10S→AA·dA→A·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcdI11I10I5I4I3I13I11A→AS·cA→S·bbcI2I12I12A→ASc·I13S→AAd·I14S→cAd·ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r5r53s5s4s3s7894r3r3r3r3r35r7r7r7r7r76s5s4s37r6r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212r4r4r4r4r413r1r1r1r1r114r2r2r2r2r2SLR(1)分析法：FOLLOW(S)={c,b}FOLLOW(A)={a,b,c,d}ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r53s5s4s3s7894r3r35r7r7r7r76s5s4s37r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212R4r4r4r413r1r114r2r2兩表的異同：兩表都用ACTION表和GOTO表反映了移進(jìn)、歸約〔包括接受〕的狀態(tài)和動(dòng)作。不同之處在于SLR(1)增加了在歸約的時(shí)候考慮向前符號(hào)a以解釋可能出現(xiàn)的“移進(jìn)——?dú)w約〞沖突；SLR〔1〕的分析較稀疏些，原因是填寫歸約項(xiàng)時(shí)，并不是在一狀態(tài)對(duì)應(yīng)行上全部填寫歸約動(dòng)作，而是考慮了相應(yīng)非終結(jié)符的FOLLOW集因素。另外，在分析效率上SLR〔1〕分析的效率更高一些，因?yàn)樵诎l(fā)現(xiàn)錯(cuò)誤方面，SLR〔1〕比LR〔0〕分析發(fā)現(xiàn)的更早些。40解：求LR(1)工程集和狀態(tài)轉(zhuǎn)換表：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·S#S→·A#A→·BA#A→·#B→·aB#,a,bB→·b#,a,bSABabI1I2I3I4I5I1S’→S·#I2S→A·#I3A→B·A#A→·#A→·BA#B→·aB#,a,bB→·b#,a,bABabI6I3I4I5I4B→a·B#,a,bB→·aB#,a,bB→·b#,a,bBabI7I4I5I5B→b·#,a,bI6A→BA·#I7B→aB·#,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOab#SAB0S4S5R31231ACC2R23S4S5R3634S4S575R5R5R56R27R4R4R4用LR(1)分析表對(duì)輸入符號(hào)串a(chǎn)bab的分析過程：步驟狀態(tài)棧中符號(hào)余留符號(hào)分析動(dòng)作下一狀態(tài)10#abab#S44204#abab#S553045#abab#R574047#aBab#R43503#Bab#S446034#Bab#S5570345#Bab#R4780347#BaB#R439033#BB#R36100336#BBA#R2611036#BA#R211201#A#acc41解：〔1〕求LR(1)工程集和狀態(tài)轉(zhuǎn)換圖：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·S#S→·A#A→·AB#,a,bA→·SAI1I2I1S’→S·#I2S→A·#A→A·B#,a,bB→·aB#,a,bB→·b#,a,bBabI3I5I4I3A→AB·#,a,bI4B→b·#,a,bI5B→a·B#,a,bB→·aB#,a,bB→·b#,a,bBabI6I5I4I6B→aB·#,a,b相應(yīng)的LR(1)分析表為：STATEACTIONGOTOab#SAB0R3R3R3121Acc2S5S4R13R2R2R24R5R5R55S5S466R4R4R4表中沒有多從定義的元素，所以文法是LR(1)文法。〔2〕LR(1)分析法：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0E’→·E#E→·E+T#/+E→·T#/+T→·(E)#/+T→·a#/+ET(aI1I1I5I4I1E’→E·#E→E·+T#/++I2I2E→E+·T#/+T→·(E)#/+T→·a#/+T(aI3I5I4I3E→E+T·#/TI4T→a·#/+I5T→(·E)#/+E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)ECTaI7I8I9I12I6E→T·#/+I7T→(E·)#/+E→E·+T+/))+I10I11I8T→(·E))/+E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)(aETI8I12I14I9I9E→T·+/)I10T→(E)·#/+I11E→E+·T+/)T→·(E)+/)T→·a+/)(TaI8I13I12I12T→a·+/)I13E→E+T·)/+I14T→(E·)+/)E→E·+T+/)+)I11I15I15T→(E)·+/)LALR(1)分析：〔合并同心集〕狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0E’→·E#E→·E+T#/+E→·T#/+T→·(E)#/+T→·a#/+ETaI1I6/I9I4/I12I1E’→E·#E→E·+T#/++I2/I11I2/I11E→E+·T#/+/〕T→·(E)#/+/〕T→·a#/+/〕T(aI3/I13I5/I8I4/I12I3/I13E→E+T·)/+/#I4/I12T→a·+/)/#I5/I8T→(·E)#/+/〕E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)T(EaI6/I9I5/I8I7/I14I4/I12I6/I9E→T·+/)/#I7/I14T→(E·)+/)/#E→E·+T+/)+)I2/I11I10/I15I10/I15T→(E)·+/)/#LR(1)ACTIONGOTO+()a#ET0S5S4161S2ACC2S5S433R1R14R4R45S8S12796R2R27S11S108S8S121499R2R210R3R311S8S121312R4R413R1R114S11S1515R3R3可以看出，表中無沖突項(xiàng)，所以是LR(1)文法；LALR〔1〕分析表：LR(1)ACTIONGOTO+()a#ET0S5/S8S4/S1216/91S2/S11ACC2/11S5/S8S4/S123/133/13R1R1R14/12R4R4R45/8S5/S8S4/S127/146/96/9R2R2R210/15R3R3R37/14S2/S11S10/S1542解：〔1〕求LR(1)工程集和狀態(tài)轉(zhuǎn)換圖：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0E’→·E#E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI1I2I1E’→E·#E→E·+E#,+,*E→E·*E#,+,*+*I3I4I2E→i·#,+,*I3E→E+·E#,+,*E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI5I2I4E→E*·E#,+,*E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI6I2I5E→E+E·#,+,*E→E·+E#,+,*E→E·*E#,+,*+*I3I4I6E→E*E·#,+,*E→E·+E#,+,*E→E·*E#,+,*+*I3I4依據(jù)以上圖求出該文法的LR(1)分析表知道由于工程I5,I6導(dǎo)致了有多重定義的元素，所以不是LR(1)文法。事實(shí)上，從文法本身可以看出它是二義性的，因此不可能是LR〔1〕文法。等價(jià)的LR(1)文法為：E→E+T|TF→T*F|FF→i。另外，對(duì)原文法的沖突項(xiàng)來說，假設(shè)考慮算術(shù)運(yùn)算符的運(yùn)算優(yōu)先級(jí)別，以及結(jié)合方式，上述沖突是可解決的。例如，假設(shè)表達(dá)式運(yùn)算滿足左結(jié)合律〔即a+b+c=(a+b)+c而不是右結(jié)合律：a+b+c=a+(b+c)〕,及*運(yùn)算和優(yōu)化優(yōu)先級(jí)高于+運(yùn)算，上述文法相應(yīng)的LR〔1〕分析表為狀態(tài)ACTIONGOTOi+*#E0s211s3s4acc2r3r3r33s254s265r1s4r16r2r2r2〔2〕解：LR(1)：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·S#S→·aSa#S→·bSb#S→·a#S→·b#SabI1I2I3I1S’→S·#I2S→a·Sa#S→a·#S→·aSaaS→·bSbaS→·aaS→·baSabI4I7I6I3S→b·Sb#S→b·#S→·aSabS→·abS→·bSbbS→·bbSabI11I14I13I4S→aS·a#aI5I5S→aSa·#I6S→b·SbaS→b·aS→·aSabS→·bSbbS→·abS→·bbSabI10I14I13I7S→a·SaaS→a·aS→·aSaaS→·bSbaS→·aaS→·baSabI8I7I6I8S→aS·aaaI9I9S→aSa·aI10S→bS·babI15I11S→bS·b#bI12I12S→bSb·#I13S→b·SbbS→b·bS→·aSabS→·bSbbS→·abS→·bbSabI16I14I13I14S→a·SabS→a·bS→·aSaaS→·bSbaS→·aaS→·baSabI18I7I6I15S→bSb·aI16S→bS·bbbI17I17S→bSb·bI18S→aS·abaI19I19S→aSa·b有移進(jìn)——?dú)w約沖突，不是LR(1)文法?！?〕求LR(1)工程集和狀態(tài)轉(zhuǎn)換圖：狀態(tài)工程集經(jīng)過的符號(hào)到達(dá)的狀態(tài)I0S’→·S#S→·V:=E#S→·LS#L→·I:IV→·I:SVLII1I2I3I4I1S’→S·#I2S→V·:=E#:I5I3S→L·S#S→·V:=E#S→·LS#V→·I:L→·I:ISLII6I3I4I4L→I·:IV→I·::I7I5S→V:·=E#=I8I6S→LS·#I7L→I:·II8S→V:=·E#EI9I9S→V:=E·#依據(jù)以上圖求出該文法的LR(1)分析表知道由于工程I4導(dǎo)致了有多重定義的元素，所以不是LR(1)文法。〔4〕略。證：根據(jù)第3章“詞法分析及詞法分析程序〞，我們知道任一正規(guī)集可以由某一正規(guī)式r表示，而對(duì)于任一正規(guī)式r，都可以構(gòu)造一個(gè)DFA,并且兩者在表述語言的意義下等價(jià)。根據(jù)這個(gè)DFA，我們可以很容易地構(gòu)造一個(gè)分析表。方法是對(duì)于DFA中的每一個(gè)子圖，如果從狀態(tài)Ii，經(jīng)過了終結(jié)符號(hào)a,到達(dá)狀態(tài)Ij,則在分析表中有ACTION(Ii,a)=Sj，如果Sj是一個(gè)終結(jié)狀態(tài)，則置ACTION(Ii,a)=ACC。解：SLR(1)分析表比LR(0)分析表在采用一定形式存儲(chǔ)時(shí)〔如稀疏矩陣〕，會(huì)少一些存儲(chǔ)空間。另外，在分析進(jìn)行到歸約動(dòng)作時(shí)，LR〔0〕無論下一符號(hào)是什么〔即使是錯(cuò)誤的輸入〕，都將先進(jìn)行歸約，然后才判斷下一輸入符是否正確；而SLR〔1〕在進(jìn)行歸約時(shí)還要先看看下一符號(hào)是否正確，否則將報(bào)錯(cuò)。從而可知，對(duì)于有錯(cuò)誤的輸入串，SLR〔1〕分析效率要高一些。證：考察LR分析器的總控程序，可以知道訪問GOTO分析表元素的可能只有兩種，下面分情況討論：先訪問ACTION(Sm,ai)=〞移進(jìn)〞，再訪問GOTO(Sm,ai)=Sm+1,其中ai是一個(gè)終結(jié)符。查看構(gòu)造LR分析表的算法的條目〔1〕，可以知道當(dāng)ai是一個(gè)終結(jié)符時(shí)，填寫ACTION(Sm,ai)=〞移進(jìn)〞總是伴隨著填寫GOTO(Sm,ai)=Sm+1，所以這種情況下結(jié)論成立。先訪問ACTION(Sm,ai)=rj，其中ai是一個(gè)終結(jié)符,rj意指按文法的第j個(gè)產(chǎn)生式A→Xm-r+1Xm-r+2···Xm進(jìn)行歸約，再訪問GOTO(Sm-r,A)=Sl,其中A是一個(gè)非終結(jié)符。查看構(gòu)造LR分析表的算法的條目〔1〕，可以知道當(dāng)ai是一個(gè)非終結(jié)符時(shí)，填寫GOTO(Sm,ai)=Sm+1，即只有歸約出了ai時(shí)，再狀態(tài)轉(zhuǎn)換到Sm+1,和總控程序情況一致，所以這種情況下結(jié)論成立。綜上所述，結(jié)論成立。46．證明：在文法G[S]中，只有非終結(jié)符S有兩個(gè)候選式，AaAb及BbBa，而兩個(gè)候選的FIRST集分別為{a}和，它們不相交，所以，文法G[S]滿足LL〔1〕文法的條件，是LL〔1〕文法。在SLR〔1〕方法識(shí)別活前綴的DFA中，工程I0={S'→·S,S→·AaAb,S→·BbBa,A→e·,B→e·}中出現(xiàn)歸約-歸約沖突，而follow(A)=follow(B)={a,b}，用SLR〔1〕方法不能解決沖突。47．略。48．略。第五章5.1解：屬性文法是文法符號(hào)帶有語義屬性的前后文無關(guān)文法；屬性翻譯文法首先是對(duì)文法的屬性依賴關(guān)系作出限制，不允許出現(xiàn)屬性的直接或間接的循環(huán)定義，即要求屬性文法是良定義的；其次還應(yīng)將屬性定義規(guī)則改造為計(jì)算屬性值的語義程序，即將靜態(tài)的定義規(guī)則改寫為可動(dòng)態(tài)執(zhí)行的語義動(dòng)作；屬性文法是靜態(tài)描述，而屬性翻譯文法是動(dòng)態(tài)描述，有語義動(dòng)作。5.2解：綜合屬性有：Z.aZ.pX.dX.c繼承屬性有：X.b屬性依賴出現(xiàn)了循環(huán)；5.3解：S屬性文法一定是L屬性文法，因?yàn)榍罢呤窃诤笳吒咨霞由舷拗茥l件，即非終結(jié)符只有綜合屬性；反之當(dāng)然不正確。5.4解：A-BC+*DE-^ad*c+d/e+f*g+ax+4<=cd3*/\\/de*c+b/\a\/f^s0=;i1=;i100<=BZssii*+=;ii1+=;BRS2’5.5解：a+b*ca*(b-c)-(c+d)/e有誤if(a<b)x=(a-b)^c;elseg=h;5.6略5.7略5.8解：(+,B,C,T1)(*,A,T1,T2)(+,T2,D,T3)(=,T3,0,X)2〕如下所示：當(dāng)前句型〔方框括起來局部為句柄〕A/\(BV(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)Expr.TC→(jnz,A,0,0);

(2)Expr.FC→(j,0,0,0);當(dāng)前句型Expr/\(BV(CVD/\?F))用產(chǎn)生式Expr^→Expr’/\’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);當(dāng)前句型Expr^(BV(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,0);

(2)Expr^.FC→(j,0,0,0);

(3)Expr.TC→(jnz,B,0,0);

(4)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(ExprV(CVD/\?F))用產(chǎn)生式Exprv→Expr'V'歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);當(dāng)前句型Expr^(Exprv(CVD/\?F))用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Expr.TC→(jnz,C,0,0);(6)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprVD/\?F)),用產(chǎn)生式Exprv→Expr’V’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);當(dāng)前句型Expr^(Exprv(ExprvD/\?F)),用產(chǎn)生式Expr4→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)Expr.TC→(jnz,D,0,0);(8)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr/\?F)),用產(chǎn)生式Expr^→exrp’/\’歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^?F)),用產(chǎn)生式Expr→iden歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.TC→(jnz,F,0,0);(10)Expr.FC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^?Expr)),用產(chǎn)生式Expr→?Expr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.FC→(jnz,F,0,0);(10)Expr.TC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr^Expr)),用產(chǎn)生式Expr→Expr^Expr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,0);當(dāng)前句型Expr^(Exprv(ExprvExpr)),用產(chǎn)生式Expr→ExprvExpr歸約，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);當(dāng)前句型Expr^(Exprv(Expr)),用產(chǎn)生式Expr→(Expr)歸約，所得四元式序列不變當(dāng)前句型Expr^(ExprvExpr),用產(chǎn)生式Expr→ExprvExpr歸約,得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);當(dāng)前句型Expr^(Expr),用產(chǎn)生式Expr→(Expr)歸約，所得四元式序列不變當(dāng)前句型Expr^Expr,用產(chǎn)生式Expr→Expr^Expr歸約,得(1)(jnz,A,0,3);(2)(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,2);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);3〕假設(shè)所產(chǎn)生的四元式序列編號(hào)從1開始1.當(dāng)前句型為whileA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式W1→while歸約，得(1)Wl.loop→2.當(dāng)前句型為WlA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用產(chǎn)生式Expr→idenropiden歸約，得(1)Wl.loop→Expr.TC→(j<A,C,0);(2)Expr.FC→(j,0,0,0);3.當(dāng)前句型為WlExprùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用