编译原理习题与答案资料

第二章2.2设有文法G[N]:N-D|NDD-0|1|…|9(1)G[N]定义的语言是什么？(2)请给出句子0123的最左推导和最右推导。NNDNDDNDDDDDDD0DDD01DD012D0123NNDN3ND3N23ND23N123D12301232.5证明下面的文法是二义性的。S→iSeS|iS|i答：对句子iiiei对应两棵不同的语法树第二章SiSSeiSiiSiSSeiSii2.9设有文法G[T]:T→T*F|FF→FîP|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第二章PFîPTF*第三章3.1构造正规式1(0|1)*101相应的NFAX1B1C10DYA(0|1)*X1B1C10DYAεEε0|1X1B1C10DYAεEε0,1第三章3.1构造正规式1(0|1)*101相应的NFAX11B10CYA(0|1)*0,1X11B10CYAX1B1C10DYAεEε0,1第三章3.5给出下述文法所对应的正规式。G：S→aAA→bA|aB|bB→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给出文法G[S]，构造相应最小的DFA。G：S→aS|bA|bA→aS解：由文法到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给出文法G[S]，构造相应最小的DFA。G：S→aS|bA|bA→aS解：②由文法直接到NFA文法对应的有自动M=({S,A,T},{a,b},f,S,{T})其对应的状态转换图为：产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S第三章正规式：(a|ba)*bTbSAaba产生式转换函数S→aSf(S,a)=SS→bAf(S,b)=AS→bf(S,b)=TA→aSf(A,a)=S第三章将NFA确定化为DFA如右图所示最小化：此状态图已经为最简了。TbSAaba{S}{S}{A,T}{A,T}{S}IbIaI0101001aba--第三章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)。XY1342abaabbabab第三章解:用子集法将NFA确定化，如下图所示。IIaIb{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}ba01213425－336435557666767重新命名XY1342abaabbabab上图所对应的DFA如下所示。345aabba2bb01a7bb6babaa第三章ba01213425－336435557666767对上图的DFA进行最小化。首先将状态分为非终态集和终态集两部分：{0,1,2,5}和{3,4,6,7}。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其化为分{0,1,2,5},{4},{3,6,7}第三章ba01213425－336435557666767第三章对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为{0},{1},{2},{5},{4},{3,6,7}按顺序重新命名为0、1、2、3、4、5，得到最简DFA如下图所示。{0,1,2,5},{4},{3,6,7}ba01213425－336435557666767012ab435aabbbbbaa345aabba2bb01a7bb6babaa6.设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。解：(1)该语言对应的正规式为a(aa)*bb(bb)*a(aa)*。(2)a(aa)*bb(bb)*a(aa)*正规表达式对应的NFA如下图所示。第三章第三章正规表达式：a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aaIIaIb用子集法将上图确定化，如图所示。{X}{1}{2}{1}{1}{2}{3}{4}{5}{6}－{Y}－{Y}－{3}－{4}{5}{4}－重命名X1234Y5612－－3－1Y6－Y45－4－ab{Y}{6}－Y1Xba345bbab6aa2aa重新命名后的状态转换矩阵可化简为(可由最小化方法得到){X,2}{1}{3,5}{4}{6}{Y}按顺序重新命名为0、1、2、3、4、5后得到最简的DFA，如下图所示。X1234Y5612－－3－1Y6－Y45－4－abY1Xba345bbab6aa2aa第三章a(aa)*bb(bb)*a(aa)*Y1Xba345bbab6aa2aa510ba23abab4aa7.有一台自动售货机，接收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)对应的NFA，如图所示。第三章XY123ababbaba第三章正规表达式：a(b|a(a|b))|b(a|b)IIaIb第三章用子集法将NFA确定化。重新命名{Y}－－{3}{Y}{Y}{2}{Y}{Y}{1}{3}{Y}{X}{1}{2}XY123ababbaba4－－344244134012ab由转换矩阵可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态即最简状态{0}、{1}、{2，3}、{4}。按顺序重新命名为0、1、2、3，则得到最简DFA，如下图所示。第三章4－－344244134012ab0312abbbaa－－3233123012ab第三章第四章作业4.3设有文法G[S]:S→AA→B|AiBB→C|B+CC→)A*|(1）将文法G[S]改写为LL(1)文法。2）求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。3）构造相应的预测分析表。第四章1）将文法G[S]改写为LL(1)文法。文法G[S]为左递归文法，削去文法左递归后的文法为：S→AA→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(S→AA→B|AiBB→C|B+CC→)A*|(第四章1）将文法G[S]改写为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,$,*}S→AA→BA’A’→iBA’|εB→CB’B’→+CB’|εC→)A*|(第四章SELECT(S→A)=FIRST(A)=((,))SELECT(A→BA’)=((,))SELECT(A’→iBA’)={i}SELECT(A’→ε)=FOLLOW(A’)={$,*}SELECT(B→CB’)=((,))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）构造相应的预测分析表。B'→εB'→εC→)A*B’→+CB’B'→εC→(B’B→CB’B→CB’BA'→εA'→εA’→iBA’A’A→BA’A→BA’AS$*)+i(终极符号语法变量S→AS→ASELECT(S→A)=((,))SELECT(A→BA’)=((,))SELECT(A’→iBA’)={i}SELECT(A’→ε)={$,*}SELECT(B→CB’)=((,))SELECT(B’→+CB’)={+}SELECT(B’→ε)={i,$,*}SELECT(C→)A*)={)}SELECT(C→()={(}C第四章作业4.5设有表格结构文法G[S]:S→a|∧|(T)T→T,S|S1）计算文法的FIRSTVT集和LASTVT集。2）构造其优先关系表，并判断其是否为算符优先文法。3）计算其优先函数。第四章1）计算文法的FIRSTVT集和LASTVT集。FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}2）构造其优先关系表，并判断其是否为算符优先文法。S→a|∧|(T)T→T,S|S∧=$a(a,)=($,)∧第四章3）计算其优先函数。用逐次加1法构造优先函数∧=$a(a,)=($,)∧1111111111迭代函数函数a∧,()fg0(初值)fg122213233313331344241fg2,第四章例文法G[S]S→EE→aA|bBA→cA|dB→cB|d1）构造识别文法活前缀的DFA2）构造其LR(0)分析表3）输入串aabab是否为文法G定义的句子0:S→·EE→·