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

《第六章 自底向上优先分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章 自底向上的优先分析法6.1自底向上优先分析概述6.2简单优先分析法6.3算符优先分析法6.4典型例题1基本思想：对输入符号串自左向右扫描，并将输入符移入一先进后出栈中，边移入边分析，一但栈顶符号串形成某个句型的句柄，就用该句柄对应产生式的左部非终结符代替栈顶相应符号串(即进行了一步归约)。重复该过程直到归约到栈中只剩文法的开始符号，则分析成功。6.1自底向上优先分析概述自底向上分析法，也称移进-归约分析法。26.1自底向上优先分析概述例6.1已知文法G[S]为：(1)S→aAcBe(2)A→b(3)A

2、→Ab(4)B→d对输入串abbcde#进行分析。由于自底向上分析的移进-归约是自顶向下最右推导的逆过程，而最右推导为规范推导，所以自左向右的归约过程称为规范归约。又因输入串abbcde的最右推导是：S=>aAcBe=>aAcde=>aAbcde=>abbcde所以，上述句子的规约过程为36.1自底向上优先分析概述4自底向上构造语法树的过程5问题：在上述移进-归约过程中，如何确定何时移进何时规约？故自底向上分析的关键是在分析过程中如何确定句柄。具体方法有：优先分析法（简单优先、算符优先）和LR类分析方法。G[

3、S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d6简单优先分析法对一个文法按一定规则求出该文法所有符号之间的优先关系，再按照这种关系确定规约过程的句柄，该规约过程实际上是一种规范规约。算符优先分析法只规定算符(广义为终结符)之间的优先关系，不考虑非终结符之间的优先关系，在规约过程中只要找到可规约串就规约，不考虑规约到那个非终结符，所以不是规范规约。6.1自底向上优先分析概述76.2简单优先分析法简单优先分析法是按照文法符号(VTandVN)的优先关系确定句柄的。6.2.1优先关系优先关系的表示

4、:XY表示X的优先性等于Y。XY表示X的优先性低于YXY表示X的优先性高于Y。优先关系是有序的，XY不一定YX；XY不一定YX；XY不一定YX；8(1)XY当且仅当G中存在产生式A→…XY…(2)XY当且仅当G中存在产生式A→…XB…,且B=>+Y…(3)XY当且仅当G中存在产生式A→…BD…,且B=>+…X和D=>*Y…优先关系的定义:6.2简单优先分析法9根据优先关系的定义可求得各文法符号之间的优先关系如下：6.2简单优先分析法106.2简单优先分析法例6.2文法中的优先关系也可用语法树的结构表示为：11

5、为表示简洁，通常用优先关系矩阵表示6.2简单优先分析法126.2.2简单优先文法的定义若一文法是简单优先文法，必须满足：在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。在文法中任意两个产生式没有相同的右部。6.2简单优先分析法136.2简单优先分析法6.2.3简单优先分析法的操作步骤首先根据已知文法构造优先关系矩阵，保存产生式，并设置符号栈S，然后按下步骤进行分析：将输入符号串a1a2…an#依次入栈，直到遇到栈顶符号ai的优先性下一个待输入符号aj为止。栈顶当前符号ai为句柄尾，由此向左在栈中找

6、句柄的头，ak（其中ak-1ak）。由句柄ak…ai在文法产生式中找右部与之相等的产生式，若找到则用相应左部代替该句柄，否则出错。重复上述操作，直到栈中只剩文法的开始符为止。146.3.0算符优先问题的提出6.3算符优先分析法已知文法G:E→E+E；E→E*E；E→i输入串i+i*i的归约过程可表示为表6.3。步骤栈当前输入字符剩余输入串动作1＃i+i*i#移进2#i+i*i#归约3＃E+i*i#移进4#E+i*i#移进5#E+i*i#归约6#E+E*i#移进7#E+E*i#移进8#E+E*i#归约（3）9#

7、E+E*E#归约（2）10#E+E#归约（1）11#E#接受156.3.1直观算符优先分析法普通算术表达式求值中，运算次序只与运算符有关而与运算对象无关，因而算符优先分析法的关键是规定文法G中算符的优先顺序和结合性。算符间的优先关系是有序的，表示如下：6.3算符优先分析法16如何确定算符优先关系？人为确定(直观算符优先分析法中)1.i的优先级最高2.优先级次于i，右结合3.*和/优先级次之，左结合4.+和-优先级最低，左结合5.括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性

8、大于外括号6.#的优先性低于与其相邻的算符表6.4算符优先关系表17例如:文法G：(1)E→E+E(2)E→E*E(3)E→i规定了算符优先性后，输入串i+i*i的归约过程不再有歧义步骤栈当前输入字符剩余输入串动作1＃i+i*i##+归约3＃E+i*i##<+移进4#E+i*i#+*归约6#E+E*i#+<*移进7#E+E*i#*