编译原理第七章课件

第8章LR(k)分析方法8.1分析方法的逻辑结构及分析过程8.2LR(0)分析表的构造8.3SLR(1)分析表的构造8.4LR(1)分析表的构造8.5LALR(1)分析表的构造第8章LR(k)分析方法8.1分析方法的逻辑结构及分析过LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读。一般来说，凡是上下文无关文法描述的程序设计语言都可以用LR方法进行有效的分析，而且还能在分析过程中及时准确地发现输入符号串的语法错误。通常的程序设计语言一般均能由LR(1)文法产生,而且能由LR(k)产生的语言也可以由LR(1)文法来产生。因此，我们通常只考虑LR(0)和LR(1)两种情况。LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次在本章中我们先后介绍LR(0),SLR(1),LR(1)和LALR(1)分析方法。8.1LR分析方法的逻辑结构及分析过程LR方法也是通过求句柄逐步归约进行语法分析。句柄在运算符优先数法中是通过运算符的优先关系而求得的；在LR方法中，则是通过求可归前缀而求得的。1.活前缀与可归前缀活前缀与可归前缀符号串的前缀是指符号串的任意首部，包括在本章中我们先后介绍LR(0),SLR(1),LR(1)空串ε。定义：对于文法G[S]，若有

Sαβ，β∈Vt*

则称α为规范前缀，也称为活前缀。r*若α是含句柄的活前缀，并且每个句柄是α的后缀或本身，则称α是可归规范前缀或可归前缀(含有句柄的活前缀)。

活前缀不含句柄之右的任何符号。是规范句型的左起部分，到当前句柄为止。如果在其右边加上终结符号串β后就可以成为一个规范句型。空串ε。定义：对于文法G[S]，若有

S’::=S S::=CbBA A::=Aab

A::=ab B::=C B::=Db

C::=a D::=a对于句子ababab有规范推导，见下面的语法树：SaS’CbABDbaba例如，设有文法G[S’]:S’::=S S::=CbBA A::=Aab

A::=a①规范句型ababab的活前缀为a，可归前缀为此a，时句柄也是a；②规范句型Cbabab的活前缀为C、Cb、Cba，

可归前缀为Cba，此时句柄为a；③规范句型CbDbab的活前缀为CbD、CbDb,可归前缀为CbDb，此时句柄为Db；④规范句型CbBab活前缀为CbB、CbBa、CbBab，可归前缀为CbBab，此时的句柄为ab;⑤规范句型CbBA的活前缀为CbBA，可归前缀为CbBA，此时亦为CbBA;⑥规范句型S的活前缀为S，可归前缀为S，此时句柄亦为S。①规范句型ababab的活前缀为a，可归前缀为此a，时句柄也又例如，设有文法G[A]：

A::=aBCbB::=BaCB::=bC::=c

对于句子abaccb。可归前缀的求法：设某文法有可归前缀

αAβ，A∈Vn

若有规则

A::=uu

∈V*

则αu也是文法的可归前缀。例如，设有文法G[S]:S::=aAc

A::=Abb

A::=b文法的所有可归前缀构成的集合称为文法的可归前缀集又例如，设有文法G[A]：

A::=aBCbB:根据上例文法对句子abbbbbc的归约过程如下：

abbbbbcaAbbbbcaAbbcaAcS△△△△其可归前缀集可用自动机来表示，称之为可归前缀图。S4S0S1S2S5S3S6baAcbc从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀；根据上例文法对句子abbbbbc的归约过程如下：

a从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀。2.LR分析方法的逻辑结构LR分析方法的逻辑结构：设有输入串a1a2a3…an，LR分析方法的逻辑结构图如下：栈顶#an…ai…a2a1#总控制器输入串S0#S1x1….…Smxm分析表输出从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可分析栈中每项都包括状态栈Si和文法符号栈xi两部分。

LR分析器包括两个部分，一个总控程序和一张分析表。不同文法的LR分析器的总控程序都是一样的，只是分析表不同，因此LR分析表是LR分析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。

LR分析的基本原理：把每个句柄(某个产生式的右部)的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每分析栈中每项都包括状态栈Si和文法符号栈xi两部分。个状态识别句柄的一部分符号。也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析工作。

由此可见，构造LR分析器的主要工作是构造分析表LR分析表的组成：LR分析表由分析动作(ACTION)表和状态转换(GOTO)表组成。1).分析动作表个状态识别句柄的一部分符号。也就是，在总控程序的控制在分析动作表中，其元素由action(si,aj)来表示。action(si,aj)表示当前分析栈的状态栈栈顶元素为si，文法符号栈栈顶元素为aj(当前输入符号)时，所执行的动作。这个动作可分为四种:移进(S)、归约(r)、接受(acc)和出错(error)。action(Sn,at)…action(Sn,a2)action(Sn,a1)Sn………action(S1,at)…action(S1,a2)action(S1,a1)S1action(S0,at)…action(S0,a2)action(S0,a1)S0at…a2a1

