【编译原理】UpDownLR分析法

LR分析法是一种相当有效的自下而上分析技术&＃xff0c;它可以用于很大一类上下文无关文法的语法分析。L表示从左向右扫描输入串&＃xff1b;R表示构造一个规范推导(最右推导)的逆过程&＃xff0c;也就是规范归约(最左规约)。LR分析法比我们前面介绍的算符优先分析法或其它的"移进-归约"技术更加广泛&＃xff0c;并且识别效率也不比它们差。能用LR分析器分析的文法类&＃xff0c;包括了能够使用LL(1)分析器分析的全部文法&＃xff0c;LR分析法在从左向右扫描输入串时就能发现其中的任何错误&＃xff0c;并能准确指出出错地点。
这种分析法的一个主要缺点在于&＃xff0c;手工构造分析程序的工作量相当大&＃xff0c;因此必须求助于自动产生这种分析程序的产生器。接下来我们会讨论4种不同分析表的构造方法。

1. 最简单的一种&＃xff0c;叫做LR(0)表构造法。这种方法的局限性极大&＃xff0c;但它是后续更加强大的LR分析法建立的基础&＃xff1b;
2. 简单LR表构造法&＃xff0c;也称为SLR表构造法。虽然有一些文法&＃xff0c;无法用构造出SLR分析表&＃xff0c;但SLR分析表是一种比较容易实现又极具使用价值的方法&＃xff1b;
3. 规范LR分析法&＃xff0c;这种分析表的能力最强&＃xff0c;能够适用一大类文法&＃xff0c;但实现代价过高&＃xff0c;或者说&＃xff0c;构造出的分析表过于庞大&＃xff1b;
4. 向前LR表构造法&＃xff0c;也称为LALR&＃xff0c;这种分析表的能力介于SLR和规范LR之间&＃xff0c;稍加努力就可以高效地实现。

最后&＃xff0c;我们会讨论如何使用一个二义文法来进行自下而上分析。

规范归约的关键问题是寻找句柄&＃xff0c;句柄也就是最左直接短语。它是在规范归约分析法中用来刻画"可归约串"的概念&＃xff0c;等同于算符优先分析法种最左素短语的概念。在LR分析法中&＃xff0c;我们一方面记住已经移进和归约出的整个符号串&＃xff0c;也就是记住"历史"&＃xff1b;另一方面根据产生式来推测未来可能遇到的输入符号&＃xff0c;也就是展望"未来"。当一串貌似句柄的符号呈现于分析栈的栈顶时&＃xff0c;我们希望可以根据已经记录的"历史"和拥有的"未来"信息以及"现实"的输入符号三方面的信息&＃xff0c;来确定栈顶的符号串是否相对于某个产生式构成了句柄。一个LR分析器实质上是一个带FILO栈的DFA&＃xff0c;也就是PDA(下推自动机)。我们将"历史"和"未来"信息抽象为PDA的状态&＃xff0c;分析栈用于存放这些状态&＃xff0c;栈中的状态都代表了整个历史和已经推测出的未来&＃xff0c;因此任何时候&＃xff0c;我们都可以从栈顶状态得知想要了解的一切信息&＃xff0c;而没有必要从底向上翻阅整个分析栈。LR分析器的每一步工作都是由栈顶状态和输入符号所唯一决定的。
那么我们要关心的问题就是&＃xff0c;如何从一个给定的CFG来构造它的LR分析表(也有可以无法构造出LR分析表的CFG)。对于一个CFG&＃xff0c;如果能够构造出一张分析表&＃xff0c;使得其每一步的入口都是唯一确定的&＃xff0c;则我们把这个文法称为LR文法。一个LR分析器有时需要展望和实际检查未来的k个输入符号才能决定应该采用什么样的"移进-归约"策略。一般而言&＃xff0c;如果一个文法能用一个每步至多向前检查k个输入符号的LR分析器进行分析&＃xff0c;那么我们称这个文法为LR(k)文法。对于多数的程序设计语言&＃xff0c;k&＃61;0或1就足够了。
LR分析法关于产生式右部的识别条件并不像预测分析法(LL(1)分析法)那样苛刻。预测分析法要求每个非终结符的所有候选的首符均不相同&＃xff0c;它要求一旦看到了首符&＃xff0c;就能够确定使用哪一个产生式进行推导&＃xff0c;但LR分析法认为只有在看到了整个右部所推导出的东西后才确定了归约策略。不能看出&＃xff0c;LR分析法相较于预测分析法更加一般化&＃xff0c;这也是LR文法包含了LL文法的本质。

