编译原理第06章 自底向上优先分析法课件

1、编译原理之优先分析法,1,PPT学习交流,第06章 自底向上优先分析法,自底向上优先分析概述 简单优先分析法 算符优先分析法,2,PPT学习交流,自底向上分析方法概述,自底向上分析方法，也称移进-归约分析法。 实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。 重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。 示例,3,PPT学习交流,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde

2、# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,最右推导：,示例,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,4,PPT学习交流,简单优先分析法,按照文法符号（包括终结符和非终结符）的优先关系确定句柄。 定义 优先关系 简单优先文法 优先关系矩阵：表示文法符号之间关系的矩阵。 算法 示例,5,PPT学习交流,优先关系 X Y：表示X、Y的优先

3、关系相同，当且仅当文法G中存在产生式A.XY； XY：表示X的优先性比Y的要低，当且仅当文法G中存在产生式A.XB.，且B Y. XY：表示X的优先性比Y的要高，当且仅当文法G中存在产生式A.BD.，且B .X，D Y,优先关系的定义,6,PPT学习交流,简单优先文法的定义,满足以下条件的文法是简单优先文法： （1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立； （2）在文法中任意两个产生式没有相同的右部。,7,PPT学习交流,简单优先分析法算法,根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下： 将输入符号串a1a2a3.an#依次逐个存入

4、符号栈S中，直到遇到栈顶符号ai的优先性.下一个待输入符号aj时为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。 由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。 重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。,8,PPT学习交流,简单优先文法分析示例,文法G S： (1) S bAb (2) A (B|a (3) B Aa) 1、确定文法符号之间的关系 2、求出文法的简单优先关系矩阵 3、对输入串进行分析（输入串b(aa)b# ）,9,P

