自下而上分析法p思想n从输入串出发，反复利用产生式进行规范归 约，如果最后能得到文法的开始符号，则输入 串是合法句子，否则输入串有语法错误。p核心n寻找句型中的归约串进行归约,用不同的方 法寻找归约串，就可获得不同的分析方法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 DOFOR i:=1 TO n-1 DOBEGINIF Xi和Xi+1均为终结符THEN 置 XiXi+1;形如P-ab第5章 算符优先分析法IF iaQb4、直观算法优先算法：(1)直观算符优先法的下推自动机：两个工作栈：算符栈OPTR：用于存放运算符算量栈OPND：用于存放运算量当前读头下符号SYM如果是运算量，则进入算量 栈。当前读头下符号SYM如果是运算符，则判断是否 将SYM加入算符栈：如果当前OPTR栈顶符号优先级高于 SYM，则先执行当前栈顶运算；否则，将SYM加入算符栈 。(2)直观算符优先法分析过程：(3)直观算符优先算法： PROCEDURE BEGINOPND:=;OPTR:=#;FLAG:=TRUE;ADVANCE;WHILE FLAG DOBEGIN IF 算符栈顶R=# AND SYM=# THEN FLAG:=falseELSE IF 算符栈顶R=( AND SYM=) THENBEGIN上弹OPTR ; ADVANCE ENDELSE IF SYM运算量 THENBEGIN 将SYM压入OPND ; ADVANCE END;ELSE IF 算符栈顶RSYM THEN BEGIN SYM进栈; ADVANCE ENDELSE IF 算符栈顶RSYM THEN BEGIN上弹OPND栈顶二项d1和d2； 将d1Rd2压入栈内；上弹OPTRENDELSE ERRORENDEND; (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 i F*T为最左素短语，是被归约的对象 ？按照文法EE+E|E*E|(E)|i ，求 i+E*i+i的短语和素短语E EE EE ET TT F T FT + F * T + iT + F * T + i第5章 算符优先分析法文法：EE+E|E*E| (E)|i 句型i+E*i+i的短语E EE EE EE EE E E Ei + E * i + ii + E * i + i最左素短语是算符优先法每一 次的归约串，而句柄是规范归约