武汉理工大学计算机科学系陈天煌课件

《武汉理工大学计算机科学系陈天煌课件》由会员分享，可在线阅读，更多相关《武汉理工大学计算机科学系陈天煌课件（41页珍藏版）》请在金锄头文库上搜索。

1、第六章 LR 分析法,1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。 LR(K)分析是指自左向右扫描和自底向上的语法分析，且 在分析的每一步，只须根据分析栈中当前已移进和归约出的 全部文法符号，并至多再向前查看K个输入符号，就能确定 相当于某一产生式右部符号的句柄是否已在分析栈的顶部形 成。从而也就可以确定所应采取的分析动作（是移进输入符号 还是按某产生式进行归约）。,当前扫描到Xn+1,向前查看k个符号，来确定是把 Xn+1移进栈，还是把XiXn作为句柄进行归约。,1） 要归约时，则根据某产生式UXiXi+1Xn进行归约： #X1X2Xi-1UXn+1Xn+2Xn+

2、k#,（续页）,LR(0) 表示在每一步分析时都不用向前输入符号 LR(1) 表示在每一步分析时都向前看一个输入符号来决定当 前的动作。 SLR(1) 表示简单的LR(1)，即只在动作不唯一的地方向前看一 个符号，在动作唯一时则不向前看输入符号。,6.1 LR分析概论,一 .LR分析器的逻辑结构及工作过程 从逻辑上来说，一个LR分析器如图：,即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。,第一种称为规范LR分析表构造法。用此法构造的分析表功能最强

3、而且也适合于很多文法，但实现代价比较高。,第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。,第三种称为向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。,二、LR 分析器的分析过程如下：,1.首先将初始状态 S0及句子的左界限#分别压入状态栈和符号栈中。,则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查 分析动作表，根据ACTIONSm, ai的指示完成相应的分析动作。

4、 表中每一表元素所规定的动作仅能是下列四种动作之一：,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个符 号退栈，然后将文

5、法符号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（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工

6、作。转出错处理。,3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。对接受状态，分析栈的格局为： S0 S # # Z ,例：,有文法GS:1：SaAcBe 2：Ab 3：AAb 4：Bd 其ACTION表和GOTO表为： 考察对输入串abbcde# 的分析过程。,对输入串abbcde# 的分析过程为：,6.2 LR(0) 分析表的构造,为了给出构造LR(0)分析表的算法，引出一些术语： 1、规范句型的活前缀 前缀：一个符号串的前缀是指该串的任意首部（包括）。,例如 abc的前缀有： ,a,ab,abc abcd的前缀有：,a,ab,abc,abcd 由此可知，对于符

7、号串 而言，其前缀的数量为+1。 例：有文法GS:SaAcBe1 Ab2 这里在每条产生式后加上了产生 AAb3 式的序号i当进行推导时把序号 Bd4 带上，以便说明问题。 对输入串abbcde进行推导如下（最右推导）： S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 由此可知，abbcde是该文法的句子。由于LR方法是自底向上的 分析，故应采用归约。,最左归约为： ab2b3cd4e1 用2式归约, aAb3cd4e1 3, aAcd4e1 4, aAcBe1 1, S,其中表示归约符,从归约的过程可看出，每次归约时，归约前和归约后的被 归约部分与剩余部分合起来仅

8、构成文法的规范句型，而用哪个 产生式归约仅取决于当前句型的前面部分；X1X2Xnp 其中Xi为文法的符号，p为第p个产生式序号。 如上例中每次归约前句型的前面部分为： ab2 aAb3 aAcd4 acABe1,我们把规范句型的这种前端部分的串称为可归前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。,SaAcBe1 Ab2 AAb3 Bd4,这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约 之故。所以我们将把规范句型具有上述性质（即不含句柄之后的 任何符号）的前缀称之为可归前缀。 对各规范句型有前缀：,ab2b3cd4e1 ,a,ab aAb3cd4e1 ,a,aA,aAb a

