编译原理第二章习题答案

1、第2章习题解答1. 文法G为：S-Ac|aBA-abB-bc写出L(GS)的全部元素。答案S=Ac=abc或 S=aB=abc所以 L(G)=abc2. 文法GN为：N-D|NDD-0|l|2|3|4|5|6|7|8|9GN的语言是什么答案GN的语言是 V+o V=0,1,2,3,4,5,6,7,8,9n=nd=ndd. =NDDDD.D=DD3已知文法GS：SdAB AaA|a B |bB问：相应的正规式是什么G能否改写成为等价的正规文法答案正规式是daa*b*；相应的正规文法为（山自动机化简来）：GS:SdA Aa | aB BaB| a|b|bC CbC | b也可为（观察得来）:G:S

2、dAAa|aA|aB BbB| 4已知文法GZ：Z-aZb|abaZb=aaZbb=aaa.Z.bbb= aaa.ab.bbbL(GZ)=anbn|n=l5.给出语言aBc叫n=l,m=O|ft上下文无关文法。分析本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基 本定义是：A-P,AeVn, P G （VnUVt） 注意关键问题是保证abn的成立， 即“a与b的个数要相等”，为此，可以用一条形如A-aAb|ab的产生式即可解 决。答案构造上下文无关文法如下：S-AB|AA-aAb|abB-Bc|c扩展凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路 是这样的

3、：要求符合anbncm,因为a与b要求个数相等，所以把它们应看作一个整体单元进 行，而凸做为另一个单位，初步产生式就应写为S-AB,其中A推出anbn, B推 出凸。因为m可为0,故上式进一步改写为S-AB|AC接下来考虑A,凡是要求两 个终结符个数相等的问题，都应写为A-aAb|ab形式，对于B就很容易写成 B-Bc|c T。6 .写一文法，使其语言是偶正整数集合。 要求：允许0开头；(2) 不允许0开头。答案(1) 允许0开头的偶正整数集合的文法E-NT|G|SFMT-NT|GN-D|1|3|5|7|9D-0|GG-2|4|6|8S-NS| eF-1|3|5|7|9|G(2) 不允许0开头

4、的偶正整数集合的文法E-NT|DT-FT|GN-D|1|3|5|7|9D-2|4|6|8F-N|OG-D|O7已知文法G：)E-E+T|E-T|TT-T*F|T/F|FF-(E)|i试给出下述表达式的推导及语法树(l)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

5、) =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= 1 + 1 * 1最右推导2表达式=表达式运算符表达式=表达式运算符表达式运算符表达式=表达式运算符表达式运算符i=表达式运算符表达式* i= 表达式运算符i * i=表达式+ i * i= 1+1*1所以，该文法是二义的。9.文法G

6、为：S-Ac|aBA-abB-bc该文法是否为二义的为什么答案对于串abc(l) S=Ac=abcS=aB=abc即存在两不同的最右推导所以，该文法是二义的。10考虑下面上下文无关文法：S-SS*|SS+|a(1) 表明通过此文法如何生成串aa+a*,并为该串构造语法树。(2) G的语言是什么答案(1) 此文法生成串aa+a*的最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2) 该文法生成的语言是即加法和乘法的逆波兰式，令文法GE为:E-E+T|E-TT-T*F|T/F|F证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案此句型对应语法树如

7、右，故为此文法一个句型。或者：因为存在推导序列：E=E+T=E+T*F,所以E+T*F句型此句型相对于E的短语有:E+T-F；相对于T的短语有T*F,直接短语为：T*F； o句柄为：T*F12.已知文法GE:EET+|T TTF* | F F | a试证：是文法的句型，指出该句型的短语、简单短语和句柄.答案该句型对应的语法树如下: 该句型相对于E的短语有FFaa*.相对于J的短语有FFaa*/F;相对于f的短语 有Fa；Faa；简单短语有F;句柄为F.13个上下文无关文法生成句子abbaa的推导树如下:给出吊abbaa最左推导、最右推导。(2) 该文法的产生式集合P可能有哪些元素(3) 找出该

8、句子的所有短语、直接短语、句柄。串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*aBSBB|b(3) 该句子的短语有 8ibib2a283、ai、bi b2、bib2、823、a2；!直接短语有ai、bi、b2、a2：句柄是aio14 给出生成下列语言的上下文无关文法。(1) anbnambm |n, m=0(2) ln0m lm0n| n, m=0(3) WaWr|W 属于

9、0|a*, W表示 W 的逆答案(1) anbnambm| n, m=0S-AAA-aAb I (2) ln0m lm0n| n, m=0S-1SO|AA-OA11 e(3) WaWr|W 属于0|a*, W表示 W 的逆S-OSO|1S1| 15 给出生成下列语言的三型文法。(1) an|n =0anbm|n,m=l(3) anbnfm=0I答案(1) an|n=0的三型文法为：S-aS| e(2) anbm|n,m=l 的三型文法为：S-aAA-aA|bBB-bB| e(3) 何已占山皿1=0的三型文法为:A-aA|bB|cC| B-bB|cC| AC-cC| 16.构造一文法产生任意长的

10、a,b $,使得|a|=|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=aabb

11、aB=aabbabS=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab即它可以产生两棵不同的语法树，故它是二义的。修改后的无二义文法如下：S-aBS|bAS|aB|bAA-bAA | a给出0, 1, 2, 3型文法的定义。答案乔姆斯基(chomsky)ffi文法分成类型，即0型，1型，2型和3型，0型强于 1型，1型强于2型，2型强于3型。如果它的每个产生式-P的结构是a (VnUVt) 且至少含有一个非终结 符，而0丘(VnUVt) S我们说G= (Vt, VN, S, 6 )是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当 于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚 举集必定是一个0型语言。如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为：1. G的任何产生式a-P均满足|