编译原理 龙书答案.doc 24页

'第四章部分习题解答Aho：《编译原理技术与工具》书中习题（Aho）4.1考虑文法S→(L)|aL→L,S|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Þ(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)Þ(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,((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)|n是任意正整数，Ai=a，或Ai∈L，i是1～n之间的整数}（Aho）4.2考虑文法S→aSbS|bSaS|ea)为句子构造两个不同的最左推导，以证明它是二义性的SÞaSbSÞabSÞabaSbSÞababSÞababSÞaSbSÞabSaSbSÞ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|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|falsea)试为句子not(trueorfalse)构造分析树解： a)试证明该文法产生所有布尔表达式证明：一、首先证明文法产生的所有符号串都是布尔表达式变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式最短的推导过程得到true、false，显然成立假定对步数小于n的推导命题都成立考虑步数等于n的推导，其开始推导步骤必为以下情况之一bexprÞbexprorbtermbexprÞbtermbtermÞbtermandbfactorbexprÞbfactorbfactorÞnotbfactorbfactorÞ(bexpr)而后继推导的步数显然j，则qi的优先级高于qj。a）试为该文法构造SLR项目集。共有多少个项目集？是n的函数吗？ 解：I0={E"→·E,E→·EqiE,E→·(E),E→·id}(1≤i≤n)goto(I0,E)={E"→E·,E→E·qiE}=I1(1≤i≤n)goto(I0,()={E→(·E),E→·EqiE,E→·(E),E→·id}=I2(1≤i≤n)goto(I0,id)={E→id·}=I3goto(I1,qi)={E→Eqi·E,E→·EqjE,E→·(E),E→·id}=I3+i(1≤i,j≤n)goto(I2,E)={E→(E·),E→E·qiE}=In+4(1≤i≤n)goto(I2,()=I2goto(I2,id)=I3goto(I3+i,E)={E→EqiE·,E→E·qjE}=In+4+i(1≤i,j≤n)goto(I3+i,()=I2goto(I3+i,id)=I3goto(In+4,qi)=I3+i(1≤i≤n)goto(In+4,))={E→(E)·}=I2n+5goto(In+4+i,qj)=I3+j(1≤j≤n)共2n+5个项目集a）试为该文法构造SLR语法分析表，并用4.7节方法进行压缩。压缩后总长度是多少？是n的函数吗？解：FOLLOW(E)={qi,),$}SLR分析表为action(0,()=s2,action(0,id)=s3,goto(0,E)=1action(1,qi)=si+3,action(1,$)=acc(1≤i≤n)action(2,()=s2,action(2,id)=s3,goto(2,E)=n+4action(3,qi)=action(3,))=action(3,$)=rn+2action(i+3,()=s2,action(i+3,id)=s3,goto(i+3,E)=n+i+4(1≤i≤n)action(n+4,qi)=si+3,action(n+4,))=s2n+5(1≤i≤n)action(n+i+4,qj)=sj+3(1≤i=j，分析过程如下id移进，id归约为E，qi移进，id移进，id归约为E，EqiE归约为E，qj移进，id移进，id归约为E，EqjE归约为E，共10步若i