编译原理龙书附标准答案

《编译原理龙书附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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,(a,S)Þ(a,(a,a))矚慫润厲钐瘗睞枥庑赖。iii)S

4、Þ(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)))聞創沟燴鐺險爱氇谴净。a)构造b)中句子的最右推导i)SÞ(L)Þ(L,S)Þ(L,a)Þ(S,a)Þ(a,a)ii)SÞ(L)Þ(L,S)Þ(L,(L))

5、Þ(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,((L,a),(a,a)))Þ(L,((S,a),(a,a)))Þ(L,((a,a),(S,S)))Þ(S,((a,a)

6、,(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ÞabSaSbSÞabaSbSÞababSÞababb)构造abab对应的最右推导SÞaSbSÞaSbaSbSÞaSbaSbÞaSbabÞaba

10、bSÞ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)试为句子not(trueorfalse)构造分析树解：a)试证明该文法产生所有布尔表达式证明：一、首先证明文法产生的所有符号串都是布尔表达式变换命题形式——以bexpr、bterm、bfactor开始的

16、推导得到的所有符号串都是布尔表达式最短的推导过程得到true、false，显然成立假定对步数小于n的推导命题都成立考虑步数等于n的推导，其开始推导步骤必为以下情况之一bexprÞbexprorbtermbexprÞbtermbtermÞbtermandbfactorbexprÞbfactorbfactorÞnotbfactorbfactorÞ(bexpr)而后继推导的步数显然

17、尔表达式均可由文法生成变换命题——所有析取式均可由bexpr推导出来，所有合取式均可由bterm（bexpr）推导出来，所有对子布尔表达式施加not运算或加括号或简单true、false都可由bfactor（bexpr、bterm）推导出来厦礴恳蹒骈時盡继價骚。最简单的布尔表达式true和false显然成立假定对长度小于n的布尔表达式，均可由文法推导出来考虑长度等于n的布尔表达式B，显然，B只能是以下形式之一B=B1orB2B=B1andB2B=notB1B=(B1)以上几种情况，B1、B2的长度均小于n对于情况1：B为析取式，B1可为析取式也可为合取式，B2

18、为合取式，根据假设可由b