编译原理习题答案

习题16．试用各种不同的形式表示法描述1⅓的一切精度的近似值集合。解：省略表示法{1.3,1.33,1.333,……}描述表示法{1.3i|i≥1}或{1}{.3i|i=1}错误：{x|x=1+3∑10-i|i=1},因为形式表示不应涉及任何含义。错误：G[N]:N::=1.MM::=M3M::=3,因为文法仅一组重写规则，不是语言。若给出答案：L(G[N])，正确，但不简洁7.设字母表x={0,1,2,3,4,5,6,7},X+与X*各是什么？各举出4个不同长度的符号串作为例子。解：X是字母表x的正闭包，X*是字母表的闭包，X*={ε}∪X+X+={0,1,00,01,123,345,1234,2345，…}因此是一切可能带前导0的八进制数的集合X*={ε,0,1,00,01,12,345,3456,…}X+:0,1,00,123X*:,1,00,123习题22．设文法G[id]的规则是:id::=a|b|c|ida|idc|id0|id1试写出VT与VN,并对下列符号串a、ab0、a0c01、0a、11与aaa给出可能的推导。解：VT={a,b,c,0,1}VN={id}a:id=aab0:id=id0不能直接推导出idb0,因此不能直接推导出ab0(不能写:id=id0=idb0不能推导出ab0)a0c01:id=id1=id01=idc01=id0c01=a0c010a:id=ida不能直接推导出0a(不能写:id=ida=0a不能推导出0a）11:id=id1不能直接推导出11(不能写：id=id1=11不能推导出11)aaa:id=ida=idaa=aaa3．设G[E]:E::=T|E+T|E-TT::=F|T*F|T/FF::=(E)|i1)试给出关于(i)、i*i-i与(i+i)/i的推导。2)证明E+T*F*i+I是该文法的句型，然后列出它的一切短语与简单短语。解：1）给出推导E=T=F=(E)=(T)=(F)=(i)不能写：E=T=F=(E)=(i)可以写:E=T=F=(E)=+(i)E=E-T=T-T=T*F-T=F*F-T=i*F-T=i*i-T=i*i-F=i*i-i(最左推导)或E=E-T=E-F=E-i=T-i=T*F-i=T*i-i=F*i-i=i*i-i(最右推导)E=T=T/F=F/F=(E)/F=(E+T)/F=(T+T)/F=(F+T)/F=(i+T)/F=(i+F)/F=(i+i)/F=(i+i)/i(最左推导)或E=T=T/F=T/i=F/i=(E)/i=(E+T)/i=(E+F)/i=(E+i)/i=(T+i)/i=(F+i)/i=(i+i)/i(最右推导)2)证明E+T*F*i+i是该文法的句型：E=E+T=E+T+T=E+T*F+T=E+T*F*F+T=E+T*F*i+T=E+T*F*i+F=E+T*F*i+i或E=E+T=E+F=E+i=E+T+i=E+T*F+i=E+T*i+i=E+T*F*i+i即，E=*E+T*F*i+i，所以是该文法的句型。因为E=*EE=+E+T*F*i+iE=*E+iE=+E+T*F*iE=*E+T+iT=+T*F*iE=*E+T*F*i+TT=+iE=*E+T*i+iT=T*FE=*E+T*F*F+FF=i(=+包括=)所以句型E+T*F*i+i中相对于E的短语有E+T*F*i+i和E+T*F*i相对于T的短语有T*F*i、T*F和i相对于F的短语有i所以句型E+T*F*i+i中相对于T的简单短语有T*F相对于F的简单短语有i不能用画语法分析树的方法来寻找短语，因按教学进度，还未讲到语法分析树。简单短语可如下寻找：首先寻找与规则右部相同的子符号串，把它归约成相应的非终结符号后,看是否是句型,如果仍是，则此子符号串是简单短语，否则不是。例如，子符号串E+T,可归约成E,但归约后成为E*F*i+i,显然不是句型，所以，E+T不是简单短语。对于短语，类似地寻找，即，先找子符号串,看它能否归约到某个非终结符号,再看归约后得到的新符号串是否是句型，是，则是短语，否则，不是短语。当在学习了语法分析树之后，可以也应该使用语法分析树来寻找短语与简单短语。6．试为下列语言构造相应的文法。1）{anbmcmdn|m,n≥1}解:写出句子的一般形式:a…aab…bbbccc…cdd…dBBBAA易见可有文法G[A]：A::=aAd|aBdB::=bc|bBc2){ambn|nm0}解：可把ambn(nm0)写成ambmbn-m。易见可有文法G[S]：S::=Sb|AbA::=ab|aAb也可以写出下列文法：G[S]：S::=ab2|Sb|aSb或G[S]：S::=aSb｜aBbB::=Bb｜b可见给定一个语言，可以为它构成若干个不同的文法。习题34．通常程序设计语言包含一些嵌套结构，例如，平衡的括号对，以及对应的if与else等。试简要说明为什么这些结构不能用正则文法描述。答：通常程序设计语言必定包含一些嵌套结构,例如，平衡的括号对，以及对应的if与else等。它们的存在必定因下列规则的必定存在：E::=E+T|TT::=T*F|FF::=(E)|i以及S::=if(E)SelseS因此，E=*xEyx,y≠与S=*uSvu,v≠,即,E与S等必定是具有自嵌套特性的非终结符号。因此通常的程序设计语言的文法必具有自嵌套特性的非终结符号，也就是说不可能是正则文法。5．下列文法中哪一个是自嵌套的，请说明理由。对于非自嵌套文法给出等价的正则文法。⑴G1=({A,B,C},{a,b},P1,A)P1：A::=CB|bB::=CAC::=AB|a答：因存在自嵌套的非终结符号B：B=CA=ABA即，B=*ABA，A≠,所以文法G1是自嵌套的。⑵G2=({A,B,C},{a,b},P2,A)P2：A::=CB|CaB::=bCC::=aB|b答：因不可能得到推导：A=*xAy,其中≠，对于B与C，情况类似，所以A、B与C都不是自嵌套的非终结符号，文法G2是非自嵌套的文法。为构造等价的正则文法，首先确定相应语言。C=aB=abC=abaB=ababC=…=(ab)iC=(ab)ib，即，C=*(ab)ibB=bC=baB=…=(ba)iB=(ba)ibC=*(ba)ib(ab)jb即，B=*(ba)ib(ab)jbA=CB=*(ab)ib(ba)jb(ab)kb又，A=Ca=(ab)iba即,A=*(ab)iba,所以,L(G2)={(ab)ib(ba)jb(ab)kb|i,j,k≥0}∪{(ab)iba|i≥0}对于文法G2,可以采用图示法给出相应的正则文法abab…abba可给出如下的规则：AA::=aA::=BaB::=AbBC::=BbS::=CaABCS显然，S=Ca=Bba=Abba=Babba=Ababba=Bababba=…=B(ab)i-1ba=…=(ab)iba即，S=*(ab)iba(i=1)。为使i=0,让C::=b，因此，对于{(ab)iba|i=0}有下列规则：S::=CaC::=Bb|bB::=AbA:=Ba|a对于{(ab)ib(ba)jb(ab)kb|i,j,k=0}可类似地给出一组规则，这里不拟详细给出。只是请注意：可利用前面的规则以减少规则的个数。习题44．试用不同的方法消去文法G：I::=Ia|Ib|c的规则左递归。解:步骤1判定文法是规则左递归步骤2消去规左递归。步骤3方法1改写规则左递归成右递归。等价文法G为：I::=cII::=(a|b)I|ε方法2改写成扩充BNF表示法.应用规则1提因子有：I::=I(a|b)|c，应用规则2有I::=c{a|b}等价文法G为：I::=c{a|b}5．试消去文法G[W]：W::=A0A::=A0|W1|0的文法左递归与规则左递归。解:步骤1判定文法是文法左递归还是规则左递归步骤2判定文法是文法左递归，所以按相应算法消去文法左递归如下。步骤2.1：把终结符排序成U1=W,U2=A(n=2)步骤2.2：执行循环i=1j=1:ji–1不执行关于j的循环，且关于U1=W不存在规则左递归。i=2j=1,有规则A::=W1|A0|0形如U2::=U1…,把U1::=r1，即，把W::=A0代入得：A::=A01|A0|0即，A::=A(01|0)|0j=2,ji-1消去关于U2=A的规则左递归有A::=0A,A::=(01|0)A|ε步骤3最后得到消去左递归的等价文法G[W]：W::=A0A::=0AA::=(01|1)A|ε说明：如果在第二步中，把原文法等价变换成扩充表示法，则最终的等价文法是G[W]:W::=A0A::=0{01|0}6．试消去文法G[S]：S::=Qc|Rd|cQ::=Rb|Se|bR::=Sa|Qf|a解:步骤1首先判定是文法左递归还是规则左递归步骤2是文法左递归，按相应算法处理如下。步骤2.1把非终结符号排序成U1=SU2=QU3=R(n=3)步骤2.2执行循环：i=1j=1:ji–1，不执行关于j的循环,且关于U1=S不存在规则左递归。i=2j=1,有规则Q::=Se|Rb|b,形如U2::=U1…,把U1::=r1即，把S::=Qc|Rd|c代入，得：Q::=(Qc|Rd|c)e|Rb|b，整理后Q::=Qce|Rde|Rb|ce|bj=2,ji-1对U2其消去规则左递归，得Q::=(R(de|b)|ce|b)QQ::=ceQ|(按扩充表示法，有Q::=（Rb|Rde|ce|b）{ce})i=3j=1,有规则R::=Sa|Qf|a，形如U3::=U1…形，把U1::=r1,即，S::=Qc|Rd|c代入:R::=(Qc|Rd|c)a|Qf|a，整理后，R::=Rda|Qca|Qf|ca|a注意:j循环还未结束,不能消去Ui=R的规则左递归!j=2,有规则R::=Rda|Qca|Qf|ca|a，形如U3::=U2…，把U2::=r2,即，把Q::=(R(b|de)|ce|b)Q代入，(按扩充表示法代入的是Q::=(Rb|Rde|ce|b){ce}))所以R::=Rda|(R(b|de)|ce|b)Q(ca|f)|ca|a，整理:R::=R((b|de)Q(ca|f)|da)|(ce|b)Q(ca|f)|ca|aj=3,ji-1消去关于U3=R的规则左递归,得：R::=((ce|b)Q(ca|f)|ca|a)RR::=((b|de)Q(ca|f)|da)R|(当按扩充表示法时是:R::=((ce|b)Q(ca|f)|ca|a){(b|de)Q(ca|f)|da})步骤3最后消去了左递归的等价文法G’[S]：S::=Qc|Rd|cQ::=(R(b|de)|ce|b)QQ::=ceQ|R::=((b|ce)Q(ca|f)|ca|a)RR::=((b|de)Q(ca|f)|da）R|(按扩充表示法时是G[S]:S::=Qc|Rd|cQ::=(Rb|Rde|ce|b){ce}R::=((ce|b)Q(ca|f)|ca|a){(b|de)Q(ca|f)|da})习题51.设有文法G[S]：S::=aAcB|BdSB::=aScA|cAB|bA::=BaB|aBc|a试对下列符号串：1）aabcccab2)ababccbb进行句型分析，识别是否是文法G[S]的句子。当是句子时，给出最左推导、最右推导与相应的语法分析树。解：1）建立最左推导如下：S=aAcB=aaBccB=aa