《第五章语法分析自下而上分析》由会员分享，可在线阅读，更多相关《第五章语法分析自下而上分析（54页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法分析-自下而上分析5.1 自下而上分析的基本问题 Figure5.5LR演示自下而上分析 i+(i+i)*i原理:自左向右扫描，自下而上分析 从输入符号串入手，通过反复查找当前句型的可归约串，并使用文法的产生式把它归约成相应的非终结符来一步步地进行分析的。 最终把输入串归约成文法的开始符号，表明分析成功。 任何自下而上分析方法的关键就是要找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符。规范归约基本概念如果A= ，则称是句型 相对于非终结符A的直接短语直接短语。G为文法，S为开始符号，假定是G的一个句型，如果则称是句型 相对于非终结符A的短语短语。表达式文法的例
2、子 i+i*i,找出所有短语，直接短语和句柄最左直接短语称为句柄句柄。从句子到开始符号的归约序列，如果每一步都是把句柄替换为相应产生式的左部符号而得到的，则称为规范归约规范归约。规范归约是最右推导（规范推导）的逆过程。例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E)并假定输入串为（i+i)*i，考察自下而上的分析过程。分析过程图表：步骤 分析栈 输入串 动作1 # (i+i)*i# 移进2 #( i+i)*i# 移进3 #(i +i)*i# 归约4 #(F +i)*i# 归约5 #(T +i)*i# 归约6 #(E +i)*i# 移进7 #(E+ i)*i# 移进8 #
3、(E+i )*i# 归约9 #(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。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。自下而上方法包括四个动作：移进：把输入流的头符读到分析
4、栈中。归约：把分析栈顶的句柄归约为一非终极符。接受：分析成功。报错：处理错误。 首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定可归约串。 算符文法：任何产生式的右部都不含两个相继的非终结符5.2 算符优先分析例：考虑文法G(E)：EE +T |T TT*F | F Fi| (E)是否是算符文法？优先关系：终结符ab的三种优先关系：当且仅当存在形如下面的产生式U ab或U aQb当且仅当存在形如下面的产生式UaW的生产式，且有 Wb当且仅当存在形如UV b的产生式且有 Va或V aQababab 如果一个算符文法的任何终结符对至多只满足三
5、种关系之一，称为算符优先文法算符优先文法。验证终结符对之间的优先关系(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并建立优
6、先关系表算符优先分析算法 素短语：这样的一个短语，它至少含一个终结符，不含比自身更小的素短语。 最左素短语：句型最左边的素短语。 定理：算符优先文法的句型#N1a1N2a2.NnanNn+1#的最左素短语是满足如下条件的最左子串Njaj.NiaiNi+1aj-1ajajaj+1.aiaiai+1优先函数 利用两个函数f和g，对每个终结符，映射为两个数f()和g()，使得：若12则f(1) g(2)有的关系表不存在优先函数！对于存在优先函数的关系表，如何构造优先函数？请自学p9495优先函数的构造方法。5.3 LR 分析法 1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。
7、 LR(K)分析是指自左向右扫描和自下而上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。当前扫描到Xn+1,向前查看k个符号，来确定是把Xn+1移进栈，还是把XiXn作为句柄进行归约。1） 要归约时，则根据某产生式UXiXi+1Xn进行归约： #X1X2Xi-1UXn+1Xn+2Xn+k#例：#X1X2Xi Xn Xn+1Xn+2Xn+kXn+k+1#栈顶LR(0) 表示在每一步分析时都不用向
8、前输入符号LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。2） 要移进时，即把Xn+1进栈，并读下一符号： #X1X2XiXnXn+1 Xn+2Xn+k# 在栈中当前扫描符栈顶5.3.1 LR分析概论一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图： 输入串#aia1SpX1#S1S0XmSm总 控 程 序输出ACTION 表 GOTO 表其中S栈为状态栈 X栈为符号栈栈所有LR分析器的总控程序大同小异,只有分析表各不相同。三种不同的分析表规范
9、LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。二、LR 分析器的分析过程如下：1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。 则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查分析动作表，根据ACTIONSm, ai的指示完成相
10、应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一： S0S1 S2 Sm Sm+1 ai+1 ai+2 an # # X1 X2 Xm 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已成
11、为当前句型的句柄。所谓按第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,
12、 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:SaAcBe e1 Ab2 这里在每条产生式后加上了产生 AAb
13、3 式的序号i当进行推导时把序号 Bd4 带上，以便说明问题。对输入串abbcde e进行推导如下（最右推导）： S aAcBe e1 aAcd4e e1 aAb3cd4e e1 ab2b3cd4e e1由此可知，abbcde e是该文法的句子。最左归约为： ab2b3cd4e e1 用2式归约 aAb3cd4e e1 3 aAcd4e e1 4 aAcBe e1 1 S其中表示归约符归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前面部分；X1X2Xnp 其中Xi为文法的符号，p为第p个产生式序号。 如上例中每次归约前句型的前面部分
14、为： ab2 aAb3 aAcd4 aAcBe e1我们把规范句型的这种前端部分的串称为活前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。SaAcBee1Ab2AAb3Bd4 这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约之故。所以我们将把规范句型具有上述性质（即不含句柄之后的任何符号）的前缀称之为活前缀。 对各规范句型有前缀：ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1 ,a,aA,aAc,aAcB,aAcBe活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。活前缀定义：在规范归
15、约过程中的任何时候只要已分析过的部分即在符号栈中的符号串为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。由此可形式地定义活前缀如下： 定义 ：若S * A 是 文法G中的一个规范推导， 如果符号串是的前缀，则称是G的一个活前缀。 其中 S为文法开始符号。 RR2、LR（0）项目活前缀与句柄间的关系：（1）活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。（2）活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。（3）活前缀中全然不包含句柄的任何符号。第一种情况表明：此时某一产生式A的右部已出现在符号栈顶，因此此时相应的分析
16、动作应当是用此产生式进行归约。第二种情况表明：形如A12的产生式的 右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由推出的 符号串，即期待2 进栈以便能进行归约。故此时分析动作是“移进”当前输入符号。第三种情况则意味着：期望从余留输入串中能看到由某产生式A的右部，即所代表的符号串(即句柄) 。所以此时分析的动作也是读输入符进符号栈。在产生式的右部相应位置上加一个圆点“. .”，来指示识别位置，标明在“. .”前的部分已被识别。如上述三种情况，可分别标注为：A. .； A1 . .2 ; A. . 。右部某位置上标有圆点的产生式称为LR(0)项目(item)。不同的LR(0)项目，
17、反映了分析过程中符号栈顶的不同情况。例如：产生式SaAcBe对应有六个项目。0 S. .aAcBe1 Sa. .AcBe2 SaA. .cBe3 SaAc. .Be4 SaAcB. .e5 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
18、 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)
19、SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B dLR(0)项目分类A. 因为它表明右部符号串已出现在栈顶，此时相应的分析动作应当是按此产生式进行归约，此种项目称为归约项目。S S. . 称为接受项目。对于拓广文法而言，接受项目是唯一的。A. X 的项目（其中 可以是 ），当X为终结符时，相应的分析动作应将当前的输入符号移入栈中，故我们将此种项目称为移进项目。当X为非终结符时，期待着从余留的输入符中进行归约后而得到X，此类项目称为待约项目。把终结符和非终结符都可看成一个有限自动机的输入符号，每把一个符号进栈相当于已识别过该符号，而状态进行转换（到下
20、一状态），当识别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句柄的终态。4、构造识别活前缀的DFADFA中的中每一个状态由若干个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. .dS.S称为项目集I0的基本项目，从基本项目出发构造项目集I0的过程，可用closu
21、re(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中
22、的每个项目都是项目集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.) I
23、3 : 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)=clo
24、sure(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
25、,d； GOM的状态转换函数，即上面定义的状态转移函数GO； I0M的唯一初态； ZM的终态集， ZC为规范族中所有含有归约项目归约项目的 那些项目集。DFA:I0 : S.S S.A S.B A.aAb A.c B.aBd B.dI1 :SS.I2 :SA.I3 :SB.I4 :Aa.Ab Ba.Bd A.aAb A.c B.aBd B.dI8 :A aAb.I7 :A aA.bI9 :B aB.dI10 :B aBd.I5 :Ac.I6 :Bd.ABdbcd dacSABa4、LR(0)分析表的构造要求每一个项目集中的的诸项目不出现下列的情况：（1）移进项目和归约项目并存，即存在移进归约冲
26、突；（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 . .
27、属于Ii ,则置ACTIONi,#=acc。(4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。 如上例可构造分析表为： ACTION GOTO a b c d # S A B0 S4 S5 S6 1 2 31 Acc 2 R1 R1 R1 R1 R1 3 R2 R2 R2 R2 R2 4 S4 S5 S6 7 95 R4 R4 R4 R4 R46 R6 R6 R6 R6 R67 S88 R3 R3 R3 R3 R39 S1010 R5 R5 R5 R5 R55、LR(0)分析器的工作过程根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作：1）若ACTIONi,a=Sj
28、, 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)规范族中有冲突的项目集（状态）
29、用向前查 看一个（输入）符号的办法进行处理，以解决冲突。即为SLR(1)。假定有一个LR(0)规范族中含有如下项目集(状态)I: I=X. .b,A. ., B. .其中,为符号串，bVT,I中含有移进归约和归约归约冲突。只要FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即： FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=当状态I面临某输入符号a时，则动作为：1）若a = b,则移进。2）若a FOLLOW(A),则用产生式A归约。3）若a FOLLOW(B),则用产生式B归约。 一般地，对于LR(0)规范族的一个项目集I可能含有多个移进项目
30、和多个归约项目，我们可假设项目集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; 若
31、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(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi2、再求识别G的全部活前缀的DFA：I0: S.E E.E+T GO
32、(I0,E)=I1 E.T T.T*F GO(I0,T)=I2 T.F GO(I0,F)=I3 F.(E) GO(I0,( )=I4I1: SE. EE.+T GO(I1,+)=I6I2: ET. TT.*F GO(I2,*)=I7I3: 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)=I5I5: 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(
33、I6,i)=I5I7: TT*.F GO(I7,F)=I10 F.(E) GO(I7,( )=I4 F.i GO(I7,i )=I5I8: F(E.) GO(I8,) )=I11 EE.+T GO(I8,+)=I6I9: EE+T. TT.*F GO(I9,)=I7I10: TT*F.I11: F(E).DFAI0: S.E E . E+T E . T T . T*F T . F F .(E) F . iI2: ET . TT . *FI5: Fi .I1: SE . EE . +TI3: TF .I4: F(. E) E . E+T E . T T . T*F T . F F .(E) F
34、. iI7: TT* . F F .(E) F . iI6: EE+ . T T . T*F T . F F .(E) F . iI8: F(E .) EE . +TI11: F(E) .I9: EE+T . TT . *FI10: TT*F .i*EF(TiiiT+)*F(+F(E(F3、解决冲突I1， I2， I9中有移进-归约冲突。 FOLLOW(S)= # FOLLOW(E)= +，)，# FOLLOW(T)= +，*，)，# FOLLOW(F)= +，*，)，# 在I1中，由于FOLLOW(S)=#).而SE.是唯一的接受项目，所以当且仅当遇到句子的结束符“#”号时才被接受,又因#+
35、=，故I1中的冲突可解决。 对于I2,因FOLLOW(E)=+,),#*=,因此当面临输入符号为“+”，“ ）”或“#”号时，则用产生式ET归约。当面临输入符为“*”时，则移进；其它情况则报错。 对于I9, 当面临输入符号为“+”，“）”或“#”时，则用产生式EE+T归约；当面临输入符号为“*”时，则移进，其余情况报错。演示Figure5.5LRDFA4、构造SLR(1)分析表对于上述三个冲突项目等均可用SLR(1)方法解决冲突。因此该文法是SLR(1)文法。我们可造成其相应的SLR(1)分析表为： i + * （ ） # E T F0 S5 S4 1 2 31 S6 acc2 R2 S7 R
36、2 R23 R4 R4 R4 R44 S5 S4 8 2 35 R6 R6 R6 R66 S5 S4 9 37 S5 S4 108 S6 S11 9 R1 S7 R1 R110 R3 R3 R3 R311 R5 R5 R5 R55.3.4 规范LR分析表的构造SLR(1)方法：若状态k含有A. ，若，若aFOLLOW(A)，则用则用A归约演示演示Figure5.9LRDFA i=*i 状态状态2移进还是归约？移进还是归约？为什么为什么=FOLLOW(R)，却不能归约？却不能归约？S=L=R =*R=R输入符号为输入符号为=时，若把时，若把L归约为归约为R,必须推导出必须推导出 R=.，这这是不
37、可能的。是不可能的。可见，可见，SLR(1)方法：若状态k含有A. ，若，若aFOLLOW(A)，则用则用A归约，失于粗糙。5.3.4 规范LR分析表的构造 LR(1)项目(A. ，x)表示： 在栈顶，输入串头部可由x导出。 LR(1)状态LR(1)项目的集合。 Closure(I)=repeat for any item(A. X，z) in I for any production X for any wFIRST(z) IIX . , wuntil I does not change GO (I,X)=J for any item(A. X，z) in I add (AX . ，z) t
38、o Jreturn Closure(J) 初态Closure(S.S，#) )LR(1)项目集和GO函数的例子a aI I0 0:S :S .S，# S S .BB，# B B .aB，a/b B B .b，a/bI I1 1:S :S S . ，#I I2 2:S :S B.B，# B B .aB，# B B .b，#I I3 3: B : B a . B，a/b B B .aB，a/b B B .b，a/bI I4 4: B : B b . ，a/bI I8 8: B : B aB . ，a/bI I7 7: B : B b . ，#I I5 5: S: SBB . ，#I I6 6: B
39、 : B a . B，# B B .aB，# B B .b，#I I9 9: B : B aB . ，#S Sb bb bB Ba aB BB Ba ab bb bB Ba a(0)SS (1) BaB(2) SBB(3) Bb5.3.5 LALR分析表的构造演示Figure5_10LR1DFA(aab#和aabab#)，观察状态4和状态7的区别同心项目集：除去搜索符之外都相同的LR(1)项目集合并同心项目集不会产生新的移进-归约冲突合并同心项目集，如果没有归约-归约冲突，则为LALR(1)文法。演示Table5.6LALRDFA(aab#和aabab#)，观察LALR和LR(1)对正确的句子和有错误的输入串的分析5.3.6 二义文法的应用演示ERYIWENFAdfaI1的移进-归约冲突SLR方法可以解决I7的移进-归约冲突用优先级和结合性解决5.3.7 LR分析中的错误处理演示LRErrorHandling缺少运算量的错误i+#右括号不匹配的错误i*i)#缺少运算符的错误（ii)#缺少右括号的错误（i+i#多个错误LL(0)LL(0)二义二义文法文法非二义文法非二义文法LR(k)LR(k)LL(k)LL(k)LR(1)LR(1)LL(1)LL(1)LALR(1)LALR(1)SLRSLRLR(0)LR(0)文法体系作业：1，2，3，5，8
