编译原理第二章习题答案

第2章习题解答1.文法G[S]为：S-Ac|aBA-abB-bc写出L(G[S])的全部元素。[答案]S=Ac=abc或S=aB=abc所以L(G[S])={abc}==============================================2.文法G[N]为：N-D|NDD-0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}N=ND=NDD....=NDDDD...D=D......D===============================================3.已知文法G[S]：S→dABA→aA|aB→ε|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案]正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b也可为(观察得来):G[S]:S→dAA→a|aA|aBB→bB|ε===============================================================================4.已知文法G[Z]：Z-aZb|ab写出L(G[Z])的全部元素。[答案]Z=aZb=aaZbb=aaa..Z...bbb=aaa..ab...bbbL(G[Z])={anbn|n=1}==============================================================================5.给出语言{anbncm|n=1,m=0}的上下文无关文法。[分析]本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A-β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A-aAb|ab的产生式即可解决。[答案]构造上下文无关文法如下：S-AB|AA-aAb|abB-Bc|c[扩展]凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的：要求符合anbncm，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S-AB，其中A推出anbn，B推出cm。因为m可为0，故上式进一步改写为S-AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A-aAb|ab形式，对于B就很容易写成B-Bc|c了。==============================================================================6.写一文法，使其语言是偶正整数集合。要求：(1)允许0开头；(2)不允许0开头。[答案](1)允许0开头的偶正整数集合的文法E-NT|G|SFMT-NT|GN-D|1|3|5|7|9D-0|GG-2|4|6|8S-NS|εF-1|3|5|7|9|GM-M0|0(2)不允许0开头的偶正整数集合的文法E-NT|DT-FT|GN-D|1|3|5|7|9D-2|4|6|8F-N|0G-D|0=============================================================================7.已知文法G：E-E+T|E-T|TT-T*F|T/F|FF-(E)|i试给出下述表达式的推导及语法树(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)[答案](1)E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i(4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T)=i+(i+T)=i+(i+F)=i+(i+i)8.为句子i+i*i构造两棵语法树，从而证明下述文法G[表达式]是二义的。〈表达式〉-〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i〈运算符〉-+|-|*|/[答案]可为句子i+i*i构造两个不同的最右推导:最右推导1〈表达式〉=〈表达式〉〈运算符〉〈表达式〉=〈表达式〉〈运算符〉i=〈表达式〉*i=〈表达式〉〈运算符〉〈表达式〉*i=〈表达式〉〈运算符〉i*i=〈表达式〉+i*i=i+i*i最右推导2〈表达式〉=〈表达式〉〈运算符〉〈表达式〉=〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式=〈表达式〉〈运算符〉〈表达式〉〈运算符〉i=〈表达式〉〈运算符〉〈表达式〉*i=〈表达式〉〈运算符〉i*i=〈表达式〉+i*i=i+i*i所以，该文法是二义的。======================================================================9.文法G[S]为：S-Ac|aBA-abB-bc该文法是否为二义的？为什么？[答案]对于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不同的最右推导所以，该文法是二义的。===========================================================================10.考虑下面上下文无关文法：S-SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。(2)G[S]的语言是什么？[答案](1)此文法生成串aa+a*的最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成的语言是即加法和乘法的逆波兰式,==============================================================================11.令文法G[E]为:E-E+T|E-TT-T*F|T/F|FF-(E)|I证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。[答案]此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列:E=E+T=E+T*F，所以E+T*F句型此句型相对于E的短语有:E+T*F；相对于T的短语有T*F,直接短语为：T*F；。句柄为：T*F12.已知文法G[E]:E→ET+|TT→TF*|FF→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.[答案]该句型对应的语法树如下：该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F.13.一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄。(1)串abbaa最左推导:S=ABS=aBS=aSBBS=aεBBS=aεbBS=aεbbS=aεbbAa=aεbbaa最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Aεbbaa=aεbbaa(2)产生式有：S→ABS|Aa|εA→aB→SBB|b(3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2；直接短语有a1、b1、b2、a2；句柄是a1。=====================================================================14.给出生成下列语言的上下文无关文法。（1）{anbnambm|n，m=0}(2){1n0m1m0n|n，m=0}（3）{WaWr|W属于{0|a}*，Wr表示W的逆}[答案]（1）{anbnambm|n，m=0}S-AAA-aAb|ε(2){1n0m1m0n|n，m=0}S-1S0|AA-0A1|ε（3）{WaWr|W属于{0|a}*，Wr表示W的逆}S-0S0|1S1|ε===================================================================15.给出生成下列语言的三型文法。(1){an|n=0}(2){anbm|n,m=1}(3){anbmck|n,m,k=0}[答案](1){an|n=0}的三型文法为：S-aS|ε(2){anbm|n,m=1}的三型文法为：S-aAA-aA|bBB-bB|ε(3){anbmck|n,m,k=0}的三型文法为:A-aA|bB|cC|εB-bB|cC|εC-cC|ε==========================================================================16.构造一文法产生任意长的a,b串，使得|a|=|b|=2|a|其中，“|a|”表示a字符的个数;“|b|”表示b字符的个数。[分析]b的个数在a与2a之间，所以应想到形如aSBS和BSaS的形式，B为1到2个b，即可满足条件。[答案]如分析中所述，可得文法如下：S-aSBS|BSaS|εB-bb|b第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b，所以第1个产生式可以保证b的个数在|a|与2|a|之间，而a与b的位置可以任意排布，所以此文法即为所求，注意第1个产生式中要包括s。==============================================================================17.下面的文法产生a的个数和b的个数相等的非空a,b串S-aB|bAB-bS|aBB|bA-aS|bAA|a其中非终结符B推出b比a的个数多1个的串，A则反之。说明该文法是二义的。对上述文法略作修改，使之非二义，并产生同样的语言。（略做修改的含义是：不增加非终结符。）[答案]句子aabbab有两种不同的推导。S=aB=aaBB=aabB=aabbS=aabbaB=aabbabS=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab即它可以产生两棵不同的语法树，故它是二义的。修改后的无二义文法如下：S-aBS|bAS|aB|bAB-aBB|bA-bAA|a====================================================================18.给出0，1，2，3型文法的定义。[答案]乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。如果它的每个产生式α-β的结构是α∈（VnUVt）*且至少含有一个非终结符,而β∈（VnUVt）*，我们说G=（Vt，VN，S，δ）是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为：1．G的任何产生式α-β均满足|α|=|β|；仅仅S-ε例外，但S不得出现在任何产生式的右部。2．G的任何产生式为A-β，A∈Vn，β∈（VnUVt）*3．G的任何产生式为A-aB或A-a，其中A，B∈Vn1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，—般不允许替换