自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b a B 4)B→>d A 输入串 a de$ 2021/2/2 《编译原理与技术》讲义
2021/2/2 《编译原理与技术》讲义 11 自底向上分析 e.g.17 文法G6 1）S→aABe 2）A→Abc 3）A→b 4）B→d 串abbcde$的对应分析树 的建立过程。 输入串 a b b c d e $ A A B S
移进一归约分析 ne917用栈来实现串 abode$的分析(1) 分析栈 输入串 动作 a s s a b bcde$移进a s a b b cdes 移进b Saa bodes归约:A→b Saab cdes 移进b Saac eS d e 移进c 2021/2/2 《编译原理与技术》讲义 2
2021/2/2 《编译原理与技术》讲义 12 移进－归约分析 e.g.17 用栈来实现串abbcde$的分析（1） 分析栈 输入串 动作 $ a b b c d e $ $ a b b c d e $ 移进a $ a b b c d e $ 移进b $ a A b c d e $ 归约：A→b $ a A b c d e $ 移进b $ a A b c d e $ 移进c
移进一归约分析 neg17用栈来实现串 abode$的分析(2) 分析栈 输入串 动作 Sabc d e s 移进c SaA d e s 归约:A→>Abc Saad e S 移进d SaA B e s 归约:B>d Saab SS $ 移进e .s-aABe 下分析成功 2021/2/2 《编译原理与技术》讲义 13
2021/2/2 《编译原理与技术》讲义 13 移进－归约分析 e.g.17 用栈来实现串abbcde$的分析（2） 分析栈 输入串 动作 $ a A b c d e $ 移进c $ a A d e $ 归约: A→Abc $ a A d e $ 移进d $ a A B e $ 归约：B→d $ a A B e $ 移进e $ S $ r: S→aABe 分析成功！
移进一归约分析 四种分析动作( action) 移进(shit)-将当前输入符号移入栈顶top (Why?) 归约( reduce)一当“句柄”出现在栈顶(从栈 中某处到栈顶top),则将“句柄”从栈顶弹弹出, 并将相应产生式左部非终结符置入栈顶top (when? 接受( accept)一分析成功! 报错(eror)一出现语法错误,调错误恢复例程 2021/2/2 《编译原理与技术》讲义 14
2021/2/2 《编译原理与技术》讲义 14 移进－归约分析 四种分析动作（action） ∙ 移进（shift）－将当前输入符号移入栈顶top （why？） ∙ 归约（reduce）－当“句柄”出现在栈顶（从栈 中某处到栈顶top），则将“句柄”从栈顶弹弹出， 并将相应产生式左部非终结符置入栈顶top。 （when？） ∙ 接受（accept）－分析成功！ ∙ 报错（error）－出现语法错误，调错误恢复例程
移进一归约分析 怎么可能呢? 分析动作冲突 移进归约冲突( shift-reduce conflict 当“句柄”处于栈顶时,分析动作指示既 可以将下一输入符号移入栈顶tp,又可以实 施归终操作。如何动作呢? 归约-归约冲突( reduce- reduce conflict) 位于栈顶的“句柄”,同时匹配两个(以 上)产生式的右部。选谁呢? 2021/2/2 《编译原理与技术》讲义 15
2021/2/2 《编译原理与技术》讲义 15 移进－归约分析 分析动作冲突 ∙ 移进-归约冲突（shift-reduce conflict） 当“句柄”处于栈顶时，分析动作指示既 可以将下一输入符号移入栈顶top，又可以实 施归约操作。如何动作呢？ ∙ 归约-归约冲突（reduce-reduce conflict） 位于栈顶的“句柄”，同时匹配两个（以 上）产生式的右部。选谁呢？ 怎么可能呢？