编译原理 龙书答案.doc

编译原理 龙书答案.doc

ID:61015

大小:458.50 KB

页数:24页

时间:2017-05-06

编译原理 龙书答案.doc_第1页
编译原理 龙书答案.doc_第2页
编译原理 龙书答案.doc_第3页
编译原理 龙书答案.doc_第4页
编译原理 龙书答案.doc_第5页
资源描述:

《编译原理 龙书答案.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章部分习题解答Aho:《编译原理技术与工具》书中习题(Aho)4.1考虑文法S→(L)

2、aL→L,S

3、Sa)列出终结符、非终结符和开始符号解:终结符:(、)、a、,非终结符:S、L开始符号:Sb)给出下列句子的语法树i)(a,a)ii)(a,(a,a))iii)(a,((a,a),(a,a)))c)构造b)中句子的最左推导i)SÞ(L)Þ(L,S)Þ(S,S)Þ(a,S)Þ(a,a)ii)SÞ(L)Þ(L,S)Þ(S,S)Þ(a,S)Þ(a,(L))Þ(a,(L,S))Þ(a,(S,S))Þ(a,

4、(a,S)Þ(a,(a,a))iii)SÞ(L)Þ(L,S)Þ(S,S)Þ(a,S)Þ(a,(L))Þ(a,(L,S))Þ(a,(S,S))Þ(a,((L),S))Þ(a,((L,S),S))Þ(a,((S,S),S))Þ(a,((a,S),S))Þ(a,((a,a),S))Þ(a,((a,a),(L)))Þ(a,((a,a),(L,S)))Þ(a,((a,a),(S,S)))Þ(a,((a,a),(a,S)))Þ(a,((a,a),(a,a)))d)构造b)中句子的最右推导i)SÞ(L)Þ(L,S)

5、Þ(L,a)Þ(S,a)Þ(a,a)ii)SÞ(L)Þ(L,S)Þ(L,(L))Þ(L,(L,S))Þ(L,(L,a))Þ(L,(S,a))Þ(L,(a,a))Þ(S,(a,a))Þ(a,(a,a))iii)SÞ(L)Þ(L,S)Þ(L,(L))Þ(L,(L,S))Þ(L,(L,(L)))Þ(L,(L,(L,S)))Þ(L,(L,(L,a)))Þ(L,(L,(S,a)))Þ(L,(L,(a,a)))Þ(L,(S,(a,a)))Þ(L,((L),(a,a)))Þ(L,((L,S),(a,a)))Þ(L,

6、((L,a),(a,a)))Þ(L,((S,a),(a,a)))Þ(L,((a,a),(S,S)))Þ(S,((a,a),(a,a)))Þ(a,((a,a),(a,a)))b)该文法产生的语言是什么解:设该文法产生语言(符号串集合)L,则L={(A1,A2,…,An)

7、n是任意正整数,Ai=a,或Ai∈L,i是1~n之间的整数}(Aho)4.2考虑文法S→aSbS

8、bSaS

9、ea)为句子构造两个不同的最左推导,以证明它是二义性的SÞaSbSÞabSÞabaSbSÞababSÞababSÞaSbSÞa

10、bSaSbSÞabaSbSÞababSÞababb)构造abab对应的最右推导SÞaSbSÞaSbaSbSÞaSbaSbÞaSbabÞababSÞaSbSÞaSbÞabSaSbÞabSabÞababc)构造abab对应语法树d)该文法产生什么样的语言?解:生成的语言:a、b个数相等的a、b串的集合(Aho)4.3考虑文法bexpr→bexprorbterm

11、btermbterm→btermandbfactor

12、bfactorbfactor→notbfactor

13、(bexpr)

14、true

15、falsea)

16、试为句子not(trueorfalse)构造分析树解:a)试证明该文法产生所有布尔表达式证明:一、首先证明文法产生的所有符号串都是布尔表达式变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式最短的推导过程得到true、false,显然成立假定对步数小于n的推导命题都成立考虑步数等于n的推导,其开始推导步骤必为以下情况之一bexprÞbexprorbtermbexprÞbtermbtermÞbtermandbfactorbexprÞbfactorbfacto

17、rÞnotbfactorbfactorÞ(bexpr)而后继推导的步数显然

18、e和false显然成立假定对长度小于n的布尔表达式,均可由文法推导出来考虑长度等于n的布尔表达式B,显然,B只能是以下形式之一B=B1orB2B=B1andB2B=notB1B=(B1)以上几种情况,B1、B2的长度均小于n对于情况1:B为析取式,B1可为析取式也可为合取式,B2为合取式,根据假设可由bexpr合bterm推导出来,显然可构造推导过程,由bexpr推导出B其他情况类似,命题二得证综合一、二,可知文法产生的语言就是布尔表达式b)(Aho)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。