编译原理习题课学习课程

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|第1页/共32页第一页，编辑于星期三：十五点 三十八分。2.3 (5) L5 = a2n+1|n=0S - aAA - aaA|或A -

2、aAa|a2.3 (6) 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|B0第2页/共32页第二页，编辑于星期三：十五点 三十八分。2.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=0第3页/共32页第三页，编辑于星期三：十五点 三十八分。2.9短语：

3、T*P(T*F), P(T*F), (T*F), T*F, P直接短语：T*F, P句柄：PTT*FF PP(T) T*F第4页/共32页第四页，编辑于星期三：十五点 三十八分。2.11短语: (SaA)(b), (SaA)(b), (SaA), (b)直接短语: (SaA), (b)句柄: (SaA) S(AS) ( A S ) ( S a A ) ( b )第5页/共32页第五页，编辑于星期三：十五点 三十八分。第第三三章章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

4、,YA,C,YX01第6页/共32页第六页，编辑于星期三：十五点 三十八分。3.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,3Q01XX22X2第7页/共32页第七页，编辑于星期三：十五点 三十八分。3.2 (a)初始划分：A,B; C第8页/共32页第八页，编辑于星期三：十五点 三十八分。3.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

5、=1;0,1b=2,42,4a=1,0;2,4b=3,53,5a=3,5;3,5b=2,4230b ba aaa第9页/共32页第九页，编辑于星期三：十五点 三十八分。3.3 构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。0*(0 | 10)*0*初始划分：1,2,4; 3ca1 00第10页/共32页第十页，编辑于星期三：十五点 三十八分。3.9 试证明正规式（a|b）*与正规式（a*|b*）*是等价的。第11页/共32页第十一页，编辑于星期三：十五点 三十八分。3.11 设字母表=a,b,给出上的正规式R=b*ab(b|ab)*第12页/共32页第十二

6、页，编辑于星期三：十五点 三十八分。3.11初始划分：1,2,3,5; 4,6再次划分：1,3; 2,5; 4,6Qab1212-4424第13页/共32页第十三页，编辑于星期三：十五点 三十八分。3.11（2）对应的右线性文法G=（X,W,Y,a,b,P,X）P:XaW|bXWbY|bYaW|bY|b第14页/共32页第十四页，编辑于星期三：十五点 三十八分。第第四四章章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第15页/共32页第十五页，编辑于星期三：十五点

7、三十八分。因此该文法是LL(1)文法第16页/共32页第十六页，编辑于星期三：十五点 三十八分。4.2 FIRSTFOLLOWE(,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) FIRST(id)= 因此该文法是LL(1)文法第17页/共32页第十七页，编辑于星期三：十五点 三十

8、八分。FIRSTFOLLOWE(,id),$ E+, ),$ T(,id+,),$ T*, +,),$ F(,id+,*,),$ id+*()$EE-TEE-TEEE-+TEE-E-TT-FTT-FTTT-T-*FTT-T-FF-idF-(E)第18页/共32页第十八页，编辑于星期三：十五点 三十八分。4.3 第19页/共32页第十九页，编辑于星期三：十五点 三十八分。4.3 SELECT(A-iBA) SELECT(A-) = FIRST(iBA) FOLLOW(A)= SELECT(B-+CB) SELECT(B-) = FIRST(+CB) FOLLOW(B)= SELECT(C-)A*

9、) SELECT(C-() = FIRST()A*) FIRST()= FirstFollowS(,)$A(,)$,*Ai,$,*B(,)i,$,*B+,i,$,*C(,)+,i,$,*第20页/共32页第二十页，编辑于星期三：十五点 三十八分。(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,$,*第21页/共32页第二十一页，编辑于星期三：十五点 三十八分。4.5 设有表格结构文法GS： S- a|(T) T-

10、 T,S|S 第22页/共32页第二十二页，编辑于星期三：十五点 三十八分。4.5 设有表格结构文法GS： S- a|(T) T- T,S|S 第23页/共32页第二十三页，编辑于星期三：十五点 三十八分。4.5 设有表格结构文法GS： S- a|(T) T- T,S|S 第24页/共32页第二十四页，编辑于星期三：十五点 三十八分。4.80. S - S1. S - AS2.S - b3. A - SA4.A - a 第25页/共32页第二十五页，编辑于星期三：十五点 三十八分。(2). I1,I5,I6存在“移进-归约”冲突。不是LR(0)文法。(3). 对于abab有两棵不同的语法树，任

11、何二义性文法不是SLR(1)文法， 也不是LALR(1)或LR(1)文法。SASaA SSA b ba S A SS A bA S ba b第26页/共32页第二十六页，编辑于星期三：十五点 三十八分。4.90. S - S1. S - rD2.D - D,i3.D - i (2). I3中有“移进-归约”冲突，不是LR(0)文法第27页/共32页第二十七页，编辑于星期三：十五点 三十八分。(3). FOLLOW(S) , = $ , = ,可以用SLR(1)文法解决 4.90. S - S1. S - rD2. D - D,i3.D - i状态ACTIONGOTOr,i$SD0S211acc2S433S5r14r3r35S66r2r2第28页/共32页第二十八页，编辑于星期三：十五点 三十八分。4.13第29页/共32页第二十九页，编辑于星期三：十五点 三十八分。不含有冲