資源描述：
《編譯原理作業(yè)20150515(答案)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第3章作業(yè)【編輯人：陳芳芳】1.寫一文法，使其語言是偶正整數(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、
35、5
36、7
37、9E—>2
38、4
39、6
40、82.一個上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下：SABSaSBBAa11?bba（1）給出該句子的相應(yīng)的最左推導(dǎo)，最右推導(dǎo)。（2）該文法的產(chǎn)生式集合P可能有哪些元素？（3）找出該句子的所有短語，簡單短語，句柄?！窘狻浚海?）最左推導(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)生式集
41、合P：S—>ABS
42、Aa
43、?A—>aB—>SBB
44、b(3)短語：a,?,b,bb,aa,abbaa直接短語：a,?,b句柄：a3、給出生成下述語言的上下文無關(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)造一個狀態(tài)數(shù)最小的DFA，它接受∑={0,1}上所有倒數(shù)第二個字符為1的字符串。（編輯：張超）解：①構(gòu)造正規(guī)式：（0│1）*1（0│1）②由正規(guī)式構(gòu)造NFA：③N
50、FA轉(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={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}）∴無等價
51、狀態(tài)。∵沒有找到多余狀態(tài)，∴無多余狀態(tài)?！嗌蠄D為最小化的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，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：最小
52、化：①{0，1，2}{3}②{0，1}{2}{3}③{0，1}{2}{3}0和1是等價的，∴得到最小化的DFA如下：11第5-7章課后作業(yè)（含答案）1、將文法G[S]改寫為等價的G′[S]，使G′[S]不含左遞歸和左公共因子。G[S]：S→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ù)測分析表【解】：①計算FIRST、FOLLOW、SELEC
61、T集產(chǎn)生式FIRSTFOLLOWSELECT左部右部SABfdbe#gdfdbeABbSdbgdfdbeeeBdAgdbfdεεbf由上表可知：該文法中，所有相同左部不同右部的產(chǎn)生式SELECT集兩兩相交均為空集，所以該文法為LL(1)文法。②構(gòu)造預(yù)測分析表fbedg#SABfABfABfABbSeBbSBεεdAg113、已知文法G[S]：S→(A)│a│bA→AcS│S構(gòu)造文法的算符優(yōu)先矩陣，并判斷該文法是否是算符優(yōu)先文法?！窘狻浚孩偻卣乖撐姆ǎ篠’→#S#S→(A)│a│bA→AcS│S②計算FI
62、RSTVT與LASTVT:FIRSTVTLASTVTS’##S(ab)abAc(abc)ab③計算算符優(yōu)先關(guān)系：#=#(=)##LASTVT(A)>)LASTVT(A)>c④構(gòu)造算符優(yōu)先矩陣（注：按終結(jié)符出現(xiàn)順序列表）:()abc#(<=<<<)>>>a>>>b>>>c<><<>#<<<=⑤因為該文法G為2型文法，且不含空產(chǎn)生式，沒有形如U?…VW…的
