資源描述：
《編譯原理作業(yè)20150515(答案)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第3章作業(yè)【編輯人：陳芳芳】1.寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求：（1）允許0打頭；（2）不允許0打頭。【解】：(1)允許0打頭且含0的偶正整數(shù)集合的文法為：N—>(0
2、D
3、E)N
4、(E
5、0)D—>1
6、3
7、5
8、7
9、9E—>2
10、4
11、6
12、8(2)不允許0打頭的偶正整數(shù)集合的文法為：R—>(D
13、E)N
14、EN—>(0
15、D
16、E)N
17、(E
18、0)D—>1
19、3
20、5
21、7
22、9E—>2
23、4
24、6
25、8(3)允許0打頭的偶正整數(shù)集合的文法為：S—>0S
26、RR—>(D
27、E)N
28、EN—>(0
29、D
30、E)N
31、(E
32、0)D—>1
33、3
34、5
35、7
36、9E—>2
37、4
38、6
39、82.一個(gè)上下文無(wú)
40、關(guān)文法生成句子abbaa的推導(dǎo)樹(shù)如下：SABSaSBBAa11?bba（1）給出該句子的相應(yīng)的最左推導(dǎo)，最右推導(dǎo)。（2）該文法的產(chǎn)生式集合P可能有哪些元素？（3）找出該句子的所有短語(yǔ)，簡(jiǎn)單短語(yǔ)，句柄。【解】：（1）最左推導(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：S—>ABS
41、Aa
42、?A—>aB—>SBB
43、b(3)短語(yǔ)：a,?,b,bb,aa,abba
44、a直接短語(yǔ)：a,?,b句柄：a3、給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：(1){anbnambm
45、n,m>=0}(2){1n0m1m0n
46、n,m>=0}【解】：（1）S—>AAA—>aAb
47、?（2）S—>1S0
48、AA—>0A1
49、?11第4章課后作業(yè)1.構(gòu)造一個(gè)狀態(tài)數(shù)最小的DFA，它接受∑={0,1}上所有倒數(shù)第二個(gè)字符為1的字符串。（編輯：張超）解：①構(gòu)造正規(guī)式：（0│1）*1（0│1）②由正規(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（mo
50、ve（Ti，0））ε－closure（move（Ti，1））T0={0}{0}{0,1}T1={0,1}{0,2}{0,1,2}T2={0,2}{0}{0,1}T3={0,1,2}{0,2}{0,1,2}用0,1,2,3代表T0，T1，T2，T3，得到如下DFA：11④最小化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)ε－clos
51、ure（move（Ti，a））ε－closure（move（Ti，b））T0={X，1，2}{1，2}{1，2，3}T1={1，2}{1，2}{1，2，3}11T2={1，2，3}{1，2，Y}{1，2，3}T3={1，2，Y}{1，2}{1，2，3}用0,1,2,3代表T0，T1，T2，T3，得到如下DFA：最小化：①{0，1，2}{3}②{0，1}{2}{3}③{0，1}{2}{3}0和1是等價(jià)的，∴得到最小化的DFA如下：11第5-7章課后作業(yè)（含答案）1、將文法G[S]改寫(xiě)為等價(jià)的G′[S]，使G′[S]不含左遞歸和左公共因子。G[S]：S→
52、bSAe
53、bAA→Abd
54、dc
55、a【解】：G[S]：S→bS’S’→SAe
56、AA→(dc
57、a)A’A’→bdA’
58、ε2、有文法G[S]：S→ABfA→BbS
59、eB→dAg
60、ε證明文法G是LL(1)文法，并構(gòu)造預(yù)測(cè)分析表【解】：①計(jì)算FIRST、FOLLOW、SELECT集產(chǎn)生式FIRSTFOLLOWSELECT左部右部SABfdbe#gdfdbeABbSdbgdfdbeeeBdAgdbfdεεbf由上表可知：該文法中，所有相同左部不同右部的產(chǎn)生式SELECT集兩兩相交均為空集，所以該文法為L(zhǎng)L(1)文法。②構(gòu)造預(yù)測(cè)分析表fbedg#SABfABfAB
61、fABbSeBbSBεεdAg113、已知文法G[S]：S→(A)│a│bA→AcS│S構(gòu)造文法的算符優(yōu)先矩陣，并判斷該文法是否是算符優(yōu)先文法?！窘狻浚孩偻卣乖撐姆ǎ篠’→#S#S→(A)│a│bA→AcS│S②計(jì)算FIRSTVT與LASTVT:FIRSTVTLASTVTS’##S(ab)abAc(abc)ab③計(jì)算算符優(yōu)先關(guān)系：#=#(=)##LASTVT(A)>)LASTVT(A)>c④構(gòu)造算符優(yōu)先矩陣（注：按終結(jié)符出現(xiàn)順序列表）:()abc#(<=<<<)
62、>>>a>>>b>>>c<><<>#<<<=⑤因?yàn)樵撐姆℅為2型文法，且不含空產(chǎn)生式，沒(méi)有形如U?…VW…的
