编译原理 第二章习题答案.docx

上传人:牧羊曲112 文档编号:3125487 上传时间:2023-03-11 格式:DOCX 页数:9 大小:39.91KB
返回 下载 相关 举报
编译原理 第二章习题答案.docx_第1页
第1页 / 共9页
编译原理 第二章习题答案.docx_第2页
第2页 / 共9页
编译原理 第二章习题答案.docx_第3页
第3页 / 共9页
编译原理 第二章习题答案.docx_第4页
第4页 / 共9页
编译原理 第二章习题答案.docx_第5页
第5页 / 共9页
亲,该文档总共9页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《编译原理 第二章习题答案.docx》由会员分享,可在线阅读,更多相关《编译原理 第二章习题答案.docx(9页珍藏版)》请在三一办公上搜索。

1、编译原理 第二章习题答案第2章 习题解答 1.文法GS为: S-Ac|aB A-ab B-bc 写出L(GS)的全部元素。 答案 S=Ac=abc 或S=aB=abc 所以L(GS)=abc = 2. 文法GN为: N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么? 答案 GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D = 3.已知文法GS: SdAB AaA|a B|bB 问:相应的正规式是什么?GS能否改写成为等价的正规文法? 答案 正规式是daa*b*; 相应的正规文法为(由自动机化简来): GS:Sd

2、A Aa|aB BaB|a|b|bC CbC|b 也可为(观察得来):GS:SdA Aa|aA|aB BbB| = 4.已知文法GZ: Z-aZb|ab 写出L(GZ)的全部元素。 答案 Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb L(GZ)=anbn|n=1 = 5.给出语言anbncm|n=1,m=0的上下文无关文法。 分析 本题难度不大,主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A-,AVn,*,注意关键问题是保证anbn的成立,即“a与b的个数要相等”,为此,可以用一条形如A-aAb|ab的产生式即可解决。 答案 构造上下文无关文法如下: S

3、-AB|A A-aAb|ab B-Bc|c 扩展 凡是诸如此类的题都应按此思路进行,本题可做为一个基本代表。基本思路是这样的: 要求符合abc,因为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|S

4、FM T-NT|G N-D|1|3|5|7|9 D-0|G G-2|4|6|8 S-NS| F-1|3|5|7|9|G M-M0|0 (2)不允许0开头的偶正整数集合的文法 E-NT|D T-FT|G nnmN-D|1|3|5|7|9 D-2|4|6|8 F-N|0 G-D|0 = 7.已知文法G: E-E+T|E-T|T T-T*F|T/F|F F-(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)

5、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 *

6、 i 最右推导2 表达式=表达式运算符表达式 =表达式运算符表达式运算符表达式 =表达式运算符表达式运算符 i =表达式运算符表达式 * i = 表达式运算符i * i =表达式+ i * i = i + i * i 所以,该文法是二义的。 = 9. 文法GS为: S-Ac|aB A-ab B-bc 该文法是否为二义的?为什么? 答案 对于串abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导 所以,该文法是二义的。 = 10.考虑下面上下文无关文法: S-SS*|SS+|a (1)表明通过此文法如何生成串aa+a*,并为该串构造语法树。 (2) GS的语言是什么?

7、答案 (1)此文法生成串aa+a*的最右推导如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a* (2)该文法生成的语言是即加法和乘法的逆波兰式, = 11. 令文法GE为: E-E+T|E-T T-T*F|T/F|F F-(E)|I 证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。 答案 此句型对应语法树如右,故为此文法一个句型。 或者:因为存在推导序列: E=E+T=E+T*F,所以 E+T*F句型 此句型相对于E的短语有:E+T*F;相对于T的短语有T*F, 直接短语为:T*F;。 句柄为:T*F 12.已知文法GE: EET+|T TTF* | F

8、 FF | 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=aBBS=abBS=abbS=abbAa=abbaa 最右推导: S=ABS=ABAa=ABaa=ASBBaa=ASBbaa

9、=ASbbaa=Abbaa=abbaa (2)产生式有:SABS |Aa| Aa BSBB|b (3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2; 直接短语有a1、b1、b2、a2; 句柄是a1。 = 14.给出生成下列语言的上下文无关文法。 anbnambm |n,m=0 (2) 1n0m 1m0n| n,m=0 WaWr|W属于0|a*,Wr表示W的逆 答案 anbnambm| n,m=0 S-AA A-aAb| (2) 1n0m 1m0n| n,m=0 S-1S0|A A-0A1| WaWr|W属于0|a*,Wr表示W的逆 S-0S0|1S1| = 1

10、5 .给出生成下列语言的三型文法。 (1) a|n =0 (2) ab|n,m=1 (3)anbmck|n,m,k=0 答案 (1) an|n =0 的三型文法为: S-aS| (2) anbm|n,m=1 的三型文法为: S-aA A-aA|bB B-bB| (3)anbmck|n,m,k=0 的三型文法为: A-aA|bB|cC| nmnB-bB|cC| C-cC| = 16.构造一文法产生任意长的a,b串,使得 |a|=|b|bb|b 第1个产生式为递归定义,由于在第2个产生式中B被定义为1或2个b,所以第1个产生式可以保证b的个数在|a|与2|a|之间,而a与b的位置可以任意排布,所以

11、此文法即为所求,注意第1个产生式中要包括s。 = 17.下面的文法产生a的个数和b的个数相等的非空a,b串 S-aB|bA B-bS|aBB|b A-aS|bAA|a 其中非终结符B推出b比a的个数多1个的串,A则反之。 说明该文法是二义的。 对上述文法略作修改,使之非二义,并产生同样的语言。 答案 句子aabbab有两种不同的推导。 S=aB=aaBB=aabB=aabbS=aabbaB=aabbab S=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab 即它可以产生两棵不同的语法树,故它是二义的。 修改后的无二义文法如下: S-aBS|bAS|aB|bA B-aBB|b

12、 A-bAA|a = 18.给出0,1,2,3型文法的定义。 答案 乔姆斯基(chomsky)把文法分成类型,即0型,1型,2型和3型,0型强于1型,1型强于2型,2型强于3型。 如果它的每个产生式-的结构是*且至少含有一个非终结符,而*,我们说G=是一个0型文法。 0型文法也称短语文法。一个非常重要的理论结果是,0型文法的能力相当于图灵(Tunring)机。或者说,任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。 如果把0型文法分别加上以下的第i条限制,则我们就得i型文法为: 1G的任何产生式- 均满足|例外,但S不得出现在任何产生式的右部。 2G的任何产生式为A-,AVn,* 3G的任何产生式为A-aB或A-a,其中A,BVn 1型文法也称上下文有关文法。这种文法意味着,对非终结符进行替换时务必考虑上下文,而且,般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文, 3型文法也称线性文法。

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号