编译原理第七章课件.ppt

1、LR(k)分析方法分析方法是指从左向右扫描和自底向上是指从左向右扫描和自底向上的语法分析。每次根据当前符号或最多向前看的语法分析。每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读个符号唯一地确定是归约还是继续读。一般来说，凡是上下文无关文法描述的程序一般来说，凡是上下文无关文法描述的程序设计语言都可以用设计语言都可以用LR方法进行有效的分析，方法进行有效的分析，而且还能在分析过程中及时准确地发现输入符而且还能在分析过程中及时准确地发现输入符号串的语法错误。号串的语法错误。通常的程序设计语言一般均能由通常的程序设计语言一般均能由LR(1)文法文法产生产生,而且能由而且能由LR(k)

2、产生的语言也可以由产生的语言也可以由LR(1)文法来产生。文法来产生。因此，我们通常只考虑因此，我们通常只考虑LR(0)和和LR(1)两种情况。两种情况。在本章中我们先后介绍在本章中我们先后介绍LR(0),SLR(1),LR(1)和和LALR(1)分析方法。分析方法。8.1 LR分析方法的逻辑结构及分析过程分析方法的逻辑结构及分析过程 LR方法也是通过求方法也是通过求句柄句柄逐步归约进行语法逐步归约进行语法分析。分析。句柄句柄在运算符优先数法中是通过运算符的在运算符优先数法中是通过运算符的优先关系而求得的；在优先关系而求得的；在LR方法中，则是通过方法中，则是通过求可归前缀求可归前缀而求得的。

3、而求得的。1.活前缀与可归前缀活前缀与可归前缀活前缀与可归前缀活前缀与可归前缀 符号串的符号串的前缀前缀是指符号串的任意首部，包括是指符号串的任意首部，包括空串空串。定义定义：对于文法：对于文法GS，若有若有 S ，Vt*则称则称为为规范前缀规范前缀，也称为，也称为活前缀活前缀。r*若若是含句柄的活前缀是含句柄的活前缀，并且每个句柄是并且每个句柄是的后缀或本身，则称的后缀或本身，则称是是可归规范前缀可归规范前缀或或可归可归前缀前缀(含有句柄的活前缀含有句柄的活前缀)。活前缀不含句柄之右的任何符号。活前缀不含句柄之右的任何符号。是规范是规范句型的左起部分，到当前句柄为止。句型的左起部分，到当前句

4、柄为止。如果在如果在其右边加上终结符号串其右边加上终结符号串后就可以成为一个规后就可以成为一个规范句型。范句型。S:=SS:=CbBA A:=AabA:=abB:=CB:=DbC:=aD:=a 对于句子对于句子ababab有规范推有规范推导，见下面的语法树：导，见下面的语法树：SaSCbABDbaba例如，设有文法例如，设有文法GS:规范句型规范句型ababab的活前缀为的活前缀为a，可归前缀为此可归前缀为此a，时句柄也是时句柄也是a；规范句型规范句型Cbabab的活前缀为的活前缀为C、Cb、Cba，可归前缀为可归前缀为Cba，此时句柄为此时句柄为a；规范句型规范句型CbDbab的活前缀为的活

5、前缀为CbD、CbDb,可可归前缀为归前缀为CbDb，此时句柄为此时句柄为Db；规范句型规范句型CbBab活前缀为活前缀为CbB、CbBa、CbBab，可归前缀为可归前缀为CbBab，此时的句柄为此时的句柄为ab;规范句型规范句型CbBA的活前缀为的活前缀为CbBA，可归前缀可归前缀为为CbBA，此时亦为此时亦为CbBA;规范句型规范句型S的活前缀为的活前缀为S，可归前缀为可归前缀为S，此时此时句柄亦为句柄亦为S。又例如，设有文法又例如，设有文法GA：A:=aBCb B:=BaC B:=b C:=c对于句子对于句子abaccb。可归前缀的求法：可归前缀的求法：设某文法有可归前缀设某文法有可归前

