《編譯原理》西北工業(yè)大學(xué)第三版課后答案.doc

上傳人：小** 文檔編號：13265633 上傳時間：2020-06-11 格式：DOC 頁數(shù)：98 大?。?72.08KB

收藏版權(quán)申訴舉報下載

第1頁 / 共98頁

第2頁 / 共98頁

第3頁 / 共98頁

下載文檔到電腦，查找使用更方便

5 積分

下載資源

還剩頁未讀，繼續(xù)閱讀

資源描述：

《《編譯原理》西北工業(yè)大學(xué)第三版課后答案.doc》由會員分享，可在線閱讀，更多相關(guān)《《編譯原理》西北工業(yè)大學(xué)第三版課后答案.doc（98頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、目錄第一章習(xí)題解答1第二章習(xí)題解答22.構(gòu)造產(chǎn)生下列語言的文法23.描述語言特點37.解：510.證明：因為存在句子：abc，它對應(yīng)有兩個語法樹（或最右推導(dǎo)）：711.解：715.消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式10第三章習(xí)題解答10第四章習(xí)題解答24第四章習(xí)題參考答案2435解：3736解：4037解：4238解：4339解：識別活前綴的DFA及LR(0)分析表：5040解：求LR(1)項目集和狀態(tài)轉(zhuǎn)換表：5441解：5542解：59第五章習(xí)題解答645.8 解：65第一章習(xí)題解答1. 解：源程序是指以某種程序設(shè)計語言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處

2、理加工而得的另一種語言（目標(biāo)語言）的程序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點是并不先將高級語言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級語言程序語句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，然后再讀入下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點是先將高級語言程序翻譯成機(jī)器語言程序，將其保存到指定的空間中，在用戶需要時再執(zhí)行之。即先翻譯、后執(zhí)行。 2. 解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)

3、代碼生成程序、信息表管理程序、錯誤檢查處理程序組成。 3. 解：C語言的關(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語言中均為保留字。 4. 解：C語言中括號有三種：，（）。其中，用于語句括號；用于數(shù)組；（）用于函數(shù)（定義與

4、調(diào)用）及表達(dá)式運算（改變運算順序）。C語言中無END關(guān)鍵字。逗號在C語言中被視為分隔符和運算符，作為優(yōu)先級最低的運算符，運算結(jié)果為逗號表達(dá)式最右側(cè)子表達(dá)式的值（如：(a,b,c,d)的值為d）。 5. 略第二章習(xí)題解答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個2.構(gòu)造產(chǎn)生下列語言的文法（1）anbn|n0解：對應(yīng)文法為G(S) = (S,a,b, S| aSb ,S) （2）anbmcp|n,m,p0解：對應(yīng)文法為G(

5、S) = (S,X,Y,a,b,c,SaS|X,XbX|Y,YcY|,S)（3）an # bn|n0cn # dn|n0解：對應(yīng)文法為G(S) = (S,X,Y,a,b,c,d,#, SX, SY,XaXb|#,YcYd|# ,S)（4）w#wr# | w?0,1*,wr是w的逆序排列解：G(S) = (S,W,R,0,1,#, SW#, W0W0|1W1|# ,S)（5）任何不是以0打頭的所有奇整數(shù)所組成的集合解：G(S) = (S,A,B,I,J,-,0,1,2,3,4,5,6,7,8,9,SJ|IBJ,B0B|IB|e, IJ|2|4|6|8, J1|3|5|7|9,S)（6）所有偶數(shù)個

7、n 或1n0n0q形式，進(jìn)一步，可知其具有形式1n0mn,m0,且n+m0。（4）SbAdcAAGSGAa解：可知，S=baSndc n0該語言特點是：產(chǎn)生的句子中，是以ba開頭dc結(jié)尾的串,且ba、dc個數(shù)相同。（5）SaSSSa解：L(G)=a(2n-1)|n1可知：奇數(shù)個a4.解：此文法產(chǎn)生的語言是：以終結(jié)符a1 、a2 an 為運算對象，以、為運算符，以、為分隔符的布爾表達(dá)式串5. 5.1解：由于此文法包含以下規(guī)則：AAe，所以此文法是0型文法。5.2證明：略6.解：（1）最左推導(dǎo)：TT：TL：TL：T L：L：T L：L：T L：L：；T L：L：；T L：L：begin；T L：L

8、：begin d；T L：L：begin d；d；T L：L：begin d；d；T L：L：begin d；d；s；復(fù)合尾部.T L：L：begin d；d；s； endT L：L：begin d；d；s；s end最右推導(dǎo)：TT：T：T：T：；T：；T：；endT：；s；endT：；s；s；endT：；說明；s；s；endT：；d；s；s；endT：begin 說明；d；s；s；endT：begin d；d；s；s；endT： 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)語法樹是：7.解：aac

