编译原理习题与答案

第二章2.2设有文法设有文法GN:N-D|NDD-0|1|9(1)GN定义的语言是什么？定义的语言是什么？(2)请给出句子请给出句子0123的最左推导和最右推导。的最左推导和最右推导。N ND NDD NDDDDDDD 0DDD01DD012D0123N ND N3ND3 N23ND23N123D12301232.5证明下面的文法是二义性的。证明下面的文法是二义性的。SiSeS|iS|i答：对句子答：对句子iiiei对应两棵不同的语法树对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii2.9设有文法设有文法GT:TT*F|F FFP|PP(T)|i分析句型分析句型T*P(T*F)的短语、直接短语和句柄的短语、直接短语和句柄答：句型答：句型T*P(T*F)的语法树：的语法树：TTF*()T五棵子树对应五个短语五棵子树对应五个短语T*P(T*F),P(T*F),P,(T*F),T*F两层子树两层子树(简单子树简单子树)的末端结点构成直接短语的末端结点构成直接短语 两棵两层子树对应两个直接短语：两棵两层子树对应两个直接短语：P,T*F位于最左边的两层子树的末端结点构成句柄：位于最左边的两层子树的末端结点构成句柄：P第二章PFPTF*第三章3.1构造正规式构造正规式1(0|1)*101相应的相应的NFAX1B1C10DYA(0|1)*X1B1C10DYAE0|1X1B1C10DYAE0,1第三章3.1构造正规式构造正规式1(0|1)*101相应的相应的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAE0,1第三章3.5给出下述文法所对应的正规式。给出下述文法所对应的正规式。G：SaAAbA|aB|bBaA解：先由产生式得解：先由产生式得: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：SaS|bA|bAaS解解：由文法到由文法到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|bAaS解解：由文法直接到由文法直接到NFA文法对应的有自动文法对应的有自动M=(S,A,T,a,b,f,S,T)其对应的状态转换图为：其对应的状态转换图为：产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,bf(S,b)=A)=ASbf(S,bf(S,b)=T)=TAaSf(A,af(A,a)=S)=S第三章正规式：正规式：(a|ba)*bTbSAaba产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,bf(S,b)=A)=ASbf(S,bf(S,b)=T)=TAaSf(A,af(A,a)=S)=S第三章将将NFA确定化为确定化为DFA如右图所示如右图所示最小化：此状态图已经为最简了。最小化：此状态图已经为最简了。TbSAabaSSA,TA,TSIbIaI0101001aba-第三章1.指出与正规式匹配的串。指出与正规式匹配的串。a)(ab|b)*c与后面的那些串匹配？与后面的那些串匹配？ababbcababcbabcaaabcb)ab*c*(a|b)c与后面的那些串匹配？与后面的那些串匹配？acacacbbcabbcacabcaccc)(a|b)aa*(ba)*与后面的那些串匹配与后面的那些串匹配?babbabaaaaababa第三章2.为下边所描述的串写正规式，字母表是为下边所描述的串写正规式，字母表是0,1.a)以以01结尾的所有串结尾的所有串b)只包含一个只包含一个0的所有串的所有串c)包含偶数个包含偶数个1但不含但不含0的所有串的所有串d)包含偶数个包含偶数个1且含任意数目且含任意数目0的所有串的所有串e)包含包含01子串的所有串子串的所有串f)不包含不包含01子串的所有串子串的所有串(0|1)*011*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.指出哪些串是自动机可接受的指出哪些串是自动机可接受的xyxyxxyyyyxxyyxyxyxxy第三章5.将将下下图图所所示示的的非非确确定定有有限限自自动动机机(NFA)变变换换成成等等价价的的确确定定有有限限自动机自动机(DFA)。第三章解解:用用子子集集法法将将NFA确确定定化化，如如下图所示。下图所示。IIaIbX132,3,Y3,Y13,432,3,4,Y2,3,Y2,3,Y2,3,Y3,43,Y3,4,Y3,43,42,3,4,Y2,3,4,Y2,3,4,Y2,3,4,Y3,4,Y3,4,Yba01213425336435557666767重新命名重新命名 上上图所对应的图所对应的DFA如下所示。如下所示。第三章ba01213425336435557666767对对上上图图的的DFA进进行行最最小小化化。首首先先将将状状态态分分为为非非终终态态集集和和终终态态集集两两部部分分：0,1,2,5和和3,4,6,7。由由终终态态集集可可知知，对对于于状状态态3、6、7，无无论论输输入入字字符符是是a还还是是b的的下下一一状状态态均均为为终终态态集集，而而状状态态4在在输输入入字字符符b的的下下一一状状态态落落入入非非终终态态集集，故故将将其其化为分化为分0,1,2,5,4,3,6,7第三章ba01213425336435557666767第三章对对于于非非终终态态集集，在在输输入入字字符符a a、b b后后按按其其下下一一状状态态落落入入的的状状态态集集不同而最终划分为不同而最终划分为0,1,2,5,4,3,6,7按按顺顺序序重重新新命命名名为为0、1、2、3、4、5，得到最简得到最简DFADFA如下图所示。如下图所示。0,1,2,5,4,3,6,7ba012134253364355576667676.设有设有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(aaa(aa)*bb(bbbb(bb)*a(aaa(aa)*IIaIb用子集法将上图确定化，如图所示。用子集法将上图确定化，如图所示。X121123456YY3454重命名重命名X1234Y561231Y6Y454abY6重重新新命命名名后后的的状状态态转转换换矩矩阵阵可化简为可化简为(可由最小化方法得到可由最小化方法得到)X,213,546Y按顺序重新命名为按顺序重新命名为0、1、2、3、4、5后得到最简的后得到最简的DFA，如，如下图所示。下图所示。X1234Y561231Y6Y454ab第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa7.7.有有一一台台自自动动售售货货机机，接接收收1 1分分和和2 2分分硬硬币币，出出售售3 3分分钱钱一一块块的的硬硬糖糖。顾顾客客每每次次向向机机器器中中投投放放3 3分分的的硬硬币币，便可得到一块糖便可得到一块糖(注意：只给一块并且不找钱注意：只给一块并且不找钱)。(1)(1)写出售货机售糖的正规表达式；写出售货机售糖的正规表达式；(2)(2)构造识别上述正规式的最简构造识别上述正规式的最简DFADFA。解解：(1)(1)设设a=1a=1，b=2b=2，则售货机售糖的正规表达式为则售货机售糖的正规表达式为a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)。(2)(2)画画出出与与正正规规表表达达式式a(b|a(a|b)|b(a|b)a(b|a(a|b)|b(a|b)对对应应的的NFANFA，如图所示。如图所示。第三章第三章正规表达式：正规表达式：a(b|a(a|b)|b(a|b)IIaIb第三章用子集法将用子集法将NFA确定化。确定化。重新命名Y3YY2YY13YX124344244134012ab由由转转换换矩矩阵阵可可看看出出，非非终终态态2 2和和非非终终态态3 3面面对对输输入入符符号号a a或或b b的的下下一一状状态态相相同同，故故合并为一个状态合并为一个状态即最简状态即最简状态00、11、22，33、44。按按顺顺序序重重新新命命名名为为0 0、1 1、2 2、3 3，则则得得到到最简最简DFADFA，如下图所示。，如下图所示。第三章4344244134012ab0312abbbaa3233123012ab第三章第四章作业作业4.3设有文法设有文法GS:SAAB|AiBBC|B+CC)A*|(1）将文法）将文法GS改写为改写为LL(1)文法。文法。2）求经改写后的文法的每个非终结符的）求经改写后的文法的每个非终结符的FIRST集和集和FOLLOW集。集。3）构造相应的预测分析表。）构造相应的预测分析表。第四章1）将文法）将文法GS改写为改写为LL(1)文法。文法。文法文法GS为左递归文法，削去文法左递归为左递归文法，削去文法左递归后的文法为：后的文法为：SAABAAiBA|BCBB+CB|C)A*|(SAAB|AiBBC|B+CC)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 ABAAiBA|BCBB+CB|C)A*|(第四章SELECT(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)=(,)FOLLOW(S)=$FOLLOW(A)=$,*FOLLOW(A)=$,*FOLLOW(B)=i,$,*FOLLOW(B)=i,$,*FOLLOW(C)=+,i,$,*3）构造相应的预测分析表。）构造相应的预测分析表。BBBBC)A*B+CBBBC(BBCBBCBBAAAAAiBAAABAABAAS$*)+i(终极符号终极符号语法语法变量变量SASASASASELECT(SA)=(,)SELECT(ABA)=(,)SELECT(AiBA)=iSELECT(A)=$,*SELECT(BCB)=(,)SELECT(B+CB)=+SELECT(B)=i,$,*SELECT(C)A*)=)SELECT(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=($,)1111111111迭代函迭代函数数函数函数a,()fg0(初初值值)fg122213233313331344241fg2,第四章例文法例文法GSS EEaA|bBAcA|dBcB|d 1）构造）构造识别识别文法活前文法活前缀缀的的DFA2）构造其）构造其LR(0)分析表分析表3）输输入串入串aabab是否是否为为文法文法G定定义义的句子的句子0:S EEaAEbB4:AcAAcAAdc5:BcBBcBBdc3:EbBBcBBdb1:S EE2:EaAAcAAda11:Bdd8:AcAAccd10:Addd9:BcBB6:EaAA7:EbBBLR(0)分析表为分析表为:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6状态状态ACTIONGOTOabcd#EAB01234567891011S EEaA|bBAcA|dBcB|d(0)S E(1)Ea(2)EbB(3)Ac(4)Ad(5)BcB(6)Bd输入串输入串bccd$的分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO1234567890$bccd$S303$bccd$S8038$bccd$S80388$bccd$S903889$bccd$r6110388$bccr511038$bcr5703$br210$accB(11)B(11)B7E1第四章8086/8088汇汇编编语语言言对对操操作作数数域域的的检检查查可可以以用用LR分分析析表表实实现现。设设m代代表表存存储储器器，r代代表表寄寄存存器器，i代代表表立立即即数数；并并且且为为了了简简单单起起见见，省省去去了了关关于于m、r和和i的的产产生生式式，暂暂且且认认为为m、r、i为为终终结结符符，则则操操作作数数域域P的文法的文法GP为为GP:Pm,r m,i r,r r,i r,m试试构造能构造能够够正确正确识别识别操作数域的操作数域的LR分析表。分析表。(1)将文法将文法GS拓广拓广为为文法文法GS：(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m第四章GP:Pm,r m,i r,r r,i r,m文法GS的DFA0:S PPm,rPm,iPr,rPr,iPr,m(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m1:S PP2:Pm,rPm,i3:Pr,rPr,iPr,m5:Pm,rPm,i4:Pr,rPr,iPr,m,mr,r6:Pm,ri7:Pm,ir8:Pr,ri9:Pr,im10:Pr,mLR(0)分析表分析表状态状态ACTIONGOTOmri，$P0s2s311acc2s53s44s10s8s95s6s76r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r4r4r4r4r410r5r5r5r5r5r1(0)SP(1)Pm,r(2)Pm,i(3)Pr,r(4)Pr,i(5)Pr,m输入串输入串m,i$的分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO123450$m,i$S202$m,i$S5025$m,i$S70257$m,i$r20$acc1P1例例：请请指指出出下下图图中中的的LRLR分分析析表表(a)(a)、(b)(b)、(c)(c)分分属属LR(0)LR(0)、SLR(1)SLR(1)和和LR(1)LR(1)中的哪一种，并说明理由。中的哪一种，并说明理由。我我们们知知道道，LR(0)、SLR(1)和和LR(1)分分析析表表构造的主要差别是构造算法。其区别如下：构造的主要差别是构造算法。其区别如下：(1)对对LR(0)分析表来说，若项目分析表来说，若项目A属属于于Ik(状态状态)，则对，则对任何终结符任何终结符a(包括包括$)，置，置ACTIONk,a为为“用产生式用产生式A进行归约进行归约(A为第为第j个产生式个产生式)”，简记为，简记为“rj”。表现在表现在ACTION子表中，则是每个归约状子表中，则是每个归约状态所在的行全部填满态所在的行全部填满“rj”；并且，并且，同一同一行的行的“rj”其下标其下标j相同，而不同行的相同，而不同行的“rj”其下标其下标j是不一样的。是不一样的。(2)(2)对对SLR(1)SLR(1)分分析析表表来来说说，若若项项目目A A属属于于I Ik k，则则对对任任何何输输入入符符号号a a，仅仅当当a aFOLLOW(A)FOLLOW(A)时时置置ACTIONk,aACTIONk,a为为“用用产产生生式式A A进进行行归归约约(A(A为为第第j j个个产产生生式式)”，简简记记为为“r rj j”。表表现现在在ACTIONACTION子子表表中中，则则存存在在某某个个归归约约状状态态所所在在的的行行并并不不全全部部填填满满r rj j，并且不同行的并且不同行的“r rj j”其下标其下标j j不同。不同。第四章(3)(3)对对LR(1)LR(1)来来说说，若若项项目目AA,a,a属属于于I Ik k(状状态态)，则则置置ACTIONk,aACTIONk,a为为“用用产产生生式式A A进进行行归归约约”，简简记记为为“r rj j”。LR(1)LR(1)是是在在SLR(1)SLR(1)状状态态(项项目目集集)的的基基础础上上，通通过过状状态态分分裂裂的的办办法法(即即分分裂裂成成更更多多的的项项目目集集)，使使得得LRLR分分析析器器的的每每个个状状态态能能够够确确切切地地指指出出当当后后跟跟哪哪些些终终结结符符时时才才容容许许把把归归约约为为A A。例例如如，假假定定AA,a,a属属于于I Ik k(状状态态)，则则置置ACTIONk,aACTIONk,a栏栏目目为为r rj j(A(A为为第第j j个个产产生生式式)；而而AA,b,b属属于于I Im m(状状态态)，则则同同样样置置ACTIONm,bACTIONm,b栏栏目目为为r rj j。表表现现在在ACTIONACTION子子表表中中，则则在在不同的行不同的行(即不同的状态即不同的状态)里有相同的里有相同的r rj j存在。存在。因因此此，图图3-12(a)3-12(a)的的分分析析表表为为LR(1)LR(1)分分析析表表(在在不不同同行行有有相相同同的的r r2 2存存在在)；图图3-12(b)3-12(b)为为LR(0)LR(0)分分析析表表(有有r rj j的的行行是是每每行行都都填填满满了了r rj j且且同同一一行行r rj j的的j j相相同同，不不同同行行r rj j的的j j不不同同)；而而图图3-12(c)3-12(c)为为LR(0)LR(0)分分析析表表(存存在在并并不不全全部部填填满满r rj j的行，且不同行的行，且不同行r rj j的的j j不同不同)。第四章第五章1 1、表达式表达式(A AB)B)(C(CD)D)的逆波兰表示为的逆波兰表示为 。2 2、有一语法制导翻译如下所示：、有一语法制导翻译如下所示：S SbAbbAb print print1 1 A A(B print(B print2 2 A Aa a print print3 3 B BAaAa)print)print4 4 若若输输入入序序列列为为b(aa)a)a)bb(aa)a)a)b，且且采采用用自自下下而而上上的分析方法，则输出序列为的分析方法，则输出序列为 。34242421ABCD3 3、给出文法、给出文法GS:GS:S SSaA|ASaA|AA AAbB|BAbB|BB BcSd|ecSd|e请证实请证实AacAbcBaAdbedAacAbcBaAdbed是文法是文法GSGS的一个句型；的一个句型；请写出该句型的所有短语、素短语以及句柄；请写出该句型的所有短语、素短语以及句柄；为为文文法法GSGS的的每每个个产产生生式式写写出出相相应应的的翻翻译译子子程程序序，使使句句型型AacAbcBaAdbedAacAbcBaAdbed经经该该翻翻译译方方案案归归约约后，输出为后，输出为131042521430131042521430。第五章第五章(1)(1)根根据据文文法法GSGS画画出出AacAbcBaAdbedAacAbcBaAdbed对对应应的的语法树如图所示。语法树如图所示。由由图图可可知知AacAbcBaAdbedAacAbcBaAdbed是是文文法法GSGS的一个句型。的一个句型。图图AacAbcBaAdbed对应的语法树对应的语法树第五章(2)(2)由由图图可可知知，句句型型AacAbcBaAdbedAacAbcBaAdbed中的短语为：中的短语为：B,B,BaABaA,cBaAdcBaAd,AbcBaAdAbcBaAd,e,e,AbcBaAdbeAbcBaAdbe,cAbcBaAdbedcAbcBaAdbed,A,A,AacAbcBaAdbedAacAbcBaAdbed第五章从从 图图 可可 看看 出出，句句 型型AacAbcBaAdbedAacAbcBaAdbed的的素短语为：素短语为：BaABaA和和e e。句柄句柄(最左直接短语最左直接短语)为：为：A A。(3)(3)采采用用修修剪剪语语法法树树的的办办法法，按按句句柄柄方方式式自自下下而而上上归归约约，每每当当一一个个产产生生式式得得到到匹匹配配时时，则则按按归归约约的的先先后后顺序与所给的输出顺序与所给的输出131042521430131042521430顺序进行对应。顺序进行对应。如如：第第一一个个句句柄柄为为A A，它它所所对对应应的的产产生生式式为为S SA A，所所以以它它的的语语义义动动作作应应为为print(print(1 1)；修修剪剪后后第第二二次次找找到到的的句句柄柄为为B,B,它它所所对对应应的的产产生生式式为为A AB B，此此时时它它对对应应输输出出序序列列中中的的“3 3”，即即它它的的语语义义动动作作为为print(print(3 3)，依依此此类类推推，得得到到每每个个产产生生式式相相应应的的语义动作如下：语义动作如下：第五章第五章SSaAprint(0)SAprint(1)AAbBprint(2)ABprint(3)BcSdprint(4)Beprint(5)句型句型AacAbcBaAdbed经该翻译方经该翻译方案归约后，输出为案归约后，输出为131042521430