2.5语法分析自下而上分析 25.1.1归约( Reduce) ●自下而上( Bottom-Up)分析采用“移进一归 约”( shift-reduce)的基本思想 把输入符号逐个移进到一个符号栈,当栈顶形成某 个产生式的候选式时,即把栈顶的这一部分替换成 (归约为)该产生式的左部符号
2.5.1.1 归约(Reduce) 自下而上(Bottom-Up)分析采用“移进－归 约”(shift-reduce)的基本思想 ⚫ 把输入符号逐个移进到一个符号栈，当栈顶形成某 个产生式的候选式时，即把栈顶的这一部分替换成 (归约为)该产生式的左部符号。 2.5 语法分析——自下而上分析
●例:设文法GS): (1)s+aAcBe (2)A→b (3)A→Ab (4)B→d 试对 abbcde进行“移进一归约”分析 eBeAa abin
例：设文法G(S)： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 试对abbcde进行“移进－归约”分析。 a bbcde b bcde A b cde c de d abbcdee e B c A Sa B c A a e
步骤:12345678910 动作:进a进b归(2)进b归(3)进c进d归(4)进e归(1 bAAa cAa dcAa BcAa BcAa S
步骤: 1 2 3 4 5 6 7 8 9 10 动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1) e d B B b c c c c b A A A A A A A a a a a a a a a a S
a B′e b d 自下而上分析过程:边输入单词符号,边 归约。 核心问题:识别可归约串
b b d a c e S A B A 自下而上分析过程：边输入单词符号，边 归约。 核心问题：识别可归约串
25.1.2规范归约 定义:令G是一个文法,S是文法的开始符号,假 定aB8是文法G的一个句型,如果有 且 S→ aA8 A=B 则β称是句型aB86相对于非终结符A的短语。 特别是,如果有A→B,则称β是句型aB8相对 于规则A→>β的直接短语。一个句型的最左 直接短语称为该句型的句柄
2.5.1.2 规范归约 定义：令G是一个文法，S是文法的开始符号，假 定是文法G的一个句型，如果有 且 S A * + A 则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对 于规则A→ 的直接短语。一个句型的最左 直接短语称为该句型的句柄