英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
４.６ LR语法分析技术介绍：简单LR技术
目前最流行的自底向上语法分析器都基于所谓的LR(ｋ)语法分析的概念。其中，“L”表示对输入进行从左到右的扫描，“R”表示反向构造出一个最右推导序列，而ｋ表示在做出语法分析决定时向前看ｋ个输入符号。ｋ＝０和ｋ＝１这两种情况具有实践意义，因此这里我们将只考虑ｋle;１的情况。当省略(ｋ)时，我们假设ｋ＝１。
本节将介绍LR语法分析的基本概念，同时还将介绍最简单的构造移入－归约语法分析器的方法。这个方法成为“简单LR技术”(或简称为SLR)。虽然LR语法分析器本身是使用语法分析器自动生成工具构造得到的，但对基本概念有所了解仍然是有益的。我们首先介绍“项”和“语法分析器状态”的概念，一个LR语法分析器生成工具给出的诊断信息通常会包含语法分析器状态。我们可以使用这些状态分离出语法分析冲突的源头。
４.７节将介绍两个更加复杂的方法——规范LR和LALR。它们被用于大多数的LR语法分析器中。
４.６.１ 为什么使用LR语法分析器
LR语法分析器是表格驱动的，在这一点上它和4.4.4节中提到的非递归LL语法分析器很相似。如果我们可以使用本节和下一节中的某个方法为一个文法构造出语法分析表，那么这个文法就被称为LR文法。直观的讲，只要存在这样一个从左到右扫描的移入－归约语法分析器，它总是能够在某文法的最右句型的句柄出现在栈顶时识别出这个句柄，那么这个文法就是LR的。
LR语法分析技术很有吸引力，原因如下：
·对于几乎所有的程序设计语言构造，只要能够写出该构造的上下文无关文法，就能够构造出识别该构造的LR语法分析器。确实存在非LR的上下文无关文法，但一般来说，常见的程序设计语言构造都可以避免使用这样的文法。
·LR语法分析方法是已知的最通用的无回溯移入－归约分析技术，并且它的实现可以和其他更原始的移入－归约方法一样高效。
·一个LR语法分析器可以在对输入进行从左到右扫描时尽可能早地检测到错误。
·可以使用LR方法进行语法分析的文法类是可以使用预测方法或LL方法进行语法分析的文法类的真超集。一个文法是LR(ｋ)的条件是当我们在一个最右句型中暗道某个产生式的右部时，我们再向前看ｋ个符号就可以决定是否使用这个产生式进行归约。这个要求比LL(ｋ)文法的要求宽松很多。对于LL(ｋ)文法，我们在决定是否使用某个产生式时，只能向前看该产生式右部推导出的串的前ｋ个符号。因此，LR文法能够比LL文法描述更多的语言就一点也不奇怪了。
LR方法的主要缺点是为一个典型的程序设计语言文法手工构造LR分析器的工作量非常大。我们需要一个特殊的工具，即一个LR语法分析器生成工具。幸运的是，有很多这样的生成工具可用，我们将在４.９节讨论其中最常用的工具Yacc。这种生成工具将一个上下文无关文法作为输入，自动生成一个该文法的语法分析器。如果该文法含有二义性的构造，或者含有其他难以在从左到右扫描时进行语法分析的构造，那么语法分析器生成工具将对这些构造进行定位，并给出详细的诊断消息。
４.６.２ 项和LR(０)自动机
一个移入－归约语法分析器怎么知道何时进行移入、何时进行归约呢？比如，当图4-28中栈的内容为$T而下一个输入符号是*时，语法分析器是怎么知道位于栈顶的T不是句柄，因此正确的动作是移入而不是将T归约到E呢？
一个LR语法分析器通过维护一些状态，用这些状态来表明我们在语法分析过程中所处的位置，从而做出移入－归约决定。这些状态代表了“项”的集合。一个文法G的一个LR(0)项是G的一个产生式再加上一个位于它的体中某处的点。因此，产生式A→XYZ产生了四个项：
A→·XYZ
A→X·YZ
A→XY·Z
A→XYZ·
产生式A→ε只生成一个项A→*。
直观地讲，项指明了在语法分析过程中的给定点上，我们已经看到了一个产生式的哪些部分。比如，项A→·XYZ表明我们希望接下来在输入中看到一个从XYZ推导得到的串。项A→X·YZ说明我们刚刚在输入中看到了一个可以由X推导得到的串，并且我们希望接下来看到一个能从YZ推导得到的串。项A→XYZ·表示我们已经看到了产生式体XYZ，已经是时候把XYZ归约为A了。
一个称为规范LR(0)项集族的一组项集提供了构建一个确定有穷自动机的基础。该自动机可用于做出语法分析决定。这样的有穷自动机称为LR(0)自动机。更明确地说，这个LR(0)自动机的每个状态代表了规范LR(0)项集族中的一个项集。表达式文法(4.1)的对应的自动机显示在图4-31中。我们将把它用作讨论规范LR(0)项集族的连续使用的例子。
为了构造一个文法的规范LR(0)项集族，我们定义了一个增广文法和两个函数：CLOSURE和GOTO。如果G是一个以S为开始符号的文法，那么G的增广文法Grsquo;就是在G中加上新开始符号Srsquo;和产生式Srsquo;→S而得到的文法。引入这个新的开始产生式的目的是告诉语法分析器何时应该停止语法分析并宣称接受输入符号串。也就是说，当且仅当语法分析器要使用规则Srsquo;→S进行归约时，输入符号串被接受。
项集的闭包
如果I是文法G的一个项集，那么CLOSURE(I)就是根据下面的两个规则从I构造得到的项集：
- 一开始，将I中的各个项加入到CLOSURE(I)中。
- 如果A→alpha;·Bbeta;在CLOSURE(I)中，B→gamma;是一个产生式，并且项B→·gamma;不在CLOSURE(I)中，就将这个项加入其中。不断应用这个规则，直到没有新项加入到CLOSURE(I)中为止。
图 4-31 表达式文法(4.1)的LR(0)自动机
直观地讲，CLOSURE(I)中的项A→alpha;·Bbeta;表明在语法分析过程的某点上，我们认为接下来可能会在输入中看到一个能够从Bbeta;推导得到的子串。这个可从Bbeta;推导得到的子串的某个前缀可以从B推导得到，而推导时必然要应用某个B产生式。因此我们加入了各个B产生式对应的项，也就是说，如果B→gamma;是一个产生式，那么我们将B→·gamma;加入到CLOSURE(I)中。
例4.40 考虑增广的表达式文法：
Ersquo;→E
E→E T | T
T→T * F | F
F→(E) | id
如果I是由一个项组成的项集{[Ersquo;→.E]}，那么CLOSURE(I)包含了图4-31中的项集I0。
下面说明一下如何计算这个闭包。根据规则(1)，Ersquo;→·E被放到CLOSURE(I)中。因为点的右边有一个E，我们加入如下的E产生式，店位于产生式体的左端：E→·E T和E→·T。现在，后一个项中有一个T在点的右边，因此我们加入T→·T*F和T→·F。接下来，位于点右边的F令我们加入F→·(E)和F→·id，然后就不再需要加入任何新的项。
闭包可以按照图4-32中的方法计算。实现函数closure的一个便利方法是设置一个布尔数组adder，该数组的下标是G的非终结符号。当我们为各个B产生式B→gamma;加入对应的项B→·gamma;时，added[B]被设置为true。
图 4-32 CLOSURE的计算
请注意，如果点在最左端的某个B产生式被加入到I的闭包中，那么所有B产生式都会被加入到这个闭包中。因此在某些情况下，不需要真的将那些被CLOSURE函数加入到I中的项B→·gamma;列出来，只需要列出这些被加入的产生式的左部非终结符号就足够了。我们将感兴趣的各个项分为如下两类：
- 内核项：包括初始项Srsquo;→·S以及点不在最左端的所有项。
- 非内核项：除了Srsquo;→·S之外的点在最左端的所有项。
不仅如此，我们感兴趣的每一个项集都是某个内核项集合的闭包，当然，在求闭包时加入的项不可能是内核项。因此，如果我们抛弃所有非内核项，就可以用很少的内存来表示真正感兴趣的项的集合，因为我们已知这些非内核项可以通过闭包运算重新生成。在图4-31中，非内核项位于表示状态的方框的阴影部分中。
GOTO函数
第二个有用的函数是GOTO(I，X)其中I是一个项集而X是一个文法符号。GOTO(I，X)被定义为I中所有形如[A→alpha;·Xbeta;]的项所对应的项[A→alpha;X·beta;]的集合的闭包。直观地讲，GOTO函数用于定义一个文法的LR(0)自动机中的转换。这个自动机的状态对应于项集，而GOTO(I，X)描述了当输入为X时离开状态I的转换。
例4.41 如果I是两个项的集合{[Ersquo;→E·]，[E→E· T]}，那么GOTO(I， )包含如下项：
E→E ·T
T→·T * F
T→·F
F→·(E)
F→·id
我们查找I中点的右边紧跟 的项，就可以计算得到GOTO(I， )。Ersquo;→·E不是这样的项，但E→E· T是这样的项。我们将点移过 号得到E→E ·T，然后求出这个单元素集合的闭包。
现在我们可以给出构造一个增广文法Grsquo;的规范LR(0)项集族C的算法。这个算法如图4-23所示。
图 4-33 规范LR(0)项集族的计算
例4.42 文法(4.1)的规范LR(０)项集族和GOTO函数如图4-31所示。其中，GOTO函数用图中的转换表示。
LR(０)自动机的用法。
“简单LR语法分析技术”(即SLR分析技术的中心思想是根据文法构造出LR(０)自动机。这个自动机的状态是规范LR(0)项集族中的元素，而它的转换由GOTO函数给出。表达式文法(4.1)的LR(0)自动机已经在前面的图4-31中显示过了。
这个LR(0)自动机的开始状态是CLOSURE({[Srsquo;→·S]})其中Srsquo;是增广文法的开始符号。所有的状态都是接收状态。我们说的“状态j”值得是对应于项集Ij的状态。
LR(0)自动机是如何帮助做出移入—归约决定的呢？移入—归约决定可以按照如下方式做出。假设文法符号串gamma;使LR(0)自动机从开始状态0运行到某个状态j。那么如果下一个输入符号为a且状态j有一个在a上的转换，就移入a。否则我们就选择规约动作。状态j的项将告诉我们使用哪个产生式来进行归约。
将在4.6.3节中介绍的LR语法菲尼算法用它的栈来跟踪状态及文法符号。实际上，文法符号可以从相应状态中获取，因此它的栈只保存状态。下面的例子将展示如何使用一个LR(0)自动机和一个状态站来做出移入—归约语法分析决定。
例4.43 图4-34给出了一个使用图4-31中的LR(0)自动机的移入—归约语法分析器在分析id*id时采取的动作。我们使用一个栈来保存状态。为清晰起见，栈中状态所对应的文法符号显示在“符号”列中。在第1行，栈中存放了自动机的开始状态0，相应的符号是栈底标记$。
图 4-34 id*id的语法分析
下一个输入符号是id，而状态0在id上有一个到达状态5的转换。因此我们选择移入。在第2行。状态5(符号id)已经被压入到栈中。从状态5出发没有输入*上的转换，因此我们选择归约。根据状态5中的项[F→id*]，这次归约应用产生式F→id。
如果栈中保存的是文法符号，那么归约就是通过将相应产生式的体(在第2行中，产生式的体是id)弹出栈并将产生式投(在这个例子中是F)压入栈中来实现的。现在栈中保存的是状态，我们弹出和符号id对应的状态5，使得状态0称为栈顶。然后我们寻找一个F(即该产生式的头部)上的转换。在图4-31中，状态0有一个F上的到达状态3的转换，因此我们压入状态3。这个状态对应的符号是F，见第3行。
我们看另一个例子，考虑第5行，状态7(符号*)位于栈顶。这个状态有一个id上的到达状态5的转换，因此我们将状态5(符号id)压入栈中。状态5没有转换，因此我们按照F→id进行归约。当我们弹出对应于产生式体id的状态5后，状态7到达栈顶。因为状态7有一个F上的转换到达状态10，我们压入状态10(符号F)。
4.6.3 LR语法分析算法
图4-35中显示了一个LR语法分析器的示意图。它由一个输入、一个输出、一个栈、一个驱动程序和一个语法分析表组成。这个分析表包括两个部分(ACTION和GOTO)。所有LR语法分析器的驱动程序都是相同的，而语法分析表是随着语法分析器的不同而变化的。语法分析器从输入缓冲区逐个读入符号。当一个移入—归约语法分析器移入一个符号时，LR语法分析器移入的是一个对应的状态。每个状态都是对栈中该状态之下的内容所含信息的摘要。
图 4-35 一个LR语法分析器的模型
分析器的栈存放了一个状态序列s0s1...sm，其中sm位于栈顶。在SLR方法中，栈中保存的是LR(0)自动机中的状态，规范LR和LALR方法和S
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236559]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