9、Acd4e1 ,a,aA,aAc,aAcd aAcBe1 ,a,aA,aAc,aAcB,aAcBe,可以发现前缀a,ab,aA,aAc是多个规范句型的前缀，因此我们可进 一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀 都称为活前缀。,可归前缀：是指规范句型的一个前缀，这种前缀不含句柄之 后的任何符号。,活前缀：可归前缀的任意首部。特指在分析过程中对于在栈顶 形成句柄之前和恰好形成句柄时，每一步中符号栈中的那些符号组成的符号串。,活前缀定义：,在前面例中对输入串abbcde的归约分析过程中，在规范归约过程 中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范 句型的活前缀，它表明

10、输入串的已被分析过的部分是该文法某规 范句型的一个正确部分。,2、LR（0）项目,由上述分析和定义可知，活前缀与句柄间的关系不外乎下述 三种情况：（1）活前缀中已含有句柄的全部符号（句柄的最后符号就是 活前缀的最后符号）。（2）活前缀中只含有句柄的前部分符号（句柄的最左子串 为活前缀的最右子串）。 （3）活前缀中全然不包含句柄的任何符号。,第一种情况表明：此时某一产生式A的右部已出现在符号 栈顶，因此此时相应的分析动作应当是用此产生式进行归约。 第二种情况表明：形如A12的产生式的 右部子串已在符号栈栈顶，如1，正期待着从余留的输入串中看到能由推出的 符号串，即期待2 进栈以便能进行归约。故此

11、时分析动作是“移进”当前输入符号。 第三种情况则意味着：期望从余留输入串中能看到由某产生式 A的右部，即所代表的符号串(即句柄) 。所以此时分析的动作也是读输入符进符号栈。,为了刻画在分析过程中，文法的一个产生式右部符号串有多大 部分已被识别，我们可在该产生式的右部相应位置上加一个圆点 “.”，来指示位置，标明在“.”前的部分已被识别。如上述三种情况，可分别标注为：A.； A1 .2 ; A. 。 我们把右部某位置上标有圆点的产生式称为相应文法的一个 LR(0)项目。特别地，对形如A 的产生式，相应的LR(0)项目， A. 显然不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。,例如：

12、产生式SaAcBe对应有六个项目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,例如：产生式SaAcBe对应有六个项目。,0 S.aAcBe 1 Sa.AcBe 2 SaA.cBe 3 SaAc.Be 4 SaAcB.e 5 SaAcBe.,一个产生式可对应的项目的数量为它的右部符号串长度加1，值得注意的是对空产生式，即A仅有项目A. 每个项目的含义与圆点的位置有关。概括地说，圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分。 文法的全部LR(0)项目将是构造识

13、别它的所有活前缀的有穷自动机的基础。,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)

14、 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)项目 进行分类： 对于形如A. 的项目，因为它表明右部符号串已出现在栈顶，此 时相应的分析动作应当是按此产生式进行归约，故我们将此种项目 称为归约项目。上例中的项目2) ,4),6),1

15、0),12),16),18)均是归约项目。 其中项目2)显然仅用于分析过程中的最后一次归约，它表明整个分 析过程已成功地完成，所以我们特别地将它称为接受项目。对于拓 广文法而言，接受项目是唯一的。由此可看出到我们为什么要首先 将文法拓广的原因。 对于形如A. X 的项目（其中 可以是 ），根据前面的讨论 可知，当X为终结符时，相应的分析动作应将当前的输入符号移入 栈中，故我们将此种项目称为移进项目。上例中的项目7) ,9), 11), 13) ,15) ,17)就都是移进项目； 当X为非终结符时，由于我们期待着从余留的输入符中进行归 约后而得到X，因此将此类项目称为待约项目。上例中的1), 3), 5), 8), 14)就都是待约项目。,在LR方法实际过程中，并不是去直接分析符号栈中的符号 是否已形成句柄，但它给我们一个启示，我们可以把终结符和非 终结符都可看成一个有限自动机的输入符号，每把一个符号进栈 时看成已识别过该符号，而状态进行转换（到下一状态），当识 别到可归前缀时相当于栈顶已形成了句柄，则认为到达了识别句 柄的终态。,4、构造识别活前缀的DFA 在作出文法的全部LR(0)项目之