语法分析-——自底向上的分析技木 引言 自底向上技术是从输入符号出发,每一步对 相应举行中的某个简单短语(或其他短语) 进行规约。如果能够最终规约到识别符号, 那么就说明这个输入符号串是句子 要解决的问题 如何找出简单短语(或其它某特定类型的短 语)? 将短语规约成哪个非终结符号? 南京大学计算机系赵建华
南京大学计算机系 赵建华 语法分析----自底向上的分析技术 引言 • 自底向上技术是从输入符号出发，每一步对 相应举行中的某个简单短语（或其他短语） 进行规约。如果能够最终规约到识别符号， 那么就说明这个输入符号串是句子。 • 要解决的问题 – 如何找出简单短语（或其它某特定类型的短 语）？ – 将短语规约成哪个非终结符号？
语法分析-——自底向上的分析技木 引言(续) 讨论的前提 对象是上下文无关文法以及相应的语言。 文法是压缩了的 般采用移入-归约方法(例子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的父亲具有同一个父亲