6、缀 A，AVn若有规则若有规则 A:=u u V*则则u也是文法的可归前缀。也是文法的可归前缀。例如，设有文法例如，设有文法GS:S:=aAcA:=AbbA:=b 文法的所有可归前缀构成的集合称为文法的文法的所有可归前缀构成的集合称为文法的可归前缀集可归前缀集根据上例文法对句子根据上例文法对句子abbbbbc的归约过程如下：的归约过程如下：abbbbbc aAbbbbc aAbbc aAc S其可归前缀集可用自动机来表示，称之为其可归前缀集可用自动机来表示，称之为可归前可归前缀图缀图。S4S0S1S2S5S3S6b ba aA Ac cb bc c从初始状态从初始状态S0到任一状态形成的符号串

7、构成了到任一状态形成的符号串构成了某规范句型的活前缀；某规范句型的活前缀；从初始状态从初始状态S0到任一终止状态形成的符号串到任一终止状态形成的符号串构成了某规范句型的可归前缀。构成了某规范句型的可归前缀。2.LR分析方法的逻辑结构分析方法的逻辑结构LR分析方法的逻辑结构：分析方法的逻辑结构：设有输入串设有输入串a1a2a3an，LR分析方法的逻辑分析方法的逻辑结构图如下：结构图如下：栈顶#anaia2a1#总控制器输入串S0#S1 x1.Sm xm分析表输出 分析栈中每项都包括状态栈分析栈中每项都包括状态栈Si和文法符号栈和文法符号栈xi两部分。两部分。LR分析器包括两个部分，一个总控程序和

8、分析器包括两个部分，一个总控程序和一张分析表。一张分析表。不同文法的不同文法的LR分析器的总控程序都是一样分析器的总控程序都是一样的，只是分析表不同，因此的，只是分析表不同，因此LR分析表是分析表是LR分分析方法的核心。总控程序根据具体的分析表析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。来决定起下一步的处理动作。LR分析的基本原理分析的基本原理：把每个句柄：把每个句柄(某个产生式某个产生式的右部的右部)的识别过程划分为若干状态。每个状的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每态下，从左向右地识别句柄中的一个符号，每个状态识别句柄的一部分符号。个

9、状态识别句柄的一部分符号。也就是，在总控程序的控制下，从左到右扫也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析号及当前输入符号，按分析表完成相应的分析工作。工作。由此可见，构造由此可见，构造LR分析器的主要工作是构造分析器的主要工作是构造分析表分析表LR分析表的组成：分析表的组成：LR分析表由分析动作分析表由分析动作(ACTION)表和状态转换表和状态转换(GOTO)表组成。表组成。1).分析动作表分析动作表 在分析动作表中，其元素由在分析动作表中，其元素由action(si,aj)

10、来表来表示。示。action(si,aj)表示当前分析栈的状态栈栈顶表示当前分析栈的状态栈栈顶元素为元素为si，文法符号栈栈顶元素为文法符号栈栈顶元素为aj(当前输入当前输入符号符号)时，所执行的动作。时，所执行的动作。这个动作可分为四种这个动作可分为四种:移进移进(S)、归约归约(r)、接接受受(acc)和出错和出错(error)。action(Sn,at)action(Sn,a2)action(Sn,a1)Snaction(S1,at)action(S1,a2)action(S1,a1)S1action(S0,at)action(S0,a2)action(S0,a1)S0ata2a1 状状

11、 态态输入输入符号符号2).状态转换表状态转换表gotoSn,xegotoSn,x2gotoSn,x1SngotoS1,xegotoS1,x2gotoS1,x1S1gotoS0,xegotoS0,x2gotoS0,x1S0 xex2x1 状状 态态文法文法符号符号 gotosi,xj指出栈顶状态为指出栈顶状态为si，文法符号为文法符号为aj时应转到的下一状态。时应转到的下一状态。3.LR分析过程分析过程LR分析步骤：分析步骤：在讲述在讲述LR的分析步骤之前，我们假设分析的分析步骤之前，我们假设分析表已经成功构造。表已经成功构造。下面我们给出下面我们给出LR分析的具体步骤：分析的具体步骤：将初始

12、状态将初始状态S0和句子的左界符和句子的左界符#分别进分析栈分别进分析栈中的状态栈和符号栈；中的状态栈和符号栈；根据栈顶状态和当前输入符号查动作表，然根据栈顶状态和当前输入符号查动作表，然后分别做如下动作：后分别做如下动作：移进移进；当前输入符号进符号栈，根据状态转；当前输入符号进符号栈，根据状态转换表，得到的新的状态进状态栈。继续扫描，换表，得到的新的状态进状态栈。继续扫描，从而下一个符号变成当前输入符号。从而下一个符号变成当前输入符号。归约归约；按某个产生式进行归约，若产生式的；按某个产生式进行归约，若产生式的右端长度为右端长度为n，则符号栈顶和状态栈顶则符号栈顶和状态栈顶n个元素个元素同

