编译原理习题解答(第2-3章)_吴蓉.ppt

按一下以編輯母片標題樣式,*,编译原理,第,2-3,章习题解答,版权所有：南京邮电大学计算机学院,声明：希望同学们不要把此解答拷贝,给他人，请大家保持诚信,第二章习题,2,P38 7.,设有文法,GS,：,S,A,A,B|IF A THEN A ELSE A,B,C|B+C|+C,C,D|C*D|*D,D,X|(A)|-D,试写出,V,N,和,V,T,。,解：,V,N,S,，,A,，,B,，,C,，,D,V,T,IF,，,THEN,，,ELSE,，,+,，*，,X,，,(,，,),，,-,P39 10.,给定文法：,S,aB|bA,A,aS|bAA|a,B,bS|aBB|b,该文法所描述的语言是什么？,解：,L(G),相同个数的,a,与,b,以任意次序连接而成的非空符号串,。,P39 11.,试分别描述下列文法所产生的语言（文法开始符号为,S,）：,(2)S,aaS|bc,(4)S:=AB,A:=aAb|ab,B:=cBd|,解：,(2)L(G),a,2n,bc|n0,；,(4)L(G),a,n,b,n,c,m,d,m,|m0,n1,。,P39 12.,试分别构造产生下列语言的文法：,（,1,）,ab,n,a|n=0,，,1,，,2,，,3,（,3,）,aba,n,|n1,（,5,）,a,n,b,m,c,p,|n,，,m,，,p0,解：,（,1,）,G,V,N,，,V,T,，,P,，,S,，,V,N,S,，,A,，,V,T,a,，,b,，,P,：,S,aAa,或,S,aB,A,bA|B,bB|a,（,3,）,G,V,N,，,V,T,，,P,，,S,，,V,N,S,，,A,，,V,T,a,，,b,，,P,：,S,abA,或,S,Sa|aba,A,aA|a,（,5,）,a,n,b,m,c,p,|n,，,m,，,p0,解：,G,V,N,，,V,T,，,P,，,S,，,V,N,S,，,A,，,B,，,C,，,V,T,a,，,b,，,c,，,P,：,S,ABC,A,aA|,B,bB|,C,cC|,P39 15.,设文法,G,规则为：,S,：,=AB,B,：,=a|Sb,A,：,=Aa|bB,对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。,（,2,）,baabaab,解：,S,A B,A a S b,b B A B,a b B a,a,句型,baabaab,的短语,a,ba,baa,baab,baabaab,，简单短语,a,，句柄,a,P40 19.,证明下述文法是二义的,S:=iEtS|iEtSeS|a E:=b,存在句子,ibtibtaeibta,或者,ibtibtaea,有两颗不同的语法树,3),解：,对于句子,ababa,可构造两棵不同的语法树，所以证明该文法是二义的,。,S,A,a C b A,b a a,S,B,B C C,a b a b a,P41 24.,下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？,1.S:=aB B:=cB B:=b C:=c,2.S:=aB B:=bC C:=c C:=,3.S:=aAb aA:=aB aA:=aaA B:=b A:=a,4.S:=aCd aC:=B aC:=aaA B:=b,5.S:=AB A:=a B:=bC B:=b C:=c,6.S:=AB A:=a B:=bC C:=c C:=,7.S:=aA S:=A:=aA A:=aB A:=a B:=b,8.S:=aA S:=A:=bAb A:=a,解：正规文法,1 2 7,或者,1,上下文无关文法,5 6 8,或者,2 5 6 7 8,上下文有关文法,3,短语结构文法,4,P41 26.,给出产生下列语言,L,（,G,）,=W|W0,，,1,+,且,W,不含相邻,1,的正规文法。,解：,G=(S,A,B,0,1,P,S),P:S:=0|1|0S|1A,A:=0|0S,解题思路一：写出满足要求的符号串，例如,0,，,1,，,00,，,01,，,10,，,000,，,101,，,010,，,001,等，根据符号串从左至右的次序画出状态转换图，然后根据状态转换图来推导出文法。这将会得到,S:=0|1|0S|1A|0Z|1Z A:=0|0S|0Z,经过分析其中,Z,为多余状态可删去。,S,Z,A,1,0,0,0,0,1,解题思路二：写出其正规表达式,(0|10)*(10|0|1)【,如果仅有,(0|10)*,的话推导不出,1,，因为是连接关系，后面缺了,10,的话就会以,1,结尾，同样的道理还要推导出,0,，所以得到此正规式,】,，画出转换系统，然后根据转换系统来推导出文法。也可以根据正规表达式直接写文法，例如正规表达式,(0|10)*(10|0|1),可以看成是,a*b,，推导出,A:=,(0|10),A|,10|0|1,，即,A:=,0A|1B,|,10|0|1,，其中,B:=0A,，但是,10,此项不符合正规文法的选项，可以进行改写从而得到,A:=,0A|1B,|,0|1 B:=0A|0,。,P41 27.,给出一个产生下列语言,L,（,G,）,W|Wa,b*,且,W,中含,a,的个数是,b,个数两倍的前后文无关文法。,解：文法,G=(S,A,B,a,b,P,S),P:S:=AAB|ABA|BAA|,A:=aS,B:=bS,或者,S:=Saab|aSab|aaSb|aabS|Saba|aSba|abSa|abaS|Sbaa|bSaa|baSa|baaS|,或者,S:=aaB|aBa|Baa|,B:=SbS,P41 28.,给出一个产生下列语言,L(G)=w|wa,b,c+,且,w,由相同个数的,a,，,b,，,c,组成的前后文有关文法。,解,:,文法,G=(S,A,B,a,b,c,P,S),P:S:=ABC,A:=aS,|,a,B:=bS,|,b,C:=cS|c,AB:=BA,BC:=CB,AC:=CA,P41 29.,用扩充的,BNF,表示以下文法规则：,(1)Z:=AB|AC|A,(2)A:=BC|BCD|AXZ|AXY,(3)S:=aABb|ab,(4)A:=Aab|,解,:,(1)Z:=A,（,B|C|,）,:=AB|C,(2)A:=BC,（,|D,）,|X,（,Z|Y,）,:=BCD|X,（,Z|Y,）,(3)A:=a(AB|)b):=aABb,(4)A:=ab|:=ab,第三章习题,P74 4.,画出下列文法的状态图：,Z:=Be,B:=Af,A:=e|Ae,并使用该状态图检查下列句子是否该文法的合法句子：,f,eeff,eefe,。,解：,由状态图可知只有,eefe,是该文法的合法句子。,P74 6.,构造下述文法,GZ,的自动机，该自动机是确定的吗？它相应的语言是什么？,Z:=A0 A:=A0|Z1|0,解,1,：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号,B,，将左线性文法变为,Z:=A0 A:=A0|B1|0 B:=A0,，具体为：,A:=Z1 A:=B1,A:=A01,Z:=A0 B:=A0,将所得的新左线性文法转换成右线性文法：,此时利用书上规则，其对应的右线性文法为：,A:=0A|0B|0 Z:=0A B:=1A,解,2,：先画出该文法状态转换图：,NFA=,（,S,，,A,，,Z,，,0,，,1,，,M,，,S,，,Z,）,其中,M,：,M,（,S,，,0,）,=A,M,（,S,，,1,）,=,M,（,A,，,0,）,=A,，,Z,M,（,A,，,1,）,=,M,（,Z,，,0,）,=,M,（,Z,，,1,）,=A,显然该文法的自动机是非确定的；它相应的语言为：,0,，,1,上所有满足以,00,开头以,0,结尾且每个,1,必有,0,直接跟在其后的字符串的集合；也可以通过求解正规表达式得到,A=0(0|01)*,，,Z=0(0|01)*0,那么如何构造其相应的有穷自动机呢？,先构造其转换系统：,Z,Z,A,S,S,0,1,0,0,根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：,(,其中,S,可以忽略，结果是一样的,),I,I,0,I,1,S,0 1,S,S,A,0,1 ,A,A,Z,Z,1,2 ,A,Z,Z,A,Z,Z,A,2,2 1,则其相应的,DFA,为：,2,1,0,0,0,0,1,P74 7.,构造一个,DFA,，它接受,0,，,1,上所有满足下述条件的字符串，其条件是：字符串中每个,1,都有,0,直接跟在右边，然后，再构造该语言的正规文法。,解,(,一,),：其状态转换图为,(,状态,S,表示空串开始，状态,A,表明串的末尾是,1,，状态,Z,表示串的末尾是,0),DFA=,（,S,，,A,，,Z,，,0,，,1,，,M,，,S,，,Z,）,其中,M,：,M,（,S,，,0,）,=Z M,（,S,，,1,）,=A,M,（,A,，,0,）,=Z,M,（,Z,，,0,）,=Z M,（,Z,，,1,）,=A,该语言的正规文法,GZ,为：,右线性文法：,/S:=0|1A|0Z,左线性文法：,A:=0|0Z A:=1|Z1,Z:=0|1A|0Z Z:=0|A0|Z0,若终止状态只引入不引出则适合构造右线性文法，若开始状态只引出不引入则适合构造左线性文法，若终态和初态均既有引入又有引出，则构造文法要注意。,解,(,二,),：可以先写出该文法的正规表达式为,(0|10)*,，根据该正规式构造转换系统,对于该转换系统可以采用子集法将其转变为,DFA,，再根据,DFA,写出其正规文法；但是注意观察后，发现开始状态,S,通过,到达,A,状态，可以直接删去,S,状态，由,A,状态作为新的开始状态，同理，只有,A,状态通过,才能到达终止状,态,Z,，因此可以删去,Z,状态，由,A,状态作为终止状态。这样，,A,状态就既为开始状态又为终止状态。可画出化简后的转换图。可写出右线性文法为：,A:=0|0A|1B B:=0|0S,P74 8.,设,(NFA)M=(A,B,a,b,M,A,B),，其中,M,定义如下：,M(A,a)=A,B M(A,b)=B,M(B,a)=M(B,b)=A,B,请构造相应确定有穷自动机,(DFA)M,。,解：构造一个如下的自动机,(DFA)M,，,(DFA)M=K,a,b,M,S,Z,K,的元素是,A B A,B,由于,M,（,A,a,）,=A,B,，故有,M,（,A,a,）,=A,B,同样,M,（,A,，,b,）,=B,M,（,B,，,a,）,=,M,（,B,，,b,）,=A,，,B,由于,M,（,A,，,B,，,a,）,=M,（,A,，,a,）,U M,（,B,，,a,）,=A,，,BU=A,，,B,故,M,（,A,，,B,，,a,）,=A,，,B,由于,M,（,A,，,B,，,b,）,=M,（,A,，,b,）,U M,（,B,，,b,）,=BU A,，,B=A,，,B,故,M,（,A,，,B,，,b,）,=A,，,B,S=A,，终态集,Z=A,，,B,，,B,重新定义：令,0=A 1=B 2=A,B,，则,DFA,如下所示：,P74 9.,设有穷自动机,M=(S,A,E,a,b,c,M,S,E),，其中,M,定义为,M(S,c)=A M(A,b)=A M(A,a)=E,请构造一个左线性文法。,解：先求右线性文法,ScA AbA Aa|aE AaE,实际上是多余的规则，应该去掉,其左线性文法,G=,（,VN,VT,P,S,）,V,N,=A,S V,T,=a,b,c,根据书上左右线性文法的转换规则，得到,P:Ac AAb SAa EAa,实际上是多余的规则，应该去掉,画出状态转换图之后就非常清晰。,P74 11.,构造下列正规式相应的,DFA,：,（,1,）,(0|11*0)*【,新课本,】,解：先构造该正规式的转换系统：,由上述转换系统可得状态转换集,K=S,1,2,3,4,Z,，状态子集转换矩阵如下表所示：,I,I,0,I,1,K,0 1,S,1,Z,1,Z,2,3,4,0,1 2,1,Z,1,Z,2,3,4,1,1 2,2,3,4,1,Z,3,4,2,1 3,3,4,1,Z,3,4,3,1 3,由状态子集转换矩阵可知，状态,0,和,1,是等价的，而状态,2,和,3,是等价的，因此，合并等价状态之后只剩下,2,个状态，也即是最少状态的,DFA,。,P74 12.,将图,3.24,非确定有穷自动机,NFA,确定化和最少化。,解：设,(DFA)M=K,V,T,M,S,Z,，其中，,K=0,0,1,1,，,V,T,=a,b,，,M,：,M(1,a)=0 M(1,b)=M(0,1,a)=0,1,M(0,1,b)=1 M(0,a)=0,1 M(0,b)=1,S=1,，,Z=0,0,1,令,0,1=2,，则其相应的状态转换图为：,现在对该,DFA,进行化简，先把状态分为两组：,终态组,0,2,和非终态组,1,，易于发现,0,2,不可以继续划分，因此化简后的状态转换图如下：,P74 15.,用两种方法将,(NFA)M=(X,Y,Z,0,1,M,X,Z),，构造相应的,DFA,，其中：,M(X,0)=Z M(X,1)=X M(Y,0)=X,Y,M(Y,1)=M(Z,0)=X,Z M(Z,1)=Y,第一种方法：先画出其状态转换图，利用非子集法：,假设,(DFA)M=(K,V,T,M,S,Z),，,其中,K=X,Y,Z,X,Y,X,Z,Y,Z,X,Y,Z,，,V,T,=0,1,，,M,的规则如下表,：,其中,Y,Z,为不可到达状态，应该删去，所以,S=X,，,Z=Z,X,Z,X,Y,Z,，再进行化简，发现,4,和,6,两状态等价，最后其,DFA,如下所示：,第二种方法：先构造其对应的转换系统：,由上述转换系统可得状态转换集、状态子集转换矩阵如下表所示：,先化简，分为非终态集,2,4,5,0,和终态集,6,1,3,，易于发现可划分为,0,2,，,1,，,3,6,，,4,，,5,，其,DFA,如下所示：,P74 18.,根据下面正规文法构造等价的正规表达式：,S:=cC|a ,A:=cA|aB ,B:=aB|c ,C:=aS|aA|bB|cC|a ,解：由式可得,B=aB+c B=a*c,由式可得,A=cA+aB A=c*aa*c,由式可得,S=cC+a,由式可得,C=aS+aA+bB+cC+a C=c*(aS+aA+bB+a),C=c*(aS+ac*aa*c+ba*c+a)S=cc*(aS+ac*aa*c+ba*c+a)+a=cc*aS+cc*(ac*aa*c+ba*c+a)+a=(cc*a)*(cc*(ac*aa*c+ba*c+a)+a)=(cc*a)*(cc*(ac*aa*c|ba*c|a)|a),另一种答案是,S=c(ac|c)*(ac*aa*c|ba*c|aa|a)|a,P75 20.,证明下列关系式成立，其中,A,、,B,是任意正规表达式。,（,4,）,(AB)*A=A(BA)*,解：,(AB)*A=(AB)0(AB)1(AB)2)A=AABAABABA=A(BA)0(BA)1(BA)2)=,A(BA)*,。,