《算符优先分析法》PPT课件.ppt

1、自下而上分析法,思想 从输入串出发，反复利用产生式进行规范归约，如果最后能得到文法的开始符号，则输入串是合法句子，否则输入串有语法错误。 核心 寻找句型中的归约串进行归约,用不同的方法寻找归约串，就可获得不同的分析方法,1、自下而上分析事例：设文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd试判断语句abbcde是否是该文法的合法句子？ 怎样实现归约过程：借鉴LL(1)分析法的体系结构,2、自下而上分析法的核心问题： 1)存在移进-归约冲突; 2)存在归约-归约冲突; 核心问题是寻找句型中的归约串进行归约。,自下而上分析法,一、算符优先分析法： 1、算符优先分析法的思想： 对于

2、文法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章 优先分析法,算符优先分析法的基本思想： 定义终结符之间的优先关系，借助终结符之间的优先关系确定归约对

3、象，进行自下而上分析。,比较相邻的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

4、),E+E-E,对文法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之间,在三种关系中最多

5、只有一种成立,则称该文法为算符优先文法。,(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

6、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) = ) LAS

7、TVT(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后面有非

8、终结符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 ,LASTVT(S) = # LASTVT(S) = ) LASTVT(R) =;,i,) LASTVT(P) =i,) LASTVT(D) = i ,文法：S#S# SD(R) RR;P|P PS|i Di,

9、练习题：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 i=n-2且Xi，Xi+2都为终结符但Xi+1为非终结符 THEN 置 XiXi+2; IF Xi为终结符而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置 Xia; IF Xi为非终结符而X

10、i+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1; END；,形如P-aQb,4、直观算法优先算法： (1)直观算符优先法的下推自动机： 两个工作栈：算符栈OPTR：用于存放运算符 算量栈OPND：用于存放运算量 当前读头下符号SYM如果是运算量，则进入算量栈。 当前读头下符号SYM如果是运算符，则判断是否将SYM加入算符栈：如果当前OPTR栈顶符号优先级高于SYM，则先执行当前栈顶运算；否则，将SYM加入算符栈。 (2)直观算符优先法分析过程： (3)直观算符优先算法：,PROCEDURE BEGIN OPND:=; OPTR:=#; FLAG:=TRU

11、E; 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 E

12、RROR 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#,算符优先分析法每一次归约时，可归约串中至少有一个终结符。,i+i*i# E+i*i# E+T*i#

13、 E+T*F# E+T# E#,E,E,+,T,i,T,*,F,i,i,第5章 算符优先分析法,(3)最左素短语： 素短语是指至少含有一个终结符，并且除它自身之外不再含有更小的素短语。 最左素短语指处于句型最左边的那个素短语。 最左素短语具备三个条件： 至少含有一个终结符。 除自身之外不再含有更小的素短语(最小性)。 在句型中具有最左性。,第5章 算符优先分析法,例：,ET+E|T TF*T|F F(E)|i 句型 T+F*T+i 的短语有 F*T i F*T+i T+F*T+i 其中的素短语为 F*T i F*T为最左素短语，是被归约的对象 ？按照文法EE+E|E*E|(E)|i ，求i+E

14、*i+i的短语和素短语,E E E T T F T + F * T + i,第5章 算符优先分析法,文法：EE+E|E*E E(E)|i 句型i+E*i+i的短语,E E E E E E i + 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-1a

15、i ， (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=#

16、; 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|T T-T*F|F F-i Eb-b,构造算符优先表,FIRSTVT(S)=if FIRSTVT(E)=+,*,i FIRSTVT(T)=*,i FIRSTVT(F)=i FIRSTVT(Eb)=b,第5章 算符优先分析法,S-if Eb then E else E E-E+T|T T-T*F|F F-i Eb-b,LASTVT(S)=else,+,*,i LASTVT(E)=+,*,i LASTVT(T)=*,