資源描述：
《編譯原理及實踐教程(黃賢英 王柯柯 編著) 習題答案》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第2章參考答案：1，2，3：解答：略！4.解答：?A：①?B：③?C：①?D：②?5.解答：用E表示<表達式>，T表示<項>，F(xiàn)表示<因子>，上述文法可以寫為：E→T
2、E+TT→F
3、T*FF→(E)
4、i最左推導：E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T=>i+i+F=>i+i+iE=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i最右推導：E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i=>F+i+i=>i+i+iE=>E+T
5、=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*ii+i+i和i+i*i的語法樹如下圖所示。i+i+i、i+i*i的語法樹6.解答：(1)終結(jié)符號為：{or,and,not,(,),true,false}非終結(jié)符號為：{bexpr,bterm,bfactor}開始符號為：bexpr(2)句子not(trueorfalse)的語法樹為：7.解答：(1)把anbnci分成anbn和ci兩部分，分別由兩個非終結(jié)符號生成，因此，生成此文法的產(chǎn)生式為：S→ABA→aAb
6、abB→cB
7、e(2)令S為開始符號，產(chǎn)生的w中a的個數(shù)恰
8、好比b多一個，令E為一個非終結(jié)符號，產(chǎn)生含相同個數(shù)的a和b的所有串，則產(chǎn)生式如下：S→aE
9、Ea
10、bSS
11、SbS
12、SSbE→aEbE
13、bEaE
14、e(3)設文法開始符號為S，產(chǎn)生的w中滿足
15、a
16、≤
17、b
18、≤2
19、a
20、。因此，可想到S有如下的產(chǎn)生式（其中B產(chǎn)生1到2個b）：S→aSBS
21、BSaSB→b
22、bb(4)解法一：S→〈奇數(shù)頭〉〈整數(shù)〉〈奇數(shù)尾〉?????
23、〈奇數(shù)頭〉〈奇數(shù)尾〉?????
24、〈奇數(shù)尾〉?〈奇數(shù)尾〉→1
25、3
26、5
27、7
28、9?〈奇數(shù)頭〉→2
29、4
30、6
31、8
32、〈奇數(shù)尾〉?〈整數(shù)〉→〈整數(shù)〉〈數(shù)字〉
33、〈數(shù)字〉?〈數(shù)字〉→0
34、〈奇數(shù)頭〉解法二：文法G=({S,A,B,C,
35、D},{0,1,2,3,4,5,6,7,8,9},P,S)S→AB
36、BA→AC
37、DB→1
38、3
39、5
40、7
41、9D→2
42、4
43、6
44、8
45、BC→0
46、D(5)文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9},S,P)S→N0
47、N5N→MD
48、eM→1
49、2
50、3
51、4
52、5
53、6
54、7
55、8
56、9D→D0
57、DM
58、e(6)G[S]：S→aSa
59、bSb
60、cSc
61、a
62、b
63、c
64、e8.解答：(1)句子abab有如下兩個不同的最左推導：S=>aSbS=>abS=>abaSbS=>ababS=>abab??S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab??所
65、以此文法是二義性的。(2)句子abab的兩個相應的最右推導：??S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab??S=>aSbS=>aSb=>abSaSb=>abSab=>abab(3)句子abab的兩棵分析樹：(a)(b)(4)此文法產(chǎn)生的語言是：在{a，b}上由相同個數(shù)的a和b組成的字符串。9，10：解答：略！第3章習題解答：1.解答：(1)??√??(2)?√??(3)??×(4)??×??(5)?√??(6)√2.[分析]???有限自動機分為確定有限自動機和非確定有限自動機。確定有限自動機的確定性表現(xiàn)在映射d：Q×VT-->q是單
66、值函數(shù)，也就是說，對任何狀態(tài)q∈Q和輸入字符串a(chǎn)∈VT，d(q,a)唯一確定下一個狀態(tài)。顯然，本題給出的是一個確定的有限自動機，它的狀態(tài)轉(zhuǎn)換圖是C中的②。????它所接受的語言可以用正則表達式表示為00(0
67、1)*，表示的含義為由兩個0開始的后跟任意個（包含0個）0或1組成的符號串的集合。2.解答：A:④??B:③??C:②??D:②??E:④3，4．解答：略！5．解答：6．解答：(1)(0
68、1)*01(2)((1
69、2
70、…
71、9)(0
72、1
73、2
74、…
75、9)*
76、e)(0
77、5)(3)(0
78、1)*(011)(0
79、1)*(4)1*
80、1*0(0
81、10)*(1
82、e)(5)a*b*c*
83、…z*(6)(0
84、10*1)*1(7)(00
85、11)*((01
86、10)(00
87、11)*(01
88、10)(00
89、11)*)*(8)[分析]設S是符合要求的串，
90、S
91、=2k+1(k≥0）。則S→S10
92、S21，
93、S1
94、=2k(k>0），
95、S2
96、=2k(k≥0）。且S1是{0,1}上的串，含有奇數(shù)個0和奇數(shù)個1。?S2是{0,1}上的串，含有偶數(shù)個0和偶數(shù)個1?？紤]有一個自動機M1接受S1，那么自動機M1如下：和L(M1)等價的正規(guī)式，即S1為：((00
97、11)
98、(01
99、10)(00
100、11)*(01
101、10))*(01
102、10)(00
103、11)*類似的考慮有一個自動機M2接受
