资源描述：
《编译原理 习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理习题课第二章2.2(1)L(G[N])={(0
2、1
3、2
4、3
5、4
6、5
7、6
8、7
9、8
10、9)+}L(G[N])={可带前导0的正整数}2.3(1)L1={ambn
11、m,n>=1}S->ABA->a
12、aAB->b
13、bB2.3(2)L2={anbnci
14、n>=1,i>=0}S->Ac
15、AA->ab
16、aAb2.3(3)L3={anbncmdm
17、m,n>=1}S->ABA->aAb
18、abB->cBd
19、cd2.3(4)L4={0n
20、n>=0}A->A0
21、ε2.3(5)L5={a2n+1
22、n>=0}S->aAA->aaA
23、ε或A->aAa
24、a2.3(6)L6={1n0m1m
25、0m
26、n,m>=0}S->1S0
27、oA1
28、εA->0A1
29、ε2.4写一个文法，不以0开头的奇数N->1
30、3
31、5
32、7
33、9
34、BNB->1
35、2
36、3
37、4
38、5
39、6
40、7
41、8
42、9
43、B02.6短语：E+T*F,T*F直接短语：T*F句柄：T*FEE+TT*F2.7G1：S->ABA->aA
44、εB->bc
45、bBcL(G1[S])={aibncn
46、i>=0,n>=1}G2：S->aA
47、aA->aSL(G2[S])={a2n+1
48、n>=0}2.9短语：T*P↑(T*F),P↑(T*F),(T*F),T*F,P直接短语：T*F,P句柄：PTT*FF↑PP(T)T*F2.11短语:(((
49、SaA)(b))),((SaA)(b)),(SaA),(b)直接短语:(SaA),(b)句柄:(SaA)S(AS)(AS)(SaA)(b)第三章3.1(3)((0
50、1)*
51、(11))*XAYBεε11Cεε0,1Q01{X,A,C,Y}{A,C,Y}{B,A,C,Y}{A,C,Y}{A,C,Y}{B,A,C,Y}{B,A,C,Y}{A,C,Y}{A,C,Y}X013.1(4)(0
52、11*0)*重命名Q01X{X,A,Y}{A,Y}{B,C,D}1{A,Y}{A,Y}{B,C,D}2{B,C,D}{A,Y}{C,D}3{C,D}{A,Y}{C,D}初始划分：{X,
53、1};{2,3}Q01XX22X23.2(a)初始划分：{A,B};{C}3.2(b)初始划分：{0,1};{2,3,4,5}{0,1}a={1};{0,1}b={2,4}{2,3,4,5}a={1,3,0,5};{2,3,4,5}b={3,2,5,4}再次划分：{0,1};{2,4};{3,5}{0,1}a={1};{0,1}b={2,4}{2,4}a={1,0};{2,4}b={3,5}{3,5}a={3,5};{3,5}b={2,4}230bbaaaa3.3构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。0*(0
54、
55、 10)*0*初始划分：{1,2,4};{3}ca1003.9试证明正规式（a
56、b）*与正规式（a*
57、b*）*是等价的。3.11设字母表∑={a,b},给出∑上的正规式R=b*ab(b
58、ab)*3.11初始划分：{1,2,3,5};{4,6}再次划分：{1,3};{2,5};{4,6}Q’ab1212-44243.11（2）对应的右线性文法G=（{X,W,Y},{a,b},P,X）P:X→aW
59、bXW→bY
60、bY→aW
61、bY
62、b第四章4.1FIRSTFOLLOWA{a,b,c,d,g}{$,f}B{b,ε}{$,a,c,d,f,g}C{a,c,d}{c,d,g
63、}D{d,ε}{$,a,b,c,g,f}E{g,c}{$,a,c,d,f,g}因此该文法是LL(1)文法4.2FIRSTFOLLOWE{(,id}{),$}E’{+,ε}{),$}T{(,id}{+,),$}T’{*,ε}{+,),$}F{(,id}{+,*,),$}SELECT(E’->+TE’)∩SELECT(E’->ε)=FIRST(+TE’)∩FOLLOW(E’)=ΦSELECT(T’->*FT’)∩SELECT(T’->ε)=FIRST(*FT’)∩FOLLOW(T’)=ΦSELECT(F->(E))∩SELECT(F->id)=FIRST((E))∩
64、FIRST(id)=Φ因此该文法是LL(1)文法FIRSTFOLLOWE{(,id}{),$}E’{+,ε}{),$}T{(,id}{+,),$}T’{*,ε}{+,),$}F{(,id}{+,*,),$}id+*()$EE->TE’E->TE’E’E’->+TE’E’->εE’->εTT->FT’T->FT’T’T’->εT’->*FT’T’->εT’->εFF->idF->(E)4.34.3SELECT(A’->iBA’)∩SELECT(A’->ε)=FIRST(iBA’)∩FOLLOW(A’)=ΦSELECT(B’->+CB’)∩SELECT(B’->ε)
65、=FIRST(+CB’)