13、时相应退栈。归约后的文法符号进符号栈，同时相应退栈。归约后的文法符号进符号栈，查状态转换表，得到的新状态进状态栈。查状态转换表，得到的新状态进状态栈。接受接受；分析成功，终止分析。；分析成功，终止分析。出错出错；报告出错信息。；报告出错信息。重复第重复第2步的工作，直到接受或出错。步的工作，直到接受或出错。LR分析流程图分析流程图(P192图图8-4)。具体分析过程具体分析过程下面我们以具体的例子来说明下面我们以具体的例子来说明LR方法的分方法的分析过程：析过程：设有文法设有文法GL：1)L:=E,L 2)L:=E 3)E:=a 4)E:=b上述文法表述的是单个上述文法表述的是单个a和和b及由

14、逗号分隔的及由逗号分隔的任意个任意个a和和b所组成的所有符号串的集合。所组成的所有符号串的集合。这里我们直接给出该文法的分析表这里我们直接给出该文法的分析表(P192图图8-3)。ri表示按第表示按第i个产生式进行归约；个产生式进行归约；Si表示把当前输入符号移进符号栈，且第表示把当前输入符号移进符号栈，且第i个个状态进状态栈；状态进状态栈；i表示转第表示转第i个状态，即第个状态，即第i个状态进状态栈；个状态进状态栈；表中未填内容的空白则表示分析动作为出错。表中未填内容的空白则表示分析动作为出错。下面我们以输入串下面我们以输入串#a,b,a#为例，具体讲述为例，具体讲述LR分析过程。分析过程。

15、状态栈状态栈符号栈符号栈产生式产生式输入符号输入符号说说 明明S0#a,b,a#S0和和#分别进栈分别进栈S0S3#a,b,a#a和和S3分别进栈分别进栈S0S2#EE:=a,b,a#a和和S3分别退栈分别退栈E和和S2分别进栈分别进栈S0S2S5#E,b,a#,和和S5分别进栈分别进栈S0S2S5S4#E,b,a#b和和S4分别进栈分别进栈S0S2S5S2#E,EE:=b,a#b和和S4分别退栈分别退栈E和和S2分别进栈分别进栈S0S2S5S2S5#E,E,a#,和和S5分别进栈分别进栈S0S2S5S2S5S3#E,E,a#a和和S3分别进栈分别进栈S0S2S5S2S5S2#E,E,EE:=

16、a#a和和S3分别退栈分别退栈E和和S2分别进栈分别进栈状态栈状态栈符号栈符号栈产生式产生式输入符号输入符号说说 明明S0S2S5S2S5S6#E,E,LL:=E#E和和S2分别退栈分别退栈L和和S6分别进栈分别进栈S0S2S5S6#E,L L:=E,L#E,L和和S2S5 S6退栈退栈L和和S6分别进栈分别进栈S0S1#L L:=E,L#E,L和和S2S5 S6退栈退栈L和和S1分别进栈分别进栈acc 可见可见#a,b,a#符合所给的文法规则。符合所给的文法规则。8.2 LR(0)分析表的构造分析表的构造 LR(0)分析是当分析是当k=0时的时的LR(k)分析方法。在分析方法。在分析的每一步

17、只要根据当前栈顶状态就能确定分析的每一步只要根据当前栈顶状态就能确定完成何种分析动作。完成何种分析动作。基本概念：基本概念：项目项目：对于文法：对于文法G，其产生式右部带有特殊其产生式右部带有特殊符号符号“”，则称之为文法的一个，则称之为文法的一个LR(0)项目项目，简称简称项目项目。有时也称为。有时也称为配置式配置式。特殊符号也可以用特殊符号也可以用“.”，并且要加在产生，并且要加在产生式右部的任何地方，表示一个位置。式右部的任何地方，表示一个位置。项目集项目集：若干个项目组成的集合称为：若干个项目组成的集合称为项目集项目集，又称为又称为配置集合配置集合。后继符号后继符号：项目中紧跟在特殊符

