第6章 自底向上优先分析.pptVIP

第六章?自底向上的优先分析法 6.1 自底向上优先分析概述 6.2 简单优先分析法 6.3 算符优先分析法 6.4 典型例题 6.1 自底向上优先分析概述 例6.1 已知文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d对输入串abbcde# 进行分析。 由于自底向上分析的移进-归约是自顶向下最右推导的逆过程，而最右推导为规范推导，所以自左向右的归约过程称为规范归约。 又因输入串abbcde的最右推导是：　　S=aAcBe=aAcde=aAbcde=abbcde所以，上述句子的规约过程为 6.1 自底向上优先分析概述 6.1 自底向上优先分析概述 简单优先分析法 对一个文法按一定规则求出该文法所有符号之间的优先关系，再按照这种关系确定规约过程的句柄，该规约过程实际上是一种规范规约。 算符优先分析法 只规定算符(广义为终结符)之间的优先关系，不考虑非终结符之间的优先关系，在规约过程中只要找到可规约串就规约，不考虑规约到那个非终结符，所以不是规范规约。 根据优先关系的定义可求得各文法符号之间的优先关系如下： 例6.2 文法中的优先关系也可用语法树的结构表示为： 为表示简洁，通常用优先关系矩阵表示 6.2.2 简单优先文法的定义 若一文法是简单优先文法，必须满足： 在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。 在文法中任意两个产生式没有相同的右部。 6.2.3 简单优先分析法的操作步骤 首先根据已知文法构造优先关系矩阵，保存产生式，并设置符号栈S，然后按下步骤进行分析： 将输入符号串a1a2…an#依次入栈，直到遇到栈顶符号ai的优先性 下一个待输入符号aj为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头，ak（其中ak-1 ak）。 由句柄ak… ai在文法产生式中找右部与之相等的产生式，若找到则用相应左部代替该句柄，否则出错。 重复上述操作，直到栈中只剩文法的开始符为止。 如何确定算符优先关系？ 人为确定(直观算符优先分析法中) 1.i的优先级最高 2.?优先级次于i，右结合 3.*和/优先级次之，左结合 4.+和-优先级最低，左结合 5.括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 6.#的优先性低于与其相邻的算符 6.3.2 算符优先文法的定义 算符文法定义：设一文法G，若没有形如A?…BC…的产生式,其中B,C∈VN 则称G为算符文法(operator grammar: OG)。 例6.1 G[E]：E→E+E|E*E|i 是OG文法 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如Ab或bA出现在算符文法的句型γ中,其中A∈VN,b∈VT, 则γ中任何含b的短语必含有A(但含A的短语不一定含b)。 算符优先关系的形式化定义： 定义6.2: 设G为不含?产生式的OG，a,b是终结符,A,B,C为非终结符，则算符优先关系的定义如下： a = b G中有形如：A?…ab… 或A ? …aBb...的产生式。 a b G中有形如: A? …aB…的产生式, 而B=+b… 或B=+ Cb… a b G中有形如: A?…Bb…的产生式, 而B =+…a 或B =+… aC 规定： 若 S =+ a… 或 S =+ Ca… 则 # a 若 S =+ …a 或 S =+ …aC 则 a # 算符优先关系定义的语法树描述： 以上三种优先关系也可由以下语法树来说明： 定义6.3: 在不含 ? 产生式的OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法 (operator precedence grammar: OPG)。 6.3.3 算符优先关系表的构造 首先定义如下两个集合： FIRSTVT(B)=｛b｜B=+b… 或 B =+ Cb…｝ LASTVT(B) =｛a｜ B =+ …a 或 B =+ … aC｝ 计算文法的算符优先关系 例文法G’[E’]：(0) E’→#E#(1) E→E+T(2) E→T(3) T→T*F(4) T→F(5) F→P?F|P(6) P→(E)(7) P→i (0) E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F(5) F→P?F|P (6) P→(E) (7) P→i 表达式文法G’[E’]的算符优先关表 优先关系表的自动构造方法 FIRSTVT集的求法 LASTVT集的求法