LR(0)分析法是一种只记录历史&＃xff0c;而不对未来进行任何展望的分析方法&＃xff0c;这就是其"0"的意思。在构造分析表之前&＃xff0c;我们首先要构造出给定CFG G[S]的活前缀自动机&＃xff0c;也叫做项目集规范族。我们以下面给出的文法为例&＃xff0c;来叙述活前缀自动机的构造方法&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

1.计算项目闭包.

我们在每一个产生式的右部添加一个●&＃xff0c;对于已经读入的输入串部分进行记录&＃xff0c;这样的产生式称为一个LR(0)项目。而后我们需要对于每一个项目进行求闭包的运算&＃xff0c;具体的计算方法如下&＃xff1a;

2.构造活前缀DFA.

构造出了项目集族后&＃xff0c;我们就可以进行活前缀自动机的构造。具体的方法就是向右移动我们添加的●&＃xff0c;看它的后继项目是哪一个&＃xff0c;就从当前项目创建一个标记为●后一个符号的弧指向后继状态。借助这一规则&＃xff0c;针对示例文法的项目集规范族构造如下&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

3.构造LR(0)分析表.

下一步是依据已经获得的活前缀DFA来构造LR(0)分析表&＃xff0c;具体的构造方法如下&＃xff1a;

依据这一规则&＃xff0c;我们构造出的LR(0)分析表如下所示&＃xff1a;

最后我们以输入串’accd’为例来叙述整个分析表的使用过程&＃xff1a;

SLR分析法实际上称它为SLR(1)分析法更加合适&＃xff0c;它的作用在于&＃xff0c;向未来简单展望以下&＃xff0c;来获取一些信息已解决当前遇到的冲突问题。例如下图所示&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

我们着眼于状态3&＃xff0c;当中的两个项目&＃xff0c;E→T●&＃43;E在面对输入符号为&＃43;时&＃xff0c;做出移进的决策&＃xff0c;而E→T●却对于所有的输入符号&＃xff0c;都做出利用2号产生式归约的决策&＃xff0c;这就是"移进-归约"冲突。SLR(1)分析法致力于解决这一冲突&＃xff0c;但并不是所有的这类冲突。

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】


