问题 单项选择题

考查文法:G(VT,VN,E,P)
其中,VT=+,*,(,),i,VN=E,T,F,E为开始符。
P:E→E+T|T
T→T*F|P
F→(E)|i
F*F+T是该文法的一个句型,在此句型中,(7) 是句柄, (8) 是该句型的直接推导, (9) 是该句型的最左推导。

A.F*F+T*F
B.F*F+T
C.F*(E)+T
D.(E)*F+T

答案

参考答案:D

解析: 定义1:令G是一文法,S是文法的开始符号,αβδ是文法的一个句型。如果有:S

aAδ且A

β,则称β是句型aβδ相对于非终结符A的短语。特别地,如有A

β则称β是aβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。
来看推导过程:
E

E+T ①

T+T ②

T*F+T ③

F*F+T ④
(27)从3到4是直接运用规则T→F推导出来的F在句型的最左边,所以F就是句型F*F+T的句柄。
定义2:如a→β是文法G的规则,若有符号串满足:V=γαδ,w=γβδ,则说V直接产生W,或者说W是V的直接推导。(28)对于答案A,没有T→i这条规则来使得F*F+T

F*F+i;对于答案B,有规则F→i这条规则来使得F*F+T

i*F+T,所以B正确,同理C,D都不对。
定义3:如果在推导的任何一步α

β,其中a,β句型,都是对a中的最左(最右)非终结符进行替换,则称这种推导为最左(最右)推导。(29)只有D是句型F*F+T运用规则F→(E)推出的句型,其余的选项都不是将句型的最左非终结符9进行推导,所以选D。

选择题
单项选择题