資源描述：
《編譯原理作業(yè)20150515(答案)》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
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、5
35、7
36、9E—>2
37、4
38、6
39、82.一個上下文無關文法生成句子abbaa的推導樹如下：SAB
40、SaSBBAa11?bba（1）給出該句子的相應的最左推導，最右推導。（2）該文法的產生式集合P可能有哪些元素？（3）找出該句子的所有短語，簡單短語，句柄?！窘狻浚海?）最左推導：S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推導：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)產生式集合P：S—>ABS
41、Aa
42、?A—>aB—>SBB
43、b(3)短語：a,?,b,bb,aa,abbaa直接短語：a,?,b句柄：a3、給出生成下述語言的上下文無關文法：(1){anbnam
44、bm
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.構造一個狀態(tài)數(shù)最小的DFA，它接受∑={0,1}上所有倒數(shù)第二個字符為1的字符串。（編輯：張超）解：①構造正規(guī)式：（0│1）*1（0│1）②由正規(guī)式構造NFA：③NFA轉化為DFA：T0=ε－closure（{0}）={0}用子集構造法求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
50、={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}）∴無等價狀態(tài)。∵沒有找到多余狀態(tài)，∴無多余狀態(tài)?！嗌蠄D為最小化的DFA。2、將下圖的NFA確定化為DFA，并最小化。（編輯：張超）解：用子集構造法求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，
51、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是等價的，∴得到最小化的DFA如下：11第5-7章課后作業(yè)（含答案）1、將文法G[S]改寫為等價的G′[S]，使G′[S]不含左遞歸和左公共因子。G[S]：S→bSAe
52、bAA→Abd
53、dc
54、a【解】：G[S]：S→bS’S’→SAe
55、AA→(dc
56、a)A’A’→bdA’
57、ε2、有文法G[S]：S→ABfA→BbS
58、eB→dAg
59、ε證明文法G是LL(1)文法，并構造預測分析表【
60、解】：①計算FIRST、FOLLOW、SELECT集產生式FIRSTFOLLOWSELECT左部右部SABfdbe#gdfdbeABbSdbgdfdbeeeBdAgdbfdεεbf由上表可知：該文法中，所有相同左部不同右部的產生式SELECT集兩兩相交均為空集，所以該文法為LL(1)文法。②構造預測分析表fbedg#SABfABfABfABbSeBbSBεεdAg113、已知文法G[S]：S→(A)│a│bA→AcS│S構造文法的算符優(yōu)先矩陣，并判斷該文法是否是算符優(yōu)先文法?！窘狻浚孩偻卣乖撐姆ǎ篠’→#S#S→(A)│a│bA→AcS│S②計算FIRSTVT與LASTVT:FIRSTVTLA
61、STVTS’##S(ab)abAc(abc)ab③計算算符優(yōu)先關系：#=#(=)##LASTVT(A)>)LASTVT(A)>c④構造算符優(yōu)先矩陣（注：按終結符出現(xiàn)順序列表）:()abc#(<=<<<)>>>a>>>b>>>c<><<>#<<<=⑤因為該文法G為2型文法，且不含空產生式，沒有形如U?…VW…的
