语法分析-自下而上分析.ppt

第五章 语法分析-自下而上分析,5.1 自下而上分析的基本问题,Figure5.5LR演示自下而上分析 i+(i+i)*i 原理:自左向右扫描，自下而上分析 从输入符号串入手，通过反复查找当前句型的可归约串，并使用文法的产生式把它归约成相应的非终结符来一步步地进行分析的。 最终把输入串归约成文法的开始符号，表明分析成功。,任何自下而上分析方法的关键就是要找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符。,规范归约基本概念,如果A= ，则称是句型 相对于非终结符A的直接短语。,G为文法，S为开始符号，假定是G的一个句型，如果 则称是句型 相对于非终结符A的短语。,表达式文法的例子 i+i*i,找出所有短语，直接短语和句柄,最左直接短语称为句柄。,从句子到开始符号的归约序列，如果每一步都是把句柄替换为 相应产生式的左部符号而得到的，则称为规范归约。规范归约 是最右推导（规范推导）的逆过程。,例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E) 并假定输入串为（i+i)*i，考察自下而上的分析过程。,分析过程图表：,步骤 分析栈 输入串 动作 # (i+i)*i# 移进 #( i+i)*i# 移进 #(i +i)*i# 归约 #(F +i)*i# 归约 #(T +i)*i# 归约 #(E +i)*i# 移进 #(E+ i)*i# 移进 #(E+i )*i# 归约 #(E+F )*i# 归约,步骤 分析栈 输入串 动作 10 #(E+T )*i# 归约 11 #(E )*i# 移进 12 #(E) *i# 归约 13 #F *i# 归约 14 #T *i# 移进 15 #T* i# 移进 16 #T*i # 归约 17 #T*F # 归约 18 #T # 归约 19 #E # 接受,栈上的候选式不一定是句柄。例如，在第14步对栈顶为T，它是E的一候选式，但它不是句柄，不能归约成E。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。,自下而上方法包括四个动作：,移进：把输入流的头符读到分析栈中。,归约：把分析栈顶的句柄归约为一非终极符。,接受：分析成功。,报错：处理错误。,首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定可归约串。,算符文法：任何产生式的右部都不含两个相继的非终结符,5.2 算符优先分析,例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E) 是否是算符文法？,优先关系：,如果一个算符文法的任何终结符对至多只满足三种关系之一，称为算符优先文法。,验证终结符对之间的优先关系(p90优先表),例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E) 是否是算符优先文法？,如何从文法构造优先关系表？,检查文法产生式的每个候选，可找出所有满足 的终结符对。,如何找出满足 和 终结符对？,对每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P),FIRSTVT(P)=,LASTVT(P) =,检查每个产生式候选，若形为.aP.,则对任何bFIRSTVT(P)， 我们有a b。,若形为.Pb.,则对任何aLASTVT(P)， 我们有a b。,对表达式文法的非终结符构造FIRSTVT和LASTVT并建立优先关系表,算符优先分析算法,素短语：这样的一个短语，它至少含一个终结符，不含比自身更小的素短语。,最左素短语：句型最左边的素短语。,演示SuanFuYouXian,优先函数,有的关系表不存在优先函数！ 对于存在优先函数的关系表，如何构造优先函数？ 请自学p9495优先函数的构造方法。,5.3 LR 分析法,1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。 LR(K)分析是指自左向右扫描和自下而上的语法分析，且 在分析的每一步，只须根据分析栈中当前已移进和归约出的 全部文法符号，并至多再向前查看K个输入符号，就能确定 相当于某一产生式右部符号的句柄是否已在分析栈的顶部形 成。从而也就可以确定所应采取的分析动作（是移进输入符号 还是按某产生式进行归约）。,当前扫描到Xn+1,向前查看k个符号，来确定是把 Xn+1移进栈，还是把XiXn作为句柄进行归约。,1） 要归约时，则根据某产生式UXiXi+1Xn进行归约： #X1X2Xi-1UXn+1Xn+2Xn+k#,LR(0) 表示在每一步分析时都不用向前输入符号 LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。,5.3.1 LR分析概论,一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图：,所有LR分析器的总控程序大同小异,只有分析表各不相同。 三种不同的分析表,规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。,简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。,向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。,二、LR 分析器的分析过程如下：,1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。,则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查 分析动作表，根据ACTIONSm, ai的指示完成相应的分析动作。 表中每一表元素所规定的动作仅能是下列四种动作之一：,2.设在分析中的某一步，分析栈及余留的输入串为如下格局： S0S1 Sm ai ai+1an #X1 Xm ,（1） ACTIONSm, ai= Sm+1 （移进） 表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成 句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有,（2） ACTIONSm, ai= Rj (归约） 表明此时应按文法的第j个产生式A Xm-k+1Xm-k+2 Xm 进行归约。即栈顶符号串Xm-k+1Xm-k+2 Xm已成为当前句型的句 柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符 号退栈，然后将文法符号A压入符号栈中。此时分析的格局为： S0S1 Sm-k ai ai+1an # # X1 Xm-k A ,然后以（ Sm-k,A)去查状态转移表，设GOTOSm-k,A= Sl ,则将此新状态压入状态栈中，则有如下格局： S0S1 Sm-k Sl ai ai+1an # # X1 Xm-k A ,（3） ACTIONSm, ai=acc （接受）,表明当前的输入串已被成功地分析完毕，应停止分析器的工作。,其中Z为文法开始符号 S为使ACTIONS ，#=acc的 唯一状态（接受状态）,（4） ACTIONSm, ai=ERROR（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。,3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态”为止。对接受状态，分析栈的格局为： S0 S # # Z ,5.3.2 LR(0) 分析表的构造,为了给出构造LR(0)分析表的算法，给出一些术语： 1、规范句型的活前缀 前缀：一个符号串的前缀是指该串的任意首部（包括）。,例如 abc的前缀有： ,a,ab,abc abcd的前缀有：,a,ab,abc,abcd 由此可知，对于符号串 而言，其前缀的数量为+1。 例：有文法GS:SaAcBe1 Ab2 这里在每条产生式后加上了产生 AAb3 式的序号i当进行推导时把序号 Bd4 带上，以便说明问题。 对输入串abbcde进行推导如下（最右推导）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 由此可知，abbcde是该文法的句子。,最左归约为： ab2b3cd4e1 用2式归约, aAb3cd4e1 3, aAcd4e1 4, aAcBe1 1, S,其中表示归约符,归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前面部分；X1X2Xnp 其中Xi为文法的符号，p为第p个产生式序号。 如上例中每次归约前句型的前面部分为： ab2 aAb3 aAcd4 aAcBe1,我们把规范句型的这种前端部分的串称为活前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。,SaAcBe1 Ab2 AAb3 Bd4,这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约 之故。所以我们将把规范句型具有上述性质（即不含句柄之后的 任何符号）的前缀称之为活前缀。 对各规范句型有前缀：,ab2b3cd4e1 ,a,ab aAb3cd4e1 ,a,aA,aAb aAcd4e1 ,a,aA,aAc,aAcd aAcBe1 ,a,aA,aAc,aAcB,aAcBe,活前缀：是指规范句型的一个前缀，这种前缀不含句柄之 后的任何符号。,活前缀定义：,在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。,2、LR（0）项目,活前缀与句柄间的关系： （1）活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。 （2）活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。 （3）活前缀中全然不包含句柄的任何符号。,第一种情况表明：此时某一产生式A的右部已出现在符号 栈顶，因此此时相应的分析动作应当是用此产生式进行归约。 第二种情况表明：形如A12的产生式的 右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由推出的 符号串，即期待2 进栈以便能进行归约。故此时分析动作是“移进”当前输入符号。 第三种情况则意味着：期望从余留输入串中能看到由某产生式 A的右部，即所代表的符号串(即句柄) 。所以此时分析的动作也是读输入符进符号栈。,在产生式的右部相应位置上加一个圆点“.”，来指示识别位置，标明在“.”前的部分已被识别。 如上述三种情况，可分别标注为：A.； A1 .2 ; A. 。 右部某位置上标有圆点的产生式称为LR(0)项目(item)。 不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。,例如：产生式SaAcBe对应有六个项目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,每个项目的含义与圆点的位置有关。 圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。 文法的全部LR(0)项目将是构造识别它的所有活前缀的有穷自动机的基础。,3、LR(0)项目的分类：,例：考虑文法GS=(S,A,B, a,b,c,d,P,S),构造其分析表： 其中P: (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,求该文法的项目集规范族C： 在上述文法中引入一个新的开始符号S,且将S S作为第0个产生式添加到文法G中，得到G的拓广文法G。显然L(G)=L(G)，则对于文法G，其LR(0)项目为：,1) S .S 2) S S. 3) S.A 4) SA . 5) S.B 6) SB. 7) A.aAb 8) Aa .Ab 9) AaA .b 10) AaAb . 11) A.c 12) Ac . 13) B.aBd 14) Ba .Bd 15) BaB .d 16) BaBd . 17)B.d 18) Bd .,G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d,LR(0)项目分类,A. 因为它表明右部符号串已出现在栈顶，此时相应的分析动作应当是按此产生式进行归约，此种项目称为归约项目。 S S. 称为接受项目。 对于拓广文法而言，接受项目是唯一的。 A. X 的项目（其中 可以是 ），当X为终结符时，相应的分析动作应将当前的输入符号移入栈中，故我们将此种项目称为移进项目。 当X为非终结符时，期待着从余留的输入符中进行归约后而得到X，此类项目称为待约项目。,把终结符和非终结符都可看成一个有限自动机的输入符号，每把一个符号进栈相当于已识别过该符号，而状态进行转换（到下一状态），当识别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句柄的终态。,4、构造识别活前缀的DFA DFA中的中每一个状态由若干个LR(0)项目所组成的集合（称为项目集）来表示。,举例：构造识别前缀的DFA 用I0表示这个DFA的初态， 将项目S.S列入项目集I0。 将项目S.A和S.B加入I0中。 将A.aAb和A.c和B.aBb, B.d加入I0中。 项目集I0将由如下项目组成： I0 : S.S, S.A, S.B, A.aAb, A.c, B.aBd, B.d S.S称为项目集I0的基本项目，从基本项目出发构造项目集I0的过程，可用closure(S.S)表示。,closure(I)的定义：,Closure(I)=IA.AGK .Aclosure(I)V*V*,构造closure(I)的算法： 1）I中的每一个项目都属于closure(I); 2）若形如K.A的项目属于I，且A是文法的一个产生式，任何形如A.的项目也应加到closure(I)中 3）重复上述过程，直至不再有新的项目加入到closure(I)中为止。,如何确定从I0可能转移到的下一状态？ 若I0中有项目K .A，从输入串识别出A后，进入下一状态。设此状态为Ii ，显然Ii中必含有形如KA .的项目，称为K .A的后继项目。 后继项目组成集合J，则J中的每个项目都是项目集Ii的基本项目，有： Ii =closure(J),定义状态转移函数：GO(I,A)=closure(J) 其中，I是当前状态，A为文法符号，J是I中所有形如K.A 的项目之后继项目KA.所组成的集合，而closure(J)就是项目 集I（即状态I)关于符号A的后继项目集（即后继状态）。,GO(I,A)=closure(所有形如KA .的项目K .AI),对于上例，有： I1 =GO(I0,S)=closure(SS.) I1 : SS.; I2 =GO(I0,A)=closure(SA.) I2 :SA.; I3 =GO(I0,B)=closure(SB.) I3 : SB.; I4 =GO(I0,a)=closure(Aa.Ab,Ba.Bd),I4 : Aa.Ab Ba.Bd A.aAb B.aBd A.c B.d I5=GO(I0,c)=closure(Ac.) I5 : Ac. I6=GO(I0,d)=closure(Bd.) I6 :Bd. I1, I2,I3,I5,I6均无后继项目集，仅I4有后继项目集： I7 =GO(I4,A)=closure(AaA.b)=AaA.b I9 =GO(I4,B)=closure(BaB.d)=BaB.d 此外，还有： GO(I4,a)=closure(Aa.Ab, Ba.Bd)= I4 GO(I4,c)=closure(Ac.)= I5 GO(I4,d)=closure(Bd.)= I6 这些项目集均不产生新的项目集。另外还有:,I8 =GO(I7,b)=closure(AaAb.)=AaAb. I10 =GO(I9,b)=closure(BaBd.)=BaBd. I8 ， I10也后继项目集。 GS的全部项目集即为I0 I10 。 将这些项目集的全体称为文法GS的LR(0)项目集规范族，并记为C=(I0, I1, I10) 识别文法GS的全部活前缀的DFA为 M=(C,V,GO, I0,Z) 其中CM的状态集，即文法GS的LR(0)项目集规范族I0 I10 V M的字母表，即V=S,S,A,B,a,b,c,d； GOM的状态转换函数，即上面定义的状态转移函数GO； I0M的唯一初态； ZM的终态集， ZC为规范族中所有含有归约项目的 那些项目集。,DFA:,4、LR(0)分析表的构造,要求每一个项目集中的的诸项目不出现下列的情况： （1）移进项目和归约项目并存，即存在移进归约冲突； （2）多个归约项目并存，即存在归约归约冲突。 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含有冲突的项目，则称G为LR(0)文法。 只有当一个文法是LR(0)文法时，才能对它构造不含冲突动作的LR(0)分析表。,构造LR(0)分析表的算法为： (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号 a 时，则置ACTIONi,a=Sj; 若X为一非终结符号时，则置GOTOi,X=j (2)若Ii中有归约项目A. ,设A为文法第j个产生式，则对文法的任何终结符和“#”（均记为a）置ACTIONi,a=Rj,(3)若接受项目SS .属于Ii ,则置ACTIONi,#=acc。 (4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。 如上例可构造分析表为：,ACTION GOTO a b c d # S A B 0 S4 S5 S6 1 2 3 Acc R1 R1 R1 R1 R1 R2 R2 R2 R2 R2 S4 S5 S6 7 9 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 S8 R3 R3 R3 R3 R3 S10 10 R5 R5 R5 R5 R5,5、LR(0)分析器的工作过程,根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作： 1）若ACTIONi,a=Sj, aVT,则把a移进符号栈，j移进状态栈。 2）若ACTIONi,a=Rj，aVT或#，则用第j个产生式归约。并将两个栈的指针减去K(其中K为第j 个产生式右部的串长度），并把产生式的左部符号A压入符号栈，同时用符号对（ Si-k,A)去查GOTO表（其中Si-k为状态栈当前栈顶元素，若GOTOSi-k,A=j,则j压入状态栈，使得两个栈内的元素一样多。 3）若ACTIONi,a=Acc,（此时a应为“#”号），则表明分析成功，结束分析。 4）若ACTIONi,a=空白，转出错处理。,5.3.3 SLR分析表的构造,大多数程序设计语言的文法不是LR(0)文法。 对LR(0)规范族中有冲突的项目集（状态）用向前查 看一个（输入）符号的办法进行处理，以解决冲突。即为SLR(1)。 假定有一个LR(0)规范族中含有如下项目集(状态)I: I=X.b,A., B.其中,为符号串，bVT, I中含有移进归约和归约归约冲突。 只要FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即：,当状态I面临某输入符号a时，则动作为： 1）若a = b,则移进。 2）若a FOLLOW(A),则用产生式A归约。 3）若a FOLLOW(B),则用产生式B归约。 一般地，对于LR(0)规范族的一个项目集I可能含有多个移进项目和多个归约项目，我们可假设项目集I中有m个移进项目： A11. b11, A2 2. b22, , Am m. bmm;同时含 有n个归约项目：B11. , B2 2. , Bn n. ,只要集合 b1, b2,bm和FOLLOW(B1),FOLLOW(B2),FOLLOW(Bn) 两两交集都为空，则我们仍可用上述归则来解决冲突： 1）若ab1, b2,bm,则移进。 2）若aFOLLOW(Bi),i=1,n,则用Bi i进行归约。 3）此外，则报错。,SLR分析表的构造方法 (1)对于每一项目集Ii中形如A.X的项目，且有GO(Ii,X)=Ij, 若X为一终结符号a时，则置ACTIONI,a=S; 若X为一非终结符号时，则仅置GOTOi,X=j； (2)若归约项目A.属于Ii,设A为文法第j个行产生式，则 对任何属于FOLLOW(A)的输入符号a,置ACTIONi,a=Rj； (3)若接受项目S S.属于Ii ,则置ACTIONi,#=acc。 (4) 在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。,例： 表达式文法GE,构造其LR(0)项目规范簇和SLR(1)分析表。 GE: EE+TT TT*FF F(E) i,解：1、拓广文法为GS : (0) SE EE+T ET TT*F TF F(E) Fi,2、再求识别G的全部活前缀的DFA：,I0: S.E E.E+T GO(I0,E)=I1 E.T T.T*F GO(I0,T)=I2 T.F GO(I0,F)=I3 F.(E) GO(I0,( )=I4,I1: SE. EE.+T GO(I1,+)=I6,I2: ET. TT.*F GO(I2,*)=I7,I3: TF.,I4: F(.E) E.E+T GO(I4,E)=I8 E.T T.T*F GO(I4,F)=I2 T.F GO(I4,F)=I3 F.(E) GO(I4,( )=I4 F.i GO(I4,i)=I5,I5: Fi.,I6: EE+.T T.T*F GO(I6,T)=I9 T.F GO(I6,F)=I3 F.(E) GO(I6,( )=I4 F.i GO(I6,i)=I5,I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4 F.i GO(I7,i )=I5,I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6,I9: EE+T. TT.*F GO(I9,)=I7,I10: TT*F.,I11: F(E).,DFA,3、解决冲突,I1， I2， I9中有移进-归约冲突。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 在I1中，由于FOLLOW(S)=#).而SE.是唯一的接受项目，所以当且仅当遇到句子的结束符“#”号时才被接受,又因#+=，故I1中的冲突可解决。 对于I2,因FOLLOW(E)=+,),#*=,因此当面临输入符号为“+”，“ ）”或“#”号时，则用产生式ET归约。当面临输入符为“*”时，则移进；其它情况则报错。 对于I9, 当面临输入符号为“+”，“）”或“#”时，则用产生式EE+T归约；当面临输入符号为“*”时，则移进，其余情况报错。 演示Figure5.5LRDFA,4、构造SLR