编译原理习题与答案

第二章2.2 设有文法设有文法GN:N-D | NDD-0|1|9(1) GN定义的语言是什么？定义的语言是什么？(2) 请给出句子请给出句子0123的最左推导和最右推导。的最左推导和最右推导。N ND NDD NDDDDDDD 0DDD01DD 012D0123N ND N3ND3 N23ND23N123 D12301232.5 证明下面的文法是二义性的。证明下面的文法是二义性的。SiSeS | iS | i答：对句子答：对句子iiiei对应两棵不同的语法树对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii2.9 设有文法设有文法GT: TT*F|F F FP|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相应的相应的NFAX 1B1C10D YA (0|1)*X 1B1C10D YAE 0|1X 1B1C10D YAE 0,1第三章3.1 构造正规式构造正规式1(0|1)*101相应的相应的NFAX 11B10C YA (0|1)* 0,1X 11B10C YAX 1B1C10D YAE 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：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)其对应的状态转换图为：其对应的状态转换图为：产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,b)=Af(S,b)=ASbf(S,b)=Tf(S,b)=TAaSf(A,a)=Sf(A,a)=S第三章正规式：正规式：(a|ba)*bTbSAaba产生式产生式转换函数转换函数SaSf(S,a)=Sf(S,a)=SSbAf(S,b)=Af(S,b)=ASbf(S,b)=Tf(S,b)=TAaSf(A,a)=Sf(A,a)=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)*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)。XY1342abaabbabab第三章解解: :用子集法将用子集法将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重新命名重新命名XY1342abaabbabab 上上图所对应的图所对应的DFA如下所示。如下所示。 345aabba2bb01a7bb6babaa第三章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,7ba01213425336435557666767012ab435aabbbbbaa345aabba2bb01a7bb6babaa6.设有设有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)a(aa)* *bb(bb)bb(bb)* *a(aa)a(aa)* *Y1Xba345bbab6aa2aaIIaIb用子集法将上图确定化，如图所示。用子集法将上图确定化，如图所示。X121123456YY3454重命名重命名X1234Y561231Y6Y454abY6Y1Xba345bbab6aa2aa重新命名后的状态转换矩阵重新命名后的状态转换矩阵可化简为可化简为( (可由最小化方法得到可由最小化方法得到) )X,2 1 3,5 46 Y按顺序重新命名为按顺序重新命名为0、1、2、3、4、5后得到最简的后得到最简的DFA，如，如下图所示。下图所示。 X1234Y561231Y6Y454abY1Xba345bbab6aa2aa第三章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，如图所示。，如图所示。第三章XY123ababbaba第三章正规表达式：正规表达式：a(b|a(a|b)|b(a|b)IIaIb第三章用子集法将用子集法将NFA确定化。确定化。 重新命名Y3YY2YY13YX12XY123ababbaba4344244134012ab由转换矩阵可看出，非终态由转换矩阵可看出，非终态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:SA AB|AiBBC|B+C C)A*|( 1）将文法）将文法GS改写为改写为LL(1)文法。文法。2）求经改写后的文法的每个非终结符的）求经改写后的文法的每个非终结符的FIRST集和集和FOLLOW集。集。3）构造相应的预测分析表。）构造相应的预测分析表。第四章1）将文法）将文法GS改写为改写为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(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）构造相应的预测分析表。）构造相应的预测分析表。C)A*B +CBC(BBCBBCBB AiBAAABAABAA S $*)+i (终极符号终极符号语法语法变量变量SELECT(SA) = (,) SELECT(ABA)=(,) SELECT(AiBA) =i SELECT(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, 第四章例文法例文法GS S E EaA|bB AcA|d BcB|d 1）构造识别文法活前缀的）构造识别文法活前缀的DFA2）构造其）构造其LR(0)分析表分析表3）输入串）输入串aabab是否为文法是否为文法G定义的句子定义的句子0: S E EaA EbB 4: AcA AcA Adc5: BcB BcB Bd c3: EbB BcB Bdb1: S EE2: EaA AcA Ada11: Bdd8: AcAAccd10: Addd9: BcBB6: EaA A7: EbBBLR(0)分析表为分析表为:s2s31accs4s106s5s117s4s108s5s11r1r1r1r1r19r2r2r2r2r2r3r3r3r3r3r5r5r5r5r5r4r4r4r4r4r6r6r6r6r6状态状态ACTIONGOTOabcd#EAB01234567891011S E EaA|bBAcA|d BcB|d(0) S E(1) Ea(2) EbB(3) Ac(4) Ad(5) BcB(6) Bd输入串输入串bccd$的分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO1 2 3 4 56789 0$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 P 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,m1: S PP2: Pm,r Pm,i3: Pr,r Pr,i Pr,m5: Pm, r Pm, i4: Pr, r Pr, i Pr, m,mr,r6: Pm, r i7: Pm, i r8: Pr, r i9: Pr, i m10: Pr, mLR(0)分析表分析表状态状态ACTIONGOTOmri，$P0s2s3 1 1 acc 2 s5 3 s4 4s10s8s9 5 s6s7 6r1r1r1r1r1 7r2r2r2r2r2 8r3r3r3r3r3 9r4r4r4r4r4 10r5r5r5r5r5r1(0) SP (1) Pm,r(2) Pm,i(3) Pr,r (4) Pr,i(5) Pr,m输入串输入串m,i$的分析过程的分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTIONGOTO1 2 3 4 5 0$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)中的哪一种，并说明理由。中的哪一种，并说明理由。 (a)(b )(c)5r14r23r22s451acc0s312状态ACTION GOTOb#SB4r1r1r13r2r2r22s2s30s3s211accg状态ACTIONGOTOab#T4r13r22acc1s1s30s12s3状态ACTIONGOTOik#P我们知道，我们知道，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 SbAb printbAb print1 1 A A(B print(B print2 2 A Aa printa print3 3 B BAa) printAa) 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的一个句型。的一个句型。AaSSBAdScABbABbAedScAaSAB图图 AacAbcBaAdbed对应的语法树对应的语法树第五章( 2 )( 2 ) 由 图 可 知 ， 句 型由 图 可 知 ， 句 型AacAbcBaAdbedAacAbcBaAdbed中的短语为：中的短语为： B, BaA, cBaAd, AbcBaAd, e, B, BaA, cBaAd, AbcBaAd, e, AbcBaAdbe, cAbcBaAdbed, A, AbcBaAdbe, cAbcBaAdbed, A, AacAbcBaAdbedAacAbcBaAdbedAaSSBAdScABbABbAedScAaSAB第五章从 图 可 看 出 ， 句 型从 图 可 看 出 ， 句 型AacAbcBaAdbedAacAbcBaAdbed的的素短语为：素短语为：BaABaA和和e e。句柄句柄( (最左直接短语最左直接短语) )为：为：A A。AaSSBAdScABbABbAedScAaSAB(3) (3) 采用修剪语法树的办法，按句柄方式自下而上采用修剪语法树的办法，按句柄方式自下而上归约，每当一个产生式得到匹配时，则按归约的归约，每当一个产生式得到匹配时，则按归约的先后顺序与所给的输出先后顺序与所给的输出131042521430131042521430顺序进行对顺序进行对应。应。如：第一个句柄为如：第一个句柄为A A，它所对应的产生式为，它所对应的产生式为S SA A，所以它的语义动作应为所以它的语义动作应为print(print(1 1) )；修剪后第；修剪后第二次找到的句柄为二次找到的句柄为B,B,它所对应的产生式为它所对应的产生式为A AB B，此时它对应输出序列中的此时它对应输出序列中的“3 3”，即它的语义动作，即它的语义动作为为print(print(3 3) )，依此类推，得到每个产生式相，依此类推，得到每个产生式相应的语义动作如下：应的语义动作如下：第五章第五章SSaA print(0)SA print(1)AAbB print(2)AB print(3)BcSd print(4)Be print(5)AaSSBAdScABbABbAedScAaSAB句型句型AacAbcBaAdbed经该翻译方经该翻译方案归约后，输出为案归约后，输出为131042521430