编译原理第六章LR分析法.doc

第六章 LR分析法在第5章中已经讨论过，自底向上分析方法是一种移进归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR（K）分析方法是1965年Knuth先生提出的，括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（K）分析方法和自底向上的优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关的文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。但是，由于它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。因此，目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的“一个编译器的编译器YACC”来实现的。它能接受一个用BNF描述的满足LALR（1）的上下文无关文法并将自动构造出LALR（1）语法分析器。本章将主要介绍LR分析的基本思想和当K1时LR分析器的基本构造原理和方法。其中LR（0）分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1是，已能满足当前绝大多数高级语言编译程序的需要。其中SLR（1）和LALR（1）分别是LR（0）和LR（1）的一种改进。 本章重点：LR（0）、SLR（1） 第一节 LR分析概述图6-1-1（a）LR分析器结构示意图 （b）分析栈示意图总控程序分析表a1 - ai- # Xm#Sm XmSm-1 Xm-1 S1 X1SO #（一）LR（1）分析器的逻辑结构及工作过程在逻辑上，一个LR（1）分析器的结构如图6-1-1（a）所示。它有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR（1）分析器在总控程序的控制下自左至右扫视输入串中的各个符号，并根据当前分析栈中所存放之文法符号的状况及正扫描之输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止的分析历程。因此，为了方便，对于分析过程的每一步，我们可将迄今的分析历程用一种“状态”来刻画，并将此状态名置于分析栈的栈顶，如图6-1-1（b）所示。分析刚开始时，栈中仅有一个句子的左界符号#，此时分析器处于初始状态SO。此SO不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着：即将扫视的输入符号，应正好是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已存有符号#X1的情况，S2刻画了栈中存有符号串#X1X2的情况，栈顶状态Sm刻出了栈中已存有符号串#X1X2Xm，等等。此外，根据分析栈栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法GE，设分析栈中已移进和归约出的符号串为# E+T时的栈顶状态为Si，则Si不仅表征了迄今所扫描过的输入符号业已被归约成# E+T，而且由Si还可作这样的预测：若输入符号串无语法错误，则当前可遇到的输入符号，仅能是（+，*，），或#。显然，对于上述栈顶状态Si，若当前所扫视到的符号为*，则应将*移入栈中；当扫视到的符号为+、）或#时，则应将符号串E+T归约为E；若扫视到的不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可唯一地确定当前分析器所应完成的动作。所以，在具体实现时，并不需要将已归约出的文法符号串也记入分析栈中。作为LR（1）分析器核心的分析表由两个子表组成：其一是分析动作表，另一个为状态转换表，分别如图6-1-2（a）和6-1-2（b）所示。其中：S1，S2，Sn为分析器的各个状态；a1，a2，ae为文法的全部终结符号或句子的界符；X1，X2，X为文法字汇表中的全部文法符号。分析表中的每一元素ACTIONSm，ai指明，当栈顶状态为Sm且扫视到的输入符号为ai时应完成的动作。状态转移表中的元素GOTOSm，Xi则指明，当栈顶状态为Sm且面临文法符号Xi时所应转移到的下一状态。a1a2aeS1ACTIONS1，a1ACTIONS1，a2ACTIONS1，aeS2ACTIONS2，a1 ACTIONS2，a2ACTIONS2，aeSnACTIONSn，a1ACTIONSn，a2ACTIONSn，ae图6-1-2（a）分析动作表X1X2XpS1GOTOS1，X1GOTOS2，X2GOTOS1，XpS2GOTOS2，X1GOTOS2，X2GOTOS2，XpSnGOTOSn，X1GOTOSn，X2GOTOSn，Xp图6-1-2（b）状态转移表LR（1）分析器在总控程序的控制下进行工作，其过程如下（为书写方便，我们将分析栈按顺时针旋转九十度）：第一步 分析开始时，首先将初始状态SO及句子左界符#推入分析栈中。第二步 设在分析的某一步，分析栈及余留的输入符号串处于如下的格局： ai ai+1 an #则以栈顶的状态及正扫视的输入符号ai组成符号对（Sm，ai）去查分析动作表，并根据表元ACTIONSm，ai，的指示完成相应的分析动作。每一分析表元所规定的动作，仅能是下列四种动作之一：（1）若ACTIONSm，ai=“移进”，这表明句柄尚未在栈顶部形成，此时正期待继续移进输入符号以形成句柄，故将当前的输入符号推入栈中，即有： ai+1 ai+2 an #然后，以符号对（Sm，ai）查状态转移表，设相应的表元GOTO Sm，ai= Sm+1，再将此新的状态（即要转移到的下一状态）推入栈中，则有如下的格局： ai+1 ai+2 an #（2）若ACTIONSm，ai= r j ，其中r j意指按文法的第j个产生式AXm-r+1 Xm-r+2Xm进行归约。这表明栈顶部的符号串Xm-r+1 Xm-r+2Xm已是当前句型（相对于非终结符号A）的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号（因为该产生式右部符号串的长度为r）退出，然后再将文法符号A推入栈中，此时分析栈的格局为 ai ai+1 an # ai ai+1 an #然后，以（Sm-r ，A）查状态转移表，设GOTO Sm-r，A=Sl，将此新状态推入栈中，则有如下的格局：须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。（3）若ACTIONSm，ai=“接受”，则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。（4）若ACTIONSm，ai=ERROR，则表明当前的输入串中有语法错误，也应中止分析器的工作。第三步 重复上述第二步的工作，直到在分析的某一步，栈顶出现“接受状态”或“出错状态”为止。对于前者，分析栈的最终格局应为： #其中，Z为文法的开始符号，Se则为使ACTIONS，#=“接受”的唯一状态（即接受状态）。上述所列的三个步骤，实质上是对LR（1）分析器总控程序的一个非形式的描述，它对任何不同的LR（1）分析表都是适用的。第二节 LR（0）分析LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。我们回顾在第5章曾给出例1文法GS为：（1）SaAcBe（2）Ab（3）AAb（4）Bd对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5）步时栈中符号串为#aAb，我们采用了产生式（3）进行归约而不是产生式（2）归约，而在第3）步归约时栈中符号串为#ab时却用产生式（2）归约，虽然在第2）步和第5）步归约前栈顶号都为b，但归约所用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在LR分析中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表6-2-1中给出例1文法GS的LR（0）分析表，在表6-2-2给出利用LR分析法对输入串abbcde#的分析过程。表6-2-1 例1文法的LR（0）分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2R2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1表6-2-2 对输入串abbcde#的分析过程步骤状态栈符号栈输入串ACTIONGOTO10#abbcde#S2202#abbcde#S43024#abbcde#r234023#aAbcde#S650236#aAbcde#r336023#aAcde#S570235#aAcde#S8802358#aAcde#r47902357#aAcBe#S910023579#aAcBe#r111101#S#acc一、可归前缀和前缀在表6-2-2分析中，每次归约前句型的前部分依次为：abaAbaAcdaAcBe这正是我们在表6-2-2的分析过程中每次采取归约动作前符号栈中的内容，即分别对应步骤3）、5）、8）10）时符号栈中的符号串，我们把规范句型的这种前部分串称可归前缀。我们再来分析上述归约时规范句型的前缀：,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe不难发现前缀a,aA,aAc都不只是某一个规范句型的前缀，因此我们把形成可归前缀之前包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。二、LR（0）项目集规范族构造1、LR（0）项目在一个规范句型的活前缀中，决不会含有句柄右边的任何符号。这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。因此，活前缀与句柄间的关系不外下述三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最右符号即为其最右符号）；（2）活前缀中含句柄的一部分符号（句柄开头的若干符号与活前缀最右的若干个符号一致）；（3）活前缀中全然不包含句柄的任何符号。第一种情况表明，此时某一产生式A的右部符号串已出现在栈顶，因此相应的分析动作应当是用此产生式进行归约。第二种情况意味着形如A12的产生式的右部子串1已出现在栈顶，正期待着从余留输入串中看到能由2推出的符号串。而第三种情况则意味着，期望从余留输入串中能看到由某一产生式A 右部，即 所推出的符号串，为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“”来指示位置。例如，对于上述三处情况，标有圆点的产生式分别为A，A12以及A 。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR（0）项目，特别对形如A 的产生式，相应的LR（0）项目为A。显然，不同的LR（0）项目，反映了分析过程中栈顶的不同情况。在文法G中的每个产生式的右部适当位置添加一个圆点构成一个LR（0）项目例如，产生式SaAcBe对应有6个项目。0SaAcBe1 SaAcBe2 SaAcBe3 SaAcBe4 SaAcBe5 SaAcBe一个产生式可对应的项目为它的右部符号长度加1。A 的产生式，相应的LR（0）项目为A下面我们就会看到，文法的全部LR（0）项目将是构造识别它的所有活前缀的有限自动机的基础。2、构造识别活前缀的NFA如果把文法的所有产生式的项目都引出，每个项目都为NFA的一个状态。仍以文法G为例SEEaA|bBAcA|dBcB|d该文法的项目有：1、SE10、A d2、SE11、E bB3、EaA12、E bB4、EaA13、E bB5、EaA14、BcB6、AcA15、BcB7、AcA16、BcB8、AcA17、B d9、A d18、B d由于S仅在第一产生式的左部出现，因此规定项目1为初态，其余每个状态都为活前缀的识别态，圆点在最后的项目为句柄识别态，第一个产生式的句柄识别态为句子识别态。状态之间的转换关系确定方法如下：若i项目为：XX1X2Xi-1XiXnj项目为：XX1X2Xi-1 XiXi+1Xni项目和j项目出于同一个产生式，对应于NFA为状态j的圆点只落后于状态i的圆点一个符号的位置，那么从状态i 到状态j连一条标记为Xi的箭弧。如果Xi为非终结符，则也会有以它为左部的有关项目及其相应的状态，例如有项目形如：iXAK A则从状态i画标记为的箭弧到状态k，对于A的所有产生式圆点在最左边的状态都做一条i状态到该状态的前弧，箭弧上标记为。按上面的的规则我们可对文法G的所有项目对应的状态构造出识别活前缀的有限自动机NFA如图6-2-3。图中双圈表示句柄识别状态，双圈外有“*”号者为句子“接受”态。我们也可以根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种： 移进项目，形如Aa其中,V*，aVT，即圆点后面为终结符的项目为移进项目，对应状态为移进状态。分析时把a移进符号栈。 待约项目，形如AB其中,V*，BVN，即圆点后面为非终结符的项目为待约项目，它表明所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A的右部。 归约项目，形如 A其中V*，即圆点在最右端的项目，称归约项目，它表明一个产生式的右部已分析完，句柄已形成可以归约。 接受项目，形如S其中V+，S为拓广文法，S为左部的产生式只有一个，因而它是归约项目的特殊情况，对应状态为接受状态。我们规定S为初态。实际上接受项目中的为文法的开始符号。对于图6-2-3识别活前缀的NFA我们可以利用第3章讲过的子集法将其确定化。对确定化后的DFA如果把每个子集中所含状态集对应的项目写在新的状态中，结果如图6-2-4所示。dcBE*bBdAAc687459103X12131117181516141图6-2-3识别活前缀的NFAddBAAaEbcddcBccI4：AcAAcAAdI2：EaAAcAAdI3：EbBBcBBdI1：SEI5：BcBBcBBdIS：AcAI10：AdI6：EaAI7：EbBI11：BdI9：BcBI0：SEEaAEbB图6-2-4 识别活前缀的有限自动机DFA3、LR（0）项目集规范族的构造对于构成识别一个文法活前缀的DFA项目集（状态）的全体称为这个文法的LR（0）项目集规范族，然而构造识别活前缀的DFA若按（2）中方法，列出拓广文法的所有项目按规定原则构造其NFA（如图6-2-3）然后再确定化为DFA（如图6-2-4），这样做确定化的工作量较大，我们可以分析图6-2-4中每个状态中项目集的构成，不难发现如下规律：若状态中包含形如AB的项目，则形如B的项目也在此状态内。例如0状态项目集为：SE,EaA,EbB回顾由NFA确定化到DFA时，EaA和EbB正是属于SE的闭包中。因而，我们也可用闭包函数（CLOSURE）来求DFA一个状态的项目集。若文法G已拓广为G，而S为文法G的开始符号，拓广后增加产生式SS。对文法进行拓广的目的是为了对某些右部含有开始符号的文法，在归约过程中能分清是否已归约到文法最初开始符，还是在文法右部出现的开始符号，拓广文法的开始符号S只在左部出现，这样确保了不会混淆。如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE（I）如下：a）I的项目均在CLOSURE（I）中。b）若AB属于CLOSURE（I），则每一形如B的项目也属于CLOSURE（I）。c）重复b）直到不出现新的项目为止。即CLOSURE（I）不再扩大。由此，我们可以很容易构造出初态的闭包，即SS属于I，再按上述三点求其闭包。有了初态的项目集，其它状态的项目集如何求出？回顾在构造识别活前缀的NFA时除了箭弧上标记为的外，其两个相邻状态对应的项目是出自同一个产生式，只是圆点的位置相差。箭弧上的标记为前一个状态和后一个状态对应项目圆点间的符号，而识别活前缀的DFA的每个状态是一个项目集，项目集中的每个项目都不相同，每个项目圆点后的符号不一定相同，因而对每个项目圆点移动一个位置后，箭弧上的标记也不会完全相同，这样，对于不同的标记将转向不同的状态。例如初态SE，EaA,，EbB对第一个项目圆点右移一个位置后变为SE箭弧标记应为E，对第二个项目EaA，圆点右移一个位置后，项目变为EaA，箭弧标记为a，同样第三个项目为圆点右移一个位置后变为EbB，箭弧标记为b，显然，初态可发出三个不同标记的箭弧，因而转向三个不同的状态，也就由初态派生出三个新的状态，对于每个新的状态我们又可以利用前面的方法，若圆点后为非终结符则可对其求闭包，得到该状态的项目集。圆点后面为终结符或在一个产生式的最后，则不会再增加新的项目，例中新状态的项目EaA求其闭包可得到项目集为EaA，AcA，Ad。同样，另一新状态的项目为SE的则不会再增加新的项目。这样我们由初态出发对其项目集的每个项目的圆点向右移动一个位置用箭弧转向不同的新状态，箭弧上用移动圆点经过的符号标记。新状态的初始项目即圆点移动后的项目称为核。例中AaA和BbB都为核，对核求闭包就为新状态的项目集，为把这个过程写成一般的形式，我们定义转换函数GO（I，X）如下：GO（I，X）=CLOSURE（J）其中：I为包含某一项目集的状态。X为一文法符号，XVNVTJ=任何形如AX的项目|AX属于I这也表明，若状态I识别活前缀，则状态J识别活前缀X。圆点不在产生式右部最左边的项目称为核，但开始状态拓广文法的第一个项目SS除外。因此用GO（I，X）转换函数（CLOSURE）和转向函数（GO（I，X）构造文法G的LR（0）项目集规范族，步骤如下：a）置项目SS为初态集的核，然后对核求闭包，CLOSURE（SS）得到初态的项目集。b）对初态集或其它所构造的项目集应用转换函数GO（I，X）=CLOSURE（J）求出新状态J的项目集。c）重复b）直到不出现新的项目集为止。最后还需要说明的是由于任何一个高级语言相应文法的产生式是有限的，每个产生式右部的文法符号个数是有限的，因此每个产生式可列出的项目也为有限的，由有限的项目组成的子集即项目集作为DFA的状态也是有限的，所以不论用哪种方法构造识别活前缀的有限自动机必定会在有穷的步骤内结束。到目前为止，我们介绍了构造识别文法活前缀DFA的二种方法，读者可对它们进行比较分析以加深理解，粗略地说。第一种方法是求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA。第二种方法是把拓广文法的第一个项目SS作为初态集的核，通过求核的闭包和转换函数，求出LR（0）项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA。二种作法虽然不同，但出发点都是把LR分析方法的归约过程，看成是识别文法规范句型活前缀的过程，因为只要分析到的当前状态是活前缀的识别态，则说明已分析过的部分是该文法的某规范句型的一部分，也就说明了已分析过的部分是正确的。进一步分析所构造的LR（0）项目集规范族的项目类型分为如下四种：a）移进项目圆点后为终结符的项目，形如Aa其中，V*，相应状态为移进状态。b）归约项目圆点后为非终结符的项目，形如A其中V*，对于=的项目为A（对应产生式为A），相应状态为归约状态。c）待约项目圆点后为非终结符的项目，形如AB，其中，V*，BVN，这表明用产生式A的右部归约时，首先要将B的产生式右部归约为B，对A的右部才能继续进行分析。也就是期待着继续分析过程中首先能进行归约得到B。d）接受项目当归约项目为SS时则表明已分析成功，即输入串为该文法的句子，相应状态为接受状态。一个项目集中可能包含以上四种不同的项目，但是一个项目集中不能有下列情况存在：a）移进和归约项目同时存在：形如：由于这时面临输入符号为a时不能确定移进a还是把归约为B，因为LR（0）分析是不向前看符号，所以对归约的项目不管当前符号是什么都应归约。对于同时存在移进和归约项目的称移进-归约冲突。b）归约和归约项目同时存在。形如：因这时不管面临什么输入符号都不能确定归约为A，还是归约为B，对同时存在两个以上归约项目的状态称归约-归约冲突。对一个文法的LR（0）项目集规范族不存在移进-归约，或归约-归约冲突时，称这个文法为LR（0）文法。根据这种方法构造的LR（0）分析表不含多重定义时，称这样的分析表为LR（0）分析表，能用LR（0）分析表的分析器称为LR（0）分析器，能构造LR（0）分析表的文法称为LR（0）文法。例1若我们对文法G的产生式编号如下（0）SE（4）Ad（1）EaA（5）BcB（2）EbB（6）Bd（3）AcA 构造识别文法活前缀DFA的过程如下：I0 ： SEEaAEbB求闭包的算法I1=G0（I0，E）=CLOSURE（SE）=SEI2=G0（I0，a）=CLOSURE（EaA）=I3=G0（I0，b）=CLOSURE（EbB）=I4=G0（I2，c）=CLOSURE=I5=G0（I3，c）=CLOSURE=I6=G0（24，c）=CLOSURE（AcA）=I4I6=G0（I2，A）=CLOSURE（EaA）=Ea AI7=G0（I3，B）=CLOSURE（EbB）=EbBI8=G0（I4，A）=CLOSURE（AcA）=AcAI9=G0（I5，C）=CLOSURE（BcB）=I5I9=G0（I5，B）=CLOSURE（BcB）=BcBI10=G0（I2，d）=CLOSURE（Ad）=AdI11=G0（I4，d）=CLOSURE（Ad）=Ad=I10I11=G0（I3，d）=CLOSURE（Bd）=BdI12=G0（I5，d）=CLOSURE（Bd）=Bd=I11至此我们已求出所给文法G的全部项目集I0I11。通常，我们将这些项目集的全体称为文法G的LR（0）项目集规范族，并记为：C=I0，I1，I11于是，我们所要构造的识别文法G（S）全部活前缀的DFA为：M=（C，V，GO，I0，C）其中M的状态集也就是文法LR（0）项目集规范族C=I0，I1，I11；M的字母表也就是文法字汇表V=S，S，A，B，a，b，c，d；M的映象函数也就是如上定义的状态转换函数GO；M的终态集也就是C，这表明M的每一状态都是它的终态。对于上述文G，我们可以画出它的识别其全部活前缀的DFA的状态转换图。图6-2-4所示三、LR（0）分析表算法假设已构造出LR（0）项目集规范族为：C=I0，I1In其中Ik为项目集的名字，k为状态名，令包含SS项目的集合Ik的下标k为分析器的初始状态。那么分析表的ACTION表和GOTO表构造步骤为：（1）对于每一项目Ii中形如AX的项目，若GO（Ii，X）=Ij且X为一终结符号a时，置ACTIONi，a=Sj。但若X为非终结符号时，则仅置GOTOi，X= j。（2）若归约项目A属于Ii，设A为文法的第j个产生式，则对文法的任何终结符或句子的右界符（将它们统一地记为a），置ACTIONi，a= rj。（3）若接受项目SS属于Ii，则置ACTINOi，#= acc。（4）在分析表中，凡不能按上述规则填入信息的元素。均置为“出错”。得到LR（0）分析表如下：表6-2-5 LR（0）分析表状态ACTIONGOTOabcd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6现用表6-2-5的LR（0）对输入串bccd#用LR（0）分析器进行分析，其状态栈和符号栈及输入串的变化过程如表6-2-6所示。表6-2-6 对输入串bccd#的LR（0）分析过程步骤状态栈符号栈输入串ACTIONGOTO10#bccd#S3203#bccd#S53035#bccd#S540355#bccd#S1150355（11）#bccd#r69603559#bccB#r5970359#bcB#r578037#bB#r21901#E#acc第三节 SLR（1）分析在上节讨论LR（0）分析表的构造算法时，我们曾经指出，只有当一个文法G是LR（0）文法，即G的每一项目集均不含冲突的项目时，才能构造出无冲突动作的LR（0）分析表。然而，对于通常的程序设计语言来说，它们一般都不能用LR（0）文法描述，即使是描述一个变量说明这样简单文法也不是LR（0）文法，因此本节将介绍对于LR（0）规范族中有冲突的项目集（状态）用向前查看一个符号的办法进行处理，以解决冲突。这种办法将能满足一些文法的需要，因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR（1）分析法，用SLR（1）表示。现举实型变量说明文法为例：实型变量说明real标识符表标识符表标识符表，i标识符表i将该文法缩写后并拓广为G如下：（0）SS（1）SrD（2）DD,i（3）Di 首先构造该文法的LR（0）项目集规范族 I0：SSSrD I1=Go（I0，S）=CLOSURE（SS）= SS I2=Go（I0，r）=CLOSURE（SrD）= I3=Go（I2，D）=CLOSURE（SrD，DD,i）=I4=Go（I2，i）=CLOSURE（Di）=I5=Go（I3，i）=CLOSURE（Di）=I6=Go（I5，i）=CLOSURE（DD i）=再用G0函数构造出识别活前缀的DFA如图6-3-1rii，I1：SSI3：SrD DD，iI5：DD,iI6：DD,iI0：SS SrDI2：SrD DD,i DiI4：Di分析每个状态包含的项目集，不难发现在状态I3中含项目：SrD 为归约项目DD ，i 为移进项目也就是按SrD项目的动作认为用SrD产生式进行归约的句柄已形成，不管当前的输入符号是什么，都应把rD归约成S。但是按DD ，i项目当面临输入符号，号时，应将，号移入符号栈，状态转向I5。显然该文法不是LR（0）文法，也可在构造它的LR（0）分析表时发现这个问题，如表6-3-2所示。表6-3-2 实数说明文法的LR（0）分析表状态ACTIONGOTOr，i#SD0S211acc2S433r1r1,S5r1r14r3r3r3r35S66r2r2r2r2在这种情况下我们只需考查当用句柄rD归约成S时，S的后跟符号集合中不包含当前所有移进项目的移进符号的集合时，则这种移进-归约冲突便可解决，例中S的后跟符集合为#，移进项目只有一个，号，因而移进项目中期待移进的符号集合为，这样我们可以在状态I3中当遇#号时做归约动作，上述LR（0）分析表做局部改动后不再存在冲突称为SLR（1）文法，其分析表如表6-3-3所示。表6-3-3 实数说明文法的SLR（1）分析表状态ACTIONGOTOr，i#SD0S211acc2S433S5r14r3r3r3r35S66r2r2r2r2因此假定一个LR（0）规范族中含有如下的项目集（状态）II=Xb, A,B 也就是在该项目集中含有移进-归约冲突和归约-归约冲突。其中,为文法符号串，b为终结符。那么只要在所有含有A或B的句型中，直接跟在A或B后的可能终结符的集合即FOLLOW（A）和FOLLOW（B）互不相交，且都不包含b，也就是只要满足FOLLOW（A）FOLLOW（B）=FOLLOW（A）b=FOLLOW（B）b=那么，当在状态I时面临某输入符号为a时，则动作可由下规定决策。1）若a=b，则移进。2）若aFOLLOW（A），则用产生式A进行归约。3）若aFOLLOW（B），则用产生式B进行归约。4）此外，报错。通常对于LR（0）规范族的一个项目集I中可能含有多个移进项目和多个归约项目，我们可假设项目集I（状态）中有m个移进项目：A11a11，A22a22，Ammamm；同时含有n个归约项目为：B11，B22，Bnn只要集合a1,a2,，am和FOLLOW（B1），FOLLOW（B2），FOLLOW（Bn）两两交集都为空，那么我们仍可用上述规则解决冲突即考查当前输入符号决定动作。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）规则有了SLR（1）规则之后，只须将前述构造LR（0）分析表的算法中的规则（2）作如下的修改：（2）若归约项目A属于Ii，设A为文法的第j个产生式，则对任何属于FOLLOW（A）输入符号a，置ACTIONi，a=rj”，且其余的规则仍保持不变，就得到了构造SLR（1）分析表的算法。对于给定的文法G，若按上述算法所构造的分析表不含多重定义的元素，则称文法G为SLR（1）文法。LR（1）分析法 前面所介绍的SLR（1）分析法是一种较为实用的方法。其优点是状态数目少，造表算法简单，且大多数程序设计语言基本上都可用SLR（1）文法来描述。然而，也的确存在这样的文法。其项目集中的移进-归约或归约-归约冲突不可能通过SLR（1）规则得到解决。即FOLLOW（A）FOLLOW（B） 或FOLLOW（A）b 或FOLLOW（B）b故SLR（1）规则对解决上述归约-归约冲突失效。故不可能通过任何SLR（K）规则使项目集中的归约-归约冲突得到解决。因此，我们需用更强的LR分析方法，即LR（1）分析来解决这一问题。第四节 习题一、单项选择题1、若a为终结符，则Aa为 项目 a.归约b.移进c.接受d.待约2、若项目集Ik含有A，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A”动作的一定是 。 a.LALR文法b.LR（0）文法c.LR（1）文法d.SLR（1）文法3、就文法的描述能力来说，有 。 a. SLR（1）LR（0） b. LR（1）LR（0）c. SLR（1）LR（1）d.无二义文法LR（1）4、在LR（0）的ACTION子表中，如果某一行中存在标记“rj”的栏，则 。 a.该行必定填满rjb.该行未填满rjc.其他行也有rjd.goto子表中也有rj5、一个 指明了在分析过程中的某时刻所能看到产生式多大一部分。 a.活前缀b.前缀c.项目d.项目集解答： 1、A称为归约项目，对文法开始符S的归约项目，如S称为接受项目，Aa（a为终结符）称为移进项目。在此选b.2、当用产生式A归约时，LR（0）无论面临什么输入符号都进行归约；SLR（1）则仅当面临的输入符号aFOLLOW(A)时进行归约；LR（1）则当在把归约为A的规范句型的前缀Aa前提下，当后跟终结符a时，才进行归约；因此选d。3、由于LR（0）SLR（1） LR（1）无二义文法，故选c。4、选a。5、选c。二、多项选择题1、一个LR分析器包括 。 a.一个总控程序b.一个项目集c.一个活前缀d.一张分析表e.一个分析