编译原理习题课

1、编译原理习题课编译原理习题课第二章第二章2.2 (1) L(GN) = (0|1|2|3|4|5|6|7|8|9)+ L(GN) = 可带前导带前导0的正整数2.3 (1) L1 = ambn|m,n=1S - ABA - a|aAB - b|bB2.3 (2) L2 = anbnci|n=1,i=0S - Ac|AA - ab|aAb2.3 (3) L3 = anbncmdm|m,n=1S - ABA - aAb|abB - cBd|cd2.3 (4) L4 = 0n|n=0A - A0|2.3 (5) L5 = a2n+1|n=0S - aAA - aaA|或A - aAa|a2.3 (6

2、) L6 = 1n0m1m0m|n,m=0S - 1S0|oA1|A - 0A1|2.4 写一个文法，不以0开头的奇数N - 1|3|5|7|9|BNB - 1|2|3|4|5|6|7|8|9|B02.6短语：E+T*F,T*F直接短语：T*F句柄：T*F EE+TT*F 2.7G1：S - AB A - aA | B - bc | bBc L(G1S)=aibncn|i=0,n=1G2：S - aA|a A - aSL(G2S)=a2n+1|n=02.9短语：T*P(T*F), P(T*F), (T*F), T*F, P直接短语：T*F, P句柄：PTT*FF PP(T) T*F2.11短语

3、: (SaA)(b), (SaA)(b), (SaA), (b)直接短语: (SaA), (b)句柄: (SaA) S(AS) ( A S ) ( S a A ) ( b )第第三三章章3.1 (3) (0|1)*|(11)*X A YB 1 1C 0,1Q01X,A,C,YA,C,YB,A,C,YA,C,YA,C,YB,A,C,YB,A,C,YA,C,YA,C,YX013.1 (4) (0|11*0)*重命名重命名Q01X X,A,YA,YB,C,D1A,YA,YB,C,D2B,C,DA,YC,D3C,DA,YC,D初始划分：X,1; 2,3Q01XX22X23.2 (a)初始划分：A,B;

4、 C3.2 (b)初始划分：0,1; 2,3,4,50,1a=1;0,1b=2,42,3,4,5a=1,3,0,5;2,3,4,5b=3,2,5,4再次划分：0,1; 2,4; 3,50,1a=1;0,1b=2,42,4a=1,0;2,4b=3,53,5a=3,5;3,5b=2,4230b ba aaa3.3 构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。0*(0 | 10)*0*初始划分：1,2,4; 3ca1 003.9 试证明正规式（a|b）*与正规式（a*|b*）*是等价的。3.11 设字母表=a,b,给出上的正规式R=b*ab(b|ab)*3.1

5、1初始划分：1,2,3,5; 4,6再次划分：1,3; 2,5; 4,6Qab1212-44243.11（2）对应的右线性对应的右线性文法文法G=（X,W,Y,a,b,P,X）P:XaW|bXWbY|bYaW|bY|b第第四四章章4.1 FIRSTFOLLOWAa,b,c,d,g$,f Bb, $,a,c,d,f,g Ca,c,d c,d,gDd, $,a,b,c,g,fEg,c$,a,c,d,f,g因此该文法是LL(1)文法4.2 FIRSTFOLLOWE(,id),$ E+, ),$ T(,id+,),$ T*, +,),$ F(,id+,*,),$ SELECT(E-+TE) SELEC

6、T(E-) = FIRST(+TE) FOLLOW(E)= SELECT(T-*FT) SELECT(T-) = FIRST(*FT) FOLLOW(T)= SELECT(F-(E) SELECT(F-id) = FIRST(E) FIRST(id)= 因此该文法是LL(1)文法FIRSTFOLLOWE(,id),$ E+, ),$ T(,id+,),$ T*, +,),$ F(,id+,*,),$ id+*()$EE-TEE-TEEE-+TEE-E-TT-FTT-FTTT-T-*FTT-T-FF-idF-(E)4.3 4.3 SELECT(A-iBA) SELECT(A-) = FIRST(

7、iBA) FOLLOW(A)= SELECT(B-+CB) SELECT(B-) = FIRST(+CB) FOLLOW(B)= SELECT(C-)A*) SELECT(C-() = FIRST()A*) FIRST()= FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*(i+)*$SS-AS-AAA-BAA-BAAA-iBAA-A-BB-CBB-CBBB-B-+CBB-B-CC-(C-)A*FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*4.5 设有表格结构文

8、法GS： S- a|(T) T- T,S|S 4.5 设有表格结构文法GS： S- a|(T) T- T,S|S 4.5 设有表格结构文法GS： S- a|(T) T- T,S|S 4.80. S - S1.S - AS2. S - b3. A - SA4. A - a (2). I1,I5,I6存在“移进-归约”冲突。不是LR(0)文法。(3). 对于abab有两棵不同的语法树，任何二义性文法不是SLR(1)文法， 也不是LALR(1)或LR(1)文法。SASaA SSA b ba S A SS A bA S ba b4.90. S - S1.S - rD2. D - D,i3. D - i (2). I3中有“移进-归约”冲突，不是LR(0)文法(3). FOLLOW(S) , = $ , = ,可以用SLR(1)文法解决 4.90. S - S1.S - rD2. D - D,i3. D - i状态状态A