编译原理(清华)第六章自底向上优先分析

第六章自底向上优先分析法学习目标：掌握：构造算符优先关系表，进行算符优先分析，构造优先函数理解：算符优先文法，最左素短语了解：简单优先分析法6.1自底向上分析方法概述6.2自底向上优先分析方法概述6.3算符优先分析法6.1自底向上分析方法概述1.基本思想从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法开始符从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上的构造语法树，使文法开始符正好是该语法树的根。如果最终根结点是开始符，则输入符号串是语言的一个句子，否则不是。自底向上分析过程实际上是一个不断进行直接归约的过程。2.遇到的问题如何找出进行直接归约的“可归约串”（句柄）3.基本实现方法－“移进－归约”方法引进一个先进后出的符号栈来存放符号对输入符号串自左向右进行扫描，并把当前输入符号下推入栈中（移进），边移进边分析，一旦栈顶符号串形成某个句型的句柄（为某产生式的右部）时，就用相应的非终结符（产生式的左部）替换它(归约)。重复这一过程，直到输入符号串的末端，此时如果栈中只剩文法开始符号，则输入符号串是文法的句子，否则不是。规范归约：自底向上分析的移进－归约过程是自顶向下最右推导的逆过程，因为最右推导为规范推导，所以自左向右的归约称为规范归约。例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde#的最右推导的过程为：S=aAcBe=aAcde=aAbcde=abbcde自底向上分析的过程为：abbcde|-aAbcde|-aAcde|-aAcBe|-S例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子用符号栈对输入符号串自底向上的分析过程为：归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤关键问题：如何在分析的过程中确定句柄何时移进？栈顶未形成句柄何时归约？栈顶形成句柄常用自底向上分析法：算符优先分析法（6.3）LR类分析法（第7章）6.2自底向上优先分析法概述优先分析法两类：简单优先分析法基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。是一种规范归约。简单优先分析法准确、规范，但效率低，不实用，不介绍。算符优先分析法基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程不是规范归约算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。6.3算符优先分析法算符优先分析法特别适用于表达式的分析从表达式得到的启发：表达式的归约顺序与运算顺序是一样的通常算术表达式的运算次序是先乘除后加减，同优先级时服从左结合E→E+T|TT→T×F|FF→(E)|i符号串E+T+T×F的归约过程为：E+T+T×F|-E+T×F|-E+T|-E运算次序只与运算符（优先级，结合性）有关，与运算对象无关可以根据运算符（终结符）的优先关系指导归约过程，与运算对象（非终结符）无关6.3.1优先关系6.3.2算符优先文法的定义6.3.3算符优先关系表的构造6.3.4算符优先分析算法6.3.5优先函数6.3.6算符优先分析法的局限性6.3.1优先关系优先关系只存在于句型中相邻出现的符号相邻：算符优先分析法只考虑终结符之间的优先关系，不考虑非终结符，所以两个终结符相邻指其中没有其他的终结符（但可以有非终结符）如：E+T×i，＋和×相邻，×和i相邻，但＋和i不相邻终结符间优先关系表示：终结符a和b之间的优先关系表示如下：ab表示a的优先级低于ba=b表示a的优先级等于bab表示a的优先级高于b优先关系定义的依据在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约，其优先关系大同一句柄中的相邻符号同时被归约，其优先关系相同不可能相邻出现在任何句型中的两个符号，无法比较其归约的先后，故它们之间无优先关系E→E+T|TT→T×F|FF→(E)|iEE+TTF(E)句型(E)+T的句柄是(E),所以‘)’‘+’‘(’=‘)’注意：，=，是三种有序关系，与数学中的，=，不同，所以a=b不意味b=a，ab不意味baEE+TTF(E)如：(=)，但是)=(不成立，因为)和(不可能相邻出现在任何句型中，它们之间没有优先关系E→E+T|TT→T×F|FF→(E)|iETF(E)E+T在句型(E)+T中得)+，在(E+T)中得+)按公认的计算顺序规定优先级和结合性，得到优先关系如下：×,/的优先级高，遵循左结合，得××,×/,//,/×+,-的优先级低，遵循左结合，得++,+-,--,-+‘(’,‘)’规定括号的优先级大于括号外的运算符，小于括号内的运算符，如…E+(E+T)…，有+(，(+规定:‘＃’任何与它相邻的运算符，任何与它相邻的运算符‘#’运算对象i的优先级最高优先关系表如右图所示：+×（）i#+×(=)i#=说明：表中为空的元素表示：在该文法的任何句型中都不会出现这两个终结符相邻，所以他们无优先关系，如不会有这样的表达式…)i…算符优先分析法1文法要满足一定的条件，即为算符优先文法2根据文法按一定规则计算算符之间的优先关系3按优先关系进行算符优先分析6.3.2算符优先文法的定义1.算符文法定义：设有上下文无关文法G，如果G中产生式的右部没有两个非终结符相连，则称G为算符文法（OperaterGrammar），也称OG文法例如：表达式文法E→E+E|E×E|(E)|i是算符文法性质：1.在算符文法中任何句型都不包含两个相连的非终结符。2.如果Ab或bA出现在算符文法的句型r中，其中A∈VN，b∈VT，则r中任何含b的短语必含有A（含A的短语不一定含有b）EE+TE+TT×F句型E+T+T×F短语有：E+TT×FE+T+T×F2.算符优先关系的定义设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A,B,C是非终结符，算符优先关系定义如下：1)a=b当且仅当G中有形如A→…ab…或A→…aBb…的产生式。说明：δ为ε或B，a，b在用一句柄中同时归约所以优先级相同abδA例如：有产生式F→(E)所以(=)2)ab当且仅当G中有形如A→…aB…的产生式，且B=+b…或B=+Cb…说明：δ为ε或C，a，b不在同一句柄中，b先归约，所以a的优先级低于baBδAPb……文法E→E+T|TT→T×F|FF→(E)|i由E→E+TT=+T×F得+×3)ab当且仅当G中有形如A→…Bb…的产生式，且B=+…a或B=+…aC说明：δ为ε或C，a，b不在同一句柄中，a先归约，所以a的优先级大于bbB…APa…δ文法E→E+T|TT→T×F|FF→(E)|i由E→E+TE=+T×F得×+3.算符优先文法定义：设有一不含ε产生式的算符文法G，如果对任意两个终结符对a,b之间至多只有一种优先关系成立，则称G是一个算符优先文法(OperaterPrecedenceGrammar)，即OPG文法。说明：两个终结符之间的优先关系是有序的，算符优先文法允许ab，ba同时存在，而不允许有ab，ab，a=b三种情况中的任两种同时存在。例如：算符优先文法允许+)，)+同时存在，不允许+)和+)同时存在例表达式文法E→E+E|E×E|(E)|i由E→E+E且E=+E×E得＋×由E→E×E且E=+E+E得＋×+和×的优先关系不唯一，所以不是算符优先文法包含优先级和结合性的表达式文法是算符优先文法E→E+T|TT→T×F|FF→(E)|i6.3.3算符优先关系表的构造1.最左终结符集FIRSTVTFIRSTVT(B)={b|B=+b…或B=+Cb…}其中b∈VT,B,C∈VN直观上说FIRSTVT(B)是由B推导出的最左终结符(允许左边有一非终结符)的集合。与FIRST()={aVT|*a......}对照文法符号串的开始符号集是由推导出的开头的终结符（包括ε）组成例文法：E→E+T|TT→T×F|FF→(E)|iFIRSTVT(F)={(，i}FIRSTVT(T)={×，(，i}FIRSTVT(E)={+，×，(，i}FIRST(F)={(，i}FIRST(T)={(，i}FIRST(E)={(，i}构造FIRSTVT(A)的算法1)令每个非终结符的FIRSTVT集为空2)依次扫描文法中的每条产生式，根据规则(a)(b)，求各非终结符的FIRSTVT集(a)若产生式A→a…，或A→Ba…，则a∈FIRSTVT(A)；(b)若有产生式A→B…,且a∈FIRSTVT(B)，则a∈FIRSTVT(A)3)重复2)，直到每个FIRSTVT集合都不发生变化为止例文法：E→E+T|TT→T×F|FF→(E)|i求各非终结符的FIRSTVT集{(，i}{×，(，i}{+,×}第三次FTE{(，i}{×}{+}第二次{(，i}{×}{+}第一次{}{}{}初值第四次迭代的时候，E、T、F的FIRSTVT集都不再发生变换，算法终止,×,(，i,(，i(a)若产生式A→a…，或A→Ba…，则a∈FIRSTVT(A)；(b)若有产生式A→B…,且a∈FIRSTVT(B)，则a∈FIRSTVT(A)2.最右终结符集LASTVTLASTVT(B)={a|B=＋…a或B=＋…aC}其中a∈VT,B,C∈VN直观上说LASTVT(B)是由B推导出的最右终结符(允许右边有一非终结符)的集合。例文法：E→E+T|TT→T×F|FF→(E)|iLASTVT(F)={)，i}LASTVT(T)={×，)，i}LASTVT(E)={+，×，)，i}构造LASTVT(A)的算法与构造FIRSTVT(A)算法相似根据下面两条规则a)若产生式A→…a，或A→…aB，则a∈LASTVT(A)b)若有产生式A→…B，且a∈LASTVT(B)，则a∈LASTVT(A)例文法：E→E+T|TT→T×F|FF→(E)|i求各非终结符的LASTVT集{)，i}{×，)，i}{+,×}第三次FTE{)，i}{×}{+}第二次{)，i}{×}{+}第一次{}{}{}初值第四次迭代的时候，E、T、F的LASTVT集都不再发生变换，算法终止,×,)，i,)，ia)若产生式A→…a，或A→…aB，则a∈LASTVT(A)b)若有产生式A→…B，且a∈LASTVT(B)，则a∈LASTVT(A)3.优先关系的确定(1)=关系：查看产生式右部，有形如A→…ab…或A→…aBb…的产生式，则a=b例E→(E)，则有(=)(2)关系：若有形如A→…aB…的产生式，对每个b∈FIRSTVT(B)，都有ab例E→E+T，FIRSTVT(T)={×,i,(}，则有+×，+i，+((3)关系：若有形如A→…Bb…的产生式，对每个a∈LASTVT(B)，都有ab例E→E+T，LASTVT(E)={+,×,i,)}，则有++，×+，i+，)+4.构造算符优先关系表算法逐条扫描文法中的每条产生式，按以下四种情况处理：1)对产生式右部终结符相邻的符号对，即产生式右部有形如A→…ab…的符号对(a,b)，则a＝b2)对产生式右部两终结符之间为一个非终结符的符号对，即产生式右部有形如A→…aBb…的符号对(a,b)，则a＝b3)对产生式右部终结符在前非终结符在后的相邻符号对，即产生式右部有形如A→…aB…的符号对(a,B)，则aFIRSTVT(B)4)对产生式右部非终结符在前终结符在后的相