编译原理习题与答案.ppt

《编译原理习题与答案.ppt》由会员分享，可在线阅读，更多相关《编译原理习题与答案.ppt（59页珍藏版）》请在三一办公上搜索。

1、第二章,2.2 设有文法GN:N-D|NDD-0|1|9(1)GN定义的语言是什么？(2)请给出句子0123的最左推导和最右推导。,N,ND,NDD,NDDD,DDDD,0DDD,01DD,012D,0123,N,ND,N3,ND3,N23,ND23,N123,D123,0123,2.5 证明下面的文法是二义性的。SiSeS|iS|i答：对句子iiiei对应两棵不同的语法树,第二章,S,S,2.9 设有文法GT:TT*F|FF FP|PP(T)|i 分析句型T*P(T*F)的短语、直接短语和句柄答：句型T*P(T*F)的语法树：,T,五棵子树对应五个短语T*P(T*F),P(T*F),P,(T

2、*F),T*F,两层子树(简单子树)的末端结点构成直接短语 两棵两层子树对应两个直接短语：P,T*F位于最左边的两层子树的末端结点构成句柄：P,第二章,第三章,3.1 构造正规式1(0|1)*101相应的NFA,第三章,3.1 构造正规式1(0|1)*101相应的NFA,(0|1)*,第三章,3.5 给出下述文法所对应的正规式。G：SaA AbA|aB|b B aA解：先由产生式得:B=aA将B代入A中得:A=bA|aaA|b=(b|aa)A|b利用规则（A-xA|y）得:A=(b|aa)*b 将A代入S中得:S=a(b|aa)*b即为所求正规式,3.4 给出文法GS，构造相应最小的DFA。G

3、：SaS|bA|b AaS解：由文法到NFA的转换有两种方法：由文法到正规式，再由正规式到NFA先由产生式得:A=aS将A代入S中得:S=aS|bA|b=aS|baS|b=(a|ba)S|b利用规则（A-xA|y）得:S=(a|ba)*b 文法G对应的正规式为(a|ba)*b，其对应的NFA的状态转换图为：,第三章,3.4 给出文法GS，构造相应最小的DFA。G：SaS|bA|b AaS解：由文法直接到NFA文法对应的有自动M=(S,A,T,a,b,f,S,T)其对应的状态转换图为：,第三章,正规式：(a|ba)*b,第三章,将NFA确定化为DFA如右图所示最小化：此状态图已经为最简了。,S,

4、S,A,T,A,T,S,Ib,Ia,I,0,1,0,1,0,-,第三章,1.指出与正规式匹配的串。a)(ab|b)*c 与后面的那些串匹配？,ababbc,abab,c,babc,aaabc,b)ab*c*(a|b)c 与后面的那些串匹配？,acac,acbbc,abbcac,abc,acc,c)(a|b)aa*(ba)*与后面的那些串匹配?,ba,bba,baa,aa,ababa,第三章,2.为下边所描述的串写正规式，字母表是 0,1.a)以01 结尾的所有串b)只包含一个0的所有串 c)包含偶数个1但不含0的所有串d)包含偶数个1且含任意数目0的所有串e)包含01子串的所有串f)不包含01

5、子串的所有串,(0|1)*01,1*01*,(11)*,(0*10*10*)*,(0|1)*01(0|1)*,1*0*,第三章,3.请描述下面正规式定义的串.字母表S=x,y。a)x(x|y)*x 必须以 x 开头和x结尾的串 b)x*(yx+)*x*每个 y 至少有一个 x 跟在后边的串 c)(x|y)*(xx|yy)(x|y)*所有含两个相继的x或两个相继的y的串,第三章,4.指出哪些串是自动机可接受的xy xyxxy yyyx xyyxyxyxxy,第三章,5.将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。,第三章,解:用子集法将NFA确定化，如下图所示。,

6、X,1,3,2,3,Y,3,Y,1,3,4,3,2,3,4,Y,2,3,Y,2,3,Y,2,3,Y,3,4,3,Y,3,4,Y,3,4,3,4,2,3,4,Y,2,3,4,Y,2,3,4,Y,2,3,4,Y,3,4,Y,3,4,Y,上图所对应的DFA如下所示。,第三章,对上图的DFA进行最小化。首先将状态分为非终态集和终态集两部分：0,1,2,5和3,4,6,7。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分0,1,2,5,4,3,6,7,第三章,第三章,对于非终态集，在输入字符a、b后按其下一状态落入的状

