资源描述：
《长安大学《编译原理》编译原理试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.2.
12、53.4对于下列语言分别写出它们的正规表达式。(1)英文字母组成的所冇符号串，耍求符号串中顺序包含五个元音。(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。(3)S=｛O,1)±的含偶数个1的所有串。(4)工二｛0,1｝上的含奇数个1的所有串。(5)具冇偶数个0和奇数个1的冇0和1组成的符号串的全体。(6)不包含子串011的由0和1组成的符号串的全体。(7)由0和1组成的符号串，把它看成二进制数，能被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｝上的串，含有奇数个0和奇数个1。S2是｛0,1｝上的串，含有偶数个0和偶数个1。考虑有一个自动机Ml接受S1,那么自动机Ml如下：和L(M1)等价的正规表达式，
23、即S1为：((00
24、11)
25、(01
26、10)(00
27、11)*(01110))*(01
28、10)(00
29、11)*类似的考虑有一个自动机M2接受S2,那么自动机M2如下:和L(M2)等价的正规表达式，即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的自动机如下:对应的正规表达式：(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转化为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解：对于产生式S-AaAb
44、BbBa来说FIRST(AaAb)nFIRST(BbBa)={a}n{b}=0而A,BGVx仅有一条候选式。因此，这个文法是I丄(1)的。下面构造
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状态下，当输入符号是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,
