哈工大编译原理习题及答案

D W T L a : ; , i

D

W =

T =

L <

a

: = > >

; = >

, = > >

i < =

r|n|b|c <

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 # + > << < > < > * > >< < > < > ↑ > >< < > < > ( < << < = < ) > >> > > I > >> > > # < << < <

（2）用Floyd方法将优先矩阵线性化得到得的优先函数为： + * ↑ ( )i # F 3 5 5 1 77 1 G 2 4 6 6 16 1