編譯原理作業(yè)20150515(答案)

1、第3章作業(yè)【編輯人：陳芳芳】1. 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求：（1）允許0打頭；（2）不允許0打頭。 【解】：(1) 允許0打頭且含0的偶正整數(shù)集合的文法為： N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|8(2) 不允許0打頭的偶正整數(shù)集合的文法為： R(D|E)N|E N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|8(3) 允許0打頭的偶正整數(shù)集合的文法為： S0S|RR(D|E)N|E N(0|D|E)N|(E|0) D1|3|5|7|9 E2|4|6|82.一個(gè)上下文無(wú)關(guān)文法生成句子abbaa的推導(dǎo)樹(shù)如下：S A B S a S

2、 B B A a b b a（1）給出該句子的相應(yīng)的最左推導(dǎo)，最右推導(dǎo)。（2）該文法的產(chǎn)生式集合P可能有哪些元素？（3）找出該句子的所有短語(yǔ)，簡(jiǎn)單短語(yǔ)，句柄?！窘狻浚海?）最左推導(dǎo)：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推導(dǎo)：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2) 產(chǎn)生式集合P：SABS | Aa| AaBSBB | b(3) 短語(yǔ)：a , , b , bb , aa , abbaa 直接短語(yǔ)：a , , b 句柄：a3、給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：(1)anbnambm |

3、 n, m = 0(2)1n0m1m0n | n, m = 0【解】：（1）SAA AaAb | （2）S1S0 | A A0A1 | 第4章課后作業(yè)1. 構(gòu)造一個(gè)狀態(tài)數(shù)最小的DFA，它接受=0,1上所有倒數(shù)第二個(gè)字符為1的字符串。（編輯：張超）解： 構(gòu)造正規(guī)式：（01）* 1（01） 由正規(guī)式構(gòu)造NFA： NFA轉(zhuǎn)化為DFA ：T0=closure（0）=0用子集構(gòu)造法求DFA狀態(tài)，T0為初態(tài)，T2，T3為終態(tài)。狀態(tài)closure（move（Ti，0）closure（move（Ti，1）T0=000,1T1=0,10,20,1,2T2=0,200,1T3=0,1,20,20,1,2用0,1,

4、2,3代表T0，T1，T2，T3，得到如下DFA ：最小化DFA ：P0=（0,1，2,3）P1=（0，1，2，3）無(wú)等價(jià)狀態(tài)。 沒(méi)有找到多余狀態(tài)， 無(wú)多余狀態(tài)。 上圖為最小化的DFA。2、將下圖的NFA確定化為DFA，并最小化。（編輯：張超）解：用子集構(gòu)造法求DFA狀態(tài)，T0為初態(tài)，T3為終態(tài)。狀態(tài)closure（move（Ti，a）closure（move（Ti，b）T0=X，1，21，21，2，3T1=1，21，21，2，3T2=1，2，31，2，Y1，2，3T3=1，2，Y1，21，2，3用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ：最小化：0，1，2 30，1 2 3

5、0，1 2 30和1是等價(jià)的， 得到最小化的DFA 如下 ：第5-7章課后作業(yè)（含答案）1、將文法GS 改寫(xiě)為等價(jià)的GS，使GS不含左遞歸和左公共因子。GS： SbSAe|bA AAbd | dc | a【解】：GS：SbS SSAe|A A(dc|a)A A bd A |2、有文法GS：SABf ABbS|e BdAg| 證明文法G是LL(1)文法，并構(gòu)造預(yù)測(cè)分析表【解】：計(jì)算FIRST、FOLLOW、SELECT集產(chǎn)生式FIRSTFOLLOWSELECT左部右部SABfd b e# g d fd b eABbS d bg d fd beeeBdAgd b fd b f 由上表可知：該文法中

6、，所有相同左部不同右部的產(chǎn)生式SELECT集兩兩相交均為空集，所以該文法為L(zhǎng)L(1)文法。 構(gòu)造預(yù)測(cè)分析表fbedg#SABfABfABfABbSeBbSBdAg3、已知文法GS：S(A)ab AAcSS 構(gòu)造文法的算符優(yōu)先矩陣，并判斷該文法是否是算符優(yōu)先文法。【解】：拓展該文法：S#S# S(A)ab AAcSS計(jì)算FIRSTVT與LASTVT:FIRSTVTLASTVTS#S( a b) a bAc ( a bc ) a b計(jì)算算符優(yōu)先關(guān)系：# = # ( = ) # FIRSTVT(S) ( FIRSTVT(A) c # LASTVT(A) ) LASTVT(A) c構(gòu)造算符優(yōu)先矩陣（注：按終結(jié)符出現(xiàn)順序列表）:()abc#( = ab c # b then x := m - k else y := m + k;【解】 對(duì)應(yīng)的四元式序列為： 100（Jnz， A， ， 108 ） 101（J ， ， ， 102 ） 102（Jnz， B， ， 104 ） 103（J ， ， ， 106 ） 104（Jnz， C， ， 106 ） 105（J ， ， ， 108 ） 106（Jnz， D， ， 108 ） 107（J ， ， ， 116 ） 108（J，a ，b ， 110 ） 109（J ， ， ， 113 ） 110