编译原理课后答案(第三版 蒋立源 康慕宁编)

内容发布更新时间 : 2024/12/23 11:45:07星期一 下面是文章的全部内容请认真阅读。

> # = < < < I

> > ( = < < < )

> >

化简后的文法是简单优先文法;

解: S A / A S > > A = < = < = /

> > a > >

A和/之间同时有关系=和<,所以不是简单优先文法;

提示:分析教材中给出的算法,选择一种合适的表示给定文法的方法(尽量简单),使得对文法的输入比较简单的同时(需要把输入转化为计算机语言表示,这种转化应该尽量简单),能够比较简单地构造3个基本关系矩阵(=,LEAD和LAST)。

证明:设xjxj+1...xi是满足条件xj-1xi+1的最左子串。由=关系的定义,可知xjxj+1...xi必出现在某产生式的右部中。又因xj-1

解:为描述方便,用符号表示各非终结符:D=<变量说明>,L=<变量表>, V= <变量>,T=<类型>,a=VAR,则消去V,并采用分层法改写文法,得到:D→aW:T;W→LL→L,i|iT→r|n|b|c 其全部简单优先关系是: D W T L a : ; , i

r|n|b|c D

W

= T

= L

>

= a = < < : = < ;

,

> > > = i

r|n|b|c

>

是简单优先文法。

证:设STna,我们对n用归纳法,证明a不含两个非终结符相邻情况。n=1时,STa,即S→a是文法的产生式,根据定义,它不含上述情况。设n=k时,上述结论成立,且设STkdAb,由归纳假设,A两侧必为终结符。我们再进行一步推导,得STkdAbTdub, 其中,A→u是文法中的产生式,由定义,u中不含两个非终结符相邻情况,从而dub两个非终结符相邻情况。得证。

证:由于G不是算符文法,G中至少有一个产生式,其右部含有两个非终结符相邻的情况。不失一般性,设其形为U→xABy,x,y∈V*,由于文法不含无用产生式,则必存在含有U的句型dUb,即存在推导ST*dUbTdxAByb.得证。

文法为:E→E↑A | AA→A*T | A/T | TT→T+V | T-V | VV→i | (E) 解:

(1)构造算符优先矩阵: - * ( ) i

# - > < > < < > < > * > < > < > < ( < < < = < ) > > > > I > > > > # <

< < <

(2)在(-,-)、(-,*)和(*,-)处有多重定义元素,不是算符优先文法;

(3)改写方法:

将E→E-T中的减号与F→-P中的赋值运算符强制规定优先关系; 或者将F-P中的赋值运算符改为别的符号来表示;

(1)证明:由设句型a =?Ua?中含a的短语不含U,即存在A,A=>*ay,则a可归约为a =?Ua?ü*?UA?=b,b是G的一个句型,这与G是算符文法矛盾,所以,a中含有a的短语必含U。

(2)的证明与(1)类似,略。 证:(1)对于a=?aU?是句型,必有ST*a(=?aU?) T+?ab?.即在归约过程中,b先于a被归约,从而,a

证:(1) 用反证法。设没有短语包含b但是不包含a,则a,b一定同时位于某个短语中,从而必使得a,b同时位于同一产生式的右部,所以a=b,与G是算符优先文法(=与<不能并存)矛盾。 (2)、(3)类似可证。

证:只要证u中不含有除自身以外的素短语。设有这样的素短语存在,即存在bx···by是素短语,其中1by+1,与bx-1=bx及 by=by+1矛盾,得证。

提示:根据27题的结论,只要证u是句型α的短语,根据=关系的定义容易知道u是句型α的素短语。

证:与28题的不同点只是a0,an+1可以是’#’,不影响结论。 证:设不能含有素短语,则只能是含有短语(不能含有终结符号),则该短语只能含有一个非终结符号,否则不符合算符文法定义,得证。 解:

(1)算符优先矩阵: + * ↑ ( ) i #

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi