教育学LR分析法.pptx

第七章第七章 LR LR 分析法分析法 1965年，年，D.knuth首先提出了首先提出了LR(K)文法及文法及LR(K)分析技术。分析技术。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)表示在每一步分析时都不用向前输入符号表示在每一步分析时都不用向前输入符号LR(1)表示在每一步分析时都向前看一个输入符号来决定当表示在每一步分析时都向前看一个输入符号来决定当 前的动作。前的动作。SLR(1)表示简单的表示简单的LR(1)，即只在动作不唯一的地方向前看，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号。一个符号，在动作唯一时则不向前看输入符号。2）要移进时，即把要移进时，即把Xn+1进栈，并读下一符号：进栈，并读下一符号：#X1X2XiXnXn+1 Xn+2Xn+k#在栈中在栈中当前扫描符当前扫描符栈顶栈顶7.1 LR7.1 LR分析概论分析概论一一.LR分析器的逻辑结构及工作过程分析器的逻辑结构及工作过程 从逻辑上来说，一个从逻辑上来说，一个LR分析器如图分析器如图7.1 所示。所示。输入串输入串#aia1SpX1#S1S0 XmSm总总 控控 程程 序序输出输出ACTION 表表GOTO 表表其中其中S栈为状态栈栈为状态栈 X栈为符号栈栈为符号栈栈栈产生式产生式 表表图图7.1 LR分析器的逻辑结构分析器的逻辑结构 即一个即一个LR(k)分析器主要由：总控程序，分析栈（状态栈分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有和符号栈）输入队列和分析表组成。一般来说所有LR分析器分析器的总控程序基本上是大同小异。只有分析表各不相同。一般的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。主要讨论三种不同的分析表的构造方法。第一种称为规范第一种称为规范LR分析表构造法。用此法构造的分析表分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。功能最强而且也适合于很多文法，但实现代价比较高。第二种称为简单第二种称为简单LR(即即SLR)分析表构造法。这是一种比较分析表构造法。这是一种比较容易实现的方法。但容易实现的方法。但SLR分析表的功能太弱，而且对某些文法分析表的功能太弱，而且对某些文法可能根本就构造不出相应的可能根本就构造不出相应的SLR分析表。分析表。第三种称为向前第三种称为向前LR（即（即LALR）分析表构造法。这种方法）分析表构造法。这种方法构造的分析表功能介于规范构造的分析表功能介于规范LR分析表分析表SLR分析表之间。这种表分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。适用于绝大多数程序语言的文法。而且也可以设法有效的实现。二、二、LR 分析器的分析过程如下：分析器的分析过程如下：1.首先将初始状态首先将初始状态 S0及句子的左界限及句子的左界限#分别压入状态栈和符号栈中。分别压入状态栈和符号栈中。则用栈顶状态则用栈顶状态Sm和当前扫描符和当前扫描符 ai组成符号对（组成符号对（Sm,ai)去查去查分析动作表，根据分析动作表，根据ACTIONSm,ai的指示完成相应的分析动作。的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一：表中每一表元素所规定的动作仅能是下列四种动作之一：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已成为当前句型的句已成为当前句型的句柄。所谓按第柄。所谓按第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,ai=ERROR（空白）。（空白）。表明当前的输入串中含有错误，也应终止当前的分析工作。表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。转出错处理。3.重复上述第重复上述第2步的工作，直到分析栈顶出现步的工作，直到分析栈顶出现“接受状态接受状态”或或“出错状态出错状态“为止。对接受状态，分析栈的格局为：为止。对接受状态，分析栈的格局为：S0 S#Z 例：例：有文法有文法GS:1：SaAcBe e 2：Ab 3：AAb 4：Bd其其ACTION表和表和GOTO表表为：为：考察对输入串考察对输入串abbcde#的的分析过程。分析过程。r1r1r1r1r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789 S a A c B e e A b d b图图7.2 abbcde#的语法树的语法树对输入串对输入串abbcde#的分析过程为：的分析过程为：ACTION GOTO步骤步骤 状态栈状态栈 符号栈符号栈 输入流输入流 分析动作分析动作 下一状态下一状态1 0#abbcde#S2(0,a)2 02#a bbcde#S4(2,b)3 024#ab bcde#r2(4,b)GOTO2,A=34 023#aA bcde#S6(3,b)6 023#aA cde#S5(3,c)5 0236#aAb cde#r3(6,b)GOTO2,A=37 0235#aAc de#S8(5,d)8 02358#aAcd e#r4(8,d)GOTO5,B=79 02357#aAcB e#S9(7,e)10 023579#aAcBe#r1(9,#)GOTO0,S=111 01#S#acc(1,#)图图7.3 abbcde#的分析过程的分析过程LR分析过程中的性质与特点：分析过程中的性质与特点：n栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型）n当该右句型的句柄出现在栈顶时，归约，否则，移进n栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀（Viable Prefixes）7.2 LR(0)分析表的构造分析表的构造为了给出构造为了给出构造LR(0)分析表的算法，引出一些术语：分析表的算法，引出一些术语：1、规范句型的活前缀、规范句型的活前缀 前缀：前缀：一个符号串的前缀是指该串的任意首部（包括一个符号串的前缀是指该串的任意首部（包括）。）。例如例如 abc的前缀有：的前缀有：,a,ab,abc abcd的前缀有：的前缀有：,a,ab,abc,abcd 由此可知，对于符号串由此可知，对于符号串 而言，其前缀的数量为而言，其前缀的数量为+1。例：有文法例：有文法GS:SaAcBe e1 Ab2 这里在每条产生式后加上了产这里在每条产生式后加上了产 AAb3 生式的序号生式的序号i当进行推导时把当进行推导时把 Bd4 序号带上，以便说明问题。序号带上，以便说明问题。对输入串对输入串abbcde e进行推导如下（最右推导）：进行推导如下（最右推导）：S aAcBe e1 aAcd4e e1 aAb3cd4e e1 ab2b3cd4e e1由此可知，由此可知，abbcde e是该文法的句子。由于是该文法的句子。由于LR方法是自底向上的方法是自底向上的分析，故应采用归约。分析，故应采用归约。最左归约为：最左归约为：ab2b3cd4e e1 用用2式归约式归约 aAb3cd4e e1 3 aAcd4e e1 4 aAcBe e1 1 S其中其中表示归约符表示归约符 从归约的过程可看出，每次归约时，归约前和归约后的被从归约的过程可看出，每次归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前面部分；产生式归约仅取决于当前句型的前面部分；X1X2Xnp 其中其中Xi为文法的符号，为文法的符号，p为第为第p个产生式序号。个产生式序号。如上例中每次归约前句型的前面部分为：如上例中每次归约前句型的前面部分为：ab2 aAb3 aAcd4 aAcBe e1我们把规范句型的这种前端部分的串称为可归我们把规范句型的这种前端部分的串称为可归前缀。实际上，它们恰好是符号栈栈顶形成句前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。柄时符号栈中的内容。SaAcBee1Ab2AAb3Bd4 这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约之故。所以我们将把规范句型具有上述性质（即不含句柄之后的之故。所以我们将把规范句型具有上述性质（即不含句柄之后的任何符号）的前缀称之为任何符号）的前缀称之为可归前缀可归前缀。对各规范句型有前缀：对各规范句型有前缀：ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1 ,a,aA,aAc,aAcB,aAcBe可以发现前缀可以发现前缀a,ab,aA,aAc是多个规范句型的前缀，因此我们可进是多个规范句型的前缀，因此我们可进一步一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀把形成可归前缀前和形成可归前缀时的所有规范句型的前缀都称为都称为活前缀活前缀。可归前缀：可归前缀：是指规范句型的一个前缀，这种前缀包含句柄且不是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。含句柄之后的任何符号。活前缀：活前缀：可归前缀的任意首部。特指在分析过程中对于在栈顶可归前缀的任意首部。特指在分析过程中对于在栈顶形成句柄之前和恰好形成句柄时，每一步中形成句柄之前和恰好形成句柄时，每一步中符号栈中的那些符符号栈中的那些符号组成的符号串号组成的符号串。活前缀定义：活前缀定义：在前面例中对输入串在前面例中对输入串abbcde的归约分析过程中，在规范归约的归约分析过程中，在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串均过程中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，它表明输入串的已被分析过的部分是该文为规范句型的活前缀，它表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。法某规范句型的一个正确部分。由此可形式地定义活前缀如下：由此可形式地定义活前缀如下：定义定义 7.1：若：若S *A 是是 文法文法G中的一个规范推导，中的一个规范推导，如果符号串如果符号串 是是的前缀，则称的前缀，则称 是是G的一个活前缀。的一个活前缀。其中其中 S为为文法开始符号。文法开始符号。RRLRLR分析分析n分析过程可以看作是识别文法规范句型活前缀的过程。n只要每一时刻栈中的文法符号串是某规范句型的活前缀，则说明已分析的部分是正确的n一个文法的规范句型的所有活前缀构成一个语言，而且是正规语言，可以用一个 DFA 来识别n例子：文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d014235769SabAbcBed8*n每个状态都是活前缀的识别态，双圈状态是可归前缀（句柄）识别态，标识了*的状态是句子识别态分析句子的过程可以看作在上面这个 DFA 上运行的过程014235769SabAbcBed8*(1)S aAcBe(2)A b(3)A Ab(4)B dn例子：步骤栈输入串ACTIONGOTO1#0abbcde#S2014235769SabAbcBed*8n例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S4014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R23014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S6014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R33014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO3#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S5*014235769SabAbcBed8n例子：步骤栈输入串ACTIONGOTO4#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S8*014235769SabAbcBed8n例子：步骤栈输入串ACTIONGOTO5#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R47014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO6#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S9014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO7#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R11014235769SabAbcBed8*n例子：步骤栈输入串ACTIONGOTO8#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R1111#0S1#Acc014235769SabAbcBed8*2、LR（0）项目）项目 由上述分析和定义可知，活前缀与句柄间的关系不外乎下由上述分析和定义可知，活前缀与句柄间的关系不外乎下述述 三种情况：三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最后符号就是活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。活前缀的最后符号）。（2）活前缀中只含有句柄的前部分符号（句柄的最左子串活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。为活前缀的最右子串）。（3）活前缀中全然不包含句柄的任何符号。活前缀中全然不包含句柄的任何符号。第一种情况表明：第一种情况表明：此时某一产生式此时某一产生式A的右部的右部已出现在符号已出现在符号栈顶，因此此时相应的分析动作应当是用此产生式进行归约。栈顶，因此此时相应的分析动作应当是用此产生式进行归约。第二种情况表明：第二种情况表明：形如形如A 1 2的产生式的的产生式的 右部子串已在符号右部子串已在符号栈栈顶，如栈栈顶，如 1，正期待着从余留的输入串中看到能由正期待着从余留的输入串中看到能由推出的推出的 符符号串，即期待号串，即期待 2 进栈以便能进行归约。故此时分析动作是进栈以便能进行归约。故此时分析动作是“移移进进”当前输入符号。当前输入符号。第三种情况则意味着：第三种情况则意味着：期望从余留输入串中能看到由某产生式期望从余留输入串中能看到由某产生式A 的右部，即的右部，即 所代表的符号串所代表的符号串(即句柄即句柄)。所以此时分析的。所以此时分析的动作也是读输入符进符号栈。动作也是读输入符进符号栈。为了刻画在分析过程中，文法的一个产生式右部符号串有多大为了刻画在分析过程中，文法的一个产生式右部符号串有多大部分已被识别，我们可在该产生式的右部相应位置上加一个圆点部分已被识别，我们可在该产生式的右部相应位置上加一个圆点“.”，来指示位置，标明在，来指示位置，标明在“.”前的部分已被识别。如上述三前的部分已被识别。如上述三种情况，可分别标注为：种情况，可分别标注为：A.；A 1.2 ;A.。我们把右部某位置上标有圆点的产生式称为相应文法的一个我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别地，对形如项目。特别地，对形如A 的产生式，相应的的产生式，相应的LR(0)项目项目表示为表示为A.。显然不同的显然不同的LR(0)项目，反映了分析过程中符号栈项目，反映了分析过程中符号栈顶的不同情况。顶的不同情况。例如：产生式例如：产生式SaAcBe对应有六个项目。对应有六个项目。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe.例如：产生式例如：产生式SaAcBe对应有六个项目。对应有六个项目。0 S.aAcBe1 Sa.AcBe2 SaA.cBe3 SaAc.Be4 SaAcB.e5 SaAcBe.一个产生式可对应的项目的数量为它的右部符号串长度加一个产生式可对应的项目的数量为它的右部符号串长度加1，值得注意的是对空产生式，即，值得注意的是对空产生式，即A仅有项目仅有项目A.每个项目的含义与圆点的位置有关。概括地说，圆点左边的每个项目的含义与圆点的位置有关。概括地说，圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。过的部分，圆点右边的子串表示待识别的部分。文法的全部文法的全部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 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)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d如前所述，由于不同的项目反映了分析过程中栈顶的不同情况，如前所述，由于不同的项目反映了分析过程中栈顶的不同情况，因此，我们可根据它们不同的作用，将一个文法的全部因此，我们可根据它们不同的作用，将一个文法的全部LR(0)项目项目进行分类：进行分类：n移进项目：A an待约项目：A Bn归约项目：A n接受项目：S S 圆点的左部表示分析过程中的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别部分4、构造识别活前缀的、构造识别活前缀的DFA 在在LR方法实际过程中，并不是去直接分析符号栈中的符号方法实际过程中，并不是去直接分析符号栈中的符号是否已形成句柄，但它给我们一个启示，我们可以把是否已形成句柄，但它给我们一个启示，我们可以把终结符和非终结符和非终结符终结符都可看成一个有限自动机的都可看成一个有限自动机的输入符号输入符号，每把一个符号进栈，每把一个符号进栈时看成已识别过该符号，而状态进行转换（到下一状态），当识时看成已识别过该符号，而状态进行转换（到下一状态），当识别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句柄的柄的终态终态。在作出文法的全部在作出文法的全部LR(0)项目之后，现在将用它们来构造识别项目之后，现在将用它们来构造识别全部活前缀的全部活前缀的DFA。这种。这种DFA中的中每一个状态由若干个中的中每一个状态由若干个LR(0)项目所组成的集合（称为项目集）来表示。项目所组成的集合（称为项目集）来表示。下面以上例中的文法为例来下面以上例中的文法为例来说明构造说明构造DFA的方法。的方法。G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d首先我们用首先我们用I I0 0表示这个表示这个DFADFA的初态，它的初态，它预示着整个分析过程的开始，并且期待着将预示着整个分析过程的开始，并且期待着将给定的输入串逐步归约为文法的开始符号给定的输入串逐步归约为文法的开始符号SS。或者反过来说，我们所期待的是，从使用产或者反过来说，我们所期待的是，从使用产生式生式SSSS开始，能够逐渐推导出所给定的开始，能够逐渐推导出所给定的输入串。因此，我们应将项目输入串。因此，我们应将项目S.SS.S列入项列入项目集目集I I0 0之中。换言之，也就是我们正期待将之中。换言之，也就是我们正期待将要扫描的输入串正好就是能由要扫描的输入串正好就是能由SS推导出的任推导出的任何终结符串。何终结符串。然而，我们不能从输入串中直然而，我们不能从输入串中直接读出非终结符号接读出非终结符号S S，因此我们也应将项目，因此我们也应将项目S.AS.A和和S.BS.B加入加入I I0 0中。由于中。由于A A和和B B同样是非同样是非终结符，所以也应将终结符，所以也应将A.aAbA.aAb和和A.cA.c和和B.aBb,B.dB.aBb,B.d加入加入I I0 0中。中。G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d 由于最后加入由于最后加入I I0 0的项目在圆点之后已都是终结符了，故的项目在圆点之后已都是终结符了，故I I0 0已经已经“封闭封闭”，宣告项目集，宣告项目集I I0 0构造结束。构造结束。这样，表示初态的项目集这样，表示初态的项目集I I0 0将由如下项目组成：将由如下项目组成：I I0:S.S,S.A,S.B,A.aAb,A.c,0:S.S,S.A,S.B,A.aAb,A.c,B.aBd,B.d B.aBd,B.dI I0:S.S,S.A,S.B,A.aAb,A.c,B.aBd,B.d 我们将我们将LR(0)项目项目S.S称为称为项目集项目集I I0的基本项目的基本项目，上述从，上述从S.S出发构造项目集出发构造项目集I I0的过程，可用一个对其基本项目集的过程，可用一个对其基本项目集S.S的闭包运算，即的闭包运算，即closure(S.S)来表示。来表示。一般地，设一般地，设I为项目集，为项目集，I的闭包的闭包closure(I)的定义为：的定义为：Closure(I)=IA.A GK .A closure(I)V*V*故构造故构造closure(I)的算法为：的算法为：1）I中的每一个项目都属于中的每一个项目都属于closure(I);2）若形如）若形如K.A 的项目属于的项目属于I，且，且A 是文法的一个产生式，是文法的一个产生式，则关于产生式则关于产生式A的任何形如的任何形如A.的项目也应加到的项目也应加到closure(I)中中 （若它们不在（若它们不在closure(I)中）；中）；3）重复上述过程，直至不再有新的项目加入到）重复上述过程，直至不再有新的项目加入到closure(I)中为中为 止。止。有了初态项目集有了初态项目集I0之后，我们来说明如何确定从之后，我们来说明如何确定从I0可能转移可能转移到的下一状态。设到的下一状态。设A为一文法符号为一文法符号(AV)，若，若I0中有圆点位于中有圆点位于A左边的项目左边的项目K .A(其中其中 可能为可能为)，则当分析器从输入串识，则当分析器从输入串识别出别出(即移进或归约出即移进或归约出)文法符号文法符号A后，分析器将进入它的下一状后，分析器将进入它的下一状态。设此状态为态。设此状态为Ii，显然，显然Ii中必含有全部形如中必含有全部形如K A.的项目，的项目，我们将这样的项目称为我们将这样的项目称为K .A 的的后继项目后继项目。对于每一个文。对于每一个文法符号法符号A，如果存在这样的后继项目，则可能不只一个，设其组，如果存在这样的后继项目，则可能不只一个，设其组成集合成集合J，则，则J中的每个项目都是项目集中的每个项目都是项目集Ii的基本项目，因此，按的基本项目，因此，按照与上面构造项目集照与上面构造项目集I0相类试的讨论，我们有：相类试的讨论，我们有：Ii=closure(J)为了指明为了指明Ii是是“I0关于文法符号关于文法符号A的后继状态的后继状态”这一事实，这一事实，我们可定义一个状态转移函数：我们可定义一个状态转移函数：GO(I0,A)=closure(J)=Ii 其中，其中，I是当前状态，是当前状态，A为文法符号，为文法符号，J是是I中所有形如中所有形如K.A 的项目之后继项目的项目之后继项目K A.所组成的集合，而所组成的集合，而closure(J)就是就是项目集项目集I（即状态（即状态I)关于符号关于符号A的后继项目集（即后继状态）。的后继项目集（即后继状态）。状态转移函数：状态转移函数：GO(I0,A)=closure(J)=Ii 其中，其中，I是当前状态，是当前状态，A为文法符号，为文法符号，J是是I中所有形如中所有形如K.A 的项目之后继项目的项目之后继项目K A.所组成的集合，而所组成的集合，而closure(J)就是项目就是项目集集I（即状态（即状态I)关于符号关于符号A的后继项目集（即后继状态）。的后继项目集（即后继状态）。即：即：GO(I,A)=closure(所有形如所有形如K A.的项目的项目 K .A I)对于上例，我们有：对于上例，我们有：I1=GO(I0,S)=closure(SS.)I1:SS.;I2=GO(I0,A)=closure(SA.)I2:SA.;I3=GO(I0,B)=closure(SB.)I3:SB.;I4=GO(I0,a)=closure(Aa.Ab,Ba.Bd)G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B dI4: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.此时，我们求出了此时，我们求出了I0的全部后继项目集的全部后继项目集I1,I2,I3,I4,I5,I6,而而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)=closure(Ac.)=I5 GO(I4,d)=closure(Bd.)=I6 这些项目集均不产生新的项目集。另外还有这些项目集均不产生新的项目集。另外还有:G：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d 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)项目集规范族项目集规范族,C=(I0,I1,I10);V M的字母表，即的字母表，即V=S,S,A,B,a,b,c,d；GOM的映射函数，即上面定义的状态转移函数的映射函数，即上面定义的状态转移函数GO；I0M的唯一初态；的唯一初态；ZM的终态集，的终态集，Z C，为规范族中所有含有归约项目的，为规范族中所有含有归约项目的 那些项目集。那些项目集。DFA:I0:S.S S.A S.B A.aAb A.c B.aBd B.dI1:SS.I2:SA.I3:SB.I4:Aa.Ab Aa.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 dacSABaG：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B d图图7.4 文法文法GS项目集规范族项目集规范族DFA:即：即：I0I1I2I3I4I5I6I7I9I8I10SABacdcdABbdG：(0)SS (1)S A (2)S B (3)A aAb (4)A c (5)B aBd (6)B da图图7.5 识别文法识别文法GS活前缀的活前缀的DFA5、LR(0)分析表的构造分析表的构造 对于一个文法对于一个文法G的拓广文法的拓广文法G，当识别它的全部活前缀的，当识别它的全部活前缀的DFA作出之后，我们可以据此构造相应的作出之后，我们可以据此构造相应的LR(0)分析表了。分析表了。然而，要注意的是，用前述方法所构造的每一个然而，要注意的是，用前述方法所构造的每一个LR(0)项目集项目集实质上表征了在分析过程中可能出现的一种分析状态；再根据前实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，就要求每一个项目集中的的诸项目应当是相动作相关联，因此，就要求每一个项目集中的的诸项目应当是相容的。所谓相容，是指在一个项目集中不出现下列的情况：容的。所谓相容，是指在一个项目集中不出现下列的情况：（1）移进项目和归约项目并存，即存在移进）移进项目和归约项目并存，即存在移进归约冲突；归约冲突；（2）多个归约项目并存，即存在归约）多个归约项目并存，即存在归约归约冲突。归约冲突。如果一个文法如果一个文法G满足上述条件，也就是它的每个满足上述条件，也就是它的每个LR(0)项目集项目集中都不含有冲突的项目，则称中都不含有冲突的项目，则称G为为LR(0)文法。文法。显然，只有当一个文法是显然，只有当一个文法是LR(0)文法时，才能对它构造不含冲文法时，才能对它构造不含冲突动作的突动作的LR(0)分析表来。分析表来。为了方便起见，我们用整数为了方便起见，我们用整数0，1，2，表示状态表示状态I0,I1,I2,;分析表的内容由两部分组成，一部分为动作分析表的内容由两部分组成，一部分为动作(ACTION)表，它表，它表示当前状态下所面临的输入符号应做的动作是移进、归约、接表示当前状态下所面临的输入符号应做的动作是移进、归约、接受或出错。另一部分为状态转移（受或出错。另一部分为状态转移（GOTO)表，它表示在当前状态表，它表示在当前状态下面临文法符号时应转向的下一个状态，相当于识别活前缀的有下面临文法符号时应转向的下一个状态，相当于识别活前缀的有限自动机限自动机DFA的状态转换矩阵。分析表的行标为状态号，动作表的状态转换矩阵。分析表的行标为状态号，动作表的列标为只包含终结符和的列标为只包含终结符和“#”；状态转移表的列标为；状态转移表的列标为非终结符非终结符，而将其有关终结符的各列并入到而将其有关终结符的各列并入到ACTION表的各列中去，也就是表的各列中去，也就是把当前状态下面临终结符应作的动作和状态转移用同一数组元素把当前状态下面临终结符应作的动作和状态转移用同一数组元素表示表示，以便节省存储空间。，以便节省存储空间。构造构造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.属于属于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 R5 构造构造LR(0)分析表的算法为：分析表的算法为：(1)对于每一项目集对于每一项目集Ii中形如中形如A.X 的项目，且有的项目，且有GO(Ii,X)=Ij,若若