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

  1. 1、本文档共13页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第2章 习题解答 1.文法G[S]为: S-Ac|aB A-ab B-bc 写出L(G[S])的全部元素。 [答案] S=Ac=abc 或S=aB=abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为: N-D|ND D-0|1|2|3|4|5|6|7|8|9 G[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→dAB? A→aA|a? B→ε|bB 问:相应的正规式是什么?G[S]能否改写成为等价的正规文法? [答案] 正规式是daa*b*; 相应的正规文法为(由自动机化简来): G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε =============================================================================== 4.已知文法G[Z]: Z-aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=aZb=aaZbb=aaa..Z...bbb= aaa..ab...bbb L(G[Z])={anbn|n=1} ============================================================================== 5.给出语言{anbncm|n=1,m=0}的上下文无关文法。 [分析] 本题难度不大,主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是:A-β,A∈Vn,β∈(Vn∪Vt)*,注意关键问题是保证anbn的成立,即“a与b的个数要相等”,为此,可以用一条形如A-aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下: S-AB|A A-aAb|ab B-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|SFM 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 N-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)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构造两个不同的最

文档评论(0)

imby0eybk9 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档