编译原理第5章-自底向上优先分析详解.ppt

5 自下而上分析法的一般原理;#;例1. 设有文法G[S]: ; 首先设一个符号栈并将输入符号串的左界符‘#’移入栈，分析时将输入符号串按从左到右扫描顺序移入栈中，其整个分析过程如下表所示。 ;S→ aAcBe (2)?A→ b (3) A→ A b (4) B→ d 输入串abbcde; 实现自下而上分析法的关键问题是如何精确定义可归约串这个直观概念，以及怎样识别“可归约串”？; 对“可归约串”的不同定义形成不同的自下而上的分析方法,在规范归约分析法中，是用句柄来刻画可归约串,而在算符优先分析法中,是用最左素短语来刻画可归约串。; (1) S→ aAcBe (2)?A→ b (3) A→ A b (4) B→ d 输入串abbcde; 识别可归约串的不同方法，也同样形成不同的自下而上的分析方法, 简单优先分析法和LR分析法都是规范归约分析法，即都是用句柄刻画可归约串。; 但它们识别句柄的方法不同，LR分析法是根据历史、现实、展望三者信息来确定栈顶符号串是否形成句柄，而简单优先分析法是根据文法符号之间的优先关系来确定栈顶符号串是否形成句柄。 ; 下面，我们将介绍两种常用的自下而上的分析方法即算符优先分析法和LR分析法。在这两种分析法中，重点讨论怎样识别栈顶符号串是可归约串以及如何进行归约。 ;4.4 算符优先分析法;4.4.1 方法概述; 句子id+id*id的两种不同的规范归约过程如下：; 分析上述归约过程，句型 E+E*id 在第一个规范归约中id是它的句柄; 而在第二个规范归约中E＋E是它的句柄。此现象是由于没有定义运算符＋和*的优先关系而引起的。 在第一个规范归约中是假定 *优先于＋, 所以不能立即把E＋E归约为E ; 而在第二个规范归约中是假定＋优先于* ,因此必须先把E＋E归约为E。; 可见上述归约过程中起决定作用的是相邻两个终结符号之间的优先关系。于是算符优先分析法的关键在于用合适的方法去定义任何两个可能相邻出现的终结符号a和b之间的优先关系。; 2. 任何两个相邻终结符号a 和 b之间的优 先关系有三种：; 通常表达式中运算符的优先关系有;4.4.1 方法概述;4.4.1 方法概述;算符优先文法的定义; 也就是说，在算符文法中，任何一个规则右部都不存在两个非终结符相邻的情况。 ; 设G是一个算符文法，a和b是任意两个终结符，P、Q、R是非终结符，算符优先关系 、 、 定义如下： ;当且仅当G中含有形如;3.算符优先文法的定义;对前述算术表达式的文法:; 因为该文法的任一规则右部都不包含两个相邻的非终结符，所以该文法是算符文法。 ; 即运算符＋和*之间存在两种不同的优先关系，所以该表达式的文法仅是算符文法而不是算符优先文法。 ;若算术表达式的文法为： ;算符优先关系表的构造;4.4.3 算符优先关系表的构造; 使用这两个集合，构造文法Ｇ的优先关系表的算法如下： ;方法：;for ( 每个产生式 A→x1x2…xn );3. 对 FIRSTVT(S)中的所有b，置# b;;例 设有表达式的文法G[E]：; 首先计算每个非终结符的FIRSTVT和LASTVT：;E→E + T | T T→T * F | F F→(E) | id ; 执行算法，逐条扫描文法规则，因有E→(E)的规则，则有 ;+ T; ; 寻找非终结符在左边，终结在右边的符号对有 ; ; 从而构造出文法G[E]的算符优系表如下：;; 对于算符优先分析法，它虽然是一种自下而上的语法分析方法，但它并不是一种规范归约的分析方法。;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;6.3.3 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计; 根据最左素短语的定理，最左素短语中的终结符号具有相同的优先关系，并且，由于最左素短语中的符号是当时最先要归约的串，其优先关系先于最左素短语之外的符号，所以我们使用一个用于存放文法符号的先进后出栈，并利用优先关系表，可以确定最左素短语是否已形成来决定分析器的动作。 ;4.4.4 算符优先分析算法的设计;4.4.4 算符优先分析算法的设计;栈置初值 K ?1, S[K] ? ‘#’ ;4.4.4 算符优先分析算法的设计; ;4.4.4 算符优先分析算法的设计; 4.4.6 算符优