《编译原理-习题答案》由会员分享，可在线阅读，更多相关《编译原理-习题答案（16页珍藏版）》请在金锄头文库上搜索。
1、第章 习题解答1.文法GS为： S-Ac|aB A-b Bc 写出L(GS)的所有元素。 答案S=Acabc 或S=aB=ac 因此L(S）ab =2. 文法G为： N-DND -0|1|2|3|4|6|7|8|N的语言是什么?答案 G的语言是V+。V=,1,2,3,4，5,6,8,9 NN=D. =DDDD.D=.D =3已知文法GS: SdABAA| |B 问：相应的正规式是什么?G能否改写成为等价的正规文法? 答案正规式是da*b*; 相应的正规文法为(由自动机化简来):G：SA Aa Ba|b|b CbC|b 也可为(观测得来）:GS:SdA Aa|aB BbB| =4.已知文法GZ:
2、 Z-aZ|ab 写出L(GZ）的所有元素。答案 Z=aZb=aaZbb=aaa.Z.bb aa.bbb L(GZ）=bn=5.给出语言anncm|n=1，=0的上下文无关文法。分析本题难度不大，重要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A-,n,(VnVt）*,注意核心问题是保证nbn的成立,即“与b的个数要相等”,为此,可以用一条形如-aAb|ab的产生式即可解决。答案 构造上下文无关文法如下: S-AB|A A-aAb|abBcc扩展但凡诸如此类的题都应按此思路进行，本题可做为一种基本代表。基本思路是这样的： 规定符合c，由于与规定个数相等，因此把它们应看作一种整体单
3、元进行,而做为另一种单位，初步产生式就应写为S-AB，其中A推出anbn,B推出cm。由于m可为,故上式进一步改写为-ABA。接下来考虑A,但凡规定两个终结符个数相等的问题，都应写为-aAb|a形式，对于B就很容易写成B-B|c了。 =6 .写一文法，使其语言是偶正整数集合。 规定: （1）容许开头; （）不容许0开头。答案 （1）容许0开头的偶正整数集合的文法ENT|G|SMT-NT|GN13|5|9-|G G-2|4|NS|F1|7|9|GMM0|0 ()不容许0开头的偶正整数集合的文法 NT|D T-FG ND13|5|7 D-2|6|8F-N|0 -D=7.已知文法G： -E+|-T|
4、T T-TF|TFFF-(）| 试给出下述体现式的推导及语法树 (1)i； (2）*ii (3)+i*i （4)i(i+)答案 （1)ET=F=i(2)=ET=+T=TF=*FT=i*+T=*iTii+*i+i (3）E=+T=TTFTi+=i+*F=i+F*Fi+i*F=ii*i (4)E=E+TTF+T=i+T=i+F=i+（E)=i+(E+T)=i+（T+T)=i+(F+T） (i+T)=i+(i+F)=i+(ii).为句子i+i*i构造两棵语法树，从而证明下述文法G是二义的。 体现式-体现式运算符体现式|（体现式)i运算符-+|-|*|/ 答案 可为句子i+ii构造两个不同的最右推导:
5、 最右推导1 体现式=体现式运算符体现式 =体现式运算符i =体现式* i=体现式运算符体现式*i =体现式运算符 *i =体现式i* i i + i * 最右推导2 体现式=体现式运算符体现式 体现式运算符体现式运算符体现式=体现式运算符体现式运算符 i 体现式运算符体现式* i = 体现式运算符i i =体现式+ *i = i+i * 因此,该文法是二义的。=. 文法GS为： S-Ac|B b B-b该文法与否为二义的?为什么? 答案对于串ac(1)S=Acabc (2)=aB=abc即存在两不同的最右推导 因此,该文法是二义的。 =10.考虑下面上下文无关文法:S-SS*|SS+|a (
6、)表白通过此文法如何生成串a+，并为该串构造语法树。(2) GS的语言是什么? 答案(1)此文法生成串a+a的最右推导如下 S=SS*=SS*=a*SS+a*=aa=aa*(2）该文法生成的语言是即加法和乘法的逆波兰式, =1. 令文法GE为： -E+T|E-TT*FT/F|F -（E) 证明+T*F是它的一种句型，指出这个句型的所有短语、直接短语和句柄。 答案 此句型相应语法树如右,故为此文法一种句型。 或者：由于存在推导序列： =E+T=+T*，因此 E+T句型 此句型相对于的短语有:ET*F；相对于T的短语有F，直接短语为:T*F;。句柄为：T*12.已知文法GE: EET+TTTF*
7、|FF 试证:FF*是文法的句型，指出该句型的短语、简朴短语和句柄.答案该句型相应的语法树如下:该句型相对于的短语有F*；相对于的短语有F*,;相对于F的短语有F;F;简朴短语有;句柄为F.13.一种上下文无关文法生成句子abbaa的推导树如下：（1）给出串abba最左推导、最右推导。 (2)该文法的产生式集合P也许有哪些元素? (3)找出该句子的所有短语、直接短语、句柄。(1)串abbaa最左推导：S=AB=aBSSBBS=aBS=bBS=abbS=abbAaabbaa 最右推导: S=S=ABABaASBBa=ASBa=ASbbaaAbaa=abba （）产生式有：SAB |Aa| Aa
8、BSBB|(3)该句子的短语有a1b1b2aa3、a1、b1、b2、b1、2a3、a2； 直接短语有、b、b2、a2;句柄是a1。 =4.给出生成下列语言的上下文无关文法。(1） bnbm |,m=0 (2） 1n0mn| n，m=0 (3)WaWr|属于0|a，Wr表达W的逆答案 (）annambmn，m0 S-AA A-aAb| (2) 0m 1m0nn，m=0S-1S0A A0A (3)aW|属于0|a*,Wr表达W的逆-0S0|11| =1 给出生成下列语言的三型文法。 (1) n =0 (2) anbm|,m1 ()anmck|n,k=0 答案 (1) an|n = 的三型文法为: SS| (2)ab|,1 的三型文法为： A A-a|bB- （3)bck|n,m,k=0 的三型文法为： -aA|bcC| B-bB|C| C-cC| =16.构造一文法产生任意长的，串，使得|ab|bb|第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b,因此第1个产生式可以保证b的个数在|a|与2|a之间，而a与b的位置可以任意排布，因此此文法即为所求，注意第1个产生式中要涉及s。 =1.下面的文法产生的个数和b的个数相等的非空a，串 -B
