编译原理清华大学第7章 LR 分析法

第七章LR分析法【预习思考】复习自顶向下和自底向上语法分析思想的区别。自底向上分析方法是一种移进-归约过程。简单优先分析法是如何确定可归约串的？什么是规范推导和规范归约？它们之间有什么关系？什么是规范句型？什么是规范句型的句柄？移进-归约过程是当分析的栈顶符号串形成句柄时就采取归约动作。自底向上分析法的关键问题是在分析过程中如何确定句柄。如何确定一个输入符号串是否是所给文法的句子？【学习目标】理解LR分析法的基本思想。理解可归前缀和活前缀概念。理解识别活前缀的有限自动机概念。掌握LR分析器的构造思想和方法。对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器。对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子LR分析中的应用。【学习指南】LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的基础。【重难点】可归前缀和活前缀概念识别活前缀的有限自动机概念对可归前缀为规范归约的句柄的理解构造LR(1)项目集族时搜索符的计算LR分析器的关键部分是分析表的构造对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器当一个文法能构造出不含移进-归约或归约-归约冲突时的LR(0)/SLR(1)/LALR(1)/LR(1)分析表时，称这个文法分别为LR(0)/SLR(1)/LALR(1)/LR(1)文法。1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。LR(K)分析是指自左向右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向右查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。当前扫描到Xn+1,向右查看k个符号，来确定是把Xn+1移进栈，还是把Xi…Xn作为句柄进行归约。1）要归约时，则根据某产生式U→XiXi+1…Xn进行归约：#X1X2…Xi-1UXn+1Xn+2…Xn+k…#例：#X1X2…Xi……XnXn+1Xn+2…Xn+kXn+k+1…#栈顶LR(0)：表示在每一步分析时都不用向前输入符号LR(1)：表示在每一步分析时都向前看一个输入符号来决定当前的动作。SLR(1)：表示简单的LR(1)，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号。LALR(1)：表示向前看的LR(1)，即基于LR(1)作相同心项目的合并以减少状态数量。2）要移进时，即把Xn+1进栈，并读下一符号：#X1X2…Xi…XnXn+1Xn+2…Xn+k…#在栈中当前扫描符栈顶7.1LR分析概论7.1.1LR分析器的逻辑结构及工作过程从逻辑上来说，一个LR分析器如图7.1所示。输入串#…ai…a1sp→X1#S1S0┋┋┋┋XmSm总控程序输出ACTION表GOTO表其中S栈为状态栈X栈为符号栈栈产生式表图7.1LR分析器的逻辑结构即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。第一种称为规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。第三种称为向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。7.1.2LR分析器的分析过程如下：1.首先将初始状态S0及句子的左界符#分别压入状态栈和符号栈中。则用栈顶状态Sm和当前扫描符ai组成符号对（Sm,ai)去查分析动作表，根据ACTION[Sm,ai]的指示完成相应的分析动作。S0S1S2…SmSm+1ai+1ai+2…an##X1X2…Xmai↑↑↓2.设在分析中的某一步，分析栈及余留的输入串为如下格局：↓S0S1…Smaiai+1…an#X1…Xm↑↑（1）ACTION[Sm,ai]=Sm+1（移进）表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有（2）ACTION[Sm,ai]=Rj(归约）表明此时应按文法的第j个产生式A→Xm-k+1Xm-k+2…Xm进行归约。即栈顶符号串Xm-k+1Xm-k+2…Xm已成为当前句型的句柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符号退栈，然后将文法符号A压入符号栈中。此时分析的格局为：然后以（Sm-k,A)去查状态转移表，设GOTO[Sm-k,A]=Sl,则将此新状态压入状态栈中，则有如下格局：↓S0S1…Sm-kaiai+1…an##X1…Xm-kA↑↑↓S0S1…Sm-kSlaiai+1…an##X1…Xm-kA↑↑（3）ACTION[Sm,ai]=acc（接受）表明当前的输入串已被成功地分析完毕，应停止分析器的工作。其中Z为文法开始符号Sα为使ACTION[Sα，#]=acc的唯一状态（接受状态）（4）ACTION[Sm,ai]=ERROR（空白）。表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。3.重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。对接受状态，分析栈的格局为：↓S0Sα##Z↑↑例7-1：有文法G[S]:1：S→aAcBe2：A→b3：A→Ab4：B→d其ACTION表和GOTO表为：r1r1r1r1r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789SaAcBeAbdb图7.2abbcde#的语法树考察对输入串abbcde#的分析过程。对输入串abbcde#的分析过程为：ACTIONGOTO步骤状态栈符号栈输入流分析动作下一状态10#abbcde#S2(0,a)202#abbcde#S4(2,b)3024#abbcde#r2(4,b)GOTO[2,A]=34023#aAbcde#S6(3,b)6023#aAcde#S5(3,c)50236#aAbcde#r3(6,c)GOTO[2,A]=370235#aAcde#S8(5,d)802358#aAcde#r4(8,d)GOTO[5,B]=7902357#aAcBe#S9(7,e)10023579#aAcBe#r1(9,#)GOTO[0,S]=11101#S#acc(1,#)图7.3abbcde#的分析过程7.2LR(0)分析表的构造例如：abc的前缀有：,a,ab,abcabcd的前缀有：,a,ab,abc,abcd由此可知，对于符号串而言，其前缀的数量为+1。例：有文法G[S]:S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]对输入串abbcde进行推导（最右推导）。1)规范句型的活前缀前缀：一个符号串的前缀是指该串的任意首部（包括）。这里在每条产生式后加上了产生式的序号[i]，当进行推导时把序号带上，以便说明问题。SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]由此可知，abbcde是该文法的句子。由于LR方法是自底向上的分析，故应考察归约过程。最左归约为：ab[2]b[3]cd[4]e[1]用[2]式归约aAb[3]cd[4]e[1][3]aAcd[4]e[1][4]aAcBe[1][1]S这里用表示归约符从归约的过程可看出，每次归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前端部分：X1X2…Xn[p]其中Xi为文法的符号，[p]为第p个产生式序号。如上例中每次归约前句型的前面部分为：ab[2]aAb[3]aAcd[4]acABe[1]规范句型的这种前端部分的串称为可归前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约之故。所以我们将把规范句型具有上述性质（即不含句柄之后的任何符号）的前缀称之为可归前缀。对各规范句型有前缀：ab[2]b[3]cd[4]e[1],a,abaAb[3]cd[4]e[1],a,aA,aAbaAcd[4]e[1],a,aA,aAc,aAcdaAcBe[1],a,aA,aAc,aAcB,aAcBe可以发现前缀a,ab,aA,aAc是多个规范句型的前缀，因此我们可进一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀都称为活前缀。可归前缀：是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。活前缀：规范句型的一个前缀，这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。在前面例中对输入串abbcde的归约分析过程中，在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，它表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。可形式地定义活前缀如下：定义7.1：若S'*A是文法G中的一个规范推导，如果符号串是的前缀，则称是G的一个活前缀。其中S'为文法开始符号。RR活前缀特指在分析过程中对于在栈顶形成句柄之前和恰好形成句柄时，每一步中符号栈中的那些符号组成的符号串。2)LR（0）项目由上述分析和定义可知，活前缀与句柄间的关系不外乎下述三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最后符号就是活前缀的最后符号）。即有:A→β.（2）活前缀中只含有句柄的前面部分符号（句柄的最左子串为活前缀的最右子串）。即有:A→1.2（3）活前缀中全然不包含句柄的任何符号。即有:A→.第一种情况表明：此时某一产生式A→β的右部β已出现在符号栈顶，因此此时相应的分析动作应当是用此产生式进行归约。第二种情况表明：形如A→12的产生式的右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由β推出的符号串，即期待2进栈以便能进行归约。故此时分析动作是“移进”当前输入符号。第三种情况则意味着：期望从余留输入串中能看到由某产生式A→的右部，即所代表的符号串(即句柄)。所以此时分析的动作也是读输入符进符号栈（“移进”）。为了刻画在分析过程中，文法的一个产生式右部符号串有多大部分已被识别，我们可在该产生式的右部相应位置上加一个圆点“.”来指示分析的位置，它表明在“.”前的部分已被识别。例如：产生式S→aAcBe对应有六个项目。[1]S→.aAcBe[2]S→a.AcBe[3]S→aA.cBe[4]S→aAc.Be[5]S→aAcB.e[6]S→aAcBe.我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别地，对形如A→的产生式，相应的LR(0)项目表示为A→.显然不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。如上述三种情况，可分别标注为：A→β.A→1.2A→.一个产生式可对应的项目的数量为它的右部符号串长度加1，值得注意的是对空产生式，即A→ε仅有项目A→.。每个项目的含义与圆点的位置有关。由上例可知：概括地说，圆点左边的子串表示在分析过程的某