讲稿第7章LR分析.docVIP

第7章 分析CFG的语法分析，称为 LR分析法显然也是自下而上的“移进－归约”，但它比算符优先和其他的“移进－归约”法更加广泛，效率也不比它们差；比一般不带回溯的自上而下分析（如LL(1)分析）也要好一些，而且在自左而右扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。 LR分析法主要的缺点是：LR分析器的手工构造工作量相当大，因此一般要借助于自动产生器。 本章首先讨论LR分析器的工作过程。然后学习四种不同分析表的构造方法。 第一种，也是最简单的，叫LR(0)分析法，在分析过程中不需要向右查看输入符号，因而它对文法的限制比较大，但它是建立其它LR分析法的基础。 第二种是简单LR分析法（简称SLR）。虽然有些文法构造不出SLR分析表，但这是一种比较容易实现又极具使用价值的方法。 第三种是规范LR分析法（即LR(1)）。这种分析表能力最强，能够适用一大类文法，但实现代价过高，或者说分析表的体积太大。 第四种是向前LR分析法（简称LALR）。这种分析表的能力介SLR和LR(1)之间，稍加努力即可高效率地实现。 教学内容： 7.1 LR分析法的概述； LR(0)分析； .3 SLR(1)分析； .4 LR(1)分析；.5 LALR(1)分析； LR(0)文法的判断及LR(0)分析表的构造与分析方法、SLR(1)文法的判断与SLR(1)分析方法和LR(1)文法的判断与LR(1)分析方法。 教学重点： LR分析法。 7.1 LR分析概述（55分钟） 根据前面的介绍我们知道：自下而上分析的中心思想是“移进－归约”，关键问题就是“寻找规范句型的句柄”。当一貌似句柄的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？这是我们一直未能解决的问题。 对于算符优先文法的特殊情况，我们借助算符间的优先关系解决了这一问题。但对于更一般的情况，该如何来做呢？仔细分析问题产生的原因，我们会发现，在分析过程中我们没有利用到已移进和归约出的整个符号串——“历史资料”，也没有根据产生式去“瞻望”未来可能遇到的输入符号，而LR分析法就是在这些方面对“移进－归约”进行改造的。 LR分析法的基本思想：根据“历史资料”、“现实输入符号”以及对未来的“展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的句柄。它是由Knuth在1965年首先提出的，后经Aho等人改造而成。 一、LR分析器 一个LR分析器实质上是一个带先进后出栈的DFA。 前面讲过，状态的变化可以反映出处理前后的经过，因此这儿我们应把“历史”和“展望”材料都综合为“状态”，存入分析栈，使得任何时候，栈顶都代表了从分析开始以来的全部“历史”和已推测出的“展望”。这样一来，在任何时候都可从栈顶来了解一切，栈顶状态和当前输入符号就唯一决定了LR分析器的每一步工作。 栈中每一项内容包括状态s和文法符号X两部分。栈的初始值为(s0,#)。栈顶状态为sm，符号串X1X2…Xm是至今已移进归约出的部分。如下页图所示。 二、分析表 LR分析器的核心是一张分析表。这张表包括两部分：“动作”(Action)和“状态转换”(Goto) ，它们都是二维数组。 Action[s,a]规定了状态s面临输入符号a时应该采取什么动作Goto[s,X]则指出状态s面对文法符号X（终结符或非终结符）时下一状态是什么。 LR分析器模型图 a.移进：把(s,a)的下一状态s=Goto[s,a]和输入符号a推进栈，下一输入符号变成现行输入符号； b.归约：指用某一产生式A(β进行归约。若|β|＝r，则把栈顶r个项托出，栈顶状态变成Sm-r，然后把(Sm-r,A)的下一状态s=Goto[Sm-r,A]和A进栈。归约动作不改变现行输入符号。执行归约动作意味着β=Xm-r+1 …Xm已呈现与栈顶而且是一个相对于A的句柄。 c.接受：宣布分析成功，停止分析器的工作； d.报错：发现源程序含有错误，调用出错处理程序。 LR分析器的总控程序本身的工作是非常简单的。它的任何一步只需按栈顶状态s和当前输入符号a执行Aciton[s,a]所规定的工作。不管什么分析表，总控程序都是一样地工作。 对于一个文法一个分析器常有若干不同的分析表，但不管什么分析表都将恰好识别文法的全部句子。本章将要讨论四种分析方法各自对应的分析表。这些分析表的构造后面再讲。下边先看一下LR分析器的工作过程。 三、LR分析器的工作过程 一个LR分析器的工作过程可以看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程： 初始三元式： (s0, #, a1a2…an#) 中间三元式： (s0s1..sm, #X1X2…Xm, aiai+1…an#) 接受: (s0…sk,#X,#) (X为开始符号，而Action[sk,#]为接) 分析器的下一步动作完全由sm和ai