第06章自底向上优先分析.docx

第06章自底向上优先分析.docx第06章自底向上优先分析《编译原理》课后****题答案第六章第6章自底向上优先分析第1题已知文法G[S]为:S-a|A|(T)T—T,S|S计算G[S]的FIRSTVT和LASTVTo构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。计算G[S]的优先函数。给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。答案:文法展开为:S—3s->AS-(T)T->T,ST-*S非终结符FIRSTVT集LASTVT集S{aA(}{aA)}T{aA(J{aA),}(1)FIRSTVT-LASTVT表:算符优先关系表:盛威网(snwei)专业的计算机学****网站1aA()a>>>A>>>(<<<<)>>><<<>><<<《编译原理》课后****题答案第六章表中无多重人口所以是算符优先(OPG)文法。友情提示:记得增加拓广文法STS#,所以#对应的算符优先函数为:FIRSTVT(S),LASTVT(S)对输入串(a,a)#ess!盛威网(snwei)专业的计算机学****网站2《编译原理》课后****题答案第六章对输入串(%(a,a))#的算符优先分析过程为:栈(STACK)当前字符(CHAR剩余输入串(INPLT_STRING)动作(ACTI,#(aja^a))#Moveintf(aJa^a))#Movein#(a(弘a))#Reduce:S—a#(N■(比a))#Movein())#Movein#(N.(aa))#Movein#(N.(na))#Reduce:S―a •、#(N.(Na))#Movein#(N.(Na))#Movein#(N.(N,a))#Reduce;S—#(N.(N,N))#Reduce:;T—*TfS#(N」N))#^Movein#(N.(N))Reduce:S—>(T)#(N,N)Reduce:T—^T;S#(N)KF#…开Movein 冬员l・;#(N)#■1Reduce:S—(Tj .#N#.*H***.V’ ・・•.•「■■y第2题已知文法G[S]为:S->a|A|(T)T->T,S|S给出(a,(a,a))和(a,Q的最右推导,和规范归约过程。(2)将⑴和题1屮的(4)进行比较给岀算符优先归约和规范归约的区别。答案:(1)(a,a)的最右推导过程为:S(T)(T,S)(T,a)(S,a)(a,a)(a,(a,a))的最右推导过程为:S(T)(T,S)(T,(T))盛威网(snwei)专业的计算机学****网站3《编译原理》课后****题答案第六章(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))(a,(a,Q)的规范归约过程:朋:?ft输入动作I(da)#移进2#()#移进3#(a,a)#.€a-#(S・a)#归约,TtES5#(T、a)#移进6#(T,a)#移进7#(>#归约,S^Ea8#()#归约•TiET,S9#(T)#移进10#(T)#归约,S7E(T)11#S#接受步骤输入动』乍1#(a.())#•杉进:2#(a.(a,a))#移进3#(a,(a,a))#人琏It]#(S,(aaj科■/、"归约,LtES5#(T•(^aj)#移进6#(T・移进7#(T.<汽二;云a))#移进8#(T.(a•J))##(T,(S・a))#归約J丁圧S10#(T.(T頁乞为 ,a))##(T.(T.⑴)#12#(T.(TaI'1约,SJ:a13#(T.(TS 「#(T・(T "朴)世15)#J归约•S?E(T)16#()#移进17粼T3#归约,T疋T・S18'<#(T)#(T)19#S#■kb ▼ ■ -•厂 rr接受(a,R的规范归约过程:盛威网(snwei)专业的计算机学****网站4《编译原理》课后****题答案第六章算符优先文法在归约过程屮只考虑终结符之间的优先关系从而确定可归约串,而与非终结符无关,只需知道把当前可归约串归约为某一个非终结符,不必知道该非终结符的名字是什么,因此去掉了单非终结符的归约。规范归约的可归约串是句柄,并且必须准确写出可归约串归约为哪个非终结符。第3题:有文法G[S]:S/EVVCT|ViTT£F|T+FF/E)V*|((1)给出(+(i(的规范推导。(2)指出句型F+Fi(的短语,句柄,素短语。(3)G[S]是否为OPG?若是,给出(1)中句子的分析过程。答案:(1)S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)句型F+Fi(的语法树:短语:F,F+F,(,F+Fi(句柄:F素短语:(SViTT+F(FIRSTVT和LASTVTF算符优先关系■+*()#.zi(/-I>