编泽原理 培法分折一自下而上分析 可用句柄来对句子进行归约 句型 归约使用规则 abbcde (2)A→b aAbcde (3)A→Ab aAcde (4)B→d -aAcBe (1)S→aAcBe ←S 第6
编译原理 第16页 语法分析-自下而上分析 可用句柄来对句子进行归约 句型 归约使用规则 abbcde (2) A → b aAbcde (3) A → Ab aAcde (4) B → d aAcBe (1) S → aAcBe S
编泽原理 培法分析一自下而上分析 定义：假定是文法G的一个句子，我们称序列 0n’0n-1’…’0 是的一个规范归约，如果此序列满足： 1.0n=0 2.0为文法的开始符号，即oo=S 3.对任何i,0≤i≤n,0.是从o经把句柄替换 成为相应产生式左部符号而得到的。 规范归约的实质 在移进过程中，当发现栈顶呈现句柄时就用相应产生 式的左部符号进行替换。 第引7负
编译原理 第17页 语法分析-自下而上分析 定义：假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的 一个规范归约，如果此序列满足： 1. n= 2. 0为文法的开始符号，即0=S 3. 对任何i，0 i n， i-1是从i经把句柄替换 成为相应产生式左部符号而得到的。 规范归约的实质 在移进过程中 ，当发现栈顶呈现句柄时就用相应产生 式的左部符号进行替换
编泽原理 培法分折一自下而上分析 把上例倒过来写，则得到一个最右推导： S → aAcBe (1)S→ aAcBe → aAcde (4)B→d → aAbcde (3)A→Ab → abbcde (2)A→b ·可见规范归约是最右推导的逆过程，规范归约又称为最 左归约。 ·最右推导又称规范推导，由规范推导所推出的句型称规 范句型。 •规范推导的逆过程是规范归约。 第丨8页
编译原理 第18页 语法分析-自下而上分析 把上例倒过来写，则得到一个最右推导： S aAcBe (1) S → aAcBe aAcde (4) B → d aAbcde (3) A → Ab abbcde (2) A → b •可见规范归约是最右推导的逆过程，规范归约又称为最 左归约。 •最右推导又称规范推导，由规范推导所推出的句型称规 范句型。 •规范推导的逆过程是规范归约
编泽原理 培法分析一自下而上分析 e d a d 第9贡
编译原理 第19页 语法分析-自下而上分析 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
编泽原理 培法分析自下而上分析 5.1.3符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。‘#’作 为栈底符号和输入串的结束标记。 第20
编译原理 第20页 语法分析-自下而上分析 5.1.3 符号栈的使用和分析树的表示 栈是语法分析的一种基本数据结构。‘#’作 为栈底符号和输入串的结束标记