> # = < < < I
> > ( = < < < )
> >
化简后的文法是简单优先文法；
解： S A / A S > > A = < = < = /
> > a > >
A和/之间同时有关系=和<,所以不是简单优先文法；
提示：分析教材中给出的算法，选择一种合适的表示给定文法的方法（尽量简单），使得对文法的输入比较简单的同时(需要把输入转化为计算机语言表示，这种转化应该尽量简单)，能够比较简单地构造3个基本关系矩阵（=，LEAD和LAST）。
证明：设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是素短语，其中1 提示：根据27题的结论，只要证u是句型α的短语，根据=关系的定义容易知道u是句型α的素短语。 证：与28题的不同点只是a0,an+1可以是’#’,不影响结论。 证：设不能含有素短语，则只能是含有短语（不能含有终结符号），则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。 解： （1）算符优先矩阵： + * ↑ （ ） i #