编译原理习题参考答案.doc

第二章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|1C B0C|1S C1A|0B3.描述语言特点（2）SSS S1A0 A1A0 A解：L(G)=1n10n11n20n2 1nm0nm |n1,n2,nm0；且n1,n2,nm 不全为零该语言特点是：产生的句子中，0、1 个数相同，并且若干相接的1 后必然紧接数量相同连续的0。（5）SaSS Sa解：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) 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 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|a BaB|bC|b CaC|a|bC|b(3)用自然语言描述输入串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b 所组成的任意串结尾。12 (1)确定化：abS SS,A AS,A AS,A AA,B A,B B A,B B B -以上为第一次作业最小化：0 S,A B,C因为 Sb= Ab=B 所以 S,A=SA因为 Cb= Bb=B 所以 B,C=BC1 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 或 (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) 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-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)=#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) 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#A -#Caac#B -aC#Cc#cc#C -c#成功-以上为第三次作业16对于如下文法G： -VAR：; -,| -i -real|integer|Boolean|char(1) 将G改造为等价的算符优先文法G;令：S，VAR：v, ：A，：B，：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=rgbc:=,;#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-)项目集规范族:分析表：ActionGOTOa(,)#SR0S211Acc2S3S243r2r2r2r2r24S6S755r1r1r1r1r16S3S287r4r4r4r4r48S6S799r3r3r3r3r3无冲突，为LR(0)文法。补充题1：对下列文法G:S D(R) R R; P|P P S|iD i 求出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系矩阵。解：文法G每个非终结符的FIRSTVT集合FIRSTVT(S)= (, i FIRSTVT(R) =;, (, I FIRSTVT(P) =i, ( FIRSTVT(D) =i 文法G的每个非终结符的LASTVT集合LASTVT(S) = ) LASTVT(R) =;, ) ,i LASTVT(P) = i , ) LASTVT(D) = i 优先关系矩阵 （ ） ； i #( = ; # 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 #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*0a+b0a0(4)if(ab) x=(a-b)c ;else g=h5.8 解：(1)(+,B,C,T1)(*,A,T1,T2)(+,T2,D,T3)(=,T3,_,X)(2)(jnz, A,_, )(j,_,_, f )(jnz,B,_,t)(j,