编译原理习题集

1、2.构造产生下列语言的文法（2）anbmcp|n,m,p0解： G(S) ：SaS|X,XbX|Y,YcY|（3）an # bn|n0cn # dn|n0解： G(S)：SX,SY,XaXb|#,YcYd|# （5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：SJ|IBJ,B0B|IB|,IJ|2|4|6|8, J1|3|5|7|9（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应文法为 S0A|1B|，A0S|1CB0C|1S C1A|0B3.描述语言特点（2）SSS S1A0A1A0A解：L(G)=1n10n11n20n2 1nm0nm |n1,n2,nm0；

2、且n1,n2,nm 不全为零该语言特点是：产生的句子中，0、1 个数相同，并且若干相接的1 后必然紧接数量相同连续的0。（5）SaSSSa解：L(G)=a(2n-1)|n1可知：奇数个a5. (1)解：由于此文法包含以下规则：AA，所以此文法是0 型文法。7.解：(1)aacb 是文法GS中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是文法GS中的句子aacbccb 不能从S推导得到时，它仅是文法GS的一个句型的一部分，而不是一个句子。11.解：最右推导:(1)

3、 S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：短语直接短语句柄a1 对A1b1a1 对 A2b2b1a1 对A3c 对S1a2cb3对Bbbaacb 对 S2第三章3 假设M:人 W:载狐狸过河，G:载山羊过河，C:载白菜过河6 根据文法知其产生的语言是L=ambnci| m,n,i1可以构造如下的文法VN=S,A,B,C, VT=a,b,cP= S aA, AaA, AbB, BbB, BcC, CcC, Cc其状态转换图如下:7 (1) 其对应的右线性文法是:A

4、0D, B0A,B1C,C1|1F,C1|0A,F0|0E|1A,D0B|1C,E1C|0B(2) 最短输入串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9对于矩阵(iii)(1) 状态转换图：(2) 3型文法（正规文法）SaA|a|bB AbA|b|aC|aBaB|bC|bCaC|a|bC|b(3)用自然语言描述输入串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b 所组成的任意串结尾。12 (1)确定化：abS SS,A A

5、S,A AS,A AA,B A,B B A,B BB -以上为第一次作业最小化：º0ºS,A B,C因为 Sb= Ab=B 所以 S,A=>SA因为 Cb= Bb=B 所以 B,C=>BCº1ºSABC原DFA已为最小DFA。10 （1）G1 的状态转换图：或(2) G1 等价的左线性文法G1F：FDd|Bb,DC,BS|Ab|Db,ASa|a, CBc,SEb,EAa或G1F：FDd|Bb,DC,BS|Ab|Db,ASa|a, CBc,SAab21 求出描述习题3-12中图（2）（3）所给出有限自动机所识别语言的正规式（2）a(ba)*b

6、或 (ab)*ab（3）a（b|aa)*a-以上为第二次作业22 (1) (0*|1)(1*0)*0110ASBCNFA:确定化：Q00ASBAA010111S,A,B SS,A,B,C AB BS,A,B,C AS,A,B,C AB BB BS,A,B,C AB B第四章1(2)将间接左递归转换成直接左递归，将A->SA A->a 代入S->AS 由原文法得S->SAS|aS|b 消除左递归：S->aSS|bS S->ASS|4又属于First(S)，First(S)Ç Follow(S)= Æ又属于First(A)，First(A)&

7、#199; Follow(A)= Æ又属于First(B)，First(A)Ç Follow(A)= Æ所以此文法为LL(1)文法。8.（1）(a)消除左递归：S->Sb|Ab|b => S->AbS|bS S->bS| A->Aa|a => A->aA A->aA|文法G：S->AbS|bSS->bS|A->aAA->aA|(b)判断G是否为LL(1)文法FirstFollowS->AbSa#S->bSbS->bSb#S'->A->aAabA'-

8、>aAabA->没有冲突，所以文法G为LL(1)文法。补充题：若有文法GS:S ->AB|cC A ->b| B ->aC| C ->aS|c 判断文法G是否为LL（1）文法，写出理由；分别求所有非终结符的First和Follow集；若为LL（1）文法，给出其预测分析表；分析句子caac是否符合该文法。答案：无左递归，无左公因子。First(A)=(b, ), First(B)=a, 因First(A)含，First(AB)=First(A) ÈFirst(B)=a,b，, First(cC)=cFollow(S)=#È Follow(C

