编译原理第六章LR分析法

第六章LR分析法在第5章中已经讨论过，自底向上分析方法是一种移进归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR（K）分析方法是1965年Knuth先生提出的，括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（K）分析方法和自底向上的优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关的文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。但是，由于它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。因此，目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的“一个编译器的编译器—YACC”来实现的。它能接受一个用BNF描述的满足LALR（1）的上下文无关文法并将自动构造出LALR（1）语法分析器。本章将主要介绍LR分析的基本思想和当K≤1时LR分析器的基本构造原理和方法。其中LR（0）分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1是，已能满足当前绝大多数高级语言编译程序的需要。其中SLR（1）和LALR（1）分别是LR（0）和LR（1）的一种改进。本章重点：LR（0）、SLR（1）第一节LR分析概述（一）LR（1）分析器的逻辑结构及工作过程在逻辑上，一个LR（1）分析器的结构如图6-1-1（a）所示。它有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR（1）分析器在总控程序的控制下自左至右扫视输入串中的各个符号，并根据当前分析栈中所存放之文法符号的状况及正扫描之输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止的分析历程。因此，为了方便，对于分析过程的每一步，我们可将迄今的分析历程用一种“状态”来刻画，并将此状态名置于分析栈的栈顶，如图6-1-1（b）所示。分析刚开始时，栈中仅有一个句子的左界符号#，此时分析器处于初始状态SO。此SO不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着：即将扫视的输入符号，应正好是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已存有符号#X1的情况，S2刻画了栈中存有符号串#X1X2的情况，…，栈顶状态Sm刻出了栈中已存有符号串#X1X2…Xm，等等。此外，根据分析栈栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为#E+T时的栈顶状态为Si，则Si不仅表征了迄今所扫描过的输入符号业已被归约成#E+T，而且由Si还可作这样的预测：若输入符号串无语法错误，则当前可遇到的输入符号，仅能是（+，*，），或#。显然，对于上述栈顶状态Si，若当前所扫视到的符号为*，则应将*移入栈中；当扫视到的符号为+、）或#时，则应将符号串E+T归约为E；若扫视到的不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可唯一地确定当前分析器所应完成的动作。所以，在具体实现时，并不需要将已归约出的文法符号串也记入分析栈中。作为LR（1）分析器核心的分析表由两个子表组成：其一是分析动作表，另一个为状态转换表，图6-1-1（a）LR分析器结构示意图（b）分析栈示意图总控程序分析表a1---ai---#Xm┇#SmXmSm-1Xm-1┇┇S1X1SO#↓SOS1S2…Sm#X1X1…Xmaiai+1…an#↓分别如图6-1-2（a）和6-1-2（b）所示。其中：S1，S2，…Sn为分析器的各个状态；a1，a2，…，ae为文法的全部终结符号或句子的界符；X1，X2，…X为文法字汇表中的全部文法符号。分析表中的每一元素ACTION[Sm，ai]指明，当栈顶状态为Sm且扫视到的输入符号为ai时应完成的动作。状态转移表中的元素GOTO[Sm，Xi]则指明，当栈顶状态为Sm且面临文法符号Xi时所应转移到的下一状态。a1a2……aeS1ACTION[S1，a1]ACTION[S1，a2]……ACTION[S1，ae]S2ACTION[S2，a1]ACTION[S2，a2]……ACTION[S2，ae]………………………SnACTION[Sn，a1]ACTION[Sn，a2]……ACTION[Sn，ae]图6-1-2（a）分析动作表X1X2……XpS1GOTO[S1，X1]GOTO[S2，X2]……GOTO[S1，Xp]S2GOTO[S2，X1]GOTO[S2，X2]……GOTO[S2，Xp]………………………SnGOTO[Sn，X1]GOTO[Sn，X2]……GOTO[Sn，Xp]图6-1-2（b）状态转移表LR（1）分析器在总控程序的控制下进行工作，其过程如下（为书写方便，我们将分析栈按顺时针旋转九十度）：第一步分析开始时，首先将初始状态SO及句子左界符#推入分析栈中。第二步设在分析的某一步，分析栈及余留的输入符号串处于如下的格局：则以栈顶的状态及正扫视的输入符号ai组成符号对（Sm，ai）去查分析动作表，并根据表元ACTION[Sm，ai，]的指示完成相应的分析动作。每一分析表元所规定的动作，仅能是下列四种动作之一：（1）若ACTION[Sm，ai]=“移进”，这表明句柄尚未在栈顶部形成，此时正期待继续移进输入符号以形成句柄，故将当前的输入符号推入栈中，即有：然后，以符号对（Sm，ai）查状态转移表，设相应的表元GOTO[Sm，ai]=Sm+1，再将此新的状态（即要转移到的下一状态）推入栈中，则有如下的格局：（2）若ACTION[Sm，ai]=rj，其中rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2…Xm进行归约。这表明栈顶部的符号串Xm-r+1Xm-r+2…Xm已是当前句型（相对于非终结符号A）的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号（因为该产生式右部符号串的长度为r）退出，然后再将文法符号A推入栈中，此时分析栈的格局为SOS1…Sm#X1…Xmaiai+1ai+2…an#↓SOS1…SmSm+1#X1…Xmaiai+1ai+2…an#↓↓SOS1…Sm-rSl#X1…Xm-rAaiai+1…an#↓↓SoSα#Z#↓然后，以（Sm-r，A）查状态转移表，设GOTO[Sm-r，A]=Sl，将此新状态推入栈中，则有如下的格局：须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。（3）若ACTION[Sm，ai]=“接受”，则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。（4）若ACTION[Sm，ai]=ERROR，则表明当前的输入串中有语法错误，也应中止分析器的工作。第三步重复上述第二步的工作，直到在分析的某一步，栈顶出现“接受状态”或“出错状态”为止。对于前者，分析栈的最终格局应为：其中，Z为文法的开始符号，Se则为使ACTION[Sα，#]=“接受”的唯一状态（即接受状态）。上述所列的三个步骤，实质上是对LR（1）分析器总控程序的一个非形式的描述，它对任何不同的LR（1）分析表都是适用的。第二节LR（0）分析LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。我们回顾在第5章曾给出例1文法G[S]为：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5）步时栈中符号串为#aAb，我们采用了产生式（3）进行归约而不是产生式（2）归约，而在第3）步归约时栈中符号串为#ab时却用产生式（2）归约，虽然在第2）步和第5）步归约前栈顶号都为b，但归约所用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在LR分析中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表6-2-1中给出例1文法G[S]的LR（0）分析表，在表6-2-2给出利用LR分析法对输入串abbcde#的分析过程。SOS1…Sm-r#X1…Xm-rAaiai+1…an#表6-2-1例1文法的LR（0）分析表表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）时符号栈中的符号串，我们把规范句型的这种前部分串称可归前缀。我们再来分析上述归约时规范句型的前缀：ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2R2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1ε,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→β的右部符号串β已出现在栈顶，因此相应的分析动作应当是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现在栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着，期望从余留输入串中能看到由某一产生式A→α右部，即α所推出的符号串，为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三处情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR（0）项目，特别对形如A→ε的产生式，相应的LR（0）项目为A→·。显然，不同的LR（0）项目，反映了分析过程中栈顶的不同情况。在文法G中的每个产生式的右部适当位置添加一个圆点构成一个LR（0）项目例如，产生式S→aAcBe对应有6个项目。[0]S→·aAcBe[1]S→a·AcBe[2]S→aA·cBe[3]S→aAc·Be[4]S→aAcB·e[5]S→aAcBe·一个产生式可对应的项目为它的右部符号长度加1。A→ε的产生式，相应的LR（0）项目为A→·下面我们就会看到，文法的全部LR（0）项目将是构造识别它的所有活前缀的有限自