第六章 自底向上优先分析讲解.ppt

标注中a与b的关系：a . b * LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO LOGO 自底向上优先分析 广东工业大学计算机学院 第六章 广东工业大学计算机学院 LOGO * 引言 自底向上分析方法也称移进-归约分析法，它的实现思想是： (1) 对输入符号串自左向右进行扫描，将输入符逐个移入一个后进先出栈中，边移入边分析。 (2) 一旦栈顶符号串形成某个句型的句柄时(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替此句柄，这称为一步归约。 (3) 重复这一过程，直到归约到栈中只剩下文法的开始符号时，则认为分析成功，即确认输入符号串是文法的句子。 目前常用的自底向上的分析算法：算符优先分析法和LR类分析法。 广东工业大学计算机学院 LOGO * 知识结构 自底向上优先分析 简单优先分析法 广东工业大学计算机学院 LOGO * 预备知识：短语、直接短语、句柄 对于文法G[S]，若有S ? ?A?且A ? ?， 则称?是句型???相对于非终结符A的短语。 若有A ?β则称β是句型???相对于A或规则A → β的直接短语。 一个句型的最左直接短语称 为该句型的句柄。 * * 广东工业大学计算机学院 LOGO * 本课内容 6.1 自底向上优先分析概述 6.2 简单优先分析法（课外阅读） 广东工业大学计算机学院 LOGO * 自底向上分析概述 自底向上分析法，也称移进-归约分析法，或 自下而上分析。现通过举例说明。 例6.1：设文法G[S]为： (1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。 答：由于自底向上分析的移进-归约过程是自顶向下最右推导的逆过程，而最右推导为规范推导，自左向右的归约过程也称规范归约。 容易看出，对输入串abbcde的最右推导是：　S ? aAcBe ? aAcde ? aAbcde ? abbcde 广东工业大学计算机学院 LOGO * 推倒的逆过程 例6.1：设文法G[S]为：　　(1) S→aAcBe　 (2) A→b　　(3) A→Ab　 (4) B→d 推导的逆过程为： abbcde 　　 ? aAcde ? aAcBe ? aAbcde ? S 广东工业大学计算机学院 LOGO * 归约过程举例 设文法G[S]为：(1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 先设一个先进后出的符号栈，并把句子左括号“#”号放入栈底，其分析过程如表： 广东工业大学计算机学院 LOGO * 归约过程举例 设文法G[S]为：(1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 先设一个先进后出的符号栈，并把句子左括号“#”号放入栈底，其分析过程如表： 广东工业大学计算机学院 LOGO * 移进-归约讨论 移进-归约是规范推导(最右推导)的逆过程，即规范归约(最左归约)。 当一个文法无二义性时，那么它对一个句子的规范推导是唯一的，规范归约也必然是唯一的。 实际上，自底向上分析的关键问题是：在分析过程中如何确定句柄。 也就是说，如何知道何时在栈顶符号串中已形成某句型的句柄，那么就可以确定何时可以进行归约。 广东工业大学计算机学院 LOGO * 优先分析法的分类 优先分析法可分为简单优先分析法和算符优先分析法。 1. 简单优先分析法的基本思想是：对一个文法，按照一定原则求出该文法所有符号之间的优先关系(包括终结符和非终结符)，按照此关系确定规约过程中的句柄。 简单优先分析法实际上是一种规范规约。 2. 算法优先分析法的基本思想是：只规定算符之间的优先关系(即只考虑终结符之间的关系)，在规约过程中找到可规约串就规约。 由于算法优先分析法没有考虑到非终结符之间的优先关系，所以不是规范规约。 广东工业大学计算机学院 LOGO * 本章内容 6.1 自底向上优先分析概述 6.2 简单优先分析法（课外阅读） 广东工业大学计算机学院 LOGO * 简单优先分析法的优先关系 简单优先分析法是按照文法符号(终结符和非终结符)的优先关系确定句柄的。 因此。首先要介绍两个文法符号的优先关系如何确定。 6.2.1 优先关系 (1) X = Y：当且仅当文法G中存在产生式A ? …XY…。 (2) X · Y：当且仅当G中存在产生式A ? …XB…，且B ? Y… (3) X · Y：当且仅当G中存在产生式A ? …BD…，且B ? X…和