第六章 LR分析.ppt

1、第六章LR 分析,迄今为止我们所学的分析方法对文法都有一定的要求,即有局限性; 1965年D.Knuth提出了分析效率极高的LR(k)分析技术; LR分析: 自左至右扫描的自底向上的分析; 在分析的每一步,只须根据分析栈中的已移进的和已归约出的符号,并至多向前扫描k个字符就能确定应采取什么分析动作(移进、归约、接受、报错); LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法,LR(K)分析法的含义 L自左向右扫描输入串(源程序) R分析过程构成最右推导的逆序 K每次根据当前的输入符号最多向前(右)查看K个符号就可以唯一地确定下一

2、步动作是移进还是归约以及用哪条规则进行归约，因而也能唯一地确定句柄,LR文法,LR文法 一个文法G若能构造一张LR分析表，并使它的每个入口(表中的元素)都是唯一确定的，则称文法G为LR文法。 LR(K)文法 一个LR文法G，若每步最多向前查看K个输入符号就能决定当前分析动作，从而按LR方法进行分析，则称文法G为LR(K)文法。,3,LR分析的特点：,是规范归约 适用范围广，适用于大多数上下文无关文法描述的语言 分析速度快，能准确定位错误 缺点：LR分析器的构造工作量大,4,LR分析法的概念,5,LR分析器的逻辑结构 在逻辑上，一个LR分析器的结构由一个输入符号串，一个下推分析栈，以及一个总控程

3、序和分析表组成。,LR分析器在总控程序的控制下自左至右扫视输入串中的各个符号 ，并根据当前分析栈中所存放之文法符号的状况 及正扫描之输入符号，按分析表的指示完成相应的分析动作。,LR分析器的逻辑结构,LR分析器组成： 分析表 总控程序 下推分析栈,a1a2an#,总控程序,输入串(源程序),分 析 栈,输出分 析结果,6,分析栈,符号栈 符号栈内存放分析过程中移进或归约的符号。 状态栈 状态栈存放的是状态(标记)，状态Si概括了栈中位于Si下面的全部信息，也就是记录分析过程从开始的某一归约阶段的整个分析历史或预测扫描可能遇到的分析符号。分析开始时，分析栈压入初始状态S0和输入符号#，分析器处于

4、初始状态S0。S0刻画了当前栈内仅有一个符号#的事实并预示将扫描的输入字符应刚好是可作为句子首符号的那些符号。,7,分析表,动作表(ACTION) 状态转换表(GOTO),8,ACTION表,ACTION表的结构如下：,9,分析动作,ACTION表中的元素ACTIONSm, ai是一个动作，表示当前状态Sm面临输入符号ai时所完成的分析动作。分析动作可分四类： 移进 归约 接受 出错,10,移进,此时ACTIONSm, ai=Sj。分析动作为移进时，表示句柄尚未在分析栈的栈顶形成，正期待继续移进符号，以形成句柄。 ACTIONSm, ai=Sj表示当前栈顶状态为Sm，输入符号为ai，应将输入符

5、号ai移进分析栈的符号栈栈顶，同时将Sj移进分析栈的状态栈栈顶。,11,归约,此时ACTIONSm, ai=rj。其中rj表示按文法的第j条规则(产生式)进行归约。设第j条规则为： AXm-r+1Xm-r+2 Xm 分析动作为归约时，表明当前分析栈顶部的符号串Xm-r+1Xm-r+2 Xm已是当前句型的句柄，需要立即进行归约。具体是将分析栈自顶向下的r个符号(包括状态栈内相应的状态)弹出，将A压入符号栈内，此时分析栈格局为：,12,再以(Sm-r,A)查GOTO表，若GOTOSm-r, A=Sk， 把Sk压入状态栈。,a1a2ai an#,输入串,13,接受,此时ACTIONSm, ai=ac