不难看出&＃xff0c;SLR(1)分析法解决这类冲突是存在先决条件的&＃xff0c;通俗地说&＃xff0c;就是这三个项目能够被它们的Follow集合区别开来。至于Follow集合的计算方法&＃xff0c;我们在【编译原理】自上而下分析与LL文法中曾经介绍过&＃xff0c;这里的计算方法是一样的。所以争对第一张图中给出的"移进-归约"冲突&＃xff0c;我们需要计算E的Follow集合&＃xff0c;其结果为{ # }&＃xff0c;所以状态3的冲突是可以解决的。我们只需要在符号&＃43;的那一列填入S4_44​&＃xff0c;而在#的那一列填入R2_22​即可。作为SLR(1)分析法的结束&＃xff0c;我们用一个例题来完整地执行一次SLR分析表的构造流程&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】


【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】


【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

前面介绍的SLR(1)分析法基于LR(0)分析法&＃xff0c;通过向前看一个输入符号&＃xff0c;来决定什么时候进行归约&＃xff0c;当一个状态中存在项目A→α●时&＃xff0c;当且仅当下一个输入符号x∈Follow(A)时&＃xff0c;才利用这一产生式进行归约。它的优点是消除了一些状态中的移进-归约冲突&＃xff0c;但我们也看到了&＃xff0c;SLR(1)解决这一冲突时是需要先决条件的&＃xff0c;如果这些条件不被满足&＃xff0c;例如同时存在项目A→α●与项目B→β●&＃xff0c;并且Follow(A)∩Follow(B)≠Φ&＃xff0c;那么显然我们无法判定&＃xff0c;对于那些同时在Follow(A)与Follow(B)中的输入符号而言&＃xff0c;究竟该使用哪一个产生式进行归约。这一问题的根源在于&＃xff0c;SLR(1)的"1"&＃xff0c;也就是我们用于解决冲突的Follow集合&＃xff0c;只是一种相比之下很简单的"展望方法"&＃xff0c;它并不能完全表征出某些项目之间的区别&＃xff0c;从而导致了项目集中的冲突无法解决。我们下面给出一个具体的例子&＃xff0c;来叙述那些SLR(1)分析法无法解决的冲突&＃xff0c;并且由此引出更加强大的LR(1)分析法&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

上图中我们可以看到&＃xff0c;2号状态中存在移进-归约冲突&＃xff0c;并且Follow®&＃61;{$,&＃61;}&＃xff0c;所以Follow®∩{&＃61;}≠Φ&＃xff0c;这就导致了我们在2号状态的输入符号为"&＃61;“的那一列&＃xff0c;无法确定一个动作(是移进还是归约)&＃xff0c;所以我们需要继续强化自下而上分析法的能力。
LR(1)中的"1”&＃xff0c;也就是它的"展望"&＃xff0c;相较于SLR(1)的展望方法&＃xff0c;就更加细致&＃xff0c;从而获得了更加强大的分析功能&＃xff0c;同时也付出了项目集规范族计算复杂&＃xff0c;分析表体积庞大的代价。简单来说&＃xff0c;LR(1)分析法还是基于最原始的LR(0)分析法&＃xff0c;我们也是需要根据文法构造出活前缀自动机(也叫做项目集规范族&＃xff0c;只是名称不同)&＃xff0c;而后根据这一活前缀自动机再构造分析表。而LR(1)和前面的LR(0)以及SLR(1)的不同就在于它的活前缀自动机中项目的计算方法&＃xff0c;后续的根据活前缀自动机构造分析表都是大同小异。下面我们给出LR(1)分析法构造项目闭包的规则&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

第一眼看到这个规则&＃xff0c;大概率不会理解它在说什么&＃xff0c;我们还是通过上面给出的实例&＃xff0c;来看看LR(1)分析法中的项目闭包如何计算&＃xff0c;然后再返回这里&＃xff0c;细细阐述这一规则。对于拓展文法中的S’→S这一产生式&＃xff0c;我们构造其项目为【S’→●S&＃xff0c;#】&＃xff0c;而后根据上面给出的规则&＃xff0c;进行活前缀自动机的构造。我们以第一个状态中的项目为例&＃xff0c;首先我们拥有项目【S’→●S&＃xff0c;#】&＃xff0c;First(#) &＃61; { # }&＃xff0c;所以根据规则我们需要加入的是&＃xff1a;

1. 【S→●L&＃61;R&＃xff0c;#】
2. 【S→●R&＃xff0c;#】

继续考察添加的第一个项目【S→●L&＃61;R,#】,First(&＃61;R#) &＃61; { &＃61; };
所以我们需要添加的是【L→●*R,&＃61;】和【L→●id,&＃61;】;
再考察第二个项目【S→●R,#】&＃xff0c;First(#) &＃61; { # },所以我们需要添加的是【R→●L,#】;
值得注意的是,到这里我们的项目闭包并没有计算完成,我们要一直计算到这个闭包不会发生变化为止.
考察项目【R→●L,#】,First(#) &＃61; { # };
显然根据我们的规则&＃xff0c;我们需要添加【L→●*R,#】和【L→●id,#】;
而这两个项目与之前来源于项目【S→●L&＃61;R,#】的【L→●*R,&＃61;】和【L→●id,&＃61;】进行合并;
得到【L→●*R,&＃61;|#】和【L→●id,&＃61;|#】
最终得到的,LR(1)分析法之下的状态1如下所示:


【上图引用自中南大学徐德智老师的编译原理2020年授课PPT】
从这一状态出发&＃xff0c;我们可以构造出整个LR(1)分析法之下的活前缀自动机&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

作为对比&＃xff0c;上一部分是LR(0)分析法中的活前缀自动机&＃xff0c;下一部分是LR(1)分析法中的活前缀自动机&＃xff0c;我们关注前面发生冲突、并且SLR(1)无法解决的状态2.可以发现&＃xff0c;【R→L●&＃xff0c;#】这一状态的搜索符是#&＃xff0c;和同在状态2中的另一个移进项目之间的冲突已经解决了——如果下一个输入符号是&＃61;&＃xff0c;则执行移进操作&＃xff1b;如果是#&＃xff0c;则执行5号产生式的归约操作&＃xff1b;其余的输入符号都引发错误处理。后续就可以根据这一活前缀自动机&＃xff0c;构造出LR(1)分析法的分析表。

上面一张图的对比很容易看出&＃xff0c;LR(1)分析法固然强大&＃xff0c;但其活前缀自动机中的状态相比于LR(0)分析法中的多了很多&＃xff0c;也导致后续的LR(1)分析表体积庞大。而LALR分析法可以在一定程度上&＃xff0c;简化LR(1)分析表的构造。我们关注前一张图中【状态8】与【状态10】以及【状态5】与【状态11】这两组状态。不难发现&＃xff0c;它们其实是相同的项目&＃xff0c;只是搜索符不同而已。以【状态8】与【状态10】为例&＃xff0c;前者的搜索符为{ &＃61;,# }&＃xff0c;后者的搜索符为{ # }&＃xff0c;这样的项目我们称为同心项。
LALR分析法的思想就是将LR(1)分析法中的同心项进行合并&＃xff0c;如果不产生冲突&＃xff0c;那么就完成了合并&＃xff0c;构成了LALR项目集&＃xff0c;否则无法合并。像我们上面的【状态8】与【状态10】以及【状态5】与【状态11】&＃xff0c;就可以完成合并。这里我们也给出一个合并之后会发生冲突的示例&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

我们还需要指出一点&＃xff1a;LALR项目集中&＃xff0c;是不会导致新的移进-归约冲突的&＃xff0c;上面一个例子中也看到了&＃xff0c;引入的新冲突是一个归约-归约冲突&＃xff0c;即面对输入符号d或e&＃xff0c;两个项目都认为自己应该进行归约。

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

任何二义文法都绝不是LR(k)的&＃xff0c;无论这个k有多大。但我们可以对一个特定的二义文法&＃xff0c;使用自下而上的分析技术&＃xff0c;来分析其输入串。
例如这样一个二义文法&＃xff1a;

并且我们给出其无二义的版本&＃xff1a;

二义文法相较于其无二义的版本&＃xff0c;有两个明显的好处&＃xff1a;如果需要改变运算符的优先级或结合性&＃xff0c;无需改变文法本身&＃xff0c;而只需要作出规定即可&＃xff1b;二义文法所对应的分析表中的状态要比其无二义的版本少得多&＃xff0c;因为无二义文法中含有众多的单非产生式&＃xff0c;这些用于定义优先级和结合性的产生式要占用不少空间和时间。所以&＃xff0c;我们对于二义文法利用自下而上的分析思想&＃xff0c;并且结合一些设定的约束条件&＃xff0c;来构造其分析表。实际上&＃xff0c;被施加了限制条件的二义文法已经不再是二义的了&＃xff0c;无二义文法是通过文法的结构来表征其优先级和结合性&＃xff0c;而限制条件正好说明了这些优先级和结合性规则。

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

下图是前面给出的二义文法的LR(0)项目集族自动机&＃xff1a;

【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】

我们关注图中标红的状态&＃xff0c;它们都是有冲突的状态。其中状态1的冲突可以使用SLR(1)的技术解决&＃xff0c;具体地说&＃xff0c;面对输入符号为&＃43;时&＃xff0c;执行S4_44​操作&＃xff1b;面对输入符号为*时&＃xff0c;执行S5_55​操作&＃xff1b;面对输入符号为#时&＃xff0c;就已经接受了。
而状态7和状态8中&＃xff0c;就涉及我们所说的限制条件了。如果按照平时算术运算的思维&＃xff0c;我们让&＃43;和×都服从左结合性&＃xff0c;并且×的优先级要高于&＃43;。所以再状态7中&＃xff0c;如果面对的输入符号时&＃43;&＃xff0c;由于左结合性&＃xff0c;我们规定进行1号产生式的归约操作&＃xff0c;而如果输入符号是×&＃xff0c;我们执行S5_55​操作。同样的&＃xff0c;对于状态8&＃xff0c;由于×服从左结合&＃xff0c;并且×的优先级高于&＃43;&＃xff0c;所以它在面对输入符号为&＃43;和×时&＃xff0c;都同样使用2号产生式进行归约操作。