编译原理与技术 自底向上分析 2021/2/2 《编译原理与技术》讲义
2021/2/2 《编译原理与技术》讲义 1 编译原理与技术 －－自底向上分析
自底向上分析 移进一归约分析 分析树的构建 从叶子结点开始,逐步构造各内部结点直至根结点出现 分析技术的关键一句柄的识别 句柄( handle)是什么? 简单讲,句柄是一个产生式的右部;自底向上分析(移 进一归约分析)过程,其实就是发现句柄并将句柄(产 生式右部)替换成相应左部非终结符的过程。该替换称 为最左归约,它对应着某最右推导逆过程的一步 2021/2/2 《编译原理与技术》讲义 2
2021/2/2 《编译原理与技术》讲义 2 自底向上分析 移进－归约分析 分析树的构建 从叶子结点开始，逐步构造各内部结点直至根结点出现。 分析技术的关键－句柄的识别 句柄（handle）是什么？ 简单讲，句柄是一个产生式的右部；自底向上分析（移 进－归约分析）过程，其实就是发现句柄并将句柄（产 生式右部）替换成相应左部非终结符的过程。该替换称 为最左归约，它对应着某最右推导逆过程的一步
自底向上分析 分析技术的关键一句柄的识别 句柄( handle)是什么? 一般地,如果有以下最右推导序列, s高aAmB0A→eP 则产生式A→>B及其在右句型aB6中的位置称为右 句型β6的句柄。 2021/2/2 《编译原理与技术》讲义 3
2021/2/2 《编译原理与技术》讲义 3 自底向上分析 分析技术的关键－句柄的识别 句柄（handle）是什么？ 一般地，如果有以下最右推导序列， 则产生式A→及其在右句型中的位置称为右 句型的句柄。 A ,A P * S rm rm →
自底向上分析 ne.917文法G6串abce的分析过程。 1)S→>aABe 2)A→Abc 最S aa b e s 3)A→>b 4)B→>d 右推导 aa d e s aa b d e s 最左归约 输入串 a bb cd e$ 2021/2/2 《编译原理与技术》讲义 4
2021/2/2 《编译原理与技术》讲义 4 自底向上分析 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 c d e $ a A d e $ a A B e $ S $ 最 左 归 约 最 右 推 导
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b 4)B→>d 输入串 a b bcd e 2021/2/2 《编译原理与技术》讲义 5
2021/2/2 《编译原理与技术》讲义 5 自底向上分析 e.g.17 文法G6 1）S→aABe 2）A→Abc 3）A→b 4）B→d 串abbcde$的对应分析树 的建立过程。 输入串 a b b c d e $
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b 4)B→>d 输入串 a b bcd e 2021/2/2 《编译原理与技术》讲义 6
2021/2/2 《编译原理与技术》讲义 6 自底向上分析 e.g.17 文法G6 1）S→aABe 2）A→Abc 3）A→b 4）B→d 串abbcde$的对应分析树 的建立过程。 输入串 a b b c d e $
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b 4)B→>d A 输入串 a b bcd e 2021/2/2 《编译原理与技术》讲义
2021/2/2 《编译原理与技术》讲义 7 自底向上分析 e.g.17 文法G6 1）S→aABe 2）A→Abc 3）A→b 4）B→d 串abbcde$的对应分析树 的建立过程。 输入串 a b b c d e $ A
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b 4)B→>d A 输入串 a b bcd e 2021/2/2 《编译原理与技术》讲义 8
2021/2/2 《编译原理与技术》讲义 8 自底向上分析 e.g.17 文法G6 1）S→aABe 2）A→Abc 3）A→b 4）B→d 串abbcde$的对应分析树 的建立过程。 输入串 a b b c d e $ A
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b 4)B→>d A 输入串 a b bcd e$ 2021/2/2 《编译原理与技术》讲义 9
2021/2/2 《编译原理与技术》讲义 9 自底向上分析 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
自底向上分析 ne.917文法G6串abce的对应分析树 1)S→>aABe 的建立过程。 2)A→Abc 3)A→>b a B 4)B→>d A 输入串 a b bcd e$ 2021/2/2 《编译原理与技术》讲义 0
2021/2/2 《编译原理与技术》讲义 10 自底向上分析 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