编译基本知识课程教材chap06(陈火旺).ppt

《编译基本知识课程教材chap06(陈火旺).ppt》由会员分享，可在线阅读，更多相关《编译基本知识课程教材chap06(陈火旺).ppt（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 语法分析-LR分析,第六章语法分析LR分析,第六章 语法分析-LR分析,第五章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法与第5章介绍的算符优先分析一样，LR方法也是通过求句柄逐步归约进行语法分析。在运算符优先分析中，句柄是通过运算符的优先关系而求得，LR方法中句柄是通过求可归前缀而求得。,第六章 语法分析-LR分析,LR分析概述,LR（k）分析是根据当前分析栈中的符号串和向右顺序查看输入串的k(k0)个符号就可以唯一确定分析的动作是移进还是归约以及用哪个产生式归约。 从左到右扫描(L)自底向上进行规约(R) (是规范规约）,第六章 语法分析-LR分析,LR分

2、析的优缺点,1)适合文法类足够大,适用于大多数上下文无关文法 2)分析效率高 3)报错及时 4)手工实现工作量大 5)可以自动生成 美国Bell实验室推出的编译程序自动构造工具YACC：能接受一个用BNF描述的满足LALR（1）上下文无关文法并对其自动构造出LALR（1）分析器。,第六章 语法分析-LR分析,第六章 LR分析法,一、LR分析概述（基本构造原理与方法） 二、LR(0)分析 三、SLR(1)分析 四、LR(1)分析 五、LALR (1)分析,第六章 语法分析-LR分析,分析器模型,第六章 语法分析-LR分析,逻辑上说，一个LR分析器由3个部分组成： (1) 总控程序，也可以称为驱动

3、程序。对所有的LR分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 (3) 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。,2、LR分析方法的逻辑结构,第六章 语法分析-LR分析,总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。 LR分析过程的思想是在总控程序的控制下，

4、从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。,第六章 语法分析-LR分析,LR分析过程的思想： 记住历史：记住已移进和归约的整个符号串。（即栈中的内容） 立足现实：输入串读头下的符号 展望未来：根据所用的产生式推测未来可能碰到的输入符号。（也通过栈识别）,第六章 语法分析-LR分析,分析表的组成： (1) 分析动作表Action,第六章 语法分析-LR分析,表中actionSi,aj为二维数组，指出当前栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。,(2) 状态转

5、换表goto,第六章 语法分析-LR分析,表中gotoSi,xj指出栈顶状态为Si，文法符号为xj时应转到的下一状态。,第六章 语法分析-LR分析,13,13,分析表种类的不同决定使用不同的LR分析方法,a) SLR分析表(简单LR分析表),b) LR（1）分析表(规范LR分析表),构造简单,最易实现,大多数上下文无关文法都 可以构造出SLR分析表,所以具有较高的实用 价值。使用SLR分析表进行语法分析的分析器 叫SLR分析器,适用文法类最大,大多数上下文无关文法都能 构造出LR分析表,但其分析表体积太大.暂时实 用价值不大.,a) LR（0）分析表,第六章 语法分析-LR分析,14,14,c

6、) LALR分析表(超前LR分析表),这种表适用的文法类及其实现上难易在上面 两种之间,在实用上很吸引人. 使用LALR分析表进行语法分析的分析器叫LALR分析器。 例：YACC,文法规则文件 YACC源文件,YACC,某语言的 LALR分析器,第六章 语法分析-LR分析,15,15,1.四种分析表对应四类文法,几点说明,2.一个SLR文法必定是LALR文法和LR（1）文法,第六章 语法分析-LR分析,3、LR分析过程： LR分析步骤： (a) 将初始状态S0和句子的左界符#分别进分析栈。 (b) 根据栈顶状态和当前输入符号查动作表，进 行如下的工作。 移进：当前输入符号进符号栈，根据状态转换

