考虑文法G(E):E→T|E+T T今F|TF F→>(E 和句型+2+3 E→ET→E+F→E+i3→T+ →TF+3→T2+3→F*i2+i3 →i1i2 问题:对于句型i2+i3而言,有哪些短语、 直接短语和句柄?
考虑文法G(E)： E → T | E+T T → F | T*F F → (E) | i 和句型i1 *i2+i3： E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1 *i2+i3 问题：对于句型i1 *i2+i3而言，有哪些短语、 直接短语和句柄？
因为 E*→F2+13→料2+3所以1是句型相对于非终结符F 的短语和直接短语。 E→*F+3→1+2+i3,所以2是句型相对于非终结符F的 短语和直接短语。 E*→1i2+F→i*2+i3,所以i3是句型相对于非终结符F的 短语和直接短语 E*→E+i3+→i1*2+i3,所以i2是句型相对于非终结符E 的短语。 E*→E→i12+3所以i12+i3是句型相对于非终结符E 的短语。 结论:对于句型1*2+3而言: 短语:i1,i2,i3,i1*i2,i1*2+3 直接短语:i1,i2,i3 句柄:i1
因为 E * F*i2+i3 i1 *i2+i3 ,所以i1是句型相对于非终结符F 的短语和直接短语。 E* i1 *F+i3 i1 *i2+i3 ,所以i2是句型相对于非终结符F的 短语和直接短语。 E* i1 *i2+F i1 *i2+i3 ,所以i3是句型相对于非终结符F的 短语和直接短语。 E* E+i3 + i1 *i2+i3 ,所以i1 *i2是句型相对于非终结符E 的短语。 E * E i1 *i2+i3 ,所以i1 *i2+i3是句型相对于非终结符E 的短语。 结论：对于句型i1 *i2+i3而言： ⚫ 短语： i1，i2，i3， i1 *i2， i1 *i2+i3 ⚫ 直接短语： i1，i2，i3 ⚫ 句柄： i1
根据语法树找短语、直接短语、句柄 ●在一个句型对应的语法 树中,以某非终结符为 根的两代以上的子树的 所有末端结点从左到右 排列就是相对于该非终 F 结符的一个短语,如果 子树只有两代,则该短 语就是直接短语。而最 左直接短语就是句柄
在一个句型对应的语法 树中，以某非终结符为 根的两代以上的子树的 所有末端结点从左到右 排列就是相对于该非终 结符的一个短语，如果 子树只有两代，则该短 语就是直接短语。而最 左直接短语就是句柄。 E F F T T T i1 + * E F i3 i2 根据语法树找短语、直接短语、句柄
可用句柄来对句子进行归约 句型归约规则 abbcde(2)A→b aBode(3)A→Ab aAcde (4)B>d aAcBe(1)s→ aAcBe s
可用句柄来对句子进行归约 句型 归约规则 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1) S → aAcBe S
●定义:假定α是文法G的一个句子,我们称序列 a 0 是一个规范归约,如果此序列满足: On- a 2a为文法的开始符号,即a=S 3对任何i,0≤isn,a;-1是从a1经把句 柄替换成为相应产生式左部符号而得到的
定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句 柄替换成为相应产生式左部符号而得到的