18、号：项目中紧跟在特殊符号“”后后面的符号称为该项目的面的符号称为该项目的后继符号后继符号。后继符号后继符号表示下一时刻读到的符号。有如下两表示下一时刻读到的符号。有如下两种情况：种情况：后继符号为终结符号和非终结符号后继符号为终结符号和非终结符号例如，对应于产生式例如，对应于产生式:E:=E+T有四个项目：有四个项目：E:=E+T E:=E+T E:=E+T E:=E+T 这一类的后继符号为：这一类的后继符号为：E:=E+T的后继符号为的后继符号为E E:=E+T的后继符号为的后继符号为+E:=E+T的后继符号为的后继符号为T后继符号为空后继符号为空规定规定：该项目的后继符号为带有：该项目的后

19、继符号为带有“#”的相应的相应产生式，用来表示下一时刻将按指定的产生式产生式，用来表示下一时刻将按指定的产生式进行归约。进行归约。后继符号集后继符号集 定义定义：项目集中诸项目的后继符号所组成的集：项目集中诸项目的后继符号所组成的集合称为合称为后继符号集后继符号集。状态内容状态内容 分成是分成是基本基本(BASIC)部分部分和和闭包闭包(CLOSURE)部分部分。设设Si是是Sk关于符号关于符号 X的后继状态，则求的后继状态，则求BASIC(Si)和和CLOSURE(Si)的方法：的方法：1).BASIC(Si)的计算：的计算：BASIC(Si)=A:=X|A:=XSk2).CLOSURE(S

20、i)的计算：的计算：.BASIC(Si)CLOSURE(Si)；.若若A:=YCLOSURE(Si),且且YVn则则Y:=rCLOSURE(Si),r为符号串；为符号串；.重复重复直到直到CLOSURE(Si)不再增加为止。不再增加为止。例如，对于文法例如，对于文法GS:S:=A A:=aAb A:=c 设其开始设其开始状态为状态为S0，则求则求S0的状态内容。的状态内容。项目类型项目类型 项目类型有三类项目类型有三类归约项目归约项目、移进项目移进项目和和待归待归项目项目。归约项目：归约项目：A:=此时已把分析结束，已在栈顶此时已把分析结束，已在栈顶,从从而可按相应的产生式进行归约。而可按相应

21、的产生式进行归约。移进项目：移进项目：A:=X，XVt 此时把此时把X移进文法符号栈。移进文法符号栈。待约项目：待约项目：A:=X，XVn 此时等待从余留的输此时等待从余留的输入符号中进行归约而得到入符号中进行归约而得到X。项目集的相容性项目集的相容性 满足以下条件的项目集称为满足以下条件的项目集称为相容的项目集相容的项目集：无移进项目和归约项目并处；无移进项目和归约项目并处；无多个归约项目并存。无多个归约项目并存。例如，项目集：例如，项目集：A:=,B:=A:=,B:=状态描述序列和状态转换图：状态描述序列和状态转换图：.在某一状态的项目集中，不同的项目，其后在某一状态的项目集中，不同的项目

22、，其后状态描述序列状态描述序列查看完毕在状态描述序列中，必须遵守以下规则：在状态描述序列中，必须遵守以下规则：.不同状态的项目集中，有若干个与前面对应不同状态的项目集中，有若干个与前面对应相同的相同的项目项目，其后继状态与前面相同时，则后，其后继状态与前面相同时，则后继状态相同。继状态相同。例如，有文法例如，有文法GS：(1)S:=A (2)S:=B (3)A:=aAb(4)A:=c (5)B:=aBb (6)B:=d 我们先对文法进行拓展，增加一条规则我们先对文法进行拓展，增加一条规则:(0)S:=S (1)S:=A (2)S:=B (3)A:=aAb (4)A:=c (5)B:=aBb (

23、6)B:=d 继符号相同时，则后继状态相同；继符号相同时，则后继状态相同；S11#SBSBS3S11#SASAS2S11#SSSSS1S1S2S3S5S6S ABaa cd SS SA SB AaAb BaBb Ac BdS0后后 继继 状状 态态后后 继继 符符 号号项项 目目 集集状状 态态S4S11#AaAb AaAbS8S8b AaAbS7S11#Bd BdS6S11#Ac AcS5S7 S9 S5 S6ABaa cd AaAb BaBb AaAb BaBb Ac BdS4后后 继继 状状 态态后后 继继 符符 号号项项 目目 集集状状 态态S4状状 态态项项 目目 集集后后 继继 符

