第7章 LR分析技术

第七讲LR分析,本章学习目标,LR(k)分析器是这样一种分析程序：它总是按从左到右的方式扫描输入串，并按照自底向上的方式进行归约。在这种分析过程中，它至多向前查看k个输入符号就能确定当前的动作是移进还是归约。本章要点：LR分析的基本原理LR（0）分析表的构造SLR（1）分析表的构造LR（1）分析表的构造LALR（1）分析表的构造,LR分析,LR含义自左而右扫描、最右推导的逆过程。注：一般地说，大多数用上下文无关文法描述的程序设计语言均可用LR分析器予以识别。LR分析法的优点（1）与算符优先分析法或其它的“移进-归约”技术相比，适应范围更加广泛，能力更强，而识别效率并不比它们差。（2）与普通不带回溯的自上而下预测技术相比也要好（3）在自左向右扫描输入串时就能发现其中的错误，并能准确地指出出错位置。LR分析法的缺点若用手工构造分析程序，则工作量太大，而且容易出错，因此，必须使用自动产生这种分析程序的产生器。,LR分析的概述,一个LR分析器由三部分组成：（1）总控程序，也称为驱动程序。对所有的LR分析器总控程序是相同的。（2）分析表或分析函数。不同的文法其分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两部分,都用二维数组表示。（3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作由栈顶状态和当前输入符号所决定。,SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态栈的内容按关系GOTOSi，X=Sj。其中X为终结符或非终结符。,图6-1LR分析器的工作过程,ACTIONSi,a规定了栈顶状态为Si时遇到输入符号a应该执行的动作。动作有4种可能：（1）移进：当Sj=GOTOSi,a成立，则把Sj移入到状态栈，把a移到文法符号栈，其中i和j表示状态。（2）归约：当在栈顶形成句柄为时，则用归约为相应的非终结符A，即当文法中有A的产生式，当的长度为（即|=）时，则从状态栈和文法符号栈中自栈顶向下去掉个符号，即栈指针SP减去；并把A移入文法符号栈，再把满足Sj=GOTOSi,A的状态移进状态栈，其中Si为修改后指针的栈顶状态。（3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则分析成功。（4）报错：当遇到状态为某一个状态下出现不该遇到的文法符号栈时，则报错。说明输入串不是该文法能接受的句子。,我们主要是关心的问题是:如何由文法构造LR分析表?对于一个文法，如果能构造一张分析表，使得它的每一个入口均是惟一确定的，则称这个文法是LR文法。对于一个LR文法，当分析器对输入串进行自左向右扫描时，一旦句柄呈现在栈顶，就能及时的对它实行归约。在有些情况下，LR分析器需要“展望”和实际检查未来的k个输入符号才能决定对应采取什么样的“移进归约”决策。一般而言，一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法称为LR(k)文法。,LR(0)分析,LR(0)语法分析方法是其他构造LR分析的基础。给出文法：（1）SaAcBe（2）Ab（3）AAb（4）Bd,可归前缀和子前缀,为了使最右推导和最左规约关系更加清楚，在推导过程中加入额外信息（1）SaAcBe1（2）Ab2（3）AAb3（4）Bd4根据这个文法对输入串abbcde进行判断，形成如下的推导过程。SaAcBe1aAcd4e1aAb3cd4e1ab2b3cd4e1它的逆过程最左归约（规范归约）则为：ab2b3cd4e1用产生式（2）归约aAb3cd4e1用产生式（3）归约aAcd4e1用产生式（4）归约aAcBe1用产生式（1）归约S,从这里可以看出对于一个合法的句子而言，每次归约后得到的都是已归约部分和输入剩余部分合起来构成文法的规范句型。而用哪个产生式继续归约仅取决于当前句型的首部。例中每次归约前的句型的首部依次为：ab2aAb3aAbcd4aAcBe1这些符号正是在归约之前栈中的符号。当栈中出现上述的符号串时，就采用相应的产生式进行归约，把规范句型的首部称为可归前缀。,我们再分析每个首部的前缀：ab2的前缀有,a,abaAb3的前缀为,a,aA,aAbaAbcd4的前缀为,a,aA,aAb,aAbc,aAbcdaAcBe1的前缀为,a,aA,aAc,aAcB,aAcBe我们把在规范句型中形成可归前缀之前包括可归前缀在内的所有的前缀称为活前缀。在规范归约的任何时刻，只要已分析过的部分即在符号栈内的符号串均为规范句型的活前缀，则表明输入串的已分析过的部分是该文法某规范句型的正确部分。,拓广文法,引入一新非终结符作为文法的新开始符，添加一新产生式：SS:S为新开始符，S为原来的开始符号。拓展文法的目的：使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。,识别活前缀的有限自动机,定义6.1若SA是文法G的拓广文法G中的一个规范推导。符号串是的前缀，则称是G的一个活前缀。也就是说是规范句型的前缀，但是它的右端不超过该句型句柄的末端。根据定义，一旦=出现在符号栈中，则形成句柄，就用产生式A进行归约。在LR分析过程中，并不是直接分析文法符号栈中的符号是否形成句柄。而是分析符号栈中所有符号组成的符号串是否形成可归前缀.我们把终结符和非终结符都看成一个有限自动机的输入符号，每有一个符号进栈，就认为自动机识别一个符号，而状态进行了转换。当识别到了可归约前缀时，相当于在栈顶形成了句柄，则认为到达识别句柄的终态。,我们将上面的文法进行拓广，文法表示成：（0）SS0（1）SaAcBe1（2）Ab2（3）AAb3（4）Bd4现对句子abbcde的可归约前缀列出：S0ab2aAb3aAbcd4aAcBe1构造出识别其活前缀的自动机如图所示。,将该不确定的自动机确定化如图所示。将该确定的有穷自动机的状态作为LR(0)分析表的状态，就可以画出LR(0)分析表,活前缀及其可归前缀的一般方法,设G=（VN，VT，P，S）是一个上下文无关文法，对于AVN有LC(A)=a|S=*RA,V*T其中S是G的拓广文法G的开始符号LC（A）表明了在规范推导中在非终结符A左边所出现的符号串的集合。推论:若文法中有产生式BA则有LC(A)包含LC(B).因为对任何一步推导S=*RB=RA,（0）SS（1）SaAcBe（2）Ab（3）AAb（4）Bd,（0）SE（1）EaA（2）EbB（3）AcA（4）Ad(5)BcB(6)Bd,LR(0)项目集规范族的构造1LR(0)项目的定义文法G的每个产生式的右部的某个位置添加一个“”。例如，产生式Axyz包含4个项目：AxyzAxyzAxyzAxyz而空产生式A，只有一个项目A。直观地说，一个项目指明了在分析过程的某一个时刻一个产生式的状态，例如，上面的第一个项目指明，希望看到可从xyz推出的符号串；第二个项目则指明，已经看到了能从x推出的符号串，但希望进一步看到可以从yz推出的符号串。,采用项目的方法构造有限自动机,LR项目的分类,我们可以根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种。移进项目:形如Aa，其中和V*，aVT，即圆点后面为终结符的项目为移进项目，对应的状态为移进状态，分析时把a移进符号栈。待约项目:形如AB，其中和V*，BVN，即圆点后面为非终结符的项目为待约项目。它表明所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A的右部。归约项目:形如A，其中V*，即圆点在最右端的项目称为归约项目。它表明一个产生式的右部已分析完成，句柄已形成，可以归约。接受项目:形如S，其中V+，S为拓广文法，S为左部的产生式只有一个，因而它是归约项目的特殊情况，对应的状态为接受状态。我们规定S为初态。实际上接受项目中的为文法的开始符号。,2构造识别活前缀的NFA,文法SEEaA|bBAcA|dBcB|d,该文法的项目有：1SE10Ad2SE11EbB3EaA12EbB4EaA13EbB5EaA14BcB6AcA15BcB7AcA16BcB8AcA17Bd9Ad18Bd,根据项目构造识别活前缀的NFA和DFA将项目的编号作为自动机的状态，在构造识别活前缀的NFA时，遵循如下的原则，即假设有一个项目i为：XX1X2Xi-1XiXn而项目j为：XX1X2Xi-1XiXi+1Xn那么从状态i到状态j连一条标记为Xi的弧。如果Xi是非终结符，则也会有以它为左部的有关项目以及相应的状态，比如：iXAkA则从状态i画标记为的箭弧到达状态k，箭弧上标记为,采用文法的项目集规范族构造有限自动机,对于构造识别一个文法活前缀的DFA项目集的全体称为这个文法的LR(0)项目集规范族。我们可以用一种简单直观的方式构造项目集规范族。1LR（0）项目集规范族的构造（1）CLOSURE（I）函数如果I是文法G的任一个项目集，那么定义和构造I的闭包CLOSURE（I）规则如下：1)I的任何项目也属于CLOSURE（I）。2)若AB属于CLOSURE（I）；若有B，则将B加到CLOSURE(I)中，此时，称AB为该闭包的核。3)重复2）上述步骤，直到CLOSURE(I)不在增大为止。,例如给出拓广文法：SEEaA|bBAcA|dBcB|d假定I0=SE，那么CLOSURE(I)包含的项目如下：SEEaAEbB,我们很容易构造出初态的闭包，有了初态的项目集，其他状态的项目集如何求出？由初态出发对其项目集的每个项目的圆点向右移动一个位置用箭弧转向不同的新状态，箭弧上用移动圆点经过的符号标记。新状态的初始项目为核，对核求闭包就是新状态的项目集。定义一个函数：GOTO（I，X）=CLOSURE（J）X为一文法符号，X为终结符或非终结符J为所有形如AX的项目且AXI,给出拓广文法：SEEaA|bBAcA|dBcB|d设I=SE，EaA,EbA那么项目集规范族：,GOTO(I，E):SE,GOTO(I，a):EaAAcAEd,GOTO(I，b):EbBBcBBd,LR(0)项目集规范族,项目集规范族的构造步骤如下：置项目SS为初态集的核，然后对核求闭包，CLOSURE(SS)得到初态的项目集。对初态集或其他所构造的项目集中每个项目应用转换函数GOTO(I，X)=CLOSURE(J)，求出新状态J的项目集。重复（2）直到不再出现新的项目集为止。,给出文法：SA|BAaAb|cBaBb|d将该文法拓广为：（0）SS（1）SA（2）SB（3）AaAb（4）Ac（5）BaBb（6）Bd根据CLOSURE(I)函数设计出项目集规范族。,令I0=CLOSURE(SS)得到项目集规范族为:I0:SSSAAaAbAcSBBaBbBd考察I0的每一个项目中“”后面就是一个要识别的符号，则令X=S，A，B，a,c,d利用GOTO（I0,X）,可以得到I0的后继项目集为：,I1=GOTO(I0,S)=CLOSURE(SS)I2=GOTO(I0,A)=CLOSURE(SA)I3=GOTO(I0,B)=CLOSURE(SB)I4=GOTO(I0,a)=CLOSURE(AaAb,BaBb)=AaAbAaAbAcBaBbBaBbBdI5:AcI6:BdI4=GOTO(I4,a)=CLOSURE(AaAb,BaBb)I7=GOTO(I4,A)=CLOSURE(AaAb)=AaAbI9=GOTO(I4,B)=CLOSURE(BaBb)=BaBbI8=GOTO(I7,b)=CLOSURE(AaAb)=AaAbI10=GOTO(I9,b)=CLOSURE(BaBb)=BaBb,根据DFA构造文法的LR(0)分析表,LR(0)分析表是LR(0)分析器的重要组成部分。它是总控程序分析动作的依据。对于不同的文法，LR(0)分析表不同。它是一个二维数组，行号表示状态号，列号为文法符号和“#”号，分析表的内容为两部分，一部分为ACTION表，它表示当前状态下所面临的输入符应做的动作是移进、归约、接受还是出错。动作表的行标号只包含终结符和“#”。另一部分为转换表，它表示在当前状态下面临文法符号时应转向的下一个状态。假设已经构造出了识别活前缀的DFA，根据DFA构造文法的LR(0)分析表，构造步骤如下：C=I0,I1,I2,In其中Ik为项目集的名字，令包含SS项目的集合Ik的下标为分析标的初始状态。那么分析表的,ACTION和GOTO表的构造步骤为：若项目为Aa属于Ik，且转换函数GO(Ik，a)=Ij，当a为终结符时置ACTIONk,a为Sj，其动作的含义为终结符a移进符号栈，状态j进入状态栈，相当于状态k时遇到a转向状态j。若GOTO(Ik，A)=Ij，则置GOTO（k，A）为“j”，其中A为非终结符，表示当前状态为k，遇到文法符号A时，状态应转向j，因此A移入文法符号栈，j进入到状态栈。若项目A属于Ik，则对于任何终结符和“#”置ACTIONk,a和ACTIONk,#为“rj”，j为在文法G中某产生式A的序号。rj动作的含义是把当前文法符号栈顶的符号串归约为A，并将栈顶向下移动|a|的长度，符号栈中弹出|a|个符号，非终结符A变为当前面临的符号。若项目SS属于Ik，则置ACTIONk,#为“acc”，表示接受。凡不能用上述方法添入的分析表的元素，均应该添上“报错标志”，在表中用空白来表示。这样构造出的分析表为LR(0)分析表。,构造LR（0）分析表,步骤小结(1)写出给定文法G的拓广文法G。(2)写出文法G的基本LR(0)项目G的LR(0)项目集。(3)利用CLOSURE和GOTO函数，求出相应的项目集规范族。(4)构造识别该文法的全部活前缀的DFA。(5)根据算法构造LR(0)分析表。,已知文法，试构造该文法的LR(0)分析表.SBBBaB|b将该文法拓广为文法：(0)SS(1)SBB(2)BaB(3)Bb写出该文法的所有的项目集，构造出DFA.,SLR(1)分析,LR(0)文法项目集规范族的冲突前面我们介绍了LR(0)分析表的构造。项目集规范族中项目的类型，不外乎以下几种：移进项目、归约项目、待约项目和接受项目。一个项目集规范族可能包含以上4种不同的项目，但是一个项目集中不能有下列情况存在：（1）移进和归约同时存在。Aa,B这时由于面临输入符号为a时不能确定是移进a还是把归约为B,因为LR(0)分析是不向前看符号，所以对于归约的项目不管当前符号是什么都应该归约。对于同时存在移进和归约项目的称为移进归约冲突,2）归约和归约项目同时存在。设在文法的项目集规范族中含有以下形式的项目。AB不管面临的是什么输入符号都不能确定归约为A，还是归约为B。对于同时存在两个以上项目的状态称为归约归约冲突。当一个文法的LR(0)项目集规范族不存在移进归约和归约归约冲突时，称这个文法为LR(0)文法。,SLR(1)分析表的构造,问题的提出给出文法：real，ii将该文法缩写并拓广如下：（0）SS（1）SrD（2）DD，i（3）Di构造该文法的LR(0)项目集规范族如表：LR(0)分析表族,在该文法中就会发现在状态I3中含有冲突的项目：SrDDD，i设计出该文法的LR(0)分析表如表所示：,解决LR(0)分析方法中冲突问题的方法,1解决冲突的方法假设在LR(0)的项目集规范族中有如下的项目集状态I：I=Xb,A,B也就是说在项目集中含有移进归约和归约归约冲突。其中，为文法的符号串，b为终结符。则要求满足如下的条件才能用SLR(1)分析方法进行分析。FOLLOW（A）FOLLOW（B）=FOLLOW（A）b=FOLLOW（B）b=,那么当在状态I面临输入符号为a时，填写在分析表中的动有以下的规定决策。1)面临输入符号为a=b时，则移进。2)若aFOLLOW（A），则用产生式A进行归约。3)若aFOLLOW（B），则用产生式B进行归约如果是其它种情况就报错。,将上述的项目集规范族的情况广而推之，则假设某个文法的项目集中有如下的状态：I=A11b11,A22b22，Ammbmm，B11，B22，Bnn要求满足的条件为：只要集合b1，b2，bm和FOLLOW（B1），FOLLOW（B2），FOLLOW（Bn）两两不相交可以通过考察当前输入符号来决定动作1)面临输入符号为ab1，b2，bm时，则移进。2)若aFOLLOW（Bi），则用产生式Bi进行归约。3)此外，报错。对于一个文法的LR(0)项目集规范族的某些项目冲突可以用上述方法解决，称这个文法为SLR(1)文法。,SLR(1)分析表的构造,2构造SLR(1)分析表的步骤假设已构造出文法的LR（0）项目集和计算出所有的非终结符的FOLLOW集合。设项目集规范族为：C=I0,I1,In，其中Ik为项目集的名字，k为状态号，SS所在的项目集的状态为初始状态。求出所有的非终结符的FOLLOW集合。则ACTION和GOTO表的构造步骤为：）若项目Aa属于Ik，且转换函数GO(Ik，a)=Ij，当a为终结符时，则置ACTIONk,a为Sj。2)若项目A属于Ik，则对a为任何终结符或“#”，且满足aFOLLOW(A)时，置ACTIONk,a=rj,j为产生式A在文法中的编号。3)若GO(Ik，A)=Ij，则置GOTOk,A=j，其中A为非终结符，j为某一个状态号。4）若项目SS属于Ik，则置ACTIONk,#=acc，表示接受。5)凡不能用上述方法填入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,给出文法EEEE+T|TTT*F|FF（E）|id采用SLR(1)的分析方法，给出符号串i+i*i#进行分析时栈的变化过程。（1）写出该文法的项目集规范族。,（2）找出该项目集规范族中的冲突,不难看出，存在三个项目集规范族的冲突。在I1中有：EE，EE+T，两个项目就是一个移进归约的冲突，该表达式的文法不是LR(0)文法，因此不能构造LR(0)分析表。考察该冲突是否可以用SLR(1)来进行分析。FOLLOW(E)=#+=，因此I1中的冲突可以解决。在I2中的冲突为：ET和TT*F，该项目集有移进归约冲突。FOLLOW(E)=+，），#+，），#*=在I9中的冲突为：EE+T和TT*F，该冲突为移进归约冲突FOLLOW(E)=+，），#+，），#*=所以该文法能够解决冲突。,写出该文法的分析表如表所示：,LR(1)分析,LR（1）分析的提出SLR(1)分析中，解决移进和归约冲突的条件是：假设在LR(0)的项目集规范族中有如下的项目集状态I如下:I=Xb,A,B也就是说在项目集中含有移进-归约和归约归约冲突。其中，为文法的符号串，b为终结符。则要求满足如下的条件才能用SLR(1)分析方法进行分析。FOLLOW（A）FOLLOW（B）=FOLLOW（A）b=FOLLOW（B）b=那么当在状态I时面临输入符号为a时，填写在分析表中的动有以下的规定决策。面临输入符号为a=b时，则移进。若aFOLLOW(A)，则用产生式A进行归约。若aFOLLOW(B)，则用产生式B进行归约如果是其它种情况就报错，也就是说当交集不为空时，无法解决,例：给定文法，构造识别活前缀的DFA,文法：（0）SS（1）SaAd（2）SbAc（3）Saec（4）Sbed（5）Ae用SS作为初态集的项目，然后用闭包和转换函数构造文法的DFA,在项目集中就有两个冲突：I5：SaecI7：SbedAeAe该项目集很显然是移进和归约冲突。求FOLLOW(A)=c,d在I5中，FOLLOW(A)c=c,dc在I7中，FOLLOW(A)d=c,dc因此根本不能用SLR(1)进行分析。所以采用新的分析方法即LR(1)的方法。,LR(1)分析的基本思想,LR(1)分析方法就是在SLR(1)分析方法的基础上进行改进。其项目集规范族的构造原则有：若AB项目集时，则B也属于I（B为一产生式）。由此不防考虑把FIRST()作为产生式B归约的搜索符，称为向前搜索符，作为归约时查看的符号集合用以代替SLR(1)分析中的FOLLOW集。把此搜索符号的集合也放在相应项目的后面，这种处理方法即LR(1)方法。,LR(1)项目集规范族的构造,以SS，#属于初始项目集中，把“#”号作为向前搜索符，表示活前缀为（设是有关S产生式的某一部分）要归约成S时，必须面临输入符为“#”才行。我们对初始项目SS，#求闭包后再用转换函数逐步求出整个文法的LR(1)项目集规范族。,（1）构造LR（1）项目集的闭包函数,(1)假定I是一个项目集，I的任何项目都属于CLOSURE(I)。(2)若有项目AB属于CLOSURE(I)，B是文法的产生式，V*，b属于FIRST(),则B，b也属于CLOSURE(I)中。(3)重复(2)直到CLOSURE(I)不再增大为止。,（2）构造转换函数,LR(1)转换函数的构造与LR(0)的相似，GO(I，X)=CLOSURE(J)，其中I是LR(1)的项目集，X是文法符号：J=任何形如AX，a的项目|AX，aI对任何G的LR(1)项目集族的构造仍以SS，#为初态集的初始项目，然后对其求出闭包和转换函数，直到项目集不再增大为止。根据上述的步骤解决前面例中SLR(1)解决不了的问题。,（3）前例中的项目集规范族为：,I0：SS，#SaAd，#SbAc，#Saec，#Sbed，#I1：SS#I2：SaAd,#Saec,#Ae，dI3：SbAc,#Sbed，#Ae，c,I4:SaAd，#I5:Saec，#Ae，dI6:SbAc，#I7:Sbed，#Ae，cI8:SaAd，#I9:Saec，#I10:SbAc，#I11:Sbed，#,这样LR(1)方法构造的项目集规范族可以解决项目集I5和I7中的移进归约冲突。由于归约项目的搜索符集合和移进项目的待移进符号不相交，所以在I5中，当面临输入符号为d时归约，为c时移进，而在I7中则当面临输入符为c时归约，为d时移进，冲突就可以解决，该文法就是一个LR(1)文法。,2.LR(1)分析表的构造,由于一个LR(1)项目可以看成两个部分组成，一部分和LR(0)项目相同，这一部分称为心，另一部分为向前搜索符集合。因此LR(1)分析表的构造和LR(0)分析表的构造形式上相同，只是归约项目的归约动作取决于该归约项目的向前搜索符号。只有当面临的输入符号属于向前搜索符号的集合时，才做归约动作，其它的情况均出错.,LR(1)构造的基本的过程,设项目集规范族为：C=I0,I1,In，其中Ik为项目集的名字，k为状态号，SS所在的项目集的状态为初始状态。则ACTION和GOTO表的构造步骤为：若项目Aa属于Ik，且转换函数GO(Ik，a)=Ij，当a为终结符时，则置ACTIONk,a为Sj。若项目A，a属于Ik，置ACTIONk,a=rj,j为产生式A在文法中的编号。若项目SS，#属于Ik，则置ACTIONk,#=acc，表示“接受”。若GO(Ik，A)=Ij，则置GOTOk,A=j,其中A为非终结符，j为某一个状态号。凡不能用上述方法添入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,如果一个文法的LR(1)分析表不含多重入口，即任何一个LR(1)项目集中即无移进归约冲突或者归约归约冲突，则称该文法为LR(1)文法，所构造的相应的分析表为LR(1)分析表，使用LR(1)分析表的分析器称为LR(1)分析器或者LR(1)分析器。一个文法是LR(0)文法一定也是SLR(1)文法，也是LR(1)文法，但是，反过来就不一定成立。LR(1)项目集规范族使某些同心集进行了分裂,项目集的个数增加了.,LR（1）文法的应用示例,给出文法:（0）SS（1）SBB（2）BaB（3）Bb写出它的LR(1)项目集规范族和LR(1)分析表,并根据LR(1)分析表判断字符串：aabb是否为文法合法的句子.,I0:SS,#SBB,#BaB,a/bBb,a/b,S,B,I1:SS,#,I2:SBB,#BaB,#Bb,#,B,I5:SBB,#,I4:Bb,a/b,a,I3:BaB,a/bBaB,a/bBb,a/b,a,b,b,I8:BaB,a/b,B,I6:BaB,#BaB,#Bb,#,I7:Bb,#,b,b,I9:BaB,#,a,项目集规范族和转换函数,a,LALR(1)分析方法,LR(1)分析表的构造对搜索符的计算方法比较确切，对文法放松了要求，但是它的状态的数目比SLR(1)的状态的数目增加了很多，主要是因为LR(1)项目集规范族中出现了许多同心的集合，这些状态占据了内存的空间。为了克服LR(1)算法的缺点，就对LR(1)中的项目集规范族进行合并，若合并后的同心集族不产生新的冲突，则为LALR(1)项目集。合并了同心集后的项目集的数目和该文法的LR(0)、SLR(1)的相同。,同心集的合并,在前面已经讲过，由于一个LR(1)项目可以看成由两个部分组成，一部分和LR(0)项目相同，这一部分称为心，另一部分为向前搜索符集合。对于LR(1)项目集规范族来讲，心相同的集合称为同心集。在上题的项目集可以发现同心集如下：I3：BaB，a/bI6:BaB，#BaB，a/bBaB，#Bb，a/bBb，#I4：Bb，a/bI7:Bb，#I8：BaB，a/bI9:BaB，#,将同心集I3和I6，I4和I7，I8和I9合并后得到新的集合：I3，6：BaB，a/b/#BaB，a/b/#Bb，a/b/#I4，7：Bb，a/b/#I8，9：BaB，a/b/#,同心集合并后的状态集并不包含冲突，说明该文法是LALR(1)文法，如果有项目的冲突，就不是LALR(1)分析方法。关于同心集的合并有如下几个问题需要说明：（1）同心集合并是心相同的项目集合并在一起，因此同心集合并后心不变，向前搜索符的集合发生变化。（2）对于合并同心集后的项目集经转换函数后所达到的仍为同心集。（3）若文法是LR(1)文法，合并同心集后若有冲突也只能是归约归约冲突，而不可能是移进和归约冲突。因为在合并前就不存在移进归约冲突，移进后更不可能出现移进和归约冲突。（4）合并同心集后对语法错误的检查可能会出现推迟现象，但是错误的分析还是正确的。,LALR分析表的构造,LALR分析表的构造步骤如下（1）构造文法的LR(1)项目集规范族，C=I0,I1,In。（2）合并所有的同心集，使C变为C，C=J0,J1,Jn。（3）构造文法的LALR(1)分析表.1）若项目Aa属于Ik，且转换函数GO（Ik，a）=Ij，当a为终结符时，则置ACTIONk,a为Sj。2）若项目A，a属于Ik，置ACTIONk,a=rj，j为产生式A在文法中的编号。3）若项目SS，#属于Ik，则置ACTIONk,#=acc，表示“接受”。4）若GO(Ik，A)=Ij，则置GOTOk,A=j，其中A为非终结符，j为某一个状态号。5）凡不能用上述方法添入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,给定文法（1）SBB（2）BaB（3）Bb写出该文法的LR(1)项目集规范族，构造出该文法的LALR分析表，输入串“aa#”，用LR(1)分析表和LALR(1)分析表来判断该输入串是否合法。将前面的LR（1）的项目集规范族合并之后，得到合并后的状态为：I3，6：BaB，a/b/#BaB，a/b/#Bb，a/b/#I4，7：Bb，a/b/#I8，9：BaB，a/b/#由合并后的集合按照LALR(1)分析表的构造算法得到LALR分析表得到如下的表格为,LR(1)分析法强于LALR(1