资源描述：
《【精品】讲稿第7章LR分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第7章LR分析（9学时，10分钟）复习：移进——归约。接下来我们介绍一种自左而右、自下而上的语法分析技术,它可用于大多数CFG的语法分析,称为LR分析法：L表示从左至右扫描输入串，R表示构造一个最右推导的逆过程。LR分析法显然也是自下而上的"移进-归约"，但它比算符优先和其他的"移进-归约"法更加广泛,效率也不比它们差；比一般不带回溯的自上而下分析（如LL（1）分析）也要好一些,而且在自左而右扫描输入串时就能发现其中的任何错误,并能准确地指出出错位置。LR分析法主要的缺点是：LR分析器的手工构造工作量相当大
2、,因此一般要借助于自动产生器。本章首先讨论LR分析器的工作过程。然后学习四种不同分析表的构造方法。第一种,也是最简单的,叫LR（0）分析法z在分析过程中不需要向右查看输入符号,因而它对文法的限制比较大，但它是建立其它LR分析法的基础。第二种是简单LR分析法（简称SLR）°虽然有些文法构造不出SLR分析表’但这是一种比较容易实现又极具使用价值的方法。第三种是规范LR分析法（即LR（1））。这种分析表能力最强，能够适用一大类文法，但实现代价过高,或者说分析表的体积太大。第7章LR分析（9学时，10分钟）复习：移
3、进——归约。接下来我们介绍一种自左而右、自下而上的语法分析技术,它可用于大多数CFG的语法分析,称为LR分析法：L表示从左至右扫描输入串，R表示构造一个最右推导的逆过程。LR分析法显然也是自下而上的"移进-归约"，但它比算符优先和其他的"移进-归约"法更加广泛,效率也不比它们差；比一般不带回溯的自上而下分析（如LL（1）分析）也要好一些,而且在自左而右扫描输入串时就能发现其中的任何错误,并能准确地指出出错位置。LR分析法主要的缺点是：LR分析器的手工构造工作量相当大,因此一般要借助于自动产生器。本章首先讨论
4、LR分析器的工作过程。然后学习四种不同分析表的构造方法。第一种,也是最简单的,叫LR（0）分析法z在分析过程中不需要向右查看输入符号,因而它对文法的限制比较大，但它是建立其它LR分析法的基础。第二种是简单LR分析法（简称SLR）°虽然有些文法构造不出SLR分析表’但这是一种比较容易实现又极具使用价值的方法。第三种是规范LR分析法（即LR（1））。这种分析表能力最强，能够适用一大类文法，但实现代价过高,或者说分析表的体积太大。第四种是向前LR分析法(简称LALR)。这种分析表的能力介SLR和LR(1)之间，稍
5、加努力即可高效率地实现。教学内容：7.1LR分析法的概述；7.2LR(O)分析；7.3SLR(l)分析；7.4LR⑴分析;7.5LALR(l)分析；教学要求：要求理解有效项目的基本概念；掌握LR(O)文法的判断及LR(O)分析表的构造与分析方法、SLR(l)文法的判断与SLR(l)分析方法和LR(1)文法的判断与LR⑴分析方法。教学重点：LR分析法。7.1LR分析概述(55分钟)根据前面的介绍我们知道：自下而上分析的中心思想是”移进-归约"，关键问题就是"寻找规范句型的句柄"。当一貌似句柄的符号串呈现于分析
6、栈顶时，如何确定用哪一个产生式来归约？这是我们一直未能解决的问题。对于算符优先文法的特殊情况,我们借助算符间的优先关系解决了这一问题。但对于更一般的情况,该如何来做呢？仔细分析问题产生的原因，我们会发现，在分析过程中我们没有利用到已移进和归约出的整个符号串——〃历史资料J也没有根据产生式去〃瞻望"未来可能遇到的输入符号,而LR分析法就是在这些方面对"移进■归约〃进行改造的。LR分析法的基本思想：根据"历史资料"■〃现实输入符号”以及对未来的"展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的塑。它
7、是由Knuth在1965年首先提出的，后经Aho等人改造而成。一.LR分析器一个LR分析器实质上是一个带先进后出栈的DFA。前面讲过，状态的变化可以反映岀处理前后的经过,因此这儿我们应把〃历史〃和〃展望〃材料都综合为〃状态'使得田可时候,栈顶都代表了从分析开始以来的全部〃历史〃和已推测出的〃展望〃。这样一来,在任何时候都可从栈顶来了解一切,栈顶状态和当前输入符号就唯一决定了LR分析器的每一步工作。栈中每一项内容包括状态s和文法符号X两部分。栈的初始值为(SO,#)。栈顶状态为Sm,符号串XiX2・・・Xm是
8、至今已移进归约出的部分。如下页图所示。二分析表LR分析器的核心是一张分析表。这张表包括两部分："动作"(Action)和"状态转换"(Goto),它们都是二维数组。Action[s.a]规定了状态s面临输入符号a时应该采取什么动作；@1露凶则指出状态s面对文法符号X(终结符或非终结符)时下一状态是什么。显然，Goto[s,X]定义了一个以文法符号为字母表的DFAO输入串・•・o■・•分析表LR分析器模型图每一项A