24、符 号号后后 继继 状状 态态S9 BaBb bS10S10 BaBb#BaBbS11S11 状态转换图状态转换图 由上面的状态描述序列可见，其项目集是相由上面的状态描述序列可见，其项目集是相容的。容的。查看相容的定义注意注意：对于一个文法：对于一个文法G，若其状态描述序列中若其状态描述序列中的状态项目集是相容的，则称的状态项目集是相容的，则称G为为LR(0)文法文法。LR(0)分析表的构造：分析表的构造：首先，设有状态转换函数首先，设有状态转换函数 GO(Si,X)=Sj 表示当前状态为表示当前状态为Si，输入，输入符号为符号为X时的后继状态为时的后继状态为Sj。LR(0)分析表的构造规则：

25、分析表的构造规则：设有文法设有文法GS,则则LR(0)分析表的构造规则为：分析表的构造规则为：对于对于A:=XSi,GO(Si,X)=Sj,若若XVt,则置则置 actionSi,X=Sj 若若XVn,则置则置 gotoSi,X=j对于对于A:=Si,若若A:=是文法的第是文法的第j个产生个产生式，则对所有的式，则对所有的 XVt,均置均置 actionSi,X=rj 对于对于S:=Si,则置则置 actionSi,#=acc 其它情况均置出错。其它情况均置出错。LR(0)分析表分析表 设有文法设有文法GS,则则LR(0)分析表的构造规则为：分析表的构造规则为：状态ACTIONGOTOabcd

26、#SABS0S4S5S6123S1accS2r1r1r1r1r1S3r2r2r2r2r2S4S4S5S679状态ACTIONGOTOabcd#SABS5r4r4r4r4r4S6r6r6r6r6r6 S7S8S8r3r3r3r3r3S9S10S10r5r5r5 r5r5应用举例应用举例 用上述分析表对输入串用上述分析表对输入串#aacbb#进行分析，过程如书表进行分析，过程如书表8-6所示。所示。8.3 SLR(1)分析表的构造：分析表的构造：问题的提出：问题的提出：只有当文法只有当文法G的每一个状态项目集相容是才的每一个状态项目集相容是才为为LR(0)文法。文法。当文法的状态项目集不相容时当文

27、法的状态项目集不相容时,就会出现不就会出现不确定的动作，此时确定的动作，此时LR(0)分析方法就已经无法分析方法就已经无法解决了。解决了。SLR(1)方法是一种简单的方法是一种简单的LR(1)方法，它用方法，它用从左到右向前看一个符号来解决冲突动作。从左到右向前看一个符号来解决冲突动作。SLR(1)与与LR(1)方法的区别方法的区别：SLR(1)的向前看的向前看的符号是在出现冲突时才确定向前看的符号。的符号是在出现冲突时才确定向前看的符号。而而LR(1)方法则是在一开始就确定向前看的符方法则是在一开始就确定向前看的符号。号。SLR(1)分析表的构造方法思想：分析表的构造方法思想：SLR(1)分

