資源描述：
《編譯原理及實(shí)踐教程(黃賢英王柯柯編著)習(xí)題答案.doc》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第2章參考答案：1，2，3：解答：略！4.解答：?A：①?B：③?C：①?D：②?5.解答：用E表示<表達(dá)式>，T表示<項(xiàng)>，F(xiàn)表示<因子>，上述文法可以寫(xiě)為：E→T
2、E+TT→F
3、T*FF→(E)
4、i最左推導(dǎo)：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最右推導(dǎo)：E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i=>F+i+i=>i+i+i
5、E=>E+T=>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的語(yǔ)法樹(shù)如下圖所示。i+i+i、i+i*i的語(yǔ)法樹(shù)6.解答：(1)終結(jié)符號(hào)為：{or,and,not,(,),true,false}非終結(jié)符號(hào)為：{bexpr,bterm,bfactor}開(kāi)始符號(hào)為：bexpr(2)句子not(trueorfalse)的語(yǔ)法樹(shù)為：7.解答：(1)把a(bǔ)nbnci分成anbn和ci兩部分，分別由兩個(gè)非終結(jié)符號(hào)生成，因此，生成此文法的產(chǎn)生式為：S→ABA→aAb
6、abB→cB
7、e(2)令S為開(kāi)始符
8、號(hào)，產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號(hào)，產(chǎn)生含相同個(gè)數(shù)的a和b的所有串，則產(chǎn)生式如下：S→aE
9、Ea
10、bSS
11、SbS
12、SSbE→aEbE
13、bEaE
14、e(3)設(shè)文法開(kāi)始符號(hào)為S，產(chǎn)生的w中滿(mǎn)足
15、a
16、≤
17、b
18、≤2
19、a
20、。因此，可想到S有如下的產(chǎn)生式（其中B產(chǎn)生1到2個(gè)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ù)頭〉
35、解法二：文法G=({S,A,B,C,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有如下兩個(gè)不同的最左推導(dǎo)：S=>aSbS=>abS=>abaSbS=>ababS=>abab??S=>aSbS=>abSaSbS
65、=>abaSbS=>ababS=>abab??所以此文法是二義性的。(2)句子abab的兩個(gè)相應(yīng)的最右推導(dǎo)：??S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab??S=>aSbS=>aSb=>abSaSb=>abSab=>abab(3)句子abab的兩棵分析樹(shù)：(a)(b)(4)此文法產(chǎn)生的語(yǔ)言是：在{a，b}上由相同個(gè)數(shù)的a和b組成的字符串。9，10：解答：略！第3章習(xí)題解答：1.解答：(1)??√??(2)?√??(3)??×(4)??×??(5)?√??(6)√2.[分析]???有限自動(dòng)機(jī)分為確定有限自動(dòng)機(jī)和非確定有限自動(dòng)
66、機(jī)。確定有限自動(dòng)機(jī)的確定性表現(xiàn)在映射d：Q×VT-->q是單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)q∈Q和輸入字符串a(chǎn)∈VT，d(q,a)唯一確定下一個(gè)狀態(tài)。顯然，本題給出的是一個(gè)確定的有限自動(dòng)機(jī)，它的狀態(tài)轉(zhuǎn)換圖是C中的②。????它所接受的語(yǔ)言可以用正則表達(dá)式表示為00(0
67、1)*，表示的含義為由兩個(gè)0開(kāi)始的后跟任意個(gè)（包含0個(gè)）0或1組成的符號(hào)串的集合。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)
79、(0
80、1)*(4)1*
81、1*0(0
82、10)*(1
83、e)(5)a*b*c*…z*(6)(0
84、10*1)*1(7)(00
85、11)*((01
86、10)(00
87、11)*(01
88、10)(00
89、11)*)*(8)[分析]設(shè)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ù)個(gè)0和奇數(shù)個(gè)1。?S2是{0,1}上的串，含有偶數(shù)個(gè)0和偶數(shù)個(gè)1。考慮有一個(gè)自動(dòng)機(jī)M1接受S1，那么自動(dòng)機(jī)M1如下：和L(M1)等價(jià)的正規(guī)式，即S1為：((00
97、11)
98、(01
99、10)(00
100、11)
101、*(01
102、10))*(01
103、10)(00
104、11)*類(lèi)似的考慮有一個(gè)自動(dòng)機(jī)M2接受