7、表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。 归约： (1)按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态顶n个元素同时相应退栈。(2)归约后的文法符号进符号栈，(3)查,第六章 语法分析-LR分析,状态转换表，新的状态进状态栈。 (c) 接受：分析成功，终止分析。 (d) 出错：报告出错信息。 (2) 具体分析过程：,举例说明具体分析过程： 设文法为GL （假定已存在LR分析表） (1) L E,L (2) L E (3) E a (4) E b,第六章 语法分析-LR分析,LR分析算法,置ip指向输入串w的第一个符号 令S为栈顶状态 a是ip指向的符号

8、重复 begin if ACTIONS,a=Sj then begin PUSH j,a(进栈) ip 前进(指向下一输入符号) end else if ACTIONS,a=rj (第j条产生式为A),第六章 语法分析-LR分析,LR分析算法,then begin pop | 项 令当前栈顶状态为S push GOTOS,A和A(进栈) end else if ACTIONs,a=acc then return (成功） else error end.重复,第六章 语法分析-LR分析,为了介绍LR分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。,ri表示按第i个产生式进行归约,

9、Si表示把当前输入符号移进栈，且转第i个状态，即第i个状态进状态栈。,i表示转第i个状态，即第i个状态进状态栈。,空白表示分析动作出错。,第六章 语法分析-LR分析,(1) L E,L (2) L E (3) E a (4) E b,第六章 语法分析-LR分析,根据上述分析表，即可对输入串进行分析。如输入串为#a,b,a#具体分析过程如下：,第六章 语法分析-LR分析,第六章 语法分析-LR分析,自底向上分析法的关键问题是在分析过程中如何确定句柄。LR方法中的句柄是通过求可归前缀而求得。,第六章 语法分析-LR分析,例：文法GS为： S aAcBe A b A Ab B d,为产生式加序号变为

10、： S aAcBe1 A b2 A Ab3 B d4,对于输入串abbcde句子的最右推导（规范推导）如下： SaAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,活前缀与可归前缀,第六章 语法分析-LR分析,对它的逆过程最左归约(规范归约)为： ab2b3cd4e1 aAb3cd4e1 aAcd4e1 aAcBe1 S,用哪个产生式继续归约仅取决于当前句型的前部。 我们把每次采取归约动作前的符号串部分称为可归前缀。LR分析的关键就是识别何时到达可归前缀。,为产生式加序号变为： S aAcBe1 A b2 A Ab3 B d4,第六章 语法分析-LR分析,在规范句型中形成可

11、归前缀之前包括可归前缀的所有前缀称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是某规范句型的一个正确部分。,例如：有下面规范句型的前缀： ，a，ab ，a，aA，aAb ，a，aA，aAc，aAcd ，a，aA，aAc，aAcB，aAcBe,左部均为活前缀，其中，红色部分为可归前缀,第六章 语法分析-LR分析,G=(Vn,Vt,P,S),若有S A , A （ 是句柄 ） 是的前缀,则称是文法G的活前缀 活前缀是规范句型的前缀，不包含句柄之后的任何符号 是含句柄的活前缀，并且句柄

12、是的后端，则称是可归前缀或可规范前缀。 在LR分析过程中，实际上是把的前缀（即文法G的活前缀）列出放在符号栈中，一旦在栈中出现（形成可归前缀），即句柄已经形成，则用产生式A 进行归约。,活前缀的定义及在LR分析中的应用,*,R,第六章 语法分析-LR分析,LR分析法如何分析句子？ 移进归约（从左到右扫描(L)自底向上进行规约(R) ） 移进归约的关键问题是什么？ 判断符号栈顶的符号串是否构成句柄。 LR分析法如何识别句柄？ LR分析法在分析过程中并不是直接分析符号栈中的符号是否形成句柄，而是通过识别可归前缀来识别句柄。 具体地，LR分析法的分析过程可以看作识别活前缀和可归前缀的过程，只要符号栈

13、中的符号串构成活前缀，就表示已分析过的部分是正确的，继续移进；直到符号栈中的符号串构成可归前缀，则表示当前栈顶符号串已形成句柄，则进行归约。,第六章 语法分析-LR分析,如何识别活前缀和可归前缀？ 通过有限自动机来识别。 如何构造识别活前缀和可归前缀的有限自动机？ 根据文法规则 状态集合：列出所有活前缀的识别状态 符号表：所有的终结符和非终结符 状态转换函数： f(Ki ，a)= Kj 某一个活前缀的识别状态，在输入符号表中的一个符号之后，转向另一个活前缀的识别状态。 终态集：所有可归前缀的识别状态,第六章 语法分析-LR分析,LR(0)分析,构造LR分析器的关键是构造其分析表 构造LR分析表

14、的方法是: （1）根据文法构造识别规范句型活前缀的有穷自动机DFA （2）由DFA构造LR分析表,第六章 语法分析-LR分析,1. 构造DFA,(1) DFA是一个五元式,M=(S, V, GOTO, S0, Z),S：有穷状态集,在此具体情况下，S=LR(0)项目集规范族LR(0)。 项目集规范族：其元素是由项目所构成的集合.,V：文法字汇表 VnVt,S0：初始状态,GOTO:状态转移函数 GOTOSi,X=Sj Si ,SjS Si ,Sj为项目集合 XVnVt 表示当前状态Si面临文法符号为X时，应将状态转移到 Sj,Z：终态集合,第六章 语法分析-LR分析,1） 确定S集合，即LR（

15、0）项目集规范族，同时确定S0,2） 确定状态转移函数GOTO,构造DFA方法：,第六章 语法分析-LR分析,LR(0)分析,确定状态集合 每一个状态对应文法中某一个产生式规则的某一个项目 每一个产生式规则的每一个项目代表一个活前缀的识别状态。 产生式规则的项目？,第六章 语法分析-LR分析,活前缀与句柄的关系：,GS: 若S = A = r是的前缀，则 称r是G的一个活前缀 1.活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶 2.活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 3. 活前缀不含有句柄的任何符号，此时期望A的右部所推出

16、的符号串,R,第六章 语法分析-LR分析,活前缀,与句柄 ,与 LR(0)项目,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A刻划产生式A的 右部已出现在栈顶 A12 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串 对于A的LR(0)项目只有A,第六章 语法分析-LR分析,项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目。,例:产生式:AXYZ 项 目: A.XYZ AX.YZ AXY.Z AXYZ. 产生式

17、:A 项 目: A.,项目的直观意义:指明在分析过程中，我们看到产生式多大一部分。,其中， 、 X、XY、 XYZ为活前缀，XYZ是可归前缀。,第六章 语法分析-LR分析,38,38,. 将文法扩充,构造LR(0)文法的方法(三步),目的：使构造出来的分析表只有一个接受状态,这是 为了实现的方便。,方法：修改文法，使识别符号的规则只有一条,L(G(E)=L(GE),第六章 语法分析-LR分析,39,39,. 根据文法列出所有的项目,例如：产生式SaAcBe对应有6个项目。 0 SaAcBe 1 SaAcBe 2 SaAcBe 3 SaAcBe 4 SaAcBe 5 SaAcBe ,第六章 语法

18、分析-LR分析,40,40,. 将有关项目组合成集合，即DFA中的状态； 所有状态再组合成一个集合，即LR（0）项目集规范族,我们通过一个具体例子来说明LR(0)的构造以及DFA 的构造方法,例：GE EE+T|T TT*F|F F(E)|i,第六章 语法分析-LR分析,41,41,例:GE EE+T|T TT*F|F F(E)|i,(0) EE (4) TF EE+T (5) F(E) ET (6) Fi TT*F,第六章 语法分析-LR分析,42,42,为实现这一步，先定义： 项目集闭包closure 状态转移函数GOTO,例:GE 令I=E.E closure(I)=E.E, E.E+T

19、, E.T, T.T*F, T.F, F.(E), F.i ,第六章 语法分析-LR分析,43,43,A.项目集闭包closure的定义和计算: 令I是文法G的任一项目集合，定义closure(I)为项目集合I的闭包，可用一个过程来定义并计算closure(I)。 Procedure closure(I); begin 将属于I的项目加入closure(I); repeat for closure(I)中的每个项目A.B(BVn) do 将B.r(rV* )加入closure(I) until closure(I)不再增大 end,例:GE 令I=E.E closure(I)=E.E, E.E

20、+T, E.T, T.T*F, T.F, F.(E), F.i ,第六章 语法分析-LR分析,44,44,所以,GOTO(I,X)=closure(J)的直观意义是: 它规定了识别文法规范句型活前缀的DFA从状态I(项目集)出发,经过X弧所应该到达的状态(项目集合),第六章 语法分析-LR分析,45,45,例. I=EE. , EE.+T 求GOTO(I , + )=? GOTO(I , +)=closure(J) J=EE+.T GOTO(I , +)=EE+.T , T.T*F , T.F , F.(E) , F.i ,例：GE EE+T|T TT*F|F F(E)|i,第六章 语法分析-

21、LR分析,46,46,LR(0)项目集规范族的构造算法:,GLR(0) Procedure ITEMSETS(G); begin LR(0):=closure(E.E); repeat for LR(0)中的每个项目集I和G的每个符号X do if GOTO(I , X)非空,且不属于LR(0) then 把GOTO(I , X)放入LR(0)中 until LR(0)不再增大 end,第六章 语法分析-LR分析,例.求GE的LR(0) V=E, T, F, I, +, *, (, ),(0) EE (4) TF EE+T (5) F(E) ET (6) Fi TT*F,第六章 语法分析-LR

22、分析,I2:ET. GOTO(I0,T)=closure(ET. TT.*F)= I2 TT.*F I3:TF. GOTO(I0,F)=closure(TF.)= I3 I4:F(.E) GOTO(I0,()=closure(F(.E)= I4 E.E+T E .T T.T*F T.F F.(E) F.i I5:Fi. GOTO(I0,i)=closure(Fi.)= I5 GOTO(I0,*)= GOTO(I0,+)= GOTO(I0,)=,I0: E.E E.E+T E.T T.T*F T.F F.(E) F.i,第六章 语法分析-LR分析,I6:EE+.T GOTO(I1,+)=clos

23、ure(EE+.T)= I6 T.T*F GOTO(I1,其他符号)为空 T.F F.(E) F.i I7:TT*.F GOTO(I2,*)=closure(TT*.F)= I7 F.(E) GOTO(I2,其他符号)为空 F.i GOTO(I3,其他符号)为空,I1: EE. EE.+T,I2: ET. TT.*F,第六章 语法分析-LR分析,I4:F(.E) E.E+T E .T T.T*F T.F F.(E) F.i,第六章 语法分析-LR分析,I10:TT*F. GOTO(I7,T)=closure(TT*F .)= I10 GOTO(I7,()= I4 GOTO(I7,i)= I5

24、I11:F(E). GOTO(I8,)=closure(F(E) .)= I11 GOTO(I7,()= I4 GOTO(I7,i)= I5 求完所有Ii的后继 GOTO(I8,+)= I6 GOTO(I9,*)= I7 GOTO(I10,所有符号)=, GOTO(I11,所有符号)=,第六章 语法分析-LR分析,（3）构造DFA,M=(S, V, GOTO, S0, Z) S =I0, I1, I2, , I11=LR(0) V =+, *, i, (, ), E, T, F GOTO(Im , X)= Im S0=I0 Z=S-I0=I1, I2, , I11,M的图解表示如下:,第六章

25、语法分析-LR分析,53,53,I0,I5,I2,I4,I3,I1,I11,I8,I6,I10,I7,I9,start,E,+,+,i,F,(,T,T,F,(,i,F,(,i,E,(,*,*,),+,i,F,第六章 语法分析-LR分析,例：设拓广文法GS的产生式为： S S S aA | bB A cA | d B cB | d,第六章 语法分析-LR分析,Ac.A A.cA A.d I4,Sa.A A.cA A.d I2,Sb.B B.cB B.d I3,Bc.B B.cB B.d I5,S.S S.aA S.bB I0,start,SS. I1,AcA. I8,SaA. I6,Ad. I1

26、0,A,d,d,A,c,a,b,S,SbB. I7,BcB. I6,Bd. I11,B,d,d,B,c,c,c,识别文法 活前缀的DFA,第六章 语法分析-LR分析,56,56,关于自动机的说明:,1,除I0以外,其余状态都是活前缀的识别状态,从I0到每一状态 的每条路径都识别和接受一个规范句型的活前缀,如对文法句子i+i*i 进行规范规约， 所得到的规范句型的活前缀都可 以由该自动机识别,如: I0I3 F(+i*i) I0I2 T(+i*i) I0I1 识别规范句型的活前缀E(+i*i) I0I6 识别规范句型的活前缀E+(i*i) I0I7 识别规范句型的活前缀E+T*(i) I0I9

27、识别规范句型的活前缀E+T(*i) I0I10 识别规范句型的活前缀E+T*F,E,E,T,+,T,8,5,4,3,2,1,(0) EE (3) TT*F (6) Fi EE+T (4) TF ET (5) F(E),6,第六章 语法分析-LR分析,注意：项目中圆点前的符号串成为活前缀的后缀,* *,第六章 语法分析-LR分析,注意：经移进或规约后,在栈内仍是规范句型的活前缀,第六章 语法分析-LR分析,4,DFA中的状态,既代表了分析历史又提供了展望信息,每条规范句型的活前缀都代表了一个确定的 的规范规约过程,故有状态可以代表分析历史.,由于状态中的项目都是有效项目,所以提供了 下一步可能采

28、取的动作.,历史+展望+实现 句柄,第六章 语法分析-LR分析,项目集的相容性： 定义 满足下列两个条件的项目集称为相容的项目集。 无移进项目和归约项目并存。 无多个归约项目并存。 例如：若有项目集A ，B 此时栈顶为，根据项目集无法确定是移进还是归约。项目集是不相容的。 对一个文法的LR(0)项目集规范族不存在移进归约或归约归约冲突时，称该文法为LR(0)文法。,第六章 语法分析-LR分析,LR(0)分析表的构造,LR（0）分析表由两部分组成： 动作表表示当前状态下面临输入符号应做的动作是移进、归约、接受或出错； 状态转换表表示在当前状态下面临文法符号时应转向的下一个状态。,第六章 语法分析

29、-LR分析,(2) LR(0)分析表的构造 构造原则： 设有文法GS，则LR(0)分析表的构造规则为： 对于A XSi，GOTO(Si,X)=Sj 若X Vt，则置actionSi,X=Sj 若X Vn，则置gotoSi,X=j 对于A Si，若A 是文法的第j个产生式，则对所有的xVt，均置actionSi,x=rj 若S Si，则置actionSi,#=acc 其他均置出错。,第六章 语法分析-LR分析,例子：文法G为： (0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d 该文法的状态描述序列见下表：,第六章 语法分析-L

30、R分析,第六章 语法分析-LR分析,第六章 语法分析-LR分析,根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下：,第六章 语法分析-LR分析,第六章 语法分析-LR分析,对于输入串#bccd#的分析过程如下：,第六章 语法分析-LR分析,三、SLR(1)分析表的构造,1、问题的提出： 只有当一个文法G是LR(0)文法，即G的每一个状态项目集相容时，才能构造出LR(0)分析表； 由于大多数适用的程序设计语言的文法不能满足LR(0) 文法的条件，因此本节将介绍对于LR(0)规范族中冲突的项目集（状态）用向前查看一个符号的办法进得处理，以解决冲突。 因为只对有冲突的状态才向前查看一个符

31、号，以确定做那种动作，因而称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。,第六章 语法分析-LR分析,文法G为： (0) S S S rD D D,i D i,状态描述序列见下表：,第六章 语法分析-LR分析,第六章 语法分析-LR分析,分析每个状态包含的项目集，不难发现在状态S3中含项目： S rD 为归约项目 D D , 为移进项目 也就是按SrD 项目的动作认为用SrD产生式进行归约的句柄已形成，不管当前的输入符号是什么，都应把rD归约成S。但是按DD ,i 项目当面临输入符为,号时，应将,号移入符号栈，状态转向S5。显然该文法不是LR(0)文法，S3项目集不相容。也可在构

32、造它的LR(0)分析表时发现这个问题，如下表所示。,第六章 语法分析-LR分析,第六章 语法分析-LR分析,如何解决这种移进-归约冲突？ LR（0）在归约时不向前看输入符号； 在LR（0）基础上，如果出现不相容的项目（存在移进-归约冲突或归约-归约冲突）则LR（k）方法通过向前看k个输入符号来解决冲突（利用上下文信息来消除当前的歧义） SLR（1）： （1）只在项目出现冲突时S，（2）才向前看1个输入符号LR（1）；,第六章 语法分析-LR分析,SLR(1)分析表的构造方法思想,在出现移进-归约冲突或归约-归约冲突时，通过观察归约成的非终结符的后跟符号集合，来区分移进-归约动作或不同的归约动作

33、。 上例冲突的解决 归约还是移进？ 如果归约，那么要构成一个合法的句子，该非终结符后都可以跟哪些终结符？ 而输入符号串中的当前符号是什么？ 是否匹配？ 匹配：则归约；不匹配：则不归约。,第六章 语法分析-LR分析,随符集合的定义：,设G=（VT，VN，P，S）是上下文无关文法，AVN，S是开始符号， Follow(A)=a | S uA且aVT，a First()，uVT*，V+。针对非终结符 若S uA，且 ，则#Follow(A) （#表示输入串的结束符，或句子括号）,可写成为： Follow(A)a|SAa， aVT 若SA，则#Follow(A)。,*,*,*,*,*,Follow(A

34、)是所有句型中出现在紧接A之后的终结符或“#”。,第六章 语法分析-LR分析,2、SLR(1)分析表的构造方法思想 在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。,第六章 语法分析-LR分析,假定一个LR(0)规范族中含有如下的项目集（状态）Si Si= X b, A , B 也就是在该项目集中含有移进-归约冲突和归约-归约冲突。其中, ,为文法符号串，b为终结符。方法如下：,对于归约项目A ，B 分别求Follow(A)和Follow(B )， Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。 如果满足如下

35、条件：,第六章 语法分析-LR分析,FOLLOW(A)FOLLOW(B) FOLLOW(A)b FOLLOW(B)b 那么，当在状态Si时面临某输入符号为a时，则构造分析表时用以下方法即可解决冲突动作。 (1) 若a=b，则移进。 (2) 若aFollow(A),则用产生式A 进行归约。 (3) 若aFollow(B),则用产生式B 进行归约。 (4) 此外，报错。,第六章 语法分析-LR分析,如果对于一个文法的LR（0）项目集规范族所含有的动作冲突都能用以上方法来解决，则称该文法为SLR（1）文法。,第六章 语法分析-LR分析,3、SLR(1)分析表的构造,例如文法： (0) E E (1)

36、 EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,第六章 语法分析-LR分析,状态描述序列如下：,第六章 语法分析-LR分析,第六章 语法分析-LR分析,第六章 语法分析-LR分析,由上图可见，S1、S2和S9的项目集均不相容，其有移进项目和归约项目并存，构造LR(0)分析表如下：,第六章 语法分析-LR分析,E E,E E+T,E T,T T*F,T F,F (E),F id,E,E E E E+T,T,E T T T*F,(,F ( E) E E+T E T T T*F T F F (E) F id,I0,I1,I2,I6,F,T F,I3,F id

37、,id,I5,T,I2,F,I3,id,I5,(,E E+ T T T*F T F F (E) F id,+,*,T T* F F (E) F id,I7,F (E ) E E+T,E,I8,T,E E+ T T T*F,I9,F,I3,id,I5,(,F,T T* F ,I10,id,I4,(,I4,*,I7,),F (E) ,+,I6,I11,第六章 语法分析-LR分析,I1:EE I2: E T I9: E E+T E E+T T T *F T T *F I=X b , A , B 若bFOLLOW(A) FOLLOW(B)= 则，面对当前读入符号a，状态I的解决方法： 1. 若a=b,

38、则移进。 2. 若a FOLLOW(A),则用A 进行归约。 3. 若a FOLLOW(B),则用B 进行归约。 4. 此外，报错。 这种解决方法是比较简单的，因此称作SLR 分析，由此构造的分析表，称作SLR分析表。,第六章 语法分析-LR分析,第六章 语法分析-LR分析,从上表也可见在S, S, S中存在移进-归约冲突 。这个表达式不是LR(0)文法，也就不能构造LR(0)分析表，现在分别考查这三个项目（状态）中的冲突是否能用SLR(1)方法解决。 对于S1：SE , EE T 由于Follow(S)=，而S E是唯一的接受项目，所以当且仅当遇到句子的结束符“”号时才被接受。又因=，因此S

39、1中的冲突可解决。 对于S2 : S2= E T , TT *F 计算Follow(E) = #, +, ) ,第六章 语法分析-LR分析,所以Follow(E)*= 因此面临输入符为+，)或号时，则用产生式ET进行归约。 当面临输入符为*号时，则移进, 其它情况则报错。 对于S9 : S9= E E+T , TT *F 计算Follow(E) = #, +, ) , 所以Follow(E)*= 因此面临输入符为+，)或号时，则用产生式EE+T进行归约。 当面临输入符为*号时，则移进。 其它情况则报错。,第六章 语法分析-LR分析,由以上考查，该文法在S，S，S三个项目集(状态)中存在的移进-

40、归约冲突都可以用SLR()方法解决，因此该文法是SLR()文法。我们可构造其相应的SLR()分析表。 SLR(1)分析表的构造与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。 进一步分析我们可以发现如下事实：例如在状态S3中，只有一个归约项目TF ，按照SLR(1)方法，在该项目中没有冲突，所以保持原来LR(0)的处理方法，不论当前面临的输入符号是什么都将用产生式TF进行归约。,第六章 语法分析-LR分析,但是很显然T的后跟符没有（符号，如果当前面临输入符是（，也进行归约显然是错误的。因此我们对所有归约项目都采取SLR(1)的思想，即对所有非终结符都求出其Follow集合，这

41、样凡是归约项目仅对面临输入符号包含在该归约项目左部非终结符的Follow集合中，才采取用该产生式归约的动作。 对于这样构造的SLR(1)分析表我们称它为改进的SLR(1)分析表。 改进的SLR(1)分析表的构造方法如下：,第六章 语法分析-LR分析,对于A X，GO Si , X Sj ，若X Vi ，则置actoinSi , X=Sj 若X Vn ，则置gotoSi , X=j (2) 对于归约项目A Si , 若A为文法的第j个产生式，则对任何输入符号a，若aFollow(A)，则置actionSi , a=rj (3) 若S Si，则置actionSi , #=acc (4) 其它情况均

42、置出错。 改进的SLR(1)分析表如下：,第六章 语法分析-LR分析,第六章 语法分析-LR分析,四、LR(1)分析表的构造,1、问题的提出 在SLR(1)方法中，对于某状态Si，其项目集若不相容时，可根据SLR(1)分析表的构造规则来解决冲突分析动作，但如果不相容的项目集中的向前看集合及其有关集合相交时，就不可能通过SLR(1)分析表构造规则来构造SLR(1)分析表。这时就用LR(1)分析。,第六章 语法分析-LR分析,SLR,例：文法G: （0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae,第六章 语法分析-LR分析,I0: S S S aAd

43、 S bAc S aec S bed,文法G：(0) S S(1) S aAd (2) S bAc(3) S aec(4) S bed(5) A e,I1: S S ,I2: S a Ad S a ec A e,I3: S b Ac S b ed A e,I4: S aA d,I5: S ae c A e ,I6: S bA c,I7: S be d A e ,I8: S aAd ,I9: S ae c ,I10: S bAc ,I11: S bed ,查看I5 ，I7中的冲突，体会LR(1)如何解决,e,a,第六章 语法分析-LR分析,I5: S aec A e S=S=aAd=aed S=

44、S=aec 活前缀ae遇到c应移进；遇到d应归约 I7: S bed A e S=S=bAc=bec S=S=bed 活前缀be遇到d应移进；遇到c应归约 并不是Follow（A）的每个元素在含A的所有句型中都会在A的后面出现,R,R,R,R,R,R,R,R,R,R,文法G：(0) S S(1) S aAd (2) S bAc(3) S aec(4) S bed(5) A e,第六章 语法分析-LR分析,LR（1）方法,在每个项目中增加向前搜索符 若项目集AB属于I时，则B也属于I 把FIRST()作为用产生式归约的搜索符（称为向前搜索符），作为用产生式B归约时查看的符号集合（用以代替SLR(

45、1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)方法,第六章 语法分析-LR分析,LR(1)项目集族的构造：针对初始项目SS,#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族。 1）构造LR（1）项目集的闭包函数a)I的项目都在CLOSURE(I)中b)若A B，a属于CLOSURE(I)， B 是文法的产生式，V*，bFIRST(a),则B ,b也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大 2)转换函数的构造GOTO（I，X）= CLOSURE（J）其中：I为LR(1)的项目集，X为一文法符号 J=任何形如

46、AX ,a的项目| A X ,a属于I,第六章 语法分析-LR分析,一个文法符号串的first集合计算方法：,如果文法符号串V*, =X1X2Xn, 1、当X1，则first()=first(X1) 2、当对任何j（1ji-1，2 i n），first(Xj) 则first()=(first(X1)-) (first(X2)-) (first(Xi-1)-) first(Xi) 3、当first(Xj)都含有时(1 j n)，则first()=first(X1) first(X2) first(Xj) ,*,第六章 语法分析-LR分析,I0: S S, # S aAd, # S bAc, #

47、S aec, # S bed, #,文法G：(0) S S(1) S aAd (2) S bAc(3) S aec(4) S bed(5) A e,I1: S S , #,I2: S a Ad, # S a ec, # A e, d,I3: S b Ac, # S b ed, # A e, c,I4: S aA d, #,I5: S ae c, # A e , d,I6: S bA c, #,I7: S be d, # A e , c,I8: S aAd , #,I9: S ae c , #,I10: S bAc , #,I11: S bed , #,查看I5 ，I7中的冲突，体会LR(1)如何解决,S,a,A,e,A,e,d,c,d,c,b,第六章 语法分析-LR分析,LR(1)分析表的构造,LR(1)分析表的构造与LR(0)分析表的构造在形式上基本相同，不同之处在于：归约项目的归约动作取决于该归约项目的向前搜索符号集。 1) 若项目A a,b属于Ik，且转换函数GO(Ik,a)= Ij ，当a为终结符时，则置ACT