28、析表的构造思想：分析表的构造思想：在构造在构造SLR(1)分析表时，根据不同的向前看分析表时，根据不同的向前看符号，将符号，将Si中的各项目所对应的动作加以区分，中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。从而即可使冲突动作得到解决。例如，对于状态例如，对于状态Si，假设其项目集为假设其项目集为 Si=B,A,C其中其中是首符号为终结符的符号串。是首符号为终结符的符号串。对于归约项目：对于归约项目：A C 分别求其分别求其Follow(A)和和Follow(C)。对于移进项目：对于移进项目：B 求其求其First()。若集合若集合Follow(A、Follow(C)、First

29、()不相不相交，则对于任何交，则对于任何a(aVt#)可按如下方法构可按如下方法构造分析表就能解决冲突：造分析表就能解决冲突：对于对于BSi,aFirst(),且且GO(Si,a)=Sj 则置：则置：actionSi,a=Sj 对于对于ASi,aFollow(A),且且A为文为文法的第法的第j个产生式，则置：个产生式，则置：actionSi,a=rj 对于对于CSi,aFollow(C),且且C为文为文法的第法的第k个产生式，则置：个产生式，则置：actionSi,a=rk 凡不能按上述方法填入的项均置出错。凡不能按上述方法填入的项均置出错。SLR(1)分析表的构造规则：分析表的构造规则：设有

30、文法设有文法GS,则则SLR(1)分析表的构造规则分析表的构造规则为：为：对于对于AXSi,GO(Si,X)=Sj,若若XVt,则置则置 actionSi,X=Sj 若若XVn,则置则置 gotoSi,X=j对于归约项目对于归约项目ASi,若若A为文法的第为文法的第j个产生式则对于任何输入符号个产生式则对于任何输入符号a,若若aFollow(A),则置：则置：actionSi,a=rj 对于对于SSi,则置则置 actionSi,#=acc 其它情况均置出错。其它情况均置出错。对于给定的文法对于给定的文法G，若按上述规则所构造的若按上述规则所构造的分析表不含多重定义的元素分析表不含多重定义的元

31、素,则称文法则称文法G为为SLR(1)文法文法。SLR(1)分析表：分析表：例如，文法例如，文法GS为算术表达式的文法：为算术表达式的文法：(0)SE (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E)(6)Fi 我们可以构造我们可以构造(见书见书P201图图8-8)状态描述序列。状态描述序列。其中，其中，S2和和S9两个项目集不相容。于是，两个项目集不相容。于是，对于对于S2 有有 S2=ET,TT*F 下面求下面求 Follow(E)=#,+,)，于是于是Follow(E)与与*不相交。不相交。状态状态ACTIONGOTOi+*()#ETFS0S5S4123S1S6ac

32、cS2r2S7r2r2S3r4r4r4r4S4S5S4823S5r6r6r6r6S6S5S493S7S5S410S8S6S11S9r1S7r1r1S10r3r3r3r3S11r5r5r5r5应用举例：应用举例：利用上述文法利用上述文法GS的的SLR(1)分析表对输入串分析表对输入串#i+i*i#进行分析。进行分析。8.4 LR(1)分析表的构造分析表的构造问题的提出：问题的提出：设有文法设有文法GS:(0)SS (1)SCbBA (2)AAab (3)Aab (4)BC (5)BDb (6)Ca (7)Da 由其状态描述序列由其状态描述序列(见图见图8-10)可得，项目集可得，项目集:S10=

33、SCbBA,AAab和项目集和项目集:S9=Ca,Da 都是不相容的。都是不相容的。可用可用LR(1)方法来解决方法来解决SLR(1)仍然出现的项仍然出现的项目集的项目不相容且目集的项目不相容且Follow和和First相交的问题。相交的问题。LR(1)分析表构造的思想：分析表构造的思想：只要输入串的已扫描部分可保持可归约成一只要输入串的已扫描部分可保持可归约成一个活前缀，那就可判定所扫描的部分未出错。个活前缀，那就可判定所扫描的部分未出错。LR(1)项目：项目：为解决为解决SLR(1)方法无法解决的问题，我们在方法无法解决的问题，我们在LR(0)项目中放置一个向前搜索的符号项目中放置一个向前

34、搜索的符号a，从而从而组成如下的形式：组成如下的形式：A,a,aFollow(A)我们把这样的项目称为我们把这样的项目称为LR(1)项目项目。有效项目：有效项目：对于文法对于文法GS,项目项目 A 对活前缀对活前缀r=是是有效有效的条件：的条件：存在规范推导存在规范推导 S Ay y,yVt*r r .若归约项目若归约项目 A 对活前缀对活前缀r=是有效的是有效的,则说明则说明应把符号串应把符号串归归约为约为A,即把活前缀即把活前缀变为变为A。1).SLR(0)有效项目：有效项目：.若移进项目若移进项目 A 对活前缀对活前缀r=是有效的是有效的,则说明则说明句柄尚未形成，句柄尚未形成，下一步动

35、作应该是移进。下一步动作应该是移进。说明：说明：.当一个项目出现在几个不同的项目集中时当一个项目出现在几个不同的项目集中时,同同一项目可能对好几个活前缀都是有效的。一项目可能对好几个活前缀都是有效的。.有可能存在这样的情形，在一个项目集中，有可能存在这样的情形，在一个项目集中，对同一个活前缀，存在若干项目对它都是有效对同一个活前缀，存在若干项目对它都是有效的，而项目集却不相容。的，而项目集却不相容。2).LR(1)有效项目：有效项目：对于文法对于文法GS,LR(1)项目项目 A,a 对活前缀对活前缀r=是是有效有效的条件：的条件：存在规范推导存在规范推导 S Ay y,yVt*且还要满足以下条

