南京大学：《编译原理》课程教学资源（PPT课件讲稿）第五章 语法分析——自底向上分析技术（2/2）

语法分析-——自底向上的分析技木 引言 自底向上技术是从输入符号出发,每一步对 相应举行中的某个简单短语(或其他短语) 进行规约。如果能够最终规约到识别符号, 那么就说明这个输入符号串是句子 要解决的问题 如何找出简单短语(或其它某特定类型的短 语)? 将短语规约成哪个非终结符号? 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 引言 • 自底向上技术是从输入符号出发，每一步对 相应举行中的某个简单短语（或其他短语） 进行规约。如果能够最终规约到识别符号， 那么就说明这个输入符号串是句子。 • 要解决的问题 – 如何找出简单短语（或其它某特定类型的短 语）？ – 将短语规约成哪个非终结符号？

语法分析-——自底向上的分析技木 引言(续) 讨论的前提 对象是上下文无关文法以及相应的语言。 文法是压缩了的 般采用移入-归约方法(例子5.1),归约 过程中有四种不同的动作: 移入:尚未发现可归约的短语,继续读入符号。 归约:发现了可归约的短语,将短语归约为特 定非终结符号 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 引言（续） • 讨论的前提 – 对象是上下文无关文法以及相应的语言。 – 文法是压缩了的。 • 一般采用移入-归约方法（例子5.1），归约 过程中有四种不同的动作： – 移入：尚未发现可归约的短语，继续读入符号。 – 归约：发现了可归约的短语，将短语归约为特 定非终结符号

语法分析-——自底向上的分析技木 引言(续) 接受:发现输入符号串是句子 报错:发现归约过程没有办法继续,也就是输 入符号串不是句子 基本的实现是使用一个栈,如果输入的符号 串是句子,那么将栈中的符号(自底向上) 序列和未扫描的符号并置后得到的必然是 个句型(LR技术归约时例外)。在移入时, 将当前输入符号压入栈中。而归约的时候, 被归约的短语总是栈顶开始的一个符号串。 将此符号串替换为非终结符号完成归约。 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 引言（续） – 接受：发现输入符号串是句子。 – 报错：发现归约过程没有办法继续，也就是输 入符号串不是句子。 • 基本的实现是使用一个栈，如果输入的符号 串是句子，那么将栈中的符号（自底向上） 序列和未扫描的符号并置后得到的必然是一 个句型（LR技术归约时例外）。在移入时， 将当前输入符号压入栈中。而归约的时候， 被归约的短语总是栈顶开始的一个符号串。 将此符号串替换为非终结符号完成归约

语法分析-——自底向上的分析技木 简单优先分析技术 试图通过考察句型中相邻两个符号的关系来 确定句柄 在从左到右扫描的时候,首先确定句柄尾部, 然后再回头(在栈中)确定句柄的头部。 确定句柄之后可以进行相应的归约 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术 • 试图通过考察句型中相邻两个符号的关系来 确定句柄。 • 在从左到右扫描的时候，首先确定句柄尾部， 然后再回头（在栈中）确定句柄的头部。 • 确定句柄之后可以进行相应的归约

语法分析-——自底向上的分析技术 简单优先分析技术(续) 对于任何两个可能在句型中相邻出现符号S1, S2,其关系可以有如下三种: SS2可以出现在同一个短语中 S是一个简单短语的尾符号,而S2紧跟在此短 语的后面。 S2是一个简单短语的头符号,而S1在这个短语 的紧前面。 对应于语法树,这三种情况分别表示了:S1,S2 具有同一个父亲,S2和S1的父亲具有同一个父亲, 以及S1和S2的父亲具有同一个父亲 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术（续） • 对于任何两个可能在句型中相邻出现符号S1， S2，其关系可以有如下三种： – S1S2可以出现在同一个短语中。 – S1是一个简单短语的尾符号，而S2紧跟在此短 语的后面。 – S2是一个简单短语的头符号，而S1在这个短语 的紧前面。 • 对应于语法树，这三种情况分别表示了：S1，S2 具有同一个父亲，S2和S1的父亲具有同一个父亲， 以及S1和S2的父亲具有同一个父亲

语法分析-——自底向上的分析技木 简单优先分析技术(续) 将前面提到的关系分别记为:=,>和关 系和它左边的最右的<的关系所限定的子符 号串。这就给出了确定句柄的方法。 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术（续） • 将前面提到的关系分别记为：=，>和关 系和它左边的最右的<的关系所限定的子符 号串。这就给出了确定句柄的方法

语法分析-——自底向上的分析技木 简单优先分析技术(续) 在选择句柄的时候使用如下的方法: 对于句型S1..S5-SSj#1.. Si-1 sisi+1..Sn,如果子符 号串SSS+1..S5:SSH是满足S;1SH+1的最左的子符号串,那么它就是句 柄 这些关系,可以使用关系矩阵来表示 具体的归约过程可以见例53 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术（续） • 在选择句柄的时候使用如下的方法： – 对于句型S1…Sj-1SjSj+1…Si-1SiSi+1…Sn，如果子符 号串Sj-1SjSj+1…Si-1SiSi+1是满足Sj-1Si+1的最左的子符号串，那么它就是句 柄。 • 这些关系，可以使用关系矩阵来表示。 • 具体的归约过程可以见例5.3

语法分析-——自底向上的分析技木 简单优先分析技术(续) 优先关系的定义: =Si文法中有规则U:=.SSi SSi存在规则U:=VW.且VTAS以及 W HEAD Sio 定理51-53证明了这个定义和前面的定义是 等价的,但是具有更加好的操作性。可以由 这个定义得到求解这些关系的算法。 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术（续） • 优先关系的定义： – Sj=Si iff 文法中有规则U::= ...SjSi… – SjSi iff 存在规则U::=…VW…且V TAIL+ Sj 以及 W HEAD* Si。 • 定理5.1-5.3证明了这个定义和前面的定义是 等价的，但是具有更加好的操作性。可以由 这个定义得到求解这些关系的算法

语法分析-——自底向上的分析技木 简单优先分析技术(续) 优先关系的形式化定义给出了相应的求解优 先关系的方法。 南京大学计算机系赵建华

南京大学计算机系 赵建华 语法分析----自底向上的分析技术 简单优先分析技术（续） • 优先关系的形式化定义给出了相应的求解优 先关系的方法