编译原理复习题(经典)

1、 欢。迎下载精品文档=(l,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)五.计算题1构造下述文法GS的自动机：S-A0A-A0|S1|0该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式S-A0,A-A0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0先01|0二A(0|01)|0=0(0|01)*。代入S-A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：由于状态A有3次输入0的重复输入，

2、所以上图只是NFA，下面将它确定化：下表由子集法将NFA转换为DFA:IIo-5-谒n琰工协Il二铲水的eT?制AIV-BXB；CY.Z,C区LZ,C区Y.ZB.2对下面的文法G：E-TEE-+E|T-FTT-T|F-PFF-*F|P-(E)|a|b(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预测分析表。解：(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E):FIRST(T):FIRST(F):FIRST(P);(,a,b,1;FIRST(E)=+,FIRST(T):FIRST(F):FIR

3、ST(P);(,a,b,1;FIRST(T)=FIRST(T)U=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,1;精品文档FIRST(F)二FIRST(P)=*,;精品文档FIRST(P);(,a,b,1;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)FFOLLOW(E)=+,),#;/不包含FOLLOW(T)=FOLLOW(T)=FIRST(E)FFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)FFOLLOW(T)=(,a,b，+,),#;/不包含FOLLOW(F)=F

4、OLLOW(F)=FIRST(T)FFOLLOW(T);(,a,b，+,),#;FOLLOW(P)=FIRST(F)FFOLLOW(F)=*,(,a,b，+,),#;/不包含证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(E-TE)=FIRST(T)=(,a,b,1;SELECT(E-+E)=+;SELECT-)=FOLLOW(E/)=),#SELECT(T-FT):FIRST(F);(,a,b,1;SELECT(T-T):FIRST(T);(,a,b,1;SELECT(T-)=FOLLOW(T/);+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,1

5、;SELECT(F-*F)=*;SELECT(F-)=FOLLOW(F)=(,a,b，+,),#;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-k)二可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL文法。(3)构造它的预测分析表。文法GE的预测分析表如下：十*(1:a;hE-4TEZ.TTE-4TE/跳4短T嚏:咤FTTFT，好FT丁泠飞fTTTF与PFtpE今pp-PF病-F.4S.*鼻麻一F3.舜、3已知NFA=(x,y,z,0,1,M,x,z)，其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(

6、x,1)=x,M(y,1)二,M(z,1)=y,构造相应的DFA并最小化。解：根据题意有NFA图：口下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1二A,D,E,P2;B,C,F(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价(见下步)，从而B与C，F可以区分。有P21二C,F,P22;B。(3)区分P1:由于A，输入0到终态，而0输入0不到终态，所以0与4，E可以区分，有P11二A,E,P12;D。(4)由于F(A,0)=B,F(E,0)=F

7、,而B，F不等价，所以A，E可以区分。综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下:4已知文法为：S-a1|(T)T-T,S|S构造它的LR(0)分析表。解：加入非终结符S，方法的增广文法为:S-SS-aS-kS-(T)T-T,ST-S下面构造它的LR(0)项目集规范族为:小主口rV+业aCt&J#1工欧法三、5a导，;(T)LsS-aI3:3告(TjfT,3TSS-*a_.3令.3号*工匕5,至5：Ii.3.CC工二1=I：ET1第)玲三ST-,SS-a沁!2XL工I.L：T-S工一SftTQTT%S%TTT)3：It：ST处卜TTTS0分J3行广2(T)LI

8、t：IG;,T-L*SS-*aSL-IzI.T-T,女；从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。从而有下面的LR(0)分析表:状态ACTIO.NGOTOa:(3：蹙筏T0%舟S.k1.acc2riHlrL11XL3r：T;r；二r-壬4冤”.篌密55SB6rsTSr5r5门r57r313r3r5r3工3S鼠,_送文窗9riI;rr.r1ii5已知文法A-aAd|aAb|e判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有：S-A精品文档A-aAd|aAb|下面构造它的LR(0

9、)项目集规范族为：招.：H学AIo：,以A-aAdA-aAbI=!A-a*AdA-a*AbA-*aAdA-*aAbIiLSA6:accIz；益H必1-aAd幺力LL：A-aAdA-aAb工壮A-aAd且TaA。A-aAd*且TaAb、5；A-aAd从上表可看出，状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)a=b,d,#a=，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。其SLR分析表为：状态ACTIOlfGOTOabd董A0sarLwr51Lacc2sarLr-r33：3s,等4工；I:工：5riXLX1II对输入串ab#给出分析过程为:步馨状态栈步馨状态栈符号栈10#2侬,5a-.3-023#aA40334#aAb501#A输悬拜ACTIOMGOTOat#*h#口:了七点S#1#acc6已知文法GS为：S-a1|(T)精品文档T-T,S|S计算GS的FIRSTVT和LASTVT。构造GS的算符优先关系表并说明GS是否未算符优先文法。计算GS的优先函数。给出输入串(a,a)#的算符优先分析过程。解：(1)各符号的FIRSTVT和LASTVT：(2)算符优先关系表：a(nA#