7、态集不同而最终划分为0,1,2,5,4,3,6,7按顺序重新命名为0、1、2、3、4、5，得到最简DFA如下图所示。,0,1,2,5,4,3,6,7,6.设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。解：(1)该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正规表达式对应的NFA如下图所示。,第三章,第三章,正规表达式：a(aa)*bb(bb)*a(aa)*,用子集法将上图确定化，如图所示。,X,1,2,1,1,2,3,4,5,

8、6,Y,Y,3,4,5,4,Y,6,重新命名后的状态转换矩阵可化简为(可由最小化方法得到)X,2 1 3,5 46 Y按顺序重新命名为0、1、2、3、4、5后得到最简的DFA，如下图所示。,第三章,a(aa)*bb(bb)*a(aa)*,7.有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。(1)写出售货机售糖的正规表达式；(2)构造识别上述正规式的最简DFA。解：(1)设a=1，b=2，则售货机售糖的正规表达式为a(b|a(a|b)|b(a|b)。(2)画出与正规表达式a(b|a(a|b)|b(a|b)对应

9、的NFA，如图所示。,第三章,第三章,正规表达式：a(b|a(a|b)|b(a|b),第三章,用子集法将NFA确定化。,Y,3,Y,Y,2,Y,Y,1,3,Y,X,1,2,由转换矩阵可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态即最简状态0、1、2，3、4。按顺序重新命名为0、1、2、3，则得到最简DFA，如下图所示。,第三章,第三章,第四章,作业4.3 设有文法GS:SA AB|AiBBC|B+C C)A*|(1）将文法GS改写为LL(1)文法。2）求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。3）构造相应的预测分析表。,第四章,1）将文法GS改

10、写为LL(1)文法。文法GS为左递归文法，削去文法左递归后的文法为：SAABAA iBA|BCBB+CB|C)A*|(,SA AB|AiBBC|B+C C)A*|(,第四章,1）将文法GS改写为LL(1)文法。FIRST(C)=(,)FIRST(B)=+,FIRST(B)=(,)FIRST(A)=i,FIRST(A)=(,)FIRST(S)=(,)FOLLOW(S)=$FOLLOW(A)=$,*FOLLOW(A)=$,*FOLLOW(B)=i,$,*FOLLOW(B)=i,$,*FOLLOW(C)=+,i,$,*,SA ABA A iBA|BCB B+CB|C)A*|(,第四章,SELECT(

11、SA)=FIRST(A)=(,)SELECT(ABA)=(,)SELECT(AiBA)=iSELECT(A)=FOLLOW(A)=$,*SELECT(BCB)=(,)SELECT(B+CB)=+SELECT(B)=i,$,*SELECT(C)A*)=)SELECT(C()=(因为同一非终结符的不同产生式的Select集交集为空，所以改写后的文法是LL(1)文法。2）求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。在上步中已经求出。,FIRST(C)=(,)FIRST(B)=+,FIRST(B)=(,)FIRST(A)=i,FIRST(A)=(,)FIRST(S)=(,)FOLLO

12、W(S)=$FOLLOW(A)=$,*FOLLOW(A)=$,*FOLLOW(B)=i,$,*FOLLOW(B)=i,$,*FOLLOW(C)=+,i,$,*,3）构造相应的预测分析表。,B,B,C)A*,B+CB,B,C(,B,BCB,BCB,B,A,A,AiBA,A,ABA,ABA,A,S,$,*,),+,i,(,终极符号,语法变量,S A,S A,SELECT(SA)=(,)SELECT(ABA)=(,)SELECT(AiBA)=i SELECT(A)=$,*SELECT(BCB)=(,)SELECT(B+CB)=+SELECT(B)=i,$,*SELECT(C)A*)=)SELECT(

13、C()=(,C,第四章,作业4.5 设有表格结构文法GS:Sa|(T)TT,S|S 1）计算文法的FIRSTVT集和LASTVT集。2）构造其优先关系表，并判断其是否为算符优先文法。3）计算其优先函数。,第四章,1）计算文法的FIRSTVT集和LASTVT集。FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)2）构造其优先关系表，并判断其是否为算符优先文法。,Sa|(T)TT,S|S,=,$,a,(,a,),=,(,$,),第四章,3）计算其优先函数。用逐次加1法构造优先函数,第四章,例文法GS SE EaA|bB AcA|d Bc

14、B|d 1）构造识别文法活前缀的DFA2）构造其LR(0)分析表3）输入串aabab是否为文法G定义的句子,0:SE EaA EbB,4:AcA AcA Ad,5:BcB BcB Bd,3:EbB BcB Bd,1:SE,2:EaA AcA Ad,11:Bd,8:AcA,10:Ad,9:BcB,6:EaA,7:EbB,LR(0)分析表为:,s2,s3,1,acc,s4,s10,6,s5,s11,7,s4,s10,8,s5,s11,9,SE EaA|bBAcA|d BcB|d,(0)SE(1)Ea(2)EbB(3)Ac(4)Ad(5)BcB(6)Bd输入串bccd$的分析过程,0,$,bccd$

15、,S3,03,$b,ccd$,S8,038,$bc,cd$,S8,0388,$bcc,d$,S9,03889,$bccd,$,$,$,$,$,r6,11,0388,$bcc,r5,11,038,$bc,r5,7,03,$b,r2,1,0,$,acc,B,(11),B,(11),B,7,E,1,第四章,8086/8088汇编语言对操作数域的检查可以用LR分析表实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起见，省去了关于m、r和i的产生式，暂且认为m、r、i为终结符，则操作数域P的文法GP为GP:Pm,rm,ir,rr,ir,m试构造能够正确识别操作数域的LR分析表。,(1)将文

16、法GS拓广为文法GS：(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m,第四章,GP:Pm,rm,ir,rr,ir,m,文法GS的DFA,0:SP Pm,r Pm,i Pr,r Pr,i Pr,m,(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m,1:SP,2:Pm,r Pm,i,3:Pr,r Pr,i Pr,m,5:Pm,r Pm,i,4:Pr,r Pr,i Pr,m,6:Pm,r,7:Pm,i,8:Pr,r,9:Pr,i,10:Pr,m,LR(0)分析表,(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)

17、Pr,m输入串m,i$的分析过程,0,$,m,i$,S2,02,$m,i$,S5,025,$m,i$,S7,0257,$m,i,$,r2,0,$,$,acc,1,P,1,例：请指出下图中的LR分析表(a)、(b)、(c)分属LR(0)、SLR(1)和LR(1)中的哪一种，并说明理由。,我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法。其区别如下：(1)对LR(0)分析表来说，若项目A属于Ik(状态)，则对任何终结符a(包括$)，置ACTIONk,a为“用产生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满

18、“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。,(2)对SLR(1)分析表来说，若项目A属于Ik，则对任何输入符号a，仅当aFOLLOW(A)时置ACTIONk,a为“用产生式A进行归约(A为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。,第四章,(3)对LR(1)来说，若项目A,a属于Ik(状态)，则置ACTIONk,a为“用产生式A进行归约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得LR分

19、析器的每个状态能够确切地指出当后跟哪些终结符时才容许把归约为A。例如，假定A,a属于Ik(状态)，则置ACTIONk,a栏目为rj(A为第j个产生式)；而A,b属于Im(状态)，则同样置ACTIONm,b栏目为rj。表现在ACTION子表中，则在不同的行(即不同的状态)里有相同的rj存在。,因此，图3-12(a)的分析表为LR(1)分析表(在不同行有相同的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同)；而图3-12(c)为LR(0)分析表(存在并不全部填满rj的行，且不同行rj的j不同)。,第四章,第五章,1、表达式(AB

20、)(CD)的逆波兰表示为。2、有一语法制导翻译如下所示：SbAb print1A(B print2Aa print3BAa)print4若输入序列为b(aa)a)a)b，且采用自下而上的分析方法，则输出序列为。,34242421,ABCD,3、给出文法GS:SSaA|AAAbB|BBcSd|e请证实AacAbcBaAdbed是文法GS的一个句型；请写出该句型的所有短语、素短语以及句柄；为文法GS的每个产生式写出相应的翻译子程序，使句型AacAbcBaAdbed经该翻译方案归约后，输出为。,第五章,第五章,(1)根据文法GS画出AacAbcBaAdbed对应的语法树如图所示。由图可知AacAbc

21、BaAdbed是文法GS的一个句型。,图 AacAbcBaAdbed对应的语法树,第五章,(2)由图可知，句型AacAbcBaAdbed中的短语为：B,BaA,cBaAd,AbcBaAd,e,AbcBaAdbe,cAbcBaAdbed,A,AacAbcBaAdbed,第五章,从图可看出，句型AacAbcBaAdbed的素短语为：BaA和e。句柄(最左直接短语)为：A。,(3)采用修剪语法树的办法，按句柄方式自下而上归约，每当一个产生式得到匹配时，则按归约的先后顺序与所给的输出顺序进行对应。如：第一个句柄为A，它所对应的产生式为SA，所以它的语义动作应为print(1)；修剪后第二次找到的句柄为B,它所对应的产生式为AB，此时它对应输出序列中的“3”，即它的语义动作为print(3)，依此类推，得到每个产生式相应的语义动作如下：,第五章,第五章,SSaA print(0)SA print(1)AAbB print(2)AB print(3)BcSd print(4)Be print(5),句型AacAbcBaAdbed经该翻译方案归约后，输出为,