資源描述：
《編譯原理課后答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第二章高級(jí)語(yǔ)言及其語(yǔ)法描述4．令+、*和↑代表加，乘和乘冪，按如下的非標(biāo)準(zhǔn)優(yōu)先級(jí)和結(jié)合性質(zhì)的約定，計(jì)算1+1*2↑2*1↑2的值：（1）優(yōu)先順序（從高至低）為+，*和↑，同級(jí)優(yōu)先采用左結(jié)合。（2）優(yōu)先順序?yàn)椤?，*，同級(jí)優(yōu)先采用右結(jié)合。解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6為N→D
2、NDD→0
3、1
4、2
5、3
6、4
7、5
8、6
9、7
10、8
11、9（1）G6的語(yǔ)言L（G6）是什么？（2）給出句子012
12、7、34和568的最左推導(dǎo)和最右推導(dǎo)。解：（1）L（G6）=｛a
13、a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N＝＞ND＝＞NDD＝＞NDDD＝＞DDDD＝＞0DDD＝＞01DD＝＞012D＝＞0127N＝＞ND＝＞N7＝＞ND7＝＞N27＝＞ND27＝＞N127＝＞D127＝＞0127N＝＞ND＝＞DD＝＞3D＝＞34N＝＞ND＝＞N4＝＞D4＝＞34N＝＞ND＝＞NDD＝＞DDD＝＞5DD＝＞56D＝＞568N＝＞ND＝＞N8＝＞ND8＝＞N68＝＞D68＝＞5687．寫一個(gè)文法
14、，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。解：A→SN,S→+
15、-
16、∑,N→D
17、MDD→1
18、3
19、5
20、7
21、9,M→MB
22、1
23、2
24、3
25、4
26、5
27、6
28、7
29、8
30、9B→0
31、1
32、2
33、3
34、4
35、5
36、6
37、7
38、8
39、98.文法：最左推導(dǎo):最右推導(dǎo):語(yǔ)法樹(shù)：/*************************************************/9．證明下面的文法是二義的：S→iSeS
40、iS
41、I解：因?yàn)閕iiiei有兩種最左推導(dǎo)，所以此文法是二義的。10．把下面文法改寫為無(wú)二義的：S→SS
42、(S)
43、()解：S→ST
44、
45、T,T→(S)
46、()11．給出下面語(yǔ)言的相應(yīng)文法L1=｛anbnci
47、n≥1,i≥0｝L2=｛aibncn
48、n≥1,i≥0｝L3=｛anbnambm
49、n,m≥0｝L4=｛1n0m1m0n
50、n,m≥0｝解：（1）S→AB
51、AA→aAb
52、abB→c
53、cB(2)S→AB
54、BA→a
55、aAB→bBc
56、bc(3)S→AB
57、A
58、B
59、∑A→aAb
60、abB→aBb
61、ab(4)S→1S0
62、0A1A→0A1
63、01第三章詞法分析7.構(gòu)造下列正規(guī)式的相應(yīng)的DFA1(0
64、1)*1011(1010*
65、1(010)*1)*00*10*
66、10*10*(00
67、11)*((01
68、10)(00
69、11)*(01
70、10)(00
71、11)*)*解答：（1）1(0
72、1)*101II0I1{X}Ф{A,B,C}{A,B,C}{B,C}{B,C,D}{B,C}{B,C}{B,C,D}{B,C,D}{B,C,E}{B,C,D}{B,C,E}{B,C}{B,C,D,y}{B,C,D,y}{B,C,E}{B,C,D}S01ABBCDCCDDEDECFFED(2)1(1010*
73、1(010)*1)*0II0I1{X}Ф{A,B,C}{A,B,C}{y}{D,H,I
74、,L}{y}ФФ{D,H,I,L}{E,J}{B,C}{E,J}Ф{B,C,F,G,K}{B,C}{y}{D,H,I,L}{B,C,F,G,K}{B,C,G,I,L,y}{D,H,I,L}{B,C,G,I,L,y}{B,C,G,J,y}{B,C,D,H,I,L}{B,C,G,J,y}{B,C,G,y}{D,H,I,L}{D,H,I,K,L}{E,I,J,L}{B,C}{E,J,y}Ф{B,C,F,G,K}{E,I,J,L}{J}{B,C,F,G,K}{J}Ф{K}{K}{I,L}Ф{I,L}{J}{B,
75、C}8.給出下面正規(guī)表達(dá)式（1）以01結(jié)尾的二進(jìn)制數(shù)串（2）能被5整除的十進(jìn)制整數(shù)（3）包含奇數(shù)個(gè)1或者奇數(shù)個(gè)0的二進(jìn)制數(shù)串（4）英文字母組成的所有符號(hào)串，要求符號(hào)串中的字母按照字典序排列。（7）不包含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體。解答：（1）（0
76、1）*01（2）(1
77、2
78、…
79、9)(0
80、1
81、2
82、…
83、9)*(0
84、5)
85、0
86、5（3）0*1(0*10*10*)*（4）A*B*…Z*(7)b*(a
87、ab)*9.對(duì)下面的情況給出DFA以及正規(guī)表達(dá)式。（1）{0，1}上的含有子串010的所有串。（2）{
88、0，1}上不含子串010的所有串。解答：（1）（0
89、1）*010（0
90、1）*（2）1*(0
91、1*
92、1)*1*12將圖3.8的（a）和(b)分別確定化和最少化。解：1確定化ab｛0｝｛0,1｝｛1｝｛0,1｝｛0,1｝｛1｝｛1｝｛0｝__令A(yù)=｛0｝B=｛0，1｝C=｛1｝則狀態(tài)轉(zhuǎn)換圖為：2最少化首先，所有狀態(tài)可分為終態(tài)集{AB}非終態(tài)集{C}其次，考察{AB}，由于{AB}由a到{B}，由b到{C}，所以不可分，令A(yù)={AB}則最少化后的