9、b是文法GS中的句子，相應(yīng)語法樹是：最右推導(dǎo)：S=aAcB=aAcb=aacb最左推導(dǎo)：S=aAcB=aacB=aacb（2）aabacbadcd不是文法GS中的句子因為文法中的句子不可能以非終結(jié)符d結(jié)尾（3）aacbccb不是文法GS中的句子可知，aacbccb僅是文法GS的一個句型的一部分，而不是一個句子。（4）aacabcbcccaacdca不是文法GS中的句子因為終結(jié)符d后必然要跟終結(jié)符a，所以不可能出現(xiàn)dc這樣的句子。（5）aacabcbcccaacbca不是文法GS中的句子由（1）可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能跟非終結(jié)符S，所以不可能出現(xiàn)caac

10、b這樣的句子。8.證明：用歸納法于n，n=1時，結(jié)論顯然成立。設(shè)n=k時，對于12.kT*b,存在i：i=1,2,.,k，iT*bi成立，現(xiàn)在設(shè)12. kk+1T*b，因文法是前后文無關(guān)的，所以12. k可推導(dǎo)出b的一個前綴b，k+1可推導(dǎo)出b的一個后綴=b(不妨稱為b k+1)。由歸納假設(shè)，對于b，存在i ：i=1,2,.,k，b=12.k,使得iT*bi成立，另外,我們有k+1T*b(=b k+1）。即n=k+1時亦成立。證畢。9.證明：(1)用反證法。假設(shè)首符號為終結(jié)符時，的首符號為非終結(jié)符。即設(shè)：=a；=A且 =*。由題意可知：=aT T A=，由于文法是CFG，終結(jié)符a不可能被替換空

11、串或非終結(jié)符，因此假設(shè)有誤。得證；（2）同（1），假設(shè)：的首符號為非終結(jié)符時，首符號為終結(jié)符。即設(shè)：=a；=A且=aT T A=，與（1）同理，得證。10.證明：因為存在句子：abc，它對應(yīng)有兩個語法樹（或最右推導(dǎo)）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。11.解：(1) STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對應(yīng)的語法樹為：全部的短語：第一個a (a1)是句子bbaacb相對于非終結(jié)符A (A1) (產(chǎn)生式A?a）的短語（直接短語）；b1a1是句子bbaacb相對于非終結(jié)符A2的短語；b2b

12、1a1是句子bbaacb相對于非終結(jié)符A3的短語；c是句子bbaacb相對于非終結(jié)符S1（產(chǎn)生式S?c）的短語（直接短語）；a2cb3是句子bbaacb相對于非終結(jié)符B的短語；b2b1a1a2cb3是句子bbaacb相對于非終結(jié)符S2的短語；注：符號的下標(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)的語法樹是：（3）解：iii*i+對應(yīng)的語法樹略。最右推導(dǎo)：E TT=F=FPT FET FET+T FEF+T FEP+T FEi+TFTi+T FTF*i+TFTP*i+T FTi*i+

13、TFFi*i+T FPi*i+TFii*i+T Pii*i+Tiii*i+12.證明：充分性：當(dāng)前文法下的每一符號串僅有一個句柄和一個句柄產(chǎn)生式T對當(dāng)前符號串有唯一的最左歸約T對每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語法樹。必要性：有唯一的語法樹T對每一步推導(dǎo)都有唯一的最右推導(dǎo)T對當(dāng)前符號串有唯一的最左歸約T當(dāng)前文法下的每一符號串僅有一個句柄和一個句柄產(chǎn)生式13.化簡下列各個文法（1）解：SbCACdAcSA| cCCCcS | c（2）解：SaAB | fA | gAe | dDADeABf（3）解：Sac14.消除下列文法中的產(chǎn)生式（1）解：SaAS | aS | bAcS（2）解：SaA

14、A | aA | aAbAc| bc | dAe| de15.消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式（1）消除后的產(chǎn)生式如下：SaB | BCBDB | bCbDb | DB（2）消除后的產(chǎn)生式如下：SSA | SB |（）|（S）| |SA() |（S）|SB |S（3）消除后的產(chǎn)生式如下：EE+T | T*F | (E) | PF | iTT*F | (E) | PF | i FPF | (E) | i P(E) | i第三章習(xí)題解答1從略23 假設(shè)W:表示載狐貍過河，G:表示載山羊過河，C:表示載白菜過河用到的狀態(tài)1：狐貍和山羊在左岸2：狐貍和白菜載左岸3:羊和白菜在左岸 4:狐貍和山羊

15、在右岸5:狐貍和白菜在右岸 6:山羊和白菜在右岸F:全在右岸4 證明：只須證明文法G:AB 或A （A,BVN, VT+）等價于G1:AaB 或Aa (aVT+) G1的產(chǎn)生式中 AaB, 則B也有BbC ,CcD . 所以有 A abcB,a,b,cVT,BVN所以與G等價。2）G的產(chǎn)生式AB，VT+，因為是字符串，所以肯定存在著一個終結(jié)符a，使AaB可見兩者等價，所以由此文法產(chǎn)生的語言是正規(guī)語言。5 6 根據(jù)文法知其產(chǎn)生的語言是L=ambnci| m,n,i1可以構(gòu)造如下的文法VN=S,A,B,C, VT=a,b,cP= S aA, AaA, AbB, BbB, BcC, CcC, Cc

17、描述輸入串的特征(i) 以任意個(包括0)b開頭，中間有任意個（大于1）a，跟一個b,還可以有一個由a,b組成的任意字符串(ii) 以a打頭，后跟任意個（包括0）b(iii)以a打頭，中間有任意個（包括0）b,再跟a,最后由一個a,b所組成的任意串結(jié)尾或者以b打頭，中間有任意個（包括0）a,再跟b,最后由一個a,b所組成的任意串結(jié)尾(iv)以任意個（包括0）b開頭,中間跟aa最后由一個a,b所組成的任意串結(jié)尾或者以任意個（包括0）b開頭，中間跟ab后再接任意（包括0）a再接b，最后由一個a,b所組成的任意串結(jié)尾10 （1）G1的狀態(tài)轉(zhuǎn)換圖：G2的狀態(tài)轉(zhuǎn)換圖：(2) G1等價的左線性文法：SBb

18、,SDd,DC,BDb,CBc,BAb,B,AaG2等價的右線性文法：SdD,SaB,DC,BabC,BbB,BbA,B,CcA,Aa（3）對G1文法,abb的推導(dǎo)序列是：S=aA=abB=abb對G1文法，abb的推導(dǎo)序列是：S=Bb=Abb=abb對G2文法，aabca的推導(dǎo)序列是：S=Aa=Cca=Babca=aabca對G2文法，aabca的推導(dǎo)序列是：S=aB=aabC=aabcA=aabca（4）對串a(chǎn)cbd來說，G1,G1文法都不能產(chǎn)生。11將右線性文法化為左線性文法的算法：o （1）對于G中每一個形如AaB的產(chǎn)生式且A是開始符，將其變?yōu)锽a,否則若A不是開始符，BAa; o （

19、2）對于G中每一個形如Aa的產(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）將具有動作的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)化簡后S0和S1作為一個狀態(tài)，S5和S6作為一個狀態(tài)。狀態(tài)轉(zhuǎn)換圖如圖15從略。16從略。 (1)

20、r*表示的正規(guī)式集是,r,rr,rrr, (|r)*表示的正規(guī)式集是, ,r,rr,rrr,=,r,rr,rrr,|rr*表示的正規(guī)式集是,r,rr,rrr,(r*)*=r*=,r,rr,rrr,所以四者是等價的。(2)（rs）*r表示的正規(guī)式集是,rs,rsrs,rsrsrs,r =r,rsr,rsrsr,rsrsrsr,r(sr)* 表示的正規(guī)式集是r,sr,srsr,srsrsr, = r,rsr,rsrsr,rsrsrsr,所以兩者等價。18 寫成方程組S=aT+aS(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*c G1: S=aA+B(

22、)c + ab*bS=(ab*ab|b)ca+ab*ba +ab*=(ab*ab|b)ca| ab*ba| ab*20 識別此語言的正規(guī)式是S=LABELd(d|,d)*; 從略。 21 從略。22 構(gòu)造NFA其余從略。 23 下面舉一個能夠識別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%upperA-Z%ONEreturn

23、ON;TWOreturn TW;THREEreturn THRE;TENreturn TE;TWENTYreturn TWENT;HUNDREDreturn HUNDRE; +|treturn WHITE;nreturn0;%main(int argc,char *argv)int c,i=0;char tmp30;if (argc=2)if (yyin=fopen(argv1,r)=NULL)printf(cant open %sn,argv1);exit(0);while (c=yylex()!=0)switch(c)case ON:c=yylex();if (c=0) goto i+=1

24、;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(%dn,i);return;24 （1）Dn表示的正規(guī)集是長度為2n任意a和b組成的字符串。此正規(guī)式的長度是2n 用來識別Dn的DFA至多需要2n1個狀態(tài)。 25 從略。26（1）由括住的,中間由任意個

25、非組成的字符串, 如,a,defg等等。（2）匹配一行僅由一個大寫字母和一個數(shù)字組成的串，如A1,F8,Z2等。（3）識別rn和除數(shù)字字符外的任何字符。由和括住的，中間由兩個或者非和n組成的任意次的字符串。如, a,bb,def，等等 27OXx0-9*a-fA-F*|0-9+|(a-zA-Z|Xx0-70-7a-fA-F|0010-70-7|a-z)28a-zA-Z_+0-9*a-zA-Z_*29 參考程序如下：%#include #include #include #define UPPER2#define WHITE3%upperA-Z%upper+returnUPPER;t| +re

26、turnWHITE;%main(int argc,char *argv)int c,i;if (argc=2)if (yyin=fopen(argv1,r)=NULL)printf(cant open %sn,argv1);exit(0); while (c=yylex()!=EOF)if (c=2)for (i=0;yytexti;i+)printf(%c,tolower(yytexti);yytext0=000;if (c=3)printf( );else printf(%s,yytext);return;yywrap()return ;30 從略。第四章習(xí)題解答第四章習(xí)題參考答案 1

27、.解： (1)S(S)Z21|()Z21|SZ31|Z31A(S)Z22|()Z22|SZ32|Z32B(S)Z23|()Z23|SZ33|Z33Z11|AZ11|BZ21Z12AZ12|BZ22Z13AZ13|BZ23Z21Z11Z22|Z12Z23Z13Z31Z21Z32Z22Z33|Z23(2)SbZ11|aZ21AbZ12|aZ22Z11| AZ21Z12AZ22Z21SZ21Z22|SZ22(3)S(T)Z11 | aZ11 | Z11S(T)Z12 | aZ12 | Z12Z11| Z21Z12Z22Z21,SZ21Z22|,SZ22 2.解： SAbB1,1.1(表示第1步，用產(chǎn)

28、生式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.2 3.解：以下Save表示save token_pointer value, Restore表示restore token_pointer value。 (1)文法沒有左遞歸。F

29、unction P:boolean;Begin Save;P:=true;If next_token=”begin” thenIf next_token=d thenIf next_token=; thenIf X thenIf next_token=”end” then return;Restore;P:=false;End;Function X:boolean;BeginSave;X:=true;If next_token=d thenIf next_token=; thenIf X then return;Restore;If next_token=s thenIf Y then ret

30、urn;Restore;X:=false;End;Function Y:boolean;BeginSave;Y=true;If next_token=; thenIf next_token=s thenIf Y then return;Restore;End;(2)消去文法左遞歸，并記為：Pbegin S endSA|CAV:=EC if E then SEVEE +VE|VIFunction P:boolean;BeginSave;P:=true;If next_token=”begin” thenIf S thenIf next_token=”end” then return;Restor

31、e;P:=false;End;Function A:boolean;BeignSave;A:=true;If V thenIf next_token=”:=” thenIf E then return;Restore;A:=flase;End;Function S:boolean;BeignSave;S:=true;If A then return;Restore;If C then return;Restore;S:=false;End;Function C:boolean;BeginSave;C:=true;If next_token=”if” thenIf E then If next_

32、token=”then” thenIf S then return;Restore;C:=false;End;Function E:boolean;BeginSave;E:=true;If V thenIf Ep then return;Restore;E:=false;End;Function Ep:boolean;BeingSave;Ep:=true;If next_token=+ thenIf V thenIf E then return;Return;End; 4.解： 5.證：因為是左遞歸文法，所以必存在左遞歸的非終結(jié)符A，及形如A|的產(chǎn)生式,且T* Ad. 則first(Ad) f

33、irst(),從而first() first()，即文法不滿足LL（1）文法條件。得證。 6.證：LL（1）文法的分析句子過程的每一步，永遠(yuǎn)只有唯一的分析動作可進(jìn)行。現(xiàn)在，假設(shè)LL(1)文法G是二義性文法，則存在句子，它有兩個不同的語法樹。即存在著句子有兩個不同的最左推導(dǎo)。從而可知，用LL（1）方法進(jìn)行句子的分析過程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進(jìn)行語法分析，即LL（1）分析動作存在不確定性。與LL（1）性質(zhì)矛盾。所以，G不是LL(1)文法。 7.解： (1)D產(chǎn)生式兩個候選式fD和f的first集交集不為空，所以不是LL(1)的。(2)此文法具有左遞歸性，據(jù)第5題結(jié)論，不是

36、造算法可知，F(xiàn)IRST(A)中一切非加到FOLLOW(A)中，則aFOLLOW(A)；又因為aFIRST(ag),所以兩集合相交非空，因此，G不是LL(1)文法；與前提矛盾，假設(shè)不成立，得證。解： (1)SA(a)bS=A=(=)b不是簡單優(yōu)先文法。(2)SRT()a,S=R=T(=a,=是簡單優(yōu)先文法。(3) SR(a,)S=(=,=是簡單優(yōu)先文法。o 首先消去無用產(chǎn)生式ZE, ZE+T SZT#i()SZ=T#=(=化簡后的文法是簡單優(yōu)先文法；解： SA/ASA=aA和/之間同時有關(guān)系=和,所以不是簡單優(yōu)先文法；提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡單）

37、，使得對文法的輸入比較簡單的同時(需要把輸入轉(zhuǎn)化為計算機(jī)語言表示，這種轉(zhuǎn)化應(yīng)該盡量簡單)，能夠比較簡單地構(gòu)造3個基本關(guān)系矩陣（=，LEAD和LAST）。證明：設(shè)xjxj+1.xi是滿足條件xj-1xi+1的最左子串。由=關(guān)系的定義，可知xjxj+1.xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj-1xj可知xj-1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。同理，xi為某產(chǎn)生式的尾符號。即存在產(chǎn)生式 Uxjxj+1.xi設(shè) ST* aUb其中，aT*. xj-1 ,bT* xi+1. 對于aUb可構(gòu)造一語法樹，并通過對其剪枝（歸約），直到U出現(xiàn)在句柄中。從而xjxj+1.xi必為句柄。反之，若xj

38、xj+1.xi是句柄，由簡單優(yōu)先關(guān)系的定義，必滿足上述條件。解：為描述方便，用符號表示各非終結(jié)符：D=,L=, V= ,T=，a=VAR,則消去V，并采用分層法改寫文法，得到：DaW:T;WLLL,i|iTr|n|b|c 其全部簡單優(yōu)先關(guān)系是：DWTLa:;,ir|n|b|cDW=T=L=a=:=ir|n|b|c是簡單優(yōu)先文法。證：設(shè)STna,我們對n用歸納法，證明a不含兩個非終結(jié)符相鄰情況。n=1時，STa,即Sa是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。設(shè)n=k時，上述結(jié)論成立，且設(shè)STkdAb，由歸納假設(shè)，A兩側(cè)必為終結(jié)符。我們再進(jìn)行一步推導(dǎo)，得STkdAbTdub, 其中，Au是文

39、法中的產(chǎn)生式，由定義，u中不含兩個非終結(jié)符相鄰情況，從而dub兩個非終結(jié)符相鄰情況。得證。證：由于G不是算符文法，G中至少有一個產(chǎn)生式，其右部含有兩個非終結(jié)符相鄰的情況。不失一般性，設(shè)其形為UxABy,x,yV*,由于文法不含無用產(chǎn)生式，則必存在含有U的句型dUb，即存在推導(dǎo)ST*dUbTdxAByb.得證。文法為：EEA | AAA*T | A/T | TTT+V | T-V | VVi | (E) 解：（1）構(gòu)造算符優(yōu)先矩陣：-*（）i#-*(=I#*ay,則a可歸約為a =Ua*UA=b，b是G的一個句型，這與G是算符文法矛盾，所以，a中含有a的短語必含U。（2）的證明與（1）類

40、似，略。證：（1）對于a=aU是句型，必有ST*a(=aU) T+ab.即在歸約過程中,b先于a被歸約,從而,ab.對于(2)的情況類似可以證明。證明略. 證明略. 證明略。證：(1) 用反證法。設(shè)沒有短語包含b但是不包含a，則a,b一定同時位于某個短語中，從而必使得a,b同時位于同一產(chǎn)生式的右部，所以a=b，與G是算符優(yōu)先文法（=與不能并存）矛盾。（2）、（3）類似可證。證：只要證u中不含有除自身以外的素短語。設(shè)有這樣的素短語存在，即存在bxby是素短語，其中1x或者yn之一成立。因素短語是短語，根據(jù)短語定義，則必有：1xTbx-1bx或yby+1，與bx-1=bx及 by=by+

41、1矛盾，得證。提示：根據(jù)27題的結(jié)論，只要證u是句型的短語，根據(jù)=關(guān)系的定義容易知道u是句型的素短語。證：與28題的不同點只是a0,an+1可以是#,不影響結(jié)論。證：設(shè)不能含有素短語，則只能是含有短語（不能含有終結(jié)符號），則該短語只能含有一個非終結(jié)符號，否則不符合算符文法定義，得證。解：（1）算符優(yōu)先矩陣：+*（）i#+*(=I#=a#（2）用Bell方法求優(yōu)先函數(shù)的過程如下：a#f5751g5561（3）顯然，文法不是算符優(yōu)先文法, 所以不能線性化。略。 35解：（1）識別全部活前綴的DFA如下：（以表格的形式來表示，很容易可以轉(zhuǎn)化為圖的形式，本章中其余的題目也是采用這種形式表

42、示。）狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SSaSbSaScSabSaI1I2I1S SI2SaSbSaScSabSaSbSaScSabSabI3I2I4I3SaSbSaScbcI5I6I4SabI5SaSbI6SaSc（2）識別全部活前綴的DFA如下：狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SScASccBScI1II1S SI2ScASccBAcAAaAcaI3I4I5I3ScAI4SccBAcABccBBbAcAAaBAcbaI6I5I7I8I5I5AaI6SccBI7BccBAcAAcAAaCAaI9I10I5I8BbI9BccBAcABccBBbAcAAaBAcbaI11I10I7I

43、8I5I10AcAI11BccB所求的LR(0)項目規(guī)范族C=I0,I1,I11（3）狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SSaSSbSaSSSScScaI1I2I3I1S SI2ScI3SaSSbSaSSSSaSSbSaSSSScScaI4I2I3I4SaSSbSaSSSSaSSbSaSSSScScaI5I2I3I5SaSSbSaSSSSaSSbSaSSSScSabcI7I3I6I2I6SaSSbI7SaSSS（4）狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SSAAAbAaSAaI1I2I3I1S SI2SASAbbI4I3AaI4SAb36解：（1）是LR(0)文法，其SLR(1)分析表如

44、下：FOLLOW(S)=#,b,cACTIONGOTOabc#S0S211ACC2S2S433S5S64R3R3R35R1R1R16R2R2R2（2）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=FOLLOW(A)=FOLLOW(B)=#ACTIONGOTOabc#SAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5（3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=#,a,b,cACTIONGOTOabc#S0S3S211ACC2R3R3R3R33S3S244S3S255S3S6S

45、276R1R1R1R17R2R2R2R2（4）因為I2中含有沖突項目，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=#b=(所以可以用SLR(1)規(guī)則解決沖突), FOLLOW(A)=b,#ACTIONGOTOab#SA0S3121ACC2S4R13R3R34R2R237解：狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SS(SRSaS(aI1I2I3I1S SI2S(SRS(SRSaS(aI4I2I3I3SaI4S(SRS(SRSaR,SRR)a(R,)I3I2I5I6I7I5S(SRI6R, SRS(SRSaS(aI8I2I3I7R) I8R,SRR,SRR),RI7I6I9I9R,SRLR(0)分析表如下：ACTIONGOTOa(),#SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可見是LR(0)文法。38解：（1）狀態(tài)項目集經(jīng)過的符號到達(dá)的狀態(tài)I0S SSSabSbRSbI1I2I1(沖突項目)S SSSabaaccI3I2SbRRSRaSSabSbRRSabI4I5I6I2I3SSabbI7I4SbRr2I5(沖突項目)RSSSabaI

展開閱讀全文

溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

點擊下載此資源

《編譯原理》西北工業(yè)大學(xué)第三版課后答案.doc

最新文檔

相關(guān)資源

相關(guān)搜索