6、c。分析动作接受表示当前输入的符号串分析成功，终止分析器工作。,14,出错,此时ACTIONSm, ai=error(error表示出错，在此用空白来表示)。分析动作为出错，表示当前输入的符号串中有语法错误，调用相应的出错处理程序。,15,GOTO表,GOTO表的结构如下：,16,状态转换,GOTO表中的元素GOTOSm, Xi是一个状态，表示当前状态Sm面临输入符号Xi时需转移的下一个状态。,17,18,18,11(S11),10(S10),7,9(S9),11,6,8(S8),4,5,10,7(S7),4,5,3,9,6(S6),5(S5),4,5,3,2,8,4(S4),3(S3),7,

7、2(S2),6,1(S1),4,5,3,2,1,0(S0),),(,*,+,i,F,T,E,GOTO表 ACTION表,文法符号,状态,状态,若移入：i为状态 若规约：i为产生式编号,文法GE ：(1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,Vn,Vt,19,19,例：文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,其LR分析表如下页,例,ACTION表 GOTO表,文法GE ：(1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F

8、:=(E) (6)F:=i,20,总控程序,总控程序是LR分析的实现算法。描述如下： 初始化，将初始状态S0及输入符号串的左界符#推入分析栈； 从输入串中读入当前的输入符号ai，根据当前状态栈栈顶状态Sm与输入符号ai查ACTION表： 若ACTIONSm, ai=Sj，完成移进动作； 若ACTIONSm, ai=rj，以文法的第j条规则完成归约动作； 若ACTIONSm, ai=acc，分析成功，结束； 若ACTIONSm, ai=error，出错处理。 重复2)直到出错或接受为止。,21,接受时分析栈的格局,a1a2ai an#,输入串,22,LR分析器在总控程序的控制下自左至右扫视输入串

9、中的各个符号，并根据当前分析栈中所存放之文法符号的状况及正扫描之输入符号，按分析表的指示完成相应的分析动作。,LR的工作过程：,第一步 分析开始时，首先将初始状态SO及句子左界符#推入分析栈中。,LR分析过程,（3）若ACTIONSm，ai=“接受”，则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。,（4）若ACTIONSm，ai=ERROR，则表明当前的输入串中有语法错误，也应中止分析器的工作。,其中，Z为文法的开始符号，S则为使ACTIONS，#=“接受”的唯一状态（即接受状态）。 对任何不同的LR（1）分析表都适用。,LR分析实例,设已给文法GL: 1. LE,L 2. LE

10、3. Ea 4. Eb 文法相应的分析表为,符号串“a,b,a”的LR分析过程,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,对输入串#abbcde#的LR分析过程,34,34,分析过程 ： i*i+i,步骤状态栈符号输入串动作,10i*i+i#初始化,20i5i*i+i#S,30F3F*i+i#R6,40T2T*i+i#R4,50T2*7T* i+i#S,60T2*7i5T*i +i#S,70T2*7F10T*F +i#R6,文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,110E1+6i

11、5#E+i #S,120E1+6F3#E+F #R6,130E1+6T9#E+T #R4,140E1#E #R1,15 #E Accept,90E1#E +i#R2,100E1+6#E+ i#S,80T2#T +i#R3,文法GE (1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i,分析过程 ： i*i+i,35,36,36,由分析过程可以看到:,(1) 每次规约总是规约当前句型的句柄，是规范归约，可以看到语法树(算符优先是规约最左素短语),(2) 分析的每一步栈内符号串与输入串的剩余部分构成规范句型.,可归前缀与活前缀,规范句型的活前

12、缀,38,38,规范句型：通过规范规约得到的句型.,规范句型前缀：将输入串的剩余部分与其连结起来就构成了规范句型. 如： x1x2. xmai . an为规范句型 x1x2. xm 为规范句型前缀 ai . an为输入串的剩余部分,活前缀：若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀. 在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。,规范句型的活前缀:,对于句型t， 表示句柄,如果=u1u2ur 那么符号串u1u2ui(1ir)即是句型t的活前缀,例：有文法 ET | E+

13、T | E-T Ti | (E) 拓广文法G：SE# ET | E+T | E-T Ti | (E) 已知句型E-(i) #，求活前缀?,E, E-, E-(, E-(i 是句型E-(i+i)# 的活前缀。,39,如何构造识别活前缀的有限自动机,已经有了活前缀如何构造有限自动机? 活前缀及其可归前缀的构造方法？,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,对输入串abbcde#的LR分析过程,状态栈,ACTION,GOTO,A,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进0S2,2） #a bbcde# 移进02 S4,4） #aA bcde#

14、移进023 S6,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab)024r23,5） #aAb cde# 归约(AAb)0236 r3 3,状态栈,ACTION,GOTO,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,*,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,对输入串abbcde#的LR分析过程,3） #ab bcde# 归

15、约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,状态栈,ACTION,GOTO,*,0,1,4,2,3,5,7,6,9,S,a,b,A,b,c,B,e,d,8,8） #aAcd e# 归约(B d) 02358 r4 7,一个LR分析器的工作过程，实质上就是一个逐步产生所给文法的规范句型的活前缀的过程。 在分析过程中，分析栈中的符号串始终是活前缀，然后通过对余留符号串的继续扫描，逐步在分析栈中构成活前缀，当栈顶形成句柄时，立即进行归约。 分析过程中的句柄获得确定和归约是通过寻找规范句型的活前缀来实现的。,活前缀与句柄间的关系不外下述三种情况： （1）

16、活前缀中已含有句柄的全部符号（句柄的符号即为其最右符号）。 （2）活前缀中含句柄的一部分符号（句柄开头的 若干符号与活前缀最右的若干个符号一致）。 （3）活前缀中全然不包含句柄的任何符号 。,LR（0）项目集规范族构造,第一种情况表明，此时某一产生式A的右部符号串已出现在栈顶，因此相应的分析动作应当是用此产生式进行归约。,第二种情况意味着形如A12的产生式的右部子串1已出现在栈顶，正期待着从余留输入串中看到能由2推出的符号串。 第三种情况则意味着，期望从余留输入串中能看到由某一产生式A右部，即所推出的符号串。,A A12 A,我们把右部某位置上标有圆点的产生式称为相应文法的一个LR（0）项目，

17、特别对形如A的产生式，A。,LR（0）项目：在每个产生式的右部适当位置添加一个圆点构成项目。,LR（0）项目,例如：产生式S aAcBe对应有6个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 有限自动机的每一个状态由一个项目构成。,项目的直观意义:指明在分过程中的某一时刻已经归约的部分和等待归约部分。,LR(0)项目的分类,归约项目：形如A，表示当前栈顶的内容已构成所期望的句柄，应按A进行归约。 接受项目：形如SS，其中S是文法唯一的开始符号。表示句柄已在栈顶形成，用SS进行归约，整个分析成功。 移进项目：

18、形如Aa(aVT)，表示栈内仅是句柄的一部分，为了构成活前缀，应先把a移进分析栈。 待约项目：形如AB(BVN)，表示栈内仅是句柄的一部分，为了构成活前缀，应先把当前输入符号串中相应的内容归约到B。,60,根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：,文法G：S EE T + E E TT int * T T int T（E）,初态：1 句柄识别态：2、6、8、12、14、18 句子识别态：2,文法的全部LR（0）项目将是构造识别它的所有活前缀的有限自动机的基础。,构造文法G的LR(0)项目集规范族的方法一识别文法G的活前缀的DFA项目集的全体称为文法的LR(0)项目集规

19、范族。可以进而构造出action和goto表。,基本思想 首先构造出识别文法活前缀的NFA，再将NFA确定化和最小化，最终得到所需的DFA。,活前缀：若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀. 在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。,63,由文法的LR(0)项目构造识别文法所有活前缀的NFA的步骤为： 令所有LR(0)项目对应NFA的一个状态，归约项目对应为终态； 令含有文法开始符号的规则(设为SA)的第一个LR(0)项目(SA)为NFA的初态； 若状态i和j中

20、的LR(0)项目出自同一条规则，只是圆点位置相差一个符号，即 i为XX1X2Xi-1XiXn j为XX1X2XiXi+1Xn 则从状态i到状态j，引一条标记为Xi的箭弧； 若状态i为待约项目(设为XA)，则从状i态引箭弧到所有A的状态并标记为。,64,例,设文法GA： AaA Ab 构造识别文法G的所有活前缀的NFA。 先对GA进行拓广，拓广后的文法GS： SA AaA Ab,65,GS的LR(0)项目,SA AaA AaA Ab Ab SA AaA,66,识别文法GS的活前缀的NFA,67,命名状态的识别活前缀的NFA,68,识别文法GS的活前缀的DFA,69,上图中每个状态都是由一组的项目

21、组成的集合，称为项目集。 通过列出拓广文法的所有项目，进而构造识别活前缀的NFA，再确定化为DFA的方法，工作量较大，不实用。 实用的方法是直接构造以项目集为状态的识别活前缀的DFA。,70,文法G：S EE T + E E TT int * T T int T（E）,构成识别一个文法活前缀的DFA项目集（状态）的全体称为这个文法的LR（0）项目集规范族。,LR（0）项目集规范族构造方法二,NFA确定化为DFA的工作量较大，我们考虑直接构造出项目集作为DFA的状态，就可直接构造DFA。 通过闭包函数（CLOSURE）来求DFA一个 状态的项目集。,若文法G已拓广为G，而S为文法G的开始符号，拓

22、广后增加产生式SS。,对文法进行拓广的目的是为了对某些右部含有开始符号的文法，在归约过程中能分清是否已归约到文法最初开始符，还是在文法右部出现的开始符号 ，拓广文法的开始符号S只在左部出现，这样确保了不会混淆。,若状态中包含形如AB的项目，则形如B的项目也在此状态内 S .E E .T E .T + E T .（E） T .int * T T .int,如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE（I）如下： a）I的项目都在CLOSURE（I）中。 b）若AB属于CLOSURE（I），则每一形如B的项目也属于CLOSURE（I）。 c）重复b）直到CLOSURE（I）不再扩大

23、。,的闭包CLOSURE（I）,由此，我们可以很容易构造出初态的闭包，即SS属于I，再按上述三点求其闭包。,有了初态的项目集，其它状态的项目集如何求出？回顾在构造识别活前缀的NFA时除了箭弧 上标记为的外，其两个相邻状态对应的项目是出自同一个产生式，只是圆点的位置相差。,定义转换函数如下：GOTO(I，X)=CLOSURE(J)其中：为包含某一项目集的状态，X为一文法符号，J=任何形如AX的项目|AX属于I。,转换函数,圆点不在产生式右部最左边的项目称为核，唯一的例外是S S。因此用GOTO（I，X）转换函数得到的J为转向后状态所含项目集的核，使用闭包函数（CLOSURE）和转向函数（GOTO

24、（I，X）构造文法G的LR（0）的项目集规范族，步骤如下：,LR（0）项目集规范族构造,a）置项目S S为初态集的核，然后对核求闭包CLOSURE（S S）得到初态的项目集。,b）对初态集或其它所构造的项目集应用转换函数GOTO（I，X）= CLOSURE（J）求出新状态J的项目集。 C）重复b）直到不出现新的项目集为止。,LR（0）项目集规范族构造,0：S EE aAE bB,I2=GO（I0，a）=CLOSURE（Ea A） =Ea A，A cA，A d I3=GO（I0，b）=CLOSURE（Eb B） =Eb B，B cB，B d I4=GO（I2，c）=CLOSURE（Ac A） =

25、Ac A，A cA，A d I5=GO（I3，c）=CLOSURE（ Bc B） =Bc B，B cB，B d,I1=GO（I0，E）=CLOSURE（SE ） =SE ,求闭包的算法,I6=GO（I4，c）=CLOSURE（Ac A） =I4,I6=G0（I2，A）=CLOSURE（EaA ） =Ea A I7=G0（I3，B）=CLOSURE（EbB ） =EbB I8=G0（I4，A）=CLOSURE（AcA ） =AcA I9=G0（I5，c）=CLOSURE（Bc B） =I5 I9=G0（I5，B）=CLOSURE（BcB ） =BcB ,I10=G0（I2，d）=CLOSURE（

26、Ad ）=Ad ,I11=G0（I4，d）=CLOSURE（Ad ）=Ad =I10 I11=G0（I3，d）=CLOSURE（Bd ）=Bd I12=G0（I5，d）=CLOSURE（Bd ）=Bd =I11,LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。,LR（0）分析,LR（0）分析表相当于识别活前缀的有限自动机DFA的状态转换矩阵。 LR（0）分析表的构造算法。,LR（0）分析表的构造,a）若项目Aa属于Ik，且转换函数GO（Ik，a）=Ij，当a为终结符时 ，则置ACTIONk，a为Sj。 b）若项目A属于Ik， 则对a为任何终结符或#，置ACTIONk，a=rj， j

27、为产生式在文法G中的编号。,LR（0）分析表的ACTION和GOTO表的构造步骤 如下：,c）若GO(Ik，A)=Ij，则置GOTOk，A=j，其中A为非终结符，j为某一状态号。,d）若项目SS属于Ik，则置ACTIONk，#= acc。 e）其它填上“报错标志”。,例,设文法GS： SA AaA|b 计算GS的LR(0)项目集规范族。,87,I0=closure(SA)=SA, AaA, Ab GO(I0, a)=closure(AaA)=AaA, AaA, Ab=I1 GO(I0, b)=closure(Ab)=Ab=I2 GO(I0, A)=closure(SA)=SA=I3 GO(I1

28、, a)=closure(AaA)=I1 GO(I1, b)=closure(Ab)=Ab=I2 GO(I1, A)=closure(Aa A)=AaA=I4 由于I2，I3 和I4都是归约项目，则GS的LR(0)项目集规范族C=I0，I1，I2，I3，I4。,88,识别文法GS的活前缀的DFA,I1,I0,I2,I3,I4,89,所给文法G的全部项目集为I0-I11。我们将这些项目集的全体称为文法G的LR（0）项目集规范族。C=I0，I1，I11 于是，我们所要构造的识别文法G（S）全部活前缀的DFA为：,识别文法G（S）全部活前缀的DFA,其中M的状态集C=I0，I1，I11； M的字母表

29、也就是文法字汇表V=S，S，A，B，a，b，c，d； M的映象函数也就是如上定义的状态转换函数GO； M的终态集也就是C，这表明M的每一状态都是它的终态。对于上述文G，我们可以画出它的识别其全部活前缀的DFA的状态转换图。,M=（C，V，GO，I0，C）,例,对于文法GA： AaA Ab 拓广后的文法为GS： SA AaA Ab,94,GS的LR(0)分析表,95,例：设拓广文法GS的产生式为： S S S aA | bB A cA | d B cB | d,96,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

30、I5,S.S S.aA S.bB I0,start,SS. I1,AcA. I8,SaA. I6,Ad. I10,A,d,d,A,c,a,b,S,SbB. I7,BcB. I9,Bd. I11,B,d,d,B,c,c,c,识别文法 活前缀的DFA,97,LR(0)分析表,98,LR（0）项目集规范族不存在移进-归约，或归约-归约冲突，称为LR（0）文法。 只有是LR（）文法，才能构造相应的 LR（0）分析表，才能用LR（0）分析法对句子进行分析。,LR（0）文法,SLR（1）分析,大多数适用的程序设计语言的文法不能满足 LR(0)文法的条件，即其规范族中会有含有冲突的项目集（状态）。 如何解决

31、这种冲突？ 直觉：对于有冲突的状态，向前查看一个符号，以确定采用的动作。,文法G：（0）S S（1）S rD （2）D D,i（3）D i,分析每个状态包含的项目集，不难发现在状态I3中含项目： SrD 为归约项目 DD，i为移进项目 也就是按SrD项目的动作认为用SrD产生式进行归约的句柄已形成，不管当前的输入符号是什么，都应把rD归约成S。但是按DD，i项目当面临输入符号，号时，应将，号移入符号栈，状态转向I5。显然该文法不是LR（0）文法，也可在构造它的LR（0）分析表时发现这个问题。,一个LR（0）规范族中含有如下的项目集（状态）I，I=Xb，A，B若有：FOLLOW（A）FOLLOW

32、（B）= FOLLOW（A）b= FOLLOW（B）b= ,SLR（1）文法,1）若a=b，则移进。 2）若aFOLLOW（A），则用产生式A进行归约。 3）若aFOLLOW（B），则用产生式B进行归约。 4）此外，报错。,状态I面临某输入符号a,通常对于LR（0）规范族的一个项目集I中可能含有多个移进项目和多个归约项目，我们可假设项目集I（状态）中有m个移进项目： A11a11，A22a22，Ammamm：，同时含有n个归约项目为：B11，B22，Bnn。,只要集合a1，a2，am和FOLLOW（B1），FOLLOW（B2），FOLLOW（Bn）两两交集都为空，那么我们仍可用上述规则解决冲突

33、，即考查当前输入符号决定动作。,1）若aa1，a2am，则移进。 2）若aFOLLOW（Bi），i=1，2n，则用Bii进行归约。 3）此外，报错。,如果对于一个文法的LR（0）项目集规范族的某些项目集或LR（0）分析表中所含有的动作冲突都能用上述方法解决， 则称这个文法是SLR（1）文法，所构造的分析表为SLR（1）分析表， 使用SLR（1）分析表的 分析器称为SLR（1）分析器。上述解决方法称为SLR（1）规则。,对所有非终结符都求出其FOLLOW集合，这样只有归约项目仅对面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。 改进的SLR（1）分析表的

34、ACTION表和GOTO表的构造步骤：,改进的SLR（1）分析表,A）若项目Aa属于Ik，且转换函数GO（Ik，a）=Ij，当a为终结符时，则置ACTIONk，a为Sj。,B）若项目A属于Ik，则对a为任何终结符或#，且满足aFOLLOW（A）时，置ACTIONk，a=rj，j为产生式在文法G中的编号。 C）若GO（Ik，A）=Ij，则置GOTOk，A=j，其中A为非终结符，j为某一状态号。 D）若项目SS属于Ik，则置ACTIONk，#=acc。 E）其它填上“报错标志”。,仍有许多文法构造的LR（0）项目集规范族存在的动作冲突不能用SLR（1）方法解决。,一个LR（0）规范族中含有如下的项

35、目集（状态）I。I=Xb，A，B有： FOLLOW（A） FOLLOW（B） 或 FOLLOW（A）b 或 FOLLOW（B）b ,1、若项目集AB属于I时，则B也属于I。 2、把FIRST（）作为用产生式归约的搜索符（称为向前搜索符） ，作为用产生式B归约时查看 的符号集合（用以代替SLR（1）分析中的FOLLOW集）， 并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR（1）方法。能用该方法进行分析句子的文法称为LR（1）文法。,LR（1）文法,针对初始项目SS，#求闭包后再用转换函数逐步求出整个文法的LR（1）项目集族。,LR（1）项目集族的构造,把作为向前搜索符，表示活前缀要归约成S时，必须面临输入符号才行。,1）构造LR（1）项目集的闭包函数,A）I的项目都在CLOSURE（I）中。,GOTO（I，X）= CLOSURE（J）其中：I为LR（1）的项目集，X为一文法符号，J=任何形如AX，a的项目|AX，a属于I,2）转换函数的构造,B）若AB，a属于CLOSURE（I），B是文法的产生式，V*，bFIRST（a），则B，b也属于CLOSURE（I）。 C）重复B）直到CLOSURE（I）不再扩大。,由于一个LR（1）项目可以看