编译原理第3讲(下).pptVIP

CompilerPrinciples 第三讲 语法分析 语法分析概述 自上而下语法分析 自下而上语法分析 基本思想：从文法的开始符号出发，推 导出句子 回溯→避免条件 First(x), Follow(u) 基本问题 无限循环→消除左递归 递归子程序法 分析方法 LL(1)分析法 基本思想：从输入串开始逐步归约 基本问题：归约的问题 简单优先 优先分析法 算符优先 优先函数的构造 分析方法 规范句型活前缀 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 二义性文法的分析 实现技术——移进归约 §3.自下而上的语法分析 一、基本问题 前面已经谈了自下而上分析的基本思想，就是自左而右地扫描输入——源程序单词符号串，并逐步进行自下而上的归约，直至规约到文法的开始符号；或者说，从树的末端开始，一步步向上归约，直至树根。这种构造树的过程与我们通常的从根开始构造的方法刚好是一个逆过程，因此这种树又称为语法分析树。 1.归约与语法分析树 上述思想可用如下的一个例子来说明： 例 文法 G[S]: (1)S→aAcBe (2)A→b (3)A→Ab (4)B→d 显然，abbcde是该文法的一个句子，于是可如右构造其语法分析树： 2.移进－归约 在计算机上模拟以上的语法分析树的构造过程，可借助于一个符号栈来实现： 由此看来，自下而上分析法就是对栈的“移进－归约”法，更进一步的，也就是对句子的一个规范归约过程——何为规范归约呢？先看两个定义： (1)短语、直接短语和句柄： 令G是一个文法，S是开始符号，αβδ是文法G的一个句型，如果有 S ?* αAδ且A ?+β， 则称β是句型αβδ相对于非终结符A的短语。 特别的，如果有A ?β，则称β是句型αβδ相对于规则A→β的直接短语，一个句型的最左直接短语称为该句型的句柄。 (2)规范归约： 假定α是文法G的一个句子，我们称序列 αn, αn-1,… α0 是 α的一个规范归约，如果此序列满足： ⅰ. αn＝ α; ⅱ. α0＝S; ⅲ. 对任何i,0i≤n,αi-1是从αi经过把句柄替换为相应产生式的左部符号而得到的。 在第一讲中，曾经谈到过规约与推导的关系。这里容易看出，规范归约是关于α的一个最右推导的逆过程，因此规范归约也称最左归约；最右推导常被称为规范推导，由规范推导得到的句型称为规范句型。 再来看上述的例子，每一步归约都是替换句柄： abbcde aAbcde aAcde aAcBe S 3.语法分析树的表示－穿线表 对每个进栈符号X配上一个指示器Px↑，同时开辟一块代表X的数据结构，并让X和Px↑一起进栈，即 (1)每个末端结点的数据结构为： (2)当要把栈顶的n个符号（如X1X2…Xn）退栈归约为A时，则开辟代表A的新结点： Pi↑分别指向Xi的数据结构， 而A的进栈结构仍为 分析结束，