5、PT学习交流,确定文法符号之间的关系,1. 求关系： 由(1)：b A A b 由(2)：(B 由(3)：A a a ) 2. 求关系： 由(1)(2)：b( b a 由(2)(3)：( A ( ( a 3. 求关系： 由(1)：B b a b ) b 由(3)：B a a a ) a,10,PPT学习交流,求出文法的简单优先关系矩阵,“#”用来表示语句括号，其优先关系低于所有与其有相邻关系的文法符号。,11,PPT学习交流,对输入串进行分析（输入串b(aa)b# ）,文法GS：(1) S bAb(2) A (B|a(3) B Aa),12,PPT学习交流,算符优先分析法,某些文法具有“算符”

6、特性 表达式运算符（优先级、结合性）； 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性； 只考虑算符之间的优先关系来确定句柄。 定义 算符文法 算符优先关系 算法优先文法 最左素短语 算符优先关系表的构造 算符优先分析法概述 算符优先文法的性质 算符优先分析算法 优先函数 算符优先分析法的局限性,13,PPT学习交流,算符文法的定义,如果不含空产生式的上下文无关文法 G 中没有形如 UBC的产生式，其中B，CVN，则称G为算符文法（Operater Grammar，OG）。 性质 1：在算符文法中任何句型都不包含两个相邻的非终结符。（归纳法） 2：如 Vx 或 xV 出现在算符文

7、法的句型 中，其中VVN,xVT, 则 中任何含 x 的短语必含有V。（反证法）,14,PPT学习交流,用归纳法,设是句型，即S* S=0 1 .n-1 n= 推导长度为n，归纳起点n=1时， S=01= ，即S ，必存在产生式S，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。 假设n1, n-1满足性质1。 若n-1= A，A为非终结符。 由假设知的尾符号和的首符号都不可能是非终结符，否则与假设矛盾。 又若A是文法的产生式，则有 n-1 n= 而A是文法的原产生式，不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1。证毕。,15,PPT学习交流,反证法,因

8、为由算符文法的性质1知可有： S*=bA 若存在B*b，这时b和A不同时归约，则必有S*BA,这样在句型BA中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。 注意：含b的短语必含A，含A的短语不一定含b。,16,PPT学习交流,算符优先关系的定义,设G是不含产生式的文法,a、b是任意两个终结符，A、B、C是非终结符，算符优先关系的定义如下： ab 当且仅当G中有形如Aab或A aBb的产生式。 ab 当且仅当G中有形如A aB的产生式,且B+b或B+ Cb ab 当且仅当G中有形如ABb的产生式,且B+a或BaC 注意： 算符优先关系中不存在递推关系，即ab bc ac或 ab bc ac

9、或ab bc ac 优先关系的语法树表示方式,17,PPT学习交流,优先关系的语法树表示方式,18,PPT学习交流,算符优先文法的定义,设G是不含产生式的算符文法,如果对任意两个终结符对a、b之间至多只有一种算符优先关系存在，则称G 为算符优先文法。 结论 算符优先文法是无二义的。,19,PPT学习交流,算符优先关系表的构造,集合的定义： FIRSTVT(B)=b|B + b或B + Cb. 对于非终结符B，其往下推导所可能出现的首个算符（终结符） LASTVT(B)=a|B + a或B +. aC 对于非终结符B，其往下推导所可能出现的最后一个算符（终结符） 构造方式： 由定义直接构造 由关

10、系图法构造 构造算法,20,PPT学习交流,由定义计算算符优先关系,直接计算 算法计算 关系图计算,21,PPT学习交流,直接计算算符优先关系,关系 直接看产生式的右部，若出现了Aab或AaBb,则a b 关系 求出每个非终结符B的FIRSTVT(B) 若AaB,则bFIRSTVT(B),ab 关系 求出每个非终结符B的LASTVT(B) 若ABb,则aLASTVT(B),a b 示例,22,PPT学习交流,直接计算示例,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,FIRSTVT(E)=#FIRSTVT(E)

11、=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i,1)关系由产生式(0)和(6),得# #，（ ）,3)关系找形如：ABb的产生式E# ,则 LASTVT(E)#E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) , 则 LASTVT(E),2）关系找形如：AaB的产生式#E：则#FIRSTVT(E)+T: 则+FIRSTVT(T) *F: 则*F

12、IRSTVT(F)F: 则 FIRSTVT(F)(E: 则 (FIRSTVT(E),23,PPT学习交流,算法计算算符优先关系,算法规则： 1、若有产生式Aa或ABa，则aFIRSTVT(A)，其中A、B为非终结符，a为终结符； 2、若aFIRSTVT(B)且有产生式ABb，则有aFIRSTVT(A)。 算法： 文本描述 按规则1对每个数组元素FA，a赋初值，并对数组元素FA，a初值为真的符号对(Aa)都放入栈中，然后对栈做如下运算。 当栈不空时，就将栈顶项弹出，并记为(B，a)，再用规则2，若FA，a为假，则使其变为真，且将(A，a)推进栈，如此重复直到栈折空为止。 程序描述 示例,24,P

13、PT学习交流,程序描述,将置为真的操作： PROCEDURE INSERT(Aa); IF NOT FA，a THEN BEGIN FAa：TRUN PUSH(Aa) 0NT0 STRACK END,主程序： BEGIN(MAIN) FOR 每一个非终结符A和终结符a， DO FA，a：FALSE； FOR 每个形如Aa或ABa的产生式 DO INSERT(A，a) WHILE STACK非空 DO BEGIN 把STACK的顶项记为(B，a)托出去 FOR 每个形如A B的产生式 Do INSERT(A ，a) END END,25,PPT学习交流,算法计算示例,文法GE：(0) E#E#(

14、1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,首次扫描STRACK的初值： (6) (P,i) (5) (P,( ) (4) (F,) (3) (T,*) (2) (E,+) (1)( E,#),栈顶（6）的改变：FP ( F,i)TF (T,i)ET (E,i),由于无右部以E开始的产生式，所以(E,i)弹出后无进栈项，此时当前的栈顶为(P,( ) 。 栈顶（5）的改变：FP ( F,( )TF (T,( )ET (E,( ),(E,（ )弹出后无进栈项，此时当前的栈顶为(F, )。 栈顶（4）的改变：TF (T, )ET (E, ),

15、(E, )弹出后无进栈项，此时当前的栈顶为(T, * )。栈顶（3）的改变：ET (E, * ),以下逐次弹出栈顶元素后，都再无进栈项，直至栈空。,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,i,26,PPT学习交流,关系图计算算符优先关系,关系图的构造方法 图中的结点为非终结符的FIRSTVT(A)和终结符; 对每一个形如Aa或ABa的产生式，则构造由FIRSTVT(A)结点到终结符结点(a)用箭弧连接的图形； 对每一个形如AB的产生式，则对应图中由FIRSTVT(A)结点到FIRSTVT

16、(B)结点用箭弧连接； 对每一非终结符的FIRSTVT(A) 经箭弧有路径能到达的终结符结点(a) ，则有a FIRSTVT(A)。 示例,27,PPT学习交流,关系图计算示例,FIRSTVT(E),FIRSTVT(E),FIRSTVT(T),FIRSTVT(F),FIRSTVT(P),#,+,*,(,),文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,28,PPT学习交流,由关系图法计算算符优先关系,文法符号的关系定义 优先关系与符号关系之间的联系 算符关系构造规则 的关系构造规则 的关系构造规则 示例 文法符

17、号之间的关系 文法终结符之间的关系图 文法终结符之间的关系图,29,PPT学习交流,文法符号的关系定义（6.4）,设G=(VN，VT，P，S)是一个上下文无关文法，则： A FIRST B 当且仅当存在形如AB的产生式； A LAST B 当且仅当存在形如AB的产生式； B FIRSTTERM b 当且仅当存在形如Bb或BCb的产生式； B LASTTERM a 当且仅当存在形如Ba或BaC的产生式； X FOLLOWEDBY Y 当且仅当存在形如AXY的产生式，中必须是一个为终结符，另一个为非终结符； A FIRST* B 当且仅当存在形如AB或存在AX1，X1X2，Xn-1Xn，XnB的产

18、生式序列； A LAST* B当且仅当存在形如BA或存在AX1，X1X2，Xn-1Xn，XnB的产生式序列。,30,PPT学习交流,优先关系与符号关系之间的联系,aba FOLLOWEDBY B B FIRST* P P FIRSTTERM b ab存在形如A aB的产生式,其中B+b或B+Cb 而B+b可写成B*P b B+Cb可写成B*P Cb 所以B+b或B+Cb B FIRST* P P FIRSTTERM b ab (B LAST* P P LASTTERM a)T B FOLLOWEDBY b ab存在形如A Bb的产生式,其中B+a或B+aC 而B+ a可写成B* P a B+

19、aC可写成B* P aC 所以B+ a或B+ aC B LAST* P P LASTTERM a,31,PPT学习交流, 的关系构造规则,凡有终结符在前非终结符在后相邻关系的，则由终结符结点到非终结符结点画一箭弧。 对有FIRSTTERM关系的非终结符和终结符对，则从非终结符结点到终结符点画一箭弧。 对非终结符对之间存在FIRST关系的，从左边的非终结符结点到右边的非终结符结点画一箭弧。 对每个终结符结点a凡有路径能到达另一终结符结点b的，则有ab关系存在。,32,PPT学习交流,的关系构造规则,对非终结符和终结符相邻关系的，由非终结符结点到终结符结点画一箭弧。 对有LASTTERM关系的，由

20、终结符结点到非终结符结点画一箭弧。 对LAST关系的非终结符对，由后面的非终结符结点到前面的非终结符结点画一箭弧。 对每个终结符结点a凡有路径能到达另一终结符结点b的，则有ab的关系成立。,33,PPT学习交流,文法符号之间的关系,E LAST T T LAST F F LAST F F LAST P,FIRST关系有 E FIRST E E FIRST T T FIRST T T FIRST F F FIRST P,FIRSTTBRM关系有 E FIRSTTBRM + T FIRSTTBRM * F FIRSTTBRM P FIRSTTBRM ( P FIRSTTBRM i,终结符在前非终结

21、符在后的相邻关系有 # FOLLOWEDBY E ( FOLLOWEDBY E + FOLLOWEDBY T * FOLLOWEDBY F FOLLOWEDBY F,E LASTTERM + T LASTTERM * F LASTTERM P LASTTERM ) P LASTTERM i,E FOLLOWEDBY # E FOLLOWEDBY + E FOLLOWEDBY ) T FOLLOWEDBY * P FOLLOWEDBY ,文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,34,PPT学习交流,文法终结

22、符之间的关系图,35,PPT学习交流,文法终结符之间的关系图,P,+,*,(,i,#,+,(,*,E,T,F,36,PPT学习交流,构造文法的优先关系算法,for(每个产生式AX1X2Xn)for(i=1;i=n-1;i+) if(Xi和Xi+1均为终结符) 置Xi Xi+1 ； if(in-2且Xi和Xi+2均为终结符,但Xi+1为非终结符) 置Xi Xi+1 ； if(Xi为终结符,Xi+1为非终结符) for(FIRSTVT(Xi+1)中的每个b)置Xib; if(Xi为非终结符,Xi+1为终结符) for(LASTVT(Xi)中的每个a)置aXi+1; ;,37,PPT学习交流,最左素

23、短语,文法GS句型的素短语是这样一个短语，它至少包含一个终结符号，并且，除它自身之外，不再包含其他素短语。 最左素短语是指处于句型最左边的那个素短语。 算符优先文法句型的最左素短语是唯一的。 示例 查找最左素短语的方法： 在句型中加入优先关系，例如：i+i*i # i i + + i i * * i i # 1、找最左素短语的右端； 从左至右扫描符号串直至遇到第一个为止。 2、找最左素短语的左端； 然后向回扫描(向左)越过任何，直至一个被发现。 3、归约； 可归约串包括在第1步所遇到的的左边和第2步所遇到的的右边的所有终结符号，包括插入在中间的或环绕在两旁的非终结符号。,38,PPT学习交流,

24、文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型#T+T*F+i#其短语有：T+T*F+iT+T*FTT*Fi,最左素短语为：T*F,素短语：T*F，i,*,E,E,T,+,+,E,T,F,F,T,T,i,句型T+T*F+i的语法树,最左素短语示例,39,PPT学习交流,算符优先分析法概述,1.算符优先分析法是一种特别有利于表达式分析，宜于手工实现的语法分析方法。 2.算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此，它不是一种规范归约法。 3.所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法

25、分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质。 示例,40,PPT学习交流,算符优先分析法示例,文法GE：(1) EE+T (2) ET (3) TT*F (4) TF(5) F (E) (7) Fi 对输入串i+i#的规约过程： 规范规约 算符优先规约,41,PPT学习交流,规范规约示例,42,PPT学习交流,算符优先规约示例,43,PPT学习交流,算符优先文法的性质,对于算符优先文法，如果aNb(或ab)出现在句型r中,则之间有且仅有一种优先关系，即： 若ab，则在r中必含有b而不含a的短语存在； 若ab，则在r中必含有a而不含b的短语存在； 若ab，则在r中含有a的

26、短语必含有b，反之亦然。 算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#, 若Niai.NjajNj+1为句柄，则Ni 、 Nj+1在句柄中，且该句柄中终结符之间的关系为： ai-1ai aiai+1.aj-1aj ajai+1,44,PPT学习交流,算符优先分析算法,算符优先分析归约的关键是寻找最左素短语。,开始,当前输入符读入a,置初值k=1,Sk=#,SkVT?,Sja?,Sja?,j=k,j=k-1,Q=Sj,Sj-1VT?,j=j-1,j=j-2,SjQ?,Sj+1Sk归约为N k=j+1 Sk=N,K=k+1 Sk=a,Sj.=a?,Sj.=#?,出错,检查是

27、否 正常结束？,结束,Y,N,N,Y,Y,Y,N,N,Y,Y,Y,Y,Y,N,N,N,45,PPT学习交流,优先函数,定义 构造方法 由定义进行构造 由关系图进行构造 示例 通过定义计算优先函数关系 通过关系图计算优先函数关系 优先函数分析的特点,46,PPT学习交流,优先函数定义,定义两个函数f、g ，满足如下条件： 当ab，则令f(a)g(b) 当ab，则令f(a)g(b) 当ab，则令f(a)g(b) 对f、g可称它为优先函数。 优先函数的值可以用整数表示。 对优先函数每个元素的值都增加同一个常数，优先关系不变，所以对同一个文法的优先关系矩阵对应的优先函数不唯一。 有一些优先关系矩阵中的

28、优先关系是唯一的，却不存在优先函数。 示例,47,PPT学习交流,由定义构造优先函数,若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g: a)对每个终结符aVT(包括#在内)令f(a)g(a)1 (也可是其它整数)。 b)如果ab，而f(a) g(b)，则令f(a)g(b)+1 c)如果ab而f(a)g(b) ，则令g(b)f(a)+1 d)如果ab，而f(a)g(b) ，则令 minf(a)，g(b)=maxf(a)，g(b) e)重复b)d)直到过程收敛。 如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。,48,PPT学习交流,由关系图构造优先函数,a对所有终结符a(包括#)用有下脚标的fa，gb为结点名，画出2n个结点。 b若ai aj；或ai aj ，则从fai到gaj画一条箭弧。 c若ai aj；或ai aj，则从gaj到fai画一条箭弧。 d给每个结点赋一个数，此数等于从该结点出发所能到达的结点(包括该结点自身在内)的个数。赋结结点fai的