6 编译原理-自底向上优先分析

第五章自顶向下语法分析方法复习11语法分析：自顶向下：确定分析和不确定分析自底向上：算符优先分析和LR分析第5章概念22FirstFollowSelectLL(1)文法第5章操作33用关系图计算First、Follow计算Select判断是否LL(1)文法消除左递归、提取左公共因子生成LL(1)分析表编写递归子程序、构造预测分析器递归子程序部分44G[E]:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i55voidE(void){T();E’();}voidE’(void){if(sym==‘+’){sym=getchar();T();E’();}请同学们写出T’和F的程序66voidT(void){F();T’();}voidT’(void){if(sym==‘*’){sym=getchar();F();T’();}77voidF(void){if(sym==‘i’)sym=getchar();elseif(sym==‘(‘){sym=getchar();E();if(sym==‘)’)sym=getchar();elseERROR();//报告出错}//endofelseifelseERROR();//报告出错}第六章自底向上优先分析886.1自底向上分析概述6.2算符优先分析法介绍6.3算符优先分析法6.4简单优先方法6.1自底向上分析99若采用自左向右的描述和分析输入串,那么自底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的句柄(最左简单短语)，并利用有关规则进行规约，若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。基本算法思想:1010分析过程是重复一下步骤：1、找出当前句型的句柄x（或句柄的变形）2、找出以x为右部的规则X::=x3、把x规约为X，产生语法树的一枝关键：找出当前句型的句柄x(或其变形），这不是很容易。算符优先分析法LR分析法6.1.1移进—规约分析（Shift-reduceparsing)1111#S.R.P#符号栈输入串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。1212分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。#S.R.P#符号栈输入串1313例：G[S]:S→aAcBeA→bA→AbB→d输入串为abbcde，检查是否是该文法的合法句子。若采用自底向上分析，即能否一步步规约当前句型的句柄，最终规约到识别符号S。先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。分析过程如下表:1414步骤符号栈输入符号串动作123456789101112##a#ab#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#S#aAabbcde#bbcde#bcde#bcde#cde#cde#de#e#e####准备.初始化移进移进规约(A→b)移进规约(A→Ab)移进移进规约(B→d)移进规约(S→aAcBe)成功例：G[S]:S→aAcBeA→bA→AbB→d1515这一方法简单明了,不断地进行移进规约,关键是确定当前句型的句柄.说明:(1)例子的分析过程是一步步地规约当前句型的句柄该句子的唯一语法树为:aAcBeAbbdS注意两点：（a）栈内符号串+未处理输入符号串=当前句型（b）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的识别问题1616(2)未真正解决句柄的识别.上述分析过程的怎样识别句柄的，主要看栈顶符号串是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。因为不能认为:对句型xuy而言若有U→u，即Uu就断定u是简单短语，u就是句柄，而是要同时满足ZxUy*6.2算符优先分析介绍(Operator-PrecedenceParsing)17171)这是一种经典的自底向上分析法，简单直观，并被广泛使用，开始主要是对表达式的分析，现在已不限于此。可以用于一大类上下无关的文法.运算法则:1.乘除的优先大于加减2.同优先级的运算符左大于右3.括号内的优先级大于括号外于是：4+8-6/2*3运算过程和结果唯一。2)称为算符优先分析是因为这种方法是仿效算术式的四则运算而建立起来的，作算术式的四则运算时，为了保证计算结果和过程的唯一性，规定了一个统一的四则运算法则，规定运算符之间的优先关系。18183)算符优先分析的特点:仿效四则运算过程，预先规定相邻终结符之间的优先关系，然后利用这种优先关系来确定句型的“句柄”，并进行规约。4)分析器结构:#分析程序优先关系矩阵#符号栈输入串1919例:G[E]E→E+E|E*E|(E)|iVt={+,*,(,),i}这是一个二义文法，要用算符优先法分析有该文法所确定的语言句子。如：i+i*i(1)先确定终结符之间的优先关系优先关系的定义:设a,b为可能相邻的终结符定义:a=ba的优先级等于baba的优先级小于baba的优先级大于b...2020a)例中文法终结符之间的优先关系可以用一个矩阵M来表示#)=(i*+#)(i*+b(右栈外)a(右栈内)............................b)矩阵元素空白处表示这两个终结符不能相邻,故没有优先关系2121步骤符号栈输入串优先关系动作1234567891011##i#E#E+#E+i#E+E#E+E*#E+E*i#E+E*E#E+E#E####i#*i#*i#i*i#+i*i#+i*i#i+i*i##ii+#++ii*+**ii#*#+#移进移进移进移进移进规约规约规约规约规约接受#)=(i*+#)(i*+ba.............................E→E+E|E*E|(E)|i算法:当栈顶项(或次栈顶项)终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进.(2)分析过程i+i*i2222分析过程是从符号串开始,根据相邻终结符之间的优先关系确定句型的“句柄”,并进行规约,直到识别符号E,最后分析成功:i+i*i∈L(G[E])出错情况:1.相邻终结符之间无优先关系2.对双目运行符进行规约时,符号栈中无足够项3.非正常结束状态2323重要说明:(1)上述分析过程不一定是严格的最左规约（即不一定是规范规约）也就是每次每次规约不一定是规约当前句型的句柄，而是句柄的变形但也是短语.(2)文法的终结符优先关系可以用一个矩阵表示,页可以用两个优先函数来表示.f—栈内优先函数g—栈外优先函数若ab则令f(a)g(b)a=bf(a)=g(b)abf(a)g(b)...2424算符优先函数值的确定方法:a.把各算符优先级按小到大定为j=0～n#（+*）i00123b.对于各算符的优先顺序若为左结合,则f(op)=2jg(op)=2j-1若为右结合,则f(op)=2j-1g(op)=2j设m2n,则f(j)=f(i)=m+1g(j)=g(i)=m，其他为0f(#)=f(()=g(#)=g())=0+*()i#f(栈内)240550g(栈外)136060f(+)g(+)左结合f(+)g(*)先乘后加f(+)g(()先括号内后括号外：根据这些原则,构造出上述文法的优先函数:2525注意特点:(a)优先函数值不唯一(b)优点：•节省内存空间若文法有n个终结符，则关系矩阵为n2而优先函数为2n•易于比较：算法上容易实现,数与数比,不必查矩阵.(c)缺点：可能掩盖错误.(不识别无优先关系情况)2626(3)可以设立两个栈来代替一个栈运算对象栈(OPND)运算符栈(OPTR)好处：便于比较,只需将输入符号与运算符栈的栈顶符号相比较(4)使用算符优先分析方法可以分析二义性文法所产生的语言例:G[E]E→E+E|E*E|(E)|iVt={+,*,(,),i}二义性文法按规范分析，其句柄不唯一这是一个二义性文法,i+i*i有两棵语法树27EE*EE+iiiE12345EE+EEE*ii2345i1按规范规约,句柄不唯一,E+E*i所以整个规约过程就不唯一,编译所得的结果也将不唯一.6.3算符优先分析法2828(1)算符优先文法(OPG)(2)构造优先关系矩阵(3)算符优先分析算法的设计2929（1）算符优先文法（OPG）算符文法（OG）的定义优先关系的定义若文法中无形如U→·¨VW·¨的规则，这里V,W∈Vn则称G为OG文法，也就是算符文法。若G是一OG文法，a,b∈Vt,U,V,W∈Vn分别有以下三种情况:3030算符优先文法（OPG）的定义设有一OG文法，如果在任意两个终结符之间，至多只有上述关系中的一种，则称该文法为算符优先文法(OPG)1)a=biff文法中有形如U→·¨ab·¨或U→·¨aVb·¨的规则。2)abiff文法中有形如U→·¨aW·¨的规则，其中Wb·¨或WVb·¨。3)abiff文法中有形如U→·¨Wb·¨的规则,其中W·¨a或W·¨aV。++...++3131对于OG算法的几点说明:1)运算是以中缀形式出现的3)算法语言中的表达式以及大部分语言成分的文法均是OG文法2)可以证明，若文法为OG文法，则不会出现两个非终结符相邻的句型。3232（2）构造优先关系矩阵FIRSTVT(U)={b|Ub…或UVb…,b∈Vt,V∈Vn}++LASTVT(U)={a|U…a或U…aV,a∈Vt,V∈Vn}++•求“=”检查每一条规则，若有U::=…ab…或U::=…aVb…,则a=b..•求“”、“”复杂一些，需定义两个集合..3333•求“”、“”:..若文法有规则W→...aU...，对任何b,b∈FIRSTVT(U)则有：ab.若文法有规则W→...Ub...，对任何a,a∈LASTVT(U)则有：ab.3434构造FIRSTVT(U)的算法1)若有规则U→b…或U→Vb…(存在Ub…或UVb…)则b∈FIRSTVT(U)++2)若有规则U→V…且b∈FIRSTVT(V),则b∈FIRSTVT(U)说明:因为Vb…或VWb…,所以有UV…b…或UV…Wb…++++3535设一个栈S和一个二维布尔数组FF[U,b]=TRUEiffb∈FIRSTVT(U)PROCEDVREINSERT(U,b)IFNOTF[U,b]THENBEGINF[U,b]:=TRUE把(U,b)推进S栈/*b∈FIRSTVT(U)*/ENDBEGIN{main}FOR每个非终结符号U和终结符bDOF[U,b]:=FALSE/*赋值符*/FOR每个形如U::=b…或U::=Vb…的规则DOINSERT(U,b)具体方法如下:3636WHILES栈非空DOBEIGN把S栈的顶项弹出,记为(V,b)/*b∈FIRSTVT(U)*/FOR每条形如U::=V…的规则DOINSTER(U,b);/*b∈FIRSTVT(U)*/ENDOFWHILEEND上述算法的工作结果是得到一个二维的布尔数组F,从F可以得到任何非终结符号U的FIRSTVTFIRSTVT(U)={b|F[U,b]=TRUE}3737构造LASTVT(U)的算法1.若有规则U::=…a或U::==…aV,则a∈LASTVT(U)2.若有规则U::=…V,且a∈LASTVT(V)则a∈LASTVT(U)设一个栈ST,和一个布尔数组BPROCEDUREINSERT(U,a)IFNOTB[U,a