讲稿第7章LR分析.doc
48页
第7章LR分析（9学时，10分钟）复习：移进——归约接下来我们介绍一种自左而右、自下而上的语法分析技术,它 可用于大多数CFG的语法分析,称为LR分析法：L表示从左至右 扫描输入串，R表示构造一个最右推导的逆过程LR分析法显然也是自下而上的"移进-归约"，但它比算符优 先和其他的"移进-归约"法更加广泛,效率也不比它们差；比一 般不带回溯的自上而下分析（如LL（1）分析）也要好一些,而且在自 左而右扫描输入串时就能发现其中的任何错误,并能准确地指出出 错位置LR分析法主要的缺点是：LR分析器的手工构造工作量相当大,因此一般要借助于自动产生器本章首先讨论LR分析器的工作过程然后学习四种不同分析表的构造方法第一种,也是最简单的,叫LR（0）分析法z在分析过程中不需要 向右查看输入符号,因而它对文法的限制比较大，但它是建立其它LR分析法的基础第二种是简单LR分析法（简称SLR ） °虽然有些文法构造不出 SLR分析表’但这是一种比较容易实现又极具使用价值的方法第三种是规范LR分析法（即LR（1））这种分析表能力最强， 能够适用一大类文法，但实现代价过高,或者说分析表的体积太大第四种是向前LR分析法(简称LALR )。
这种分析表的能力介 SLR和LR(1)之间，稍加努力即可高效率地实现教学内容：7.1 LR分析法的概述；7.2 LR(O)分析；7.3 SLR(l)分析；7.4 LR⑴分析;7.5 LALR(l)分析；教学要求：要求理解有效项目的基本概念；掌握LR(O)文法的判断及LR(O) 分析表的构造与分析方法、SLR(l)文法的判断与SLR(l)分析方法和 LR(1)文法的判断与LR⑴分析方法教学重点：LR分析法7.1 LR分析概述(55分钟)根据前面的介绍我们知道：自下而上分析的中心思想是”移进-归约"，关键问题就是"寻找规范句型的句柄"当一貌似句柄 的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？这 是我们一直未能解决的问题对于算符优先文法的特殊情况,我们借助算符间的优先关系解 决了这一问题但对于更一般的情况,该如何来做呢？仔细分析问 题产生的原因，我们会发现，在分析过程中我们没有利用到已移进和归约出的整个符号串——〃历史资料J也没有根据产生式去〃瞻 望"未来可能遇到的输入符号,而LR分析法就是在这些方面对"移 进■归约〃进行改造的LR分析法的基本思想：根据"历史资料"■〃现实输入符号”以及对未来的"展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的塑。
它是由Knuth在1965年首先提出的，后 经Aho等人改造而成一.LR分析器一个LR分析器实质上是一个带先进后出栈的DFA前面讲过，状态的变化可以反映岀处理前后的经过,因此这儿我们应把〃历史〃和〃展望〃材料都综合为〃状态' 使得田可时候,栈顶都代表了从分析开始以来的全部〃历史〃和已 推测出的〃展望〃这样一来,在任何时候都可从栈顶来了解一切, 栈顶状态和当前输入符号就唯一决定了 LR分析器的每一步工作栈中每一项内容包括状态s和文法符号X两部分栈的初始值为(SO,#)栈顶状态为Sm ,符号串XiX2・・・Xm是至今已移进归约出的部分如下页图所示二分析表LR分析器的核心是一张分析表这张表包括两部分："动作"(Action)和"状态转换"(Goto),它们都是二维数组Action[s.a]规定了状态s面临输入符号a时应该采取什么动作；@1露凶则指出状态s面对文法符号X (终结符或非终结符)时下一 状态是什么显然，Goto[s,X]定义了一个以文法符号为字母表的DFAO输入串・•・ o ■・•分析表LR分析器模型图每一项Action［s,a］所规定的动作无非是下述四种可能之一:a移进:把(s,a)的下一状态s=Goto$a］和输入符号a推进栈, 下一输入符号变成现行输入符号；b.归约:指用某一产生式ATB进行归约。
若IBI二r,则把栈顶r 个项托出”栈顶状态变成Sow ,然后把(Sow,A)的下一状态 syGoto［Sm・“A］和A进栈归约动作不改变现行输入符号执行归约动作意味着P=Xm.r+i・・Xm已呈现与栈顶而且是一个相对于A的句柄C•接受:宣布分析成功，停止分析器的工作；d.报错:发现源程序含有错误,调用出错处理程序LR分析器的总控程序本身的工作是非常简单的它的任何一步只需按栈顶状态s和当前输入符号a执行Aciton［s,a］所规定的工作 不管什么分析表，总控程序都是一样地工作对于一个文法一个分析器常有若干不同的分析表，但不管什么分析表都将恰好识别文法的全部句子本章将要讨论四种分析方法 各自对应的分析表这些分析表的构造后面再讲下边先看一下LR 分析器的工作过程三.LR分析器的工作过程 一个LR分析器的工作过程可以看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程:初始二兀式：(so, #. aia2・・.an#)中间三兀式：(soSi・・Sm/ #XiX2...Xmz ajaj+i...an#)接受：(So...Sk,#X,#) (X为开始符号，而Action[sk,#]为接受)分析器的下一步动作完全由sm和ai唯一决定z即执行Action[sm/ai]o经执行每种可能的动作之后，三元式的变化IW形是:1、若action[sm,ai]为移进且s=qoto[sm,ai],则三元式变为：(SoSi・・・SmSj #XiX2...Xmai/ ai+i・・.an#)2、若action[sm/ai]={A^[3} z则按产生式进行归约』匕时 三元式变为：(SoSi・・・Sm・rS / #XiX2・・・Xm・rA，aiai+i・・.an#)此处 S =gOto[Sm-r；A] , r 为B的度 / P = Xm-r+l--«Xmo3、若action[smQ]为接受,则三元式不再变化,过程终止,分 析成功。
4、若action[smQ]为报错,则三元式的变化过程终止,报告错 误LR分析器的工作过程就是一步一步地变换三元式,直至执行〃接受〃或〃报错"为止再看前面的例子:教材P124例7・1文法G[S]:(1) S 弓 aAcBe(2) A Tb(3) A TAb(4) B Td步骤符号栈输入符号串动作1)#abbcde#移进2)#abbcde*移进3)bed尉归约(Aztb)4)bede#移进|5)#aAbcde#归约(Az*Ab)6)cde#移进7)#aAcde#移进8)# sAcde#归约（B二d）9)e#移进10)#归约11)#s#扌毀这是前面讲过的对输入串abbcde#的移进——分析过程，下面我们来看如何用LR分析法来分析该句子Si：移进：将下一状态i和当前输入符号进栈；邙归约：用第i个产生式归约，同时状态栈与符号栈退出相应的符号，并把GOTO表柑应状态和第i个产生式的左部非终结符入栈LR分析表如下：ACTBDNGOTOa€ebdsAB011acc2St33Ss4Ti巧巧a巧5s.76liT1巧n7%8T4r4T49nT10n对输入串abbcde#的LR分析过程:舛檜入ACTIONGOTO1)abbcde#0&2)#abbcde#02643)#abbcde#财(Rb)024%34)#aAbcde#023&5)#aAbcde#财(A*b)023636)IFoACO0rr0237)#oAcde»02355>8)#oAcde#归为甘402358片79)#aAcB8#023575>10)#oAcBe财(S-dAcBe：1 023579111)#S01ate如:第3)步,状态4面对b, Action[45b]=r2=A^b,状态栈退|b| =1位是状态2, Goto[2,A]=3,相应地有：第 5)步，状态 6 面对 c, Action[6,c]=r3 = Ab, Goto[2,A]=3第 8)步,状态 8 面对 e, Action[6?c]=r4=B->d? Goto[5,B]=7第 10)步，状态 9 面对# ,Action[9,#]=n = STaAcBe,Goto[0,S]=l 对于一个文法，如果能够构造出一张分析表，使得它的每个入111LR文法口均是唯一的,则称该文法为LR文法。
注意：并非所有上下文无关文法都是LR文法，例：二义性文法 S^iCtS|iCtSeSo但是对于多数程序语言来说，一般都可用LR文法 描述直观上说,对于一个LR文法，当分析器对输入串进行自左而右扫描时,—旦句柄呈现于栈顶z就能及时对它进行归约一个LR分析器有时需要〃展望〃未来的k个输入符号才能决定应采取什么样的〃移进■归约〃决策于是又有如下定义：对于文法Gz若能用一个每步顶多向前查看k个输入符号的LR分析器进行分析,则称之为LR(k)文法但是对大多数的程序语言来说，k二0或:L 就足够了因此，我们只考虑k
字的前缀：字的任意首部，如abc: a, ab, abco我们把形成可归前缀之前包括可归前缀在内的所有规范句型的 前缀都称为活前缀之所以称之为活前缀,是因为在其右边添加一 些终结符号后就可以形成规范句型活前缀例：£,a,abE ,a,aA,aAb£ 5a9aA,aAc5aAcde 5a5aA5aAc5aAcB9a。
