算符优先分析法.pptx

1、自下而上分析事例：设文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd试判断语句abbcde是否是该文法的合法句子？怎样实现归约过程：借鉴LL(1)分析法的体系结构步骤栈内输入串动作0#abbcde#1#a bbcde#移进2#ab bcde#移进3#aA bcde#归约4#aAb cde#移进5#aA cde#归约6#aAc de#移进7#aAcd e#移进8#aAcB e#归约9#aAcBe#移进10#S#归约11识别成功 2、自下而上分析法的核心问题：1)存在移进-归约冲突;2)存在归约-归约冲突;核心问题是寻找句型中的归约串进行归约。自下而上分析法 一、算符优先分析法：1、算符优先分析法的思想：对于文法G:EE+E|E-E|E*E|E/E|(E)|i，分析i+i-i*(i+i)规范推导：EE*EE*(E)E*(E+E)E*(E+i)E*(i+i)E+E*(i+i)E+E-E*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章 优先分析法逆过程是规范归约另外一种推导：EE-EE-E*EE-E*(E)E-E*(E+E)E-E*(E+i)E-E*(i+i)E-i*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章 优先分析法算符优先分析法的基本思想：定义终结符之间的优先关系，借助终结符之间的优先关系确定归约对象，进行自下而上分析。比较相邻的2个算符的优先级 2种推导过程对于8+7-5*(3+2)的计算结果2、算符优先分析技术的引进：必须给出文法中两个可能在句子中相继出现的终结符之间的优先关系。(1)相继出现：在句子中若有“ab”或“aQb”.(a,bT,QN),则称a，b相继出现。(2)终结符号对优先关系的存储：优先关系表是一个矩阵M(a,b),aT,bT,矩阵行数、列数都为|+1。如:对于文法G:EE+E|E-E|E*E|E/E|(E)|i,对应的优先矩阵为：矩阵元素M(a,b)表示a在前,b在后时,a与b之间的优先关系。矩阵元素M(a,b)的取值:,。i+i-i*(i+i)E+E-Ep对文法EE+E|E-E|E*E|E/E|(E)|i+-*/()i#+-*/()i#如何获得一般的文法的优先分析表？#优先级低于其右部符号源程序中不会出现)(的情形如何获得一般的文法的优先分析表？3、优先表的构造方法：算符文法：给定上下文无关文法G=（VN，VT，P，S）中不存在形如ABC的产生式，则称之为算符文法(OGOperator Grammar)(其中A,B,CN)即：如果文法中不存在具有相邻非终结符的产生式，则称为算符文法。算符优先文法:设文法G是一个不包含有空串产生式的算符文法,如果该文法中的任何终结符号对a,b之间,在三种关系中最多只有一种成立,则称该文法为算符优先文法。(1)求文法中每个非终结符P的首终结符集合FIRSTVT(P)定义：FIRSTVT(P)=a|P+a或者P+Qa,a T,P,Q N 复习：FIRST()=a|*a，aT 构造FIRSTVT(P)的算法：1)若有产生式Pa或者PQa,则aFIRSTVT(P)2)若有产生式PQ,则FIRSTVT(Q)FIRSTVT(P)例如：下述文法 S#S#SD(R)RR;P|P PS|i Di 求其每个非终结符P的FIRSTVT(P)FIRSTVT(S)=#FIRSTVT(S)=FIRSTVT(R)=FIRSTVT(P)=(,i FIRSTVT(D)=i(FIRSTVT(D)=(,i;FIRSTVT(P)=;,(,i (2)求文法中每个非终结符P的尾终结符集合LASTVT(P)定义：LASTVT(P)=a|p+a或者P+aQ,a T,P,Q N 复习：FOLLOW(A)=a|S*Aa，aT 构造LASTVT(P)的算法：1)若有产生式Pa或者PaQ,则aLASTVT(P)2)若有产生式PQ,则LASTVT(Q)LASTVT(P)例如：下述文法 S#S#SD(R)RR;P|P PS|i Di 求其每个非终结符P的LASTVT(P)LASTVT(S)=#LASTVT(S)=)LASTVT(R)=LASTVT(P)=LASTVT(D)=i;LASTVT(P)=;,i,)iLASTVT(S)=i,)(3)构造算符优先表：用产生式求出ab的符号对：方法：对形如Pab或PaQb的产生式,有ab(其中a,b T,P,Q N)利用构造的FIRSTVT(P)求出ab的符号对：方法：对形如PaR的产生式,若有bFIRSTVT(R)，则ab 利用构造的LASTVT(P)求出a b的符号对：方法：对形如PRb的产生式,若有aLASTVT(R)，则a b 对于文法的每个产生式，找出其中的终结符，同一产生式中的终结符使用第一条规则，如果某终结符a后面有非终结符P；则使用第二条规则，即有aFIRSTVT(P)；如果某终结符a前面有非终结符P，则使用第三条规则，即有LASTVT(P)a 例如：下述文法 S#S#SD(R)RR;P|P PS|i Di 构造其算符优先分析表。FIRSTVT(S)=#FIRSTVT(S)=(,i FIRSTVT(R)=;,(,i FIRSTVT(P)=(,i FIRSTVT(D)=i ();i#();i#LASTVT(S)=#LASTVT(S)=)LASTVT(R)=;,i,)LASTVT(P)=i,)LASTVT(D)=i 文法：S#S#SD(R)RR;P|P PS|i Di 练习题：S#S#SfStS Si=E EE+T|T TPT|P P(E)|i 求此文法的算符优先表。第5章 算符优先分析法PROCEDURE OPT;/构造优先表算法 FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符THEN 置 XiXi+1;形如P-ab第5章 算符优先分析法 IF iaQb 4、直观算法优先算法：(1)直观算符优先法的下推自动机：两个工作栈：算符栈OPTR：用于存放运算符 算量栈OPND：用于存放运算量 当前读头下符号SYM如果是运算量，则进入算量栈。当前读头下符号SYM如果是运算符，则判断是否将SYM加入算符栈：如果当前OPTR栈顶符号优先级高于SYM，则先执行当前栈顶运算；否则，将SYM加入算符栈。(2)直观算符优先法分析过程：(3)直观算符优先算法：PROCEDURE BEGIN OPND:=;OPTR:=#;FLAG:=TRUE;ADVANCE;WHILE FLAG DO BEGIN IF 算符栈顶R=#AND SYM=#THEN FLAG:=false ELSE IF 算符栈顶R=(AND SYM=)THEN BEGIN上弹OPTR;ADVANCE END ELSE IF SYM运算量 THEN BEGIN 将SYM压入OPND;ADVANCE END;ELSE IF 算符栈顶RSYM THEN BEGIN SYM进栈;ADVANCE END ELSE IF 算符栈顶RSYM THEN BEGIN 上弹OPND栈顶二项d1和d2；将d1Rd2压入栈内；上弹OPTR END ELSE ERROR END END;(4)直观算符优先分析法的缺点：会把错误句子当作合法句子分析 无法指出输入串的出错位置 对单目“负”和双目“减”的算术表达式不好处理。xy+zx+r()5、直观算符优先分析的若干问题：(1)二义文法不是算符优先文法。(2)算符优先分析是一种非规范规约分析。例如：E-E+T|T T-T*F|F F-(E)|i 分析句子i+i*i#规范归约分析：i+i*i#F+i*i#T+i*i#E+i*i#E+F*i#E+T*i#E+T*F#E+T#E#EE+TTFiT*FFii 算符优先分析法每一次归约时，可归约串中至少有一个终结符。算符优先分析法每一次归约时，可归约串中至少有一个终结符。i+i*i#E+i*i#E+T*i#E+T*F#E+T#E#EE+TiT*Fii第5章 算符优先分析法(3)最左素短语：素短语是指至少含有一个终结符，并且除它自身之外不再含有更小的素短语。最左素短语指处于句型最左边的那个素短语。最左素短语具备三个条件：至少含有一个终结符。除自身之外不再含有更小的素短语(最小性)。在句型中具有最左性。第5章 算符优先分析法例：例：pET+E|T TF*T|F F(E)|i句型 T+F*T+i 的短语有F*T i F*T+i T+F*T+i其中的素短语为F*T iF*T为最左素短语，是被归约的对象？按照文法EE+E|E*E|(E)|i，求i+E*i+i的短语和素短语 E E E E E E T T T F T FT +F *T +iT +F *T +i第5章 算符优先分析法文法：EE+E|E*E E(E)|i句型i+E*i+i的短语 E E E E E EE E E E E Ei +E *i +ii +E *i +i 最左素短语是算符优先法每一次的归约串，而句柄是规范归约每一次的归约串。i i E*i i i+E*i i+E*i+i其中的素短语为i i i(4)寻找句型最左素短语的方法：设句型的一般形式为：#N1a1 N2a2 NnanNn+1#（Ni VN,ai VT）它的最左素短语是满足下列条件的最左子串 Niai Ni+1ai+1 Njaj Nj+1 其中(1)ai-1ai，(2)aiai+1aj-1aj，(3)ajaj+1 综合起来即：ai-1 aiai+1aj-1aj aj+1，例如：#E+(E)-i#(5)通用算符优先分析：算法思想：第一个终结符入栈S。把下一个输入符号读入SYM中，则比较当前栈顶第一个终结符Sj同SYM的优先关系，如果SjSYM或SjSYM，则SYM入栈S，直到当前栈顶SjSYM。#入栈 从栈顶向下寻找最左素短语：若Sk-1Sk，则k-1，直到Sk-1Sk，此时Sk到栈顶就是最左素短语。如果当前栈中已经没有最左素短语，则转第2步继续，直到归约为文法开始符号。PROCEDUR BEGIN k:=1;Sk=#;REPEAT 把下一个输入符号i 读入SYM中；IF SkT THEN j:=k ELSE j:=k-1 WHILE SjSYM DO BEGIN REPEAT Q:=Sj;IF Sj-1T THEN j:=j-1 ELSE j:=j-2;UNTIL Sj Q;把Sj+1Sk归约为某个N；k:=j+1;Sk:=N END OF WHILE;IF SjSYM OR SjSYM THEN BEGIN k:=k+1;SK:=SYM END ELSE ERROR UNTIL SYM=#END分析if b then i else i#例：给定文法如下：第5章 算符优先分析法S-if Eb then E else E E-E+T|TT-T*F|F F-i Eb-b构造算符优先表FIRSTVT(S)=ifFIRSTVT(E)=+,*,iFIRSTVT(T)=*,iFIRSTVT(F)=iFIRSTVT(Eb)=b第5章 算符优先分析法S-if Eb then E else E E-E+T|TT-T*F|F F-i Eb-bLASTVT(S)=else,+,*,iLASTVT(E)=+,*,iLASTVT(T)=*,iLASTVT(F)=iLASTVT(Eb)=b第5章 算符优先分析法步骤下推栈关系输入串动作0#if b then i else i#1#if b then i else i#移进2#if b then i else i#移进3#if N then i else i#归约4#if N then i else i#移进5#if N then i else i#移进6#if N then N else i#归约7#if N then N else i#移进8#if N then N else i#移进9#if N then N else N#归约10#N#归约11成功LL(1)LL(1)的体系结构的体系结构 输入缓冲区输入缓冲区(符号序列符号序列)栈栈控制程序控制程序预测分析表预测分析表M输出的输出的输出的输出的产生式序列产生式序列产生式序列产生式序列返回返回返回返回作业1、给定算符文法：Sa|(T)TT,S|S（1）构造算符优先关系表；（2）该文法是否为算符优先文法？为什么？如果是算符优先文法，请给出句子(a,(a,a)的算符优先分析过程（指出堆栈和缓冲区的变化）。2、给定算符文法为：S#S#SfStS Si=E EE+T|T TPT|P P(E)|i 构造此文法的算符优先表。