E ■在一个句型对应的 E 语法树中，以某非 十 T 终结符为根的两代 F 以上的子树的所有 末端结点从左到右 排列就是相对于该 F 2 非终结符的一个短 语，如果子树只有 i 两代，则该短语就 是直接短语。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 在一个句型对应的 语法树中，以某非 终结符为根的两代 以上的子树的所有 末端结点从左到右 排列就是相对于该 非终结符的一个短 语，如果子树只有 两代，则该短语就 是直接短语。 E F F T T T i1 + * E F i3 i2
■可用句柄来对句子进行归约 句型 归约规则 abbcde (2)A→b aAbcde (3)A→Ab aAcde (4)B→d aAcBe (1)S→aAcBe S 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 可用句柄来对句子进行归约 句型 归约规则 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1) S → aAcBe S
■ 定义：假定是文法G的一个句子，我们 称序列 0n’0n-1’…’00 是的一个规范归约，如果此序列满足： 10n=0 20为文法的开始符号，即o=S 3对任何i,0≤i≤n,1是从，经把句 柄替换成为相应产生式左部符号而得到 的。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 定义：假定是文法G的一个句子，我们 称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句 柄替换成为相应产生式左部符号而得到 的
把上例倒过来写，则得到： S→aAcBe:→aAcde→aAbcde→abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。 规范归约是关于是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型
e d d 鹵防科技大学计算机系602教研室
国防科技大学计算机系602教研室 b b d a c e S A B A d b a c e S A B A d a c e S A B a c e S A B