状态输入符号在分析动作表中，其元素由action(si,aj)来2).状态转换表goto[Sn,xe]…goto[Sn,x2]goto[Sn,x1]Sn………goto[S1,xe]…goto[S1,x2]goto[S1,x1]S1goto[S0,xe]…goto[S0,x2]goto[S0,x1]S0xe…x2x1

状态文法符号goto[si,xj]指出栈顶状态为si，文法符号为aj时应转到的下一状态。3.LR分析过程LR分析步骤：

在讲述LR的分析步骤之前，我们假设分析2).状态转换表goto[Sn,xe]…goto[Sn,x表已经成功构造。下面我们给出LR分析的具体步骤：将初始状态S0和句子的左界符#分别进分析栈中的状态栈和符号栈；根据栈顶状态和当前输入符号查动作表，然后分别做如下动作：①移进；当前输入符号进符号栈，根据状态转换表，得到的新的状态进状态栈。继续扫描，从而下一个符号变成当前输入符号。②归约；按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态栈顶n个元素同时相应退栈。归约后的文法符号进符号栈，表已经成功构造。下面我们给出LR分析的具体步骤：将初始状态S查状态转换表，得到的新状态进状态栈。③接受；分析成功，终止分析。④出错；报告出错信息。重复第2步的工作，直到接受或出错。LR分析流程图(P192图8-4)。具体分析过程

下面我们以具体的例子来说明LR方法的分析过程：设有文法G[L]：

1)L::=E,L2)L::=E

3)E::=a4)E::=b查状态转换表，得到的新状态进状态栈。③接受；分析成功，终止分上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成的所有符号串的集合。这里我们直接给出该文法的分析表(P192图8-3)。ri表示按第i个产生式进行归约；Si表示把当前输入符号移进符号栈，且第i个状态进状态栈；i表示转第i个状态，即第i个状态进状态栈；表中未填内容的空白则表示分析动作为出错。下面我们以输入串

#a,b,a#为例，具体讲述LR分析过程。上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成状态栈符号栈产生式输入符号说明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::=a#a和S3分别退栈

E和S2分别进栈状态栈符号栈产生式输入符号说明S0#a,b,a#S0和#状态栈符号栈产生式输入符号说明S0S2S5S2S5S6#E,E,LL::=E#E和S2分别退栈

L和S6分别进栈S0S2S5S6#E,LL::=E,L#E,L和S2S5S6退栈

L和S6分别进栈S0S1#L

L::=E,L#E,L和S2S5S6退栈

L和S1分别进栈acc

可见#a,b,a#符合所给的文法规则。8.2LR(0)分析表的构造LR(0)分析是当k=0时的LR(k)分析方法。在分析的每一步只要根据当前栈顶状态就能确定状态栈符号栈产生式输入符号说明S0S2S5S2S5S6#完成何种分析动作。基本概念：项目：对于文法G，其产生式右部带有特殊符号“△”，则称之为文法的一个LR(0)项目，简称项目。有时也称为配置式。

特殊符号也可以用“.”，并且要加在产生式右部的任何地方，表示一个位置。项目集：若干个项目组成的集合称为项目集，又称为配置集合。后继符号：项目中紧跟在特殊符号“△”后面的符号称为该项目的后继符号。完成何种分析动作。基本概念：项目：对于文法G，其产生式右部带后继符号表示下一时刻读到的符号。有如下两种情况：后继符号为终结符号和非终结符号例如，对应于产生式:

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后继符号为空

规定：该项目的后继符号为带有“#”的相应产生式，用来表示下一时刻将按指定的产生式进行归约。后继符号集

定义：项目集中诸项目的后继符号所组成的集合称为后继符号集。状态内容

分成是基本(BASIC)部分和闭包(CLOSURE)部分。E::=E△+T的后继符号为+

设Si是Sk关于符号X的后继状态，则求BASIC(Si)和CLOSURE(Si)的方法：1).BASIC(Si)的计算：

BASIC(Si)={A::=αX△β|A::=α△Xβ∈Sk}2).CLOSURE(Si)的计算：

①.BASIC(Si)CLOSURE(Si)；②.若A::=α△Yβ∈CLOSURE(Si),且Y∈Vn则Y::=△r∈CLOSURE(Si),r为符号串；③.重复②直到CLOSURE(Si)不再增加为止。例如，对于文法G[S]:

S::=AA::=aAbA::=c设其开始状态为S0，则求S0的状态内容。设Si是Sk关于符号X的后继状态，则求BASIC项目类型

项目类型有三类归约项目、移进项目和待归项目。①归约项目：

A::=α△此时已把分析结束，已在栈顶,从而可按相应的产生式进行归约。②移进项目：

A::=α△Xβ