9、)=#Follow(A)=First(B) È Follow(S) - =a,#Follow(B)=Follow(S) =#Follow(C)=Follow(B) È Follow(S) =#对S，First(AB) Ç First(cC)= Æ对A，First(b) Ç First()= Æ,因First(A)含, First(A) Ç Follow(A)=b, Ça,#= Æ对B，First(aC) Ç First()= Æ,因First(B)含, First(B) Ç

10、Follow(B)=a, Ç#= Æ对C，First(aS) Ç First(c)= Æ所以，文法G是LL（1）文法First集： abceSABCFollow集：abc#SABC预测分析表abc#SS ->ABS ->ABS ->cCS ->ABAA ->A ->bA ->BB ->aCB ->CC ->aSC ->c分析句子caac栈输入缓冲区 动作#S caac#Cccaac#S ->cC#Caac#Saaac#C ->aS#Sac#BAac#S ->AB#Bac#

11、A ->#Caac#B ->aC#Cc#cc#C ->c#成功-以上为第三次作业16对于如下文法G<变量说明>： <变量说明>->VAR<变量表>：<类型> <变量表>-><变量表>,<变量>|<变量> <变量>->i <类型>->real|integer|Boolean|char(1) 将G改造为等价的算符优先文法G;令<变量说明>：S，VAR：v, <变量表>：A，<类型>：B，<变量&g

12、t;：C real：r integer:g Boolean:b char:c文法G 可改写为：S->vA:B;A->A,C|CC->iB->r|g|b|c该文法是算符文法(2) 求出G的全部优先关系。求FirstVT，得:virgbc:,;SACB求LastVT，得：virgbc:,;SACB优先关系表：virgbc:,;#v<=<i>>r>g>b>c>:<<<<=,<>>>#<=无冲突，该文法是算符优先文法。35.对于以下文法，试构造它们的LR(0)项目集规范族及识别

13、全部活前缀的DFA。（2）S->cA S->ccB A->cA A->a B->ccB B->b解：拓展文法得文法列表：(0) S->S (1) S->cA (2)S->ccB (3)A->cA (4)A->a (5)B->ccB (6)B->b37判断下面的文法是哪 一类LR文法，并构造LR分析表。S->(SR S->a R->,SR R->)解：拓展文法得文法列表：(0) S->S (1)S->(SR (2)S->a (3) R->,SR (4) R->)项目

14、集规范族:分析表：ActionGOTOa(,)#SR0S211Acc2S3S243r2r2r2r2r24S6S755r1r1r1r1r16S3S287r4r4r4r4r48S6S799r3r3r3r3r3无冲突，为LR(0)文法。补充题1：对下列文法G:S ®D(R) R ®R; P|PP ®S|iD ®i 求出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系矩阵。解：文法G每个非终结符的FIRSTVT集合FIRSTVT(S)= (, i FIRSTVT(R) =;, (, I FIRSTVT(P) =i, ( FIRSTVT(D) =

15、i 文法G的每个非终结符的LASTVT集合LASTVT(S) = ) LASTVT(R) =;, ) ,i LASTVT(P) = i , ) LASTVT(D) = i 优先关系矩阵 （ ） ； i #( <· =· <· <· ) ·> ·> ·> <· ·> ·> <·i ·> ·> ·> # <· <· =· 补充题2:对于如下的

16、文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法，若是LR(1)方法，分析符号串abab的分析过程。 SA AAB A BaB Bb解：扩展后文法为：->S 1.SA 2.AAB 3.A 4.BaB 5.Bb构造LR(1)项目集族：LR(1)分析表：ActionGOTOab#SAB0R3R3R3121acc2S4S5R133R2R2R24S4S565R5R5R56R4R4R4分析符号串abab：序号栈输入动作00abab#R3,A#102abab#S4#A2024bab#S5#Aa30245ab#R5,Bb#Aab40246ab#R4,BaB#AaB5023ab#R2,AAB

17、 #AB602ab#S4#A7024b#S5#Aa80245#R5,Bb#Aab90246#R4,BaB#AaB10023#R2,AAB #AB1102#R1,SA#A1201#acc#S-以上为第四、五次作业5.4 解：（1）A-BC+*DE-（2）ad*c+d/e+f*g+（3）ax+4 cd3*>（4）abcdef*<（5）123456789101112131415161718192021222324s0=i1=i10024jezsii*+=ii1+=7j5.5 解：(1)a+b*c(2)a*(b-c)-(c+d)/e(3)ab+ca>0a+b0a<0(4)if(a<b) x=(a-b)c ;else g=h5.8 解：(1)(+,B,C,T1)(*,A,T1,T2)(+,T2,D,T3)(=,T3,_