資源描述：
《長安大學《編譯原理》編譯原理試卷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、第三章3.2.2描述下列正則表達式代表的語言。a)a(a
2、b)*ab)((e
3、a)b*)*c)(a
4、b)*a(a
5、b)(a
6、b)d)a*ba*ba*ba*c)(aa
7、bb)*((ab
8、ba)(aa
9、bb)*(ab
10、ba)(aa
11、bb)*)*答案(a)由a開頭并結(jié)尾的由a和b構(gòu)成的字符串(b)由a和b構(gòu)成的字符串(c)倒數(shù)第三位為a的由a和b構(gòu)成的字符串(d)僅含3個b的由a和b構(gòu)成的字符串(e)含有偶數(shù)個a和偶數(shù)個b的由a和b構(gòu)成的字符串注意：請準確描述語言的性質(zhì)而不是列舉滿足正則表達式的串3.2.
12、53.4對于下列語言分別寫出它們的正規(guī)表達式。(1)英文字母組成的所冇符號串，耍求符號串中順序包含五個元音。(2)英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。(3)S=｛O,1)±的含偶數(shù)個1的所有串。(4)工二｛0,1｝上的含奇數(shù)個1的所有串。(5)具冇偶數(shù)個0和奇數(shù)個1的冇0和1組成的符號串的全體。(6)不包含子串011的由0和1組成的符號串的全體。(7)由0和1組成的符號串，把它看成二進制數(shù)，能被3整除的符號串的全體。答案(1)令Letter表示除這五個元音外的其它字母。((
13、letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2)A*B*....Z*⑶(0
14、10*1)*(4)(0
15、10*1)*1(5)［分析］設S是符合要求的串,
16、S
17、=2k+l(k>0)o則StS10
18、S21,
19、Sl
20、=2k(k>0),
21、S2
22、=2k(k>0)o且SI是｛0,1｝上的串，含有奇數(shù)個0和奇數(shù)個1。S2是｛0,1｝上的串，含有偶數(shù)個0和偶數(shù)個1?？紤]有一個自動機Ml接受S1,那么自動機Ml如下：和L(M1)等價的正規(guī)表達式，
23、即S1為：((00
24、11)
25、(01
26、10)(00
27、11)*(01110))*(01
28、10)(00
29、11)*類似的考慮有一個自動機M2接受S2,那么自動機M2如下:和L(M2)等價的正規(guī)表達式，即S2為:((00
30、11)
31、(01110)(00
32、11)*(01
33、10))*因此，S為：((00
34、11)
35、(01
36、10)(00111)*(01110))*(01110)(00111)*0
37、((00
38、11)1(01110)(00
39、11)*(01110))*1⑺接受W的自動機如下:對應的正規(guī)表達式：(1(01*0)
40、110)*Figure3.29:NFAforExercise3.6.33.5.3Figure3.30:NFAforExercise3.6.4EFigure3.26:NFAacceptingaa*
41、bb*3.6.3對于圖3.29表示的NFA,列出aabb的所有路徑。這個NFA能否接受aabb?答案：aabb的所有路徑012230011101200000000012220001100123存在路徑1223和0123所以能接受aabb(a)(b)a3.7.1(a)圖把下列3.26NFA轉(zhuǎn)化為DFA(b)圖
42、3.29(c)圖3.30答案■■ba(C)A3.7.3用算法3.23和a)(alb)*答案：a)NFAEDFANFAStateDFAStateab{0,1,2,37}ABC{1,2,346,7}BBC{1,2,3,5,67}CBC第四章465證明下面的文法是LL(1)文法，但不是SLR(l)文法S~*AaAb
43、BbBa￡B-*e解：對于產(chǎn)生式S-AaAb
44、BbBa來說FIRST(AaAb)nFIRST(BbBa)={a}n=0而A,BGVx僅有一條候選式。因此，這個文法是I丄(1)的。下面構(gòu)造
45、這個文法的識別活前綴的DFA。10={S'f?S,S—?AaAb,S—?BbBa,A—?,B-*?L={S'-S?}12二{SfA?aAb}13二{S->B?bBa}14={S->Aa?Ab,A->?}15={S-Bb?Ba,B-?}16={S->AaA?b}17二{SfBbB?a}18二{S->AaAb?}19={S-BbBa?}rfl于FOLLOW(A)=FOLLOW(B)={a,b}因此項目集IO中存在歸約一歸約沖突。在10狀態(tài)下，當輸入符號是a或是b時,不知用A->e還是進行歸約。故此文法不
46、是SLR⑴的。但是，此文法吋LR⑴的。4.40證明下面的文法是LR(1)文法S-*Aa
47、bAc
48、Bc
49、bBaA-dB->d解拓廣文法為：G':(0)S'—S(1)S—Aa(2)S-*bAc(3)S—Be(4)S-*bAa(5)A->d(6)B->d有效項目集族為：Io：S'T?S,#S—>?Aa,#ST?bAc,#St?Bc,#ST?bBa,#A—>?d,aBt?d,c【2：goto(Io,A)S—>A*a,#Ii：goto(I0,S)S'tS?,#ggoto(Io,