，X∈Vt

此时把X移进文法符号栈。③待约项目：

A::=α△Xβ

，X∈Vn此时等待从余留的输入符号中进行归约而得到X。项目类型

项目类型有三类归约项目、移进项目和项目集的相容性

满足以下条件的项目集称为相容的项目集：①无移进项目和归约项目并处；②无多个归约项目并存。例如，项目集：

{A::=α△β,B::=α△}

{A::=α△,B::=α△}状态描述序列和状态转换图：

①.在某一状态的项目集中，不同的项目，其后状态描述序列查看完毕在状态描述序列中，必须遵守以下规则：项目集的相容性

满足以下条件的项目集称为相容

②.不同状态的项目集中，有若干个与前面对应相同的项目，其后继状态与前面相同时，则后继状态相同。例如，有文法G[S]：

(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

(6)B::=d继符号相同时，则后继状态相同；②.不同状态的项目集中，有若干个与前面对应相同的项目，其后S11#S→B{S→B△}S3S11#S→A{S→A△}S2S11#S’→S{S’→S△}S1S1

S2

S3

S5

S6S

A

B

a

a

c

d{S’→△S

S→△A

S→△B

A→△aAb

B→△aBb

A→△c

B→△d}S0后继状态后继符号项目集状态S4S11#S→B{S→B△}S3S11#S→A{S→A△}S2S11#A→aAb{A→aAb△}S8S8b{A→aA△b}S7S11#B→d{B→d△}S6S11#A→c{A→c△}S5S7

S9

S5

S6A

B

a

a

c

d{A→a△Ab

B→a△Bb

A→△aAb

B→△aBb

A→△c

B→△d}S4后继状态后继符号项目集状态S4S11#A→aAb{A→aAb△}S8S8b{A→a状态项目集后继符号后继状态S9{B→aB△b}bS10S10{B→aBb△}#B→aBbS11S11{}状态转换图由上面的状态描述序列可见，其项目集是相容的。查看相容的定义注意：对于一个文法G，若其状态描述序列中的状态项目集是相容的，则称G为LR(0)文法。LR(0)分析表的构造：状态项目集后继符号后继状态S9{B→首先，设有状态转换函数

GO(Si,X)=Sj

表示当前状态为Si，输入符号为X时的后继状态为Sj。LR(0)分析表的构造规则：

设有文法G[S],则LR(0)分析表的构造规则为：①对于A::=α△Xβ∈Si,GO(Si,X)=Sj,若X∈Vt,

则置action[Si,X]=Sj

若X∈Vn,则置

goto[Si,X]=j②对于A::=α△∈Si,若A::=α是文法的第j个产生式，则对所有的X∈Vt,均置

action[Si,X]=rj

首先，设有状态转换函数

GO(S③对于S::=α△∈Si,则置

action[Si,#]=acc

④其它情况均置出错。LR(0)分析表

设有文法G[S],则LR(0)分析表的构造规则为：状态ACTIONGOTOabcd#SABS0S4S5S6123S1accS2r1r1r1r1r1S3r2r2r2r2r2S4S4S5S679③对于S::=α△∈Si,则置

actio状态ACTIONGOTOabcd#SABS5r4r4r4r4r4S6r6r6r6r6r6

S7S8S8r3r3r3r3r3S9S10S10r5r5r5

r5r5应用举例

用上述分析表对输入串

#aacbb#

进行分析，过程如书表8-6所示。状态ACTIONGOTOabcd#SABS5r4r4r4r48.3SLR(1)分析表的构造：问题的提出：

只有当文法G的每一个状态项目集相容是才为LR(0)文法。

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

只有而LR(1)方法则是在一开始就确定向前看的符

号。SLR(1)分析表的构造方法思想：SLR(1)分析表的构造思想：

在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。例如，对于状态Si，假设其项目集为

Si={B→α△β,A→α△,C→α△}

其中β是首符号为终结符的符号串。对于归约项目：而LR(1)方法则是在一开始就确定向前看的符

号。SLR(1A→α△

C→α△

分别求其Follow(A)和Follow(C)。

对于移进项目：

B→α△β

求其First(β)。若集合Follow(A、Follow(C)、First(β)不相交，则对于任何a(a∈Vt∪{#}

)可按如下方法构造分析表就能解决冲突：对于B→α△β∈Si,a∈First(β),且GO(Si,a)=Sj则置：

action[Si,a]=Sj

A→α△

C→α△

分别求其Fo对于A→α△∈Si,a∈Follow(A),且A→α为文法的第j个产生式，则置：

action[Si,a]=rj

对于C→α△∈Si,a∈Follow(C),且C→α为文法的第k个产生式，则置：

action[Si,a]=rk

凡不能按上述方法填入的项均置出错。SLR(1)分析表的构造规则：

设有文法G[S],则SLR(1)分析表的构造规则为：①对于A→α△Xβ∈Si,GO(Si,X)=Sj,若X∈Vt,对于A→α△∈Si,a∈Follow(A),且A→α为文则置action[Si,X]=Sj

若X∈Vn,则置

goto[Si,X]=j②对于归约项目A→α△∈Si,若A→α为文法的第j个产生式则对于任何输入符号a,

若a∈Follow(A),则置：

action[Si,a]=rj

③对于S→α△∈Si,则置

action[Si,#]=acc

④其它情况均置出错。

对于给定的文法G，若按上述规则所构造的则置action[Si,X]=Sj

若X∈分析表不含多重定义的元素,则称文法G为SLR

(1)文法。SLR(1)分析表：

例如，文法G[S]为算术表达式的文法：

(0)S→E(1)E→E+T(2)E→T

(3)T→T*F(4)T→F(5)F→(E)

(6)F→i我们可以构造(见书P201图8-8)状态描述序列。其中，S2和S9两个项目集不相容。于是，对于S2有S2={E→T△,

T→T△*F}

下面求Follow(E)={#,+,)}，于是Follow(E)与{*}不相交。分析表不含多重定义的元素,则称文法G为SLR

(1)文法。S状态ACTIONGOTOi+*()#ETFS0S5S4123S1S6accS2r2S7r2r2S3r4r4r4r4S4S5S4823S5r6r6r6r6S6S5S493S7S5S410S8S6S11S9r1S7r1r1S10r3r3r3r3S11r5r5r5r5状态ACTIONGOTOi+*()#ETFS0S5S4123应用举例：

利用上述文法G[S]的SLR(1)分析表对输入串#i+i*i#

进行分析。8.4LR(1)分析表的构造问题的提出：

设有文法G[S’]:(0)S’→S(1)S→CbBA

(2)A→Aab(3)A→ab(4)B→C

(5)B→Db(6)C→a(7)D→a由其状态描述序列(见图8-10)可得，项目集:

S10={S→CbBA△,A→A△ab}

和项目集:应用举例：

利用上述文法G[S]的SLR(1)分析表S9={C→a△,D→a△}都是不相容的。可用LR(1)方法来解决SLR(1)仍然出现的项目集的项目不相容且Follow和First相交的问题。LR(1)分析表构造的思想：

只要输入串的已扫描部分可保持可归约成一个活前缀，那就可判定所扫描的部分未出错。LR(1)项目：

为解决SLR(1)方法无法解决的问题，我们在LR(0)项目中放置一个向前搜索的符号a，从而组成如下的形式：

[A→α△β,

a],a∈Follow(A)

S9={C→a△,D→a△}都是不相容的。可我们把这样的项目称为LR(1)项目。有效项目：对于文法G[S],项目

A→α△β

对活前缀r=δα是有效的条件：存在规范推导

SδAyδαβy,y∈Vt**r

r

①.若归约项目

A→α△

对活前缀r=δα是有效的,

则说明应把符号串α归约为A,即把活前缀δα变为δA。1).SLR(0)有效项目：我们把这样的项目称为LR(1)项目。有效项目：对于文法

②.若移进项目

A→α△β

对活前缀r=δα是有效的,

则说明句柄尚未形成，下一步动作应该是移进。说明：

①.当一个项目出现在几个不同的项目集中时,同一项目可能对好几个活前缀都是有效的。②.有可能存在这样的情形，在一个项目集中，对同一个活前缀，存在若干项目对它都是有效的，而项目集却不相容。2).LR(1)有效项目：②.若移进项目

A→α△β

对活前缀r对于文法G[S],LR(1)项目

[A→α△β,a]

对活前缀r=δα是有效的条件：存在规范推导

SδAyδαβy,y∈Vt*

且还要满足以下条件：

i).当y≠ε时，a=First(y);ii).当y=ε时，a=#。*r

r构造LR(1)分析表的思想：

对于上述例子的规范句型Cbabab,根据定义，LR(1)项目[D→a△,b]对活前缀r=Cba有效。因此，应将栈顶文法符号a归约成D，而不应归约成C。对于文法G[S],LR(1)项目

由此可见，在LR(1)分析表的构造过程中，要根据Si的项目集中的各个项目,对活前缀有效情况，来确定相应的动作。状态描述序列:

每一个状态也是由一个LR(1)项目集来表示的，每一个项目集都是由若干个对相应的活前缀有效的LR(1)项目组成。①.Si中的任何LR(1)项目都属于CLOSURE(Si);②.设有项目

[A→α△Xβ,a]∈CLOSURE(Si),X∈Vn

则[X→△η,b]∈CLOSURE(Si),η∈V*由此可见，在LR(1)分析表的构造过程中，要根据Si其中，a为已知，b=First(β)。③.重复②直到CLOSURE(Si)不再增加。注意：每一个LR(1)项目与其后继项目有相同的向前的搜索符号。注意：每一个LR(1)项目与其后继项目有相同的向前的搜索符号。如：LR(1)项目

[A→α△Xβ,a]

其后继项目

[A→αX△β,a]具有相同的向前搜索符号a。其中，a为已知，b=First(β)。③.重复②直到CLOS构造LR(1)项目的状态描述序列：设有文法G[S’]:

(0)S’→S(1)S→CbBA

(2)A→Aab(3)A→ab(4)B→C

(5)B→Db(6)C→a(7)D→aFollow(S’)={#}

Follow(S)=Follow(S’)={#}

Follow(A)=Follow(S)+First(ab)={#,a}

Follow(B)=First(A)={a}

Follow(C)=First(bBA)+Follow(B)={b,a}

Follow(D)={b}构造LR(1)项目的状态描述序列：设有文法G[S’]:

LR(1)分析表的构造规则:

对于文法G[S]，其LR(1)分析表的构造规则为：①.对于[A→α△Xβ,a]∈Si,GO(Si,X)=Sj,

若X∈Vt,则置action[Si,X]=Sj

若X∈Vn,则置

goto[Si,X]=j②.对于归约项目[A→α△,a]∈Si,

若A→α为文法的第j个产生式，则对于任何输入符号a,LR(1)分析表的构造规则:

对于文法G[S]，其L若a∈Follow(A),则置：

action[Si,a]=rj

③对于[S→α△,#]∈Si,则置

action[Si,#]=acc

④其它情况均置出错。对于给定的文法G，若按上述规则所构造的分析表不含多重定义的元素，则称文法G为LR(1)文法。LR(1)分析表的构造:

对于文法G[S’]，其LR(1)分析表的构造为：若a∈Follow(A),则置：

状态ACTIONGOTOab#SABCDS0S312S1accS2S4S3r6S4S8567S5S1110S6r4S7S9S8r6r7S9r5S10S13r1S11S12状态ACTIONGOTOab#SABCDS0S312S1ac状态ACTIONGOTOab#SABCDS12r3r3S13S14S14r2r28.5LALR(1)分析表的构造：

LALR(1)分析表的构造与LR(1)分析表的构造相似，不同之处在于LALR(1)的状态部分把若干非等价状态进行合并而已。状态ACTIONGOTOab#SABCDS12r3r3S13第8章LR(k)分析方法8.1分析方法的逻辑结构及分析过程8.2LR(0)分析表的构造8.3SLR(1)分析表的构造8.4LR(1)分析表的构造8.5LALR(1)分析表的构造第8章LR(k)分析方法8.1分析方法的逻辑结构及分析过LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读。一般来说，凡是上下文无关文法描述的程序设计语言都可以用LR方法进行有效的分析，而且还能在分析过程中及时准确地发现输入符号串的语法错误。通常的程序设计语言一般均能由LR(1)文法产生,而且能由LR(k)产生的语言也可以由LR(1)文法来产生。因此，我们通常只考虑LR(0)和LR(1)两种情况。LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次在本章中我们先后介绍LR(0),SLR(1),LR(1)和LALR(1)分析方法。8.1LR分析方法的逻辑结构及分析过程LR方法也是通过求句柄逐步归约进行语法分析。句柄在运算符优先数法中是通过运算符的优先关系而求得的；在LR方法中，则是通过求可归前缀而求得的。1.活前缀与可归前缀活前缀与可归前缀符号串的前缀是指符号串的任意首部，包括在本章中我们先后介绍LR(0),SLR(1),LR(1)空串ε。定义：对于文法G[S]，若有

Sαβ，β∈Vt*

则称α为规范前缀，也称为活前缀。r*若α是含句柄的活前缀，并且每个句柄是α的后缀或本身，则称α是可归规范前缀或可归前缀(含有句柄的活前缀)。

活前缀不含句柄之右的任何符号。是规范句型的左起部分，到当前句柄为止。如果在其右边加上终结符号串β后就可以成为一个规范句型。空串ε。定义：对于文法G[S]，若有

S’::=S S::=CbBA A::=Aab

A::=ab B::=C B::=Db

C::=a D::=a对于句子ababab有规范推导，见下面的语法树：SaS’CbABDbaba例如，设有文法G[S’]:S’::=S S::=CbBA A::=Aab

A::=a①规范句型ababab的活前缀为a，可归前缀为此a，时句柄也是a；②规范句型Cbabab的活前缀为C、Cb、Cba，

可归前缀为Cba，此时句柄为a；③规范句型CbDbab的活前缀为CbD、CbDb,可归前缀为CbDb，此时句柄为Db；④规范句型CbBab活前缀为CbB、CbBa、CbBab，可归前缀为CbBab，此时的句柄为ab;⑤规范句型CbBA的活前缀为CbBA，可归前缀为CbBA，此时亦为CbBA;⑥规范句型S的活前缀为S，可归前缀为S，此时句柄亦为S。①规范句型ababab的活前缀为a，可归前缀为此a，时句柄也又例如，设有文法G[A]：

A::=aBCbB::=BaCB::=bC::=c

对于句子abaccb。可归前缀的求法：设某文法有可归前缀

αAβ，A∈Vn

若有规则

A::=uu

∈V*

则αu也是文法的可归前缀。例如，设有文法G[S]:S::=aAc

A::=Abb

A::=b文法的所有可归前缀构成的集合称为文法的可归前缀集又例如，设有文法G[A]：

A::=aBCbB:根据上例文法对句子abbbbbc的归约过程如下：

abbbbbcaAbbbbcaAbbcaAcS△△△△其可归前缀集可用自动机来表示，称之为可归前缀图。S4S0S1S2S5S3S6baAcbc从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀；根据上例文法对句子abbbbbc的归约过程如下：

a从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀。2.LR分析方法的逻辑结构LR分析方法的逻辑结构：设有输入串a1a2a3…an，LR分析方法的逻辑结构图如下：栈顶#an…ai…a2a1#总控制器输入串S0#S1x1….…Smxm分析表输出从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可分析栈中每项都包括状态栈Si和文法符号栈xi两部分。

LR分析器包括两个部分，一个总控程序和一张分析表。不同文法的LR分析器的总控程序都是一样的，只是分析表不同，因此LR分析表是LR分析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。

LR分析的基本原理：把每个句柄(某个产生式的右部)的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每分析栈中每项都包括状态栈Si和文法符号栈xi两部分。个状态识别句柄的一部分符号。也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析工作。

由此可见，构造LR分析器的主要工作是构造分析表LR分析表的组成：LR分析表由分析动作(ACTION)表和状态转换(GOTO)表组成。1).分析动作表个状态识别句柄的一部分符号。也就是，在总控程序的控制在分析动作表中，其元素由action(si,aj)来表示。action(si,aj)表示当前分析栈的状态栈栈顶元素为si，文法符号栈栈顶元素为aj(当前输入符号)时，所执行的动作。这个动作可分为四种:移进(S)、归约(r)、接受(acc)和出错(error)。action(Sn,at)…action(Sn,a2)action(Sn,a1)Sn………action(S1,at)…action(S1,a2)action(S1,a1)S1action(S0,at)…action(S0,a2)action(S0,a1)S0at…a2a1

状态输入符号在分析动作表中，其元素由action(si,aj)来2).状态转换表goto[Sn,xe]…goto[Sn,x2]goto[Sn,x1]Sn………goto[S1,xe]…goto[S1,x2]goto[S1,x1]S1goto[S0,xe]…goto[S0,x2]goto[S0,x1]S0xe…x2x1

状态文法符号goto[si,xj]指出栈顶状态为si，文法符号为aj时应转到的下一状态。3.LR分析过程LR分析步骤：

在讲述LR的分析步骤之前，我们假设分析2).状态转换表goto[Sn,xe]…goto[Sn,x表已经成功构造。下面我们给出LR分析的具体步骤：将初始状态S0和句子的左界符#分别进分析栈中的状态栈和符号栈；根据栈顶状态和当前输入符号查动作表，然后分别做如下动作：①移进；当前输入符号进符号栈，根据状态转换表，得到的新的状态进状态栈。继续扫描，从而下一个符号变成当前输入符号。②归约；按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态栈顶n个元素同时相应退栈。归约后的文法符号进符号栈，表已经成功构造。下面我们给出LR分析的具体步骤：将初始状态S查状态转换表，得到的新状态进状态栈。③接受；分析成功，终止分析。④出错；报告出错信息。重复第2步的工作，直到接受或出错。LR分析流程图(P192图8-4)。具体分析过程

下面我们以具体的例子来说明LR方法的分析过程：设有文法G[L]：

1)L::=E,L2)L::=E

3)E::=a4)E::=b查状态转换表，得到的新状态进状态栈。③接受；分析成功，终止分上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成的所有符号串的集合。这里我们直接给出该文法的分析表(P192图8-3)。ri表示按第i个产生式进行归约；Si表示把当前输入符号移进符号栈，且第i个状态进状态栈；i表示转第i个状态，即第i个状态进状态栈；表中未填内容的空白则表示分析动作为出错。下面我们以输入串

#a,b,a#为例，具体讲述LR分析过程。上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成状态栈符号栈产生式输入符号说明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::=a#a和S3分别退栈

E和S2分别进栈状态栈符号栈产生式输入符号说明S0#a,b,a#S0和#状态栈符号栈产生式输入符号说明S0S2S5S2S5S6#E,E,LL::=E#E和S2分别退栈

L和S6分别进栈S0S2S5S6#E,LL::=E,L#E,L和S2S5S6退栈

L和S6分别进栈S0S1#L

L::=E,L#E,L和S2S5S6退栈

L和S1分别进栈acc

可见#a,b,a#符合所给的文法规则。8.2LR(0)分析表的构造LR(0)分析是当k=0时的LR(k)分析方法。在分析的每一步只要根据当前栈顶状态就能确定状态栈符号栈产生式输入符号说明S0S2S5S2S5S6#完成何种分析动作。基本概念：项目：对于文法G，其产生式右部带有特殊符号“△”，则称之为文法的一个LR(0)项目，简称项目。有时也称为配置式。

特殊符号也可以用“.”，并且要加在产生式右部的任何地方，表示一个位置。项目集：若干个项目组成的集合称为项目集，又称为配置集合。后继符号：项目中紧跟在特殊符号“△”后面的符号称为该项目的后继符号。完成何种分析动作。基本概念：项目：对于文法G，其产生式右部带后继符号表示下一时刻读到的符号。有如下两种情况：后继符号为终结符号和非终结符号例如，对应于产生式:

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后继符号为空

规定：该项目的后继符号为带有“#”的相应产生式，用来表示下一时刻将按指定的产生式进行归约。后继符号集

定义：项目集中诸项目的后继符号所组成的集合称为后继符号集。状态内容

分成是基本(BASIC)部分和闭包(CLOSURE)部分。E::=E△+T的后继符号为+

设Si是Sk关于符号X的后继状态，则求BASIC(Si)和CLOSURE(Si)的方法：1).BASIC(Si)的计算：

BASIC(Si)={A::=αX△β|A::=α△Xβ∈Sk}2).CLOSURE(Si)的计算：

①.BASIC(Si)CLOSURE(Si)；②.若A::=α△Yβ∈CLOSURE(Si),且Y∈Vn则Y::=△r∈CLOSURE(Si),r为符号串；③.重复②直到CLOSURE(Si)不再增加为止。例如，对于文法G[S]:

S::=AA::=aAbA::=c设其开始状态为S0，则求S0的状态内容。设Si是Sk关于符号X的后继状态，则求BASIC项目类型

项目类型有三类归约项目、移进项目和待归项目。①归约项目：

A::=α△此时已把分析结束，已在栈顶,从而可按相应的产生式进行归约。②移进项目：

A::=α△Xβ

，X∈Vt

此时把X移进文法符号栈。③待约项目：

A::=α△Xβ

，X∈Vn此时等待从余留的输入符号中进行归约而得到X。项目类型

项目类型有三类归约项目、移进项目和项目集的相容性

满足以下条件的项目集称为相容的项目集：①无移进项目和归约项目并处；②无多个归约项目并存。例如，项目集：

{A::=α△β,B::=α△}

{A::=α△,B::=α△}状态描述序列和状态转换图：

①.在某一状态的项目集中，不同的项目，其后状态描述序列查看完毕在状态描述序列中，必须遵守以下规则：项目集的相容性

满足以下条件的项目集称为相容

②.不同状态的项目集中，有若干个与前面对应相同的项目，其后继状态与前面相同时，则后继状态相同。例如，有文法G[S]：

(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

(6)B::=d继符号相同时，则后继状态相同；②.不同状态的项目集中，有若干个与前面对应相同的项目，其后S11#S→B{S→B△}S3S11#S→A{S→A△}S2S11#S’→S{S’→S△}S1S1

S2

S3

S5

S6S

A

B

a

a

c

d{S’→△S

S→△A

S→△B

A→△aAb

B→△aBb

A→△c

B→△d}S0后继状态后继符号项目集状态S4S11#S→B{S→B△}S3S11#S→A{S→A△}S2S11#A→aAb{A→aAb△}S8S8b{A→aA△b}S7S11#B→d{B→d△}S6S11#A→c{A→c△}S5S7

S9

S5

S6A

B

a

a

c

d{A→a△Ab

B→a△Bb

A→△aAb

B→△aBb

A→△c

B→△d}S4后继状态后继符号项目集状态S4S11#A→aAb{A→aAb△}S8S8b{A→a状态项目集后继符号后继状态S9{B→aB△b}bS10S10{B→aBb△}#B→aBbS11S11{}状态转换图由上面的状态描述序列可见，其项目集是相容的。查看相容的定义注意：对于一个文法G，若其状态描述序列中的状态项目集是相容的，则称G为LR(0)文法。LR(0)分析表的构造：状态项目集后继符号后继状态S9{B→首先，设有状态转换函数

GO(Si,X)=Sj

表示当前状态为Si，输入符号为X时的后继状态为Sj。LR(0)分析表的构造规则：

设有文法G[S],则LR(0)分析表的构造规则为：①对于A::=α△Xβ∈Si,GO(Si,X)=Sj,若X∈Vt,

则置action[Si,X]=Sj

若X∈Vn,则置

goto[Si,X]=j②对于A::=α△∈Si,若A::=α是文法的第j个产生式，则对所有的X∈Vt,均置

action[Si,X]=rj

首先，设有状态转换函数

GO(S③对于S::=α△∈Si,则置

action[Si,#]=acc

④其它情况均置出错。LR(0)分析表

设有文法G[S],则LR(0)分析表的构造规则为：状态ACTIONGOTOabcd#SABS0S4S5S6123S1accS2r1r1r1r1r1S3r2r2r2r2r2S4S4S5S679③对于S::=α△∈Si,则置

actio状态ACTIONGOTOabcd#SABS5r4r4r4r4r4S6r6r6r6r6r6

S7S8S8r3r3r3r3r3S9S10S10r5r5r5

r5r5应用举例

用上述分析表对输入串

#aacbb#

进行分析，过程如书表8-6所示。状态ACTIONGOTOabcd#SABS5r4r4r4r48.3SLR(1)分析表的构造：问题的提出：

只有当文法G的每一个状态项目集相容是才为LR(0)文法。

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

只有而LR(1)方法则是在一开始就确定向前看的符

号。SLR(1)分析表的构造方法思想：SLR(1)分析表的构造思想：

在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。例如，对于状态Si，假设其项目集为

Si={B→α△β,A→α△,C→α△}

其中β是首符号为终结符的符号串。对于归约项目：而LR(1)方法则是在一开始就确定向前看的符

号。SLR(1A→α△

C→α△

分别求其Follow(A)和Follow(C)。

对于移进项目：

B→α△β

求其First(β)。若集合Follow(A、Follow(C)、First(β)不相交，则对于任何a(a∈Vt∪{#}

)可按如下方法构造分析表就能解决冲突：对于B→α△β∈Si,a∈First(β),且GO(Si,a)=Sj则置：

action[Si,a]=Sj

A→α△

C→α△

分别求其Fo对于A→α△∈Si,a∈Follow(A),且A→α为文法的第j个产生式，则置：

action[Si,a]=rj

对于C→α△∈Si,a∈Follow(C),且C→α为文法的第k个产生式，则置：

action[Si,a]=rk

凡不能按上述方法填入的项均置出错。SLR(1)分析表的构造规则：

设有文法G[S],则SLR(1)分析表的构造规则为：①对于A→α△Xβ∈Si,GO(Si,X)=Sj,若X∈Vt,对于A→α△∈Si,a∈Follow(A),且A→α为文则置action[Si,X]=Sj

若X∈Vn,则置

goto[Si,X]=j②对于归约项目A→α△∈Si,若A→α为文法的第j个产生式则对于任何输入符号a,

若a∈Follow(A),则置：

action[Si,a]=rj

③对于S→α△∈Si,则置

action[Si,#]=acc

④其它情况均置出错。

对于给定的文法G，若按上述规则所构造的则置action[Si,X]=Sj

若X∈分析表不含多重定义的元素,则称文法G为SLR

(1)文法。SLR(1)分析表：

例如，文法G[S]为算术表达式的文法：

(0)S→E(1)E→E+T(2)E→T

(3)T→T*F(4)T→F(5)F→(E)

(6)F→i我们可以构造(见书P201图8-8)状态描述序列。其中，S2和S9两个项目集不相容。于是，对于S2有S2={E→T△,

T→T△*F}

下面求Follow(E)={#,+,)}，于是Follow(E)与{*}不相交。分析表不含多重定义的元素,则称文法G为SLR

(1)文法。S状态ACTIONGOTOi+*()#ETFS0S5S4123S1S6accS2r2S7r2r2S3r4r4r4r4S4S5S4823S5r6r6r6r6S6S5S493S7S5S410S8S6S11S9r1S7r1r1S10r3r3r3r3S11r5r5r5r5状态ACTIONGOTOi+*()#ETFS0S5S4123应用举例：

利用上述文法G[S]的SLR(1)分析表对输入串#i+i*i#

进行分析。8.4LR(1)分析表的构造问题的提出：

设有文法G[S’]:(0)S’→S(1)S→CbBA

(2)A→Aab(3)A→ab(4)B→C

(5)B→Db(6)C→a(7)D→a由其状态描述序列(见图8-10)可得，项目集:

S10={S→CbBA△,A→A△ab}

和项目集:应用举例：

利用上述文法G[S]的SLR(1)分析表S9={C→a△,D→a△}都是不相容的。可用LR(1)方法来解决SLR(1)仍然出现的项目集的项目不相容且Follow和First相交的问题。LR(1)分析表构造的思想：

只要输入串的已扫描部分可保持可归约成一个活前缀，那就可判定所扫描的部分未出错。LR(1)项目：

为解决SLR(1)方法无法解决的问题，我们在LR(0)项目中放置一个向前搜索的符号a，从而组成如下的形式：

[A→α△β,

a],a∈Follow(A