36、件：且还要满足以下条件：i).当当y时，时，a=First(y);ii).当当y=时，时，a=#。*r r构造构造LR(1)分析表的思想：分析表的思想：对于上述例子的规范句型对于上述例子的规范句型Cbabab,根据定义，根据定义，LR(1)项目项目Da,b对活前缀对活前缀r=Cba有效。因有效。因此，应将栈顶文法符号此，应将栈顶文法符号a归约成归约成D，而不应归约而不应归约成成C。由此可见，在由此可见，在LR(1)分析表的构造过程中，分析表的构造过程中，要根据要根据Si的项目集中的各个项目的项目集中的各个项目,对活前缀有效对活前缀有效情况，来确定相应的动作。情况，来确定相应的动作。状态描述序列

37、状态描述序列:每一个状态也是由一个每一个状态也是由一个LR(1)项目集来表示项目集来表示的，的，每一个项目集都是由若干个对相应的活每一个项目集都是由若干个对相应的活前缀有效的前缀有效的LR(1)项目组成。项目组成。.Si中的任何中的任何LR(1)项目都属于项目都属于CLOSURE(Si);.设有项目设有项目 AX,aCLOSURE(Si),XVn 则则 X,bCLOSURE(Si),V*其中，其中，a为已知，为已知，b=First()。.重复重复直到直到CLOSURE(Si)不再增加。不再增加。注意：注意：每一个每一个LR(1)项目与其后继项目有相同项目与其后继项目有相同的向前的搜索符号。的向

38、前的搜索符号。注意：注意：每一个每一个LR(1)项目与其后继项目有相同项目与其后继项目有相同的向前的搜索符号。的向前的搜索符号。如：如：LR(1)项目项目 AX,a其后继项目其后继项目 AX,a 具有相同的向前搜索符具有相同的向前搜索符号号a。构造构造LR(1)项目的状态描述序列：项目的状态描述序列：设有文法设有文法GS:(0)SS (1)SCbBA (2)AAab (3)Aab (4)BC (5)BDb (6)Ca (7)DaFollow(S)=#Follow(S)=Follow(S)=#Follow(A)=Follow(S)+First(ab)=#,aFollow(B)=First(A)=

39、aFollow(C)=First(bBA)+Follow(B)=b,aFollow(D)=bLR(1)分析表的构造规则分析表的构造规则:对于文法对于文法GS，其其LR(1)分析表的构造规则分析表的构造规则为：为：.对于对于 AX,aSi,GO(Si,X)=Sj,若若XVt,则置则置 actionSi,X=Sj 若若XVn,则置则置 gotoSi,X=j.对于归约项目对于归约项目A,aSi,若若A为文法的第为文法的第j个产生式，则对于任何个产生式，则对于任何输入符号输入符号a,若若aFollow(A),则置：则置：actionSi,a=rj 对于对于S,#Si,则置则置 actionSi,#=a

40、cc 其它情况均置出错。其它情况均置出错。对于给定的文法对于给定的文法G，若按上述规则所构造若按上述规则所构造的分析表不含多重定义的元素，则称文法的分析表不含多重定义的元素，则称文法G为为LR(1)文法文法。LR(1)分析表的构造分析表的构造:对于文法对于文法GS，其其LR(1)分析表的构造为：分析表的构造为：状态状态ACTIONGOTOab#SABCDS0S312S1accS2S4S3r6S4S8567S5S1110S6r4S7S9S8r6r7S9r5S10S13r1S11S12状态状态ACTIONGOTOab#SABCDS12r3r3S13S14S14r2r28.5 LALR(1)分析表的构造：分析表的构造：LALR(1)分析表的构造与分析表的构造与LR(1)分析表的构分析表的构造相似，不同之处在于造相似，不同之处在于LALR(1)的状态部分的状态部分把若干非等价状态进行合并而已。把若干非等价状态进行合并而已。