LALR
4.7.4 Constructing LALR Parsing Tables
We now introduce our last parser construction method, the LALR (lookaheadLR) technique. This method is often used in practice, because the tables obtaIned by it are considerably smaller than the canonical LR tables, yet most common syntactic constructs of programming languages can be expressed conveniently by an LALR grammar. The same is almost true for SLR grammars, but there are a few constructs that cannot be conveniently handled by SLR techniques (see Example 4.48, for example).
For a comparison of parser size, the SLR and LALR tables for a grammar always have the same number of states, and this number is typically several hundred states for a language like C. The canonical LR table would typically have several thousand states for the same-size language. Thus, it is much easier and more economical to construct SLR and LALR tables than the canonical LR tables.
By way of introduction, let us again consider grammar (4.55), whose sets of LR(1) items were shown in Fig. 4.41. Take a pair of similar looking states, such as I4 and I7. Each of these states has only items with first component C→d·. In I4 , the lookaheads are c or d; in I7, $ is the only lookahead.
To see the difference between the roles of I4 and I7 in the parser, note that the grammar generates the regular language c*dc*d. When reading an input cc ... cdcc ... cd, the parser shifts the first group of cs and their following d onto the stack, entering state 4 after reading the d, The parser then calls for a reduction by C → d, provided the next input symbol is c or d. The requirement that c or d follow makes sense, since these are the symbols that could begin strings in c*d. If $ follows the first d, we have an input like ccd, which is not in the language, and state 4 correctly declares an error if $ is the next input.
The parser enters state 7 after reading the second d. Then, the parser must see $ on the input, or it started with a string not of the form c*dc*d. It thus makes sense that state 7 should reduce by C→d on input $ and declare error on inputs c or d.
Let us now replace I4 and h by I47, the union of I4 and I7, consisting of the set of three items represented by [C → d·, c/d/$]. The gotos on d to I4 or I7 from I0,I2,I3, and I6 now enter I47. The action of state 47 is to reduce on any input. The revised parser behaves essentially like the original, although it might reduce d to C in circumstances where the original would declare error, for example, on input like ccd or cdcdc. The error will eventually be caught; in fact, it will be caught before any more input symbols are shifted.
More generally, we can look for sets of LR(1) items having the same core, that is, set of first components, and we may merge these sets with common cores into one set of items. For example, in Fig. 4.41, I4 and I7 form such a pair, with core {C→d·}. Similarly, I3 and I6 form another pair, with core {C → c·C, C → ·cC, C → ·d}. There is one more pair, 18 and 19, with common core {C → cC·}. Note that, in general, a core is a set of LR(0) items for the grammar at hand, and that an LR(1) grammar may produce more than two sets of items with the same core.
Since the core of GOTO(I, X) depends only on the core of I, the gotos of merged sets can themselves be merged. Thus, there is no problem revising the goto function as we merge sets of items. The action functions are modified to reflect the non-error actions of all sets of items in the merger.
Suppose we have an LR(1) grammar, that is, one whose sets of LR(1) items produce no parsing-action conflicts. If we replace all states having the same core with their union, it is possible that the resulting union will have a conflict, but it is unlikely for the following reason: Suppose in the union there is a conflict on lookahead a because there is an item [A → alpha;·, a] calling for a reduction by A → alpha;, and there is another item [B → beta;·alpha;gamma;, b) calling for a shift. Then some set of items from which the union was formed has item [A → alpha;·, a], and since the cores of all these states are the same, it must have an item [B →beta;·alpha;gamma;, c] for some c. But then this state has the same shift/reduce conflict on a, and the grammar was not LR(1) as we assumed. Thus, the merging of states with common cores can never produce a shift/reduce conflict that was not present in one of the original states, because shift actions depend only on the core, not the lookahead.
It is possible, however, that a merger will produce a reduce/reduce conflict, as the following example shows.
Example 4.58 : Consider the grammar
which generates the four strings acd, ace, bcd, and bce. The reader can check that the grammar is LR(1) by constructing the sets of items. Upon doing so, we find the set of items {[A → c·, d), [B → c·, e]} valid for viable prefix ac and {[A → c·, e] , [B → c·, d)} valid for bc. Neither of these sets has a conflict, and their cores are the same. However, their union, which is
generates a reduce/reduce conflict, since reductions by both A → c and B → c are called for on inputs d and e.
We are now prepared to give the first of two LALR table-construction algorithms. The general idea is to construct the sets of LR(1) items, and if no conflicts arise, merge sets with common cores. We then construct the parsing table from the collection of merged sets of items. The method we are about to describe serves primarily as a definition of LALR(1) grammars. Constructing the entire collection of LR(1) sets of items requires too much space and time to be useful in practice.
Algorithm 4.59 : An easy, but spa
剩余内容已隐藏，支付完成后下载完整资料
4.7.4 构造LALR语法分析表
现在我们介绍最后一种语法分析器构造方法，即LALR（向前看-LR）技术。这个方法经常在实践中使用，因为用这种方法得到的分析表比规范LR分析表小很多，而且大部分常见的程序设计语言构造都可以方便地使用一个LALR文法表示，对于SLR文法，这一点也基本成立，只是仍然存在少量构造不能够方便地使用SLR技术来处理（例如，见例4.48）
我们对语法分析器的大小做一下比较。一个文法的SLR和LALR分析表总具有相同数量的状态，对于像C这样的语言来说，通常有几百个状态。对于同样大小的语言，规范LR分析表通常有几千个状态。因此，构造SLR和LALR分析表要比构造规范LR分析表更容易，而且更经济。
为了介绍LALR技术，让我们们再次考虑文法（4.55）。该文法的LR(1)项集如图4-41所示。让我们查看两个看起来差不多的状态，比如I4和I7。它们都只有一个项，其第一个分量都是C→d·。再I4中，向前看符号是c或者d，在I7中，$是唯一的向前看符号。
为了了解I4和I7在语法分析器中担负的不同角色，请注意这个文法生成了正则语言c*de*d.当读入输入cchellip;cdcchellip;cd的时候，语法分析器首先将第一组c以及跟在它们后面的d移入栈中。语法分析器在读入d之后进人状态4。然后，当下一个输人符号是c或d时，语法分析器按照产生式C→d进行一次归约。 要求c或d跟在后面是有道理的，因为它们可能是c* d中的串的开始符号。如果$跟在第一个d后面，我们就有形如ccd的输入，而它们不在这个语言中。如果$是下一个输人符号，状态4就会正确地报告一个错误。
语法分析器在读入第二个d之后进入状态7。然后，语法分析器必须在输人中看到$，否则输人开头的符号串就不具有c*dc*d的形式。因此状态7应该在输入为$时按照C→d进行归约，而在输入为c或d的时候报告错误。
现在，我们将I4和I7替换为I47,即I4和I7的并集。这个项集包含了[C→d·, c/d/$」所代表的三个项。原来在输入d上从I0、I2、I3,到达I4或I7的goto关系现在都到达I47。状态47在所有输入上的动作都是归约。这个经过修改的语法分析器行为在本质上和原分析器一样。虽然在有些情况下，原分析器会报告错误，而新分析器却将d归约为C。比如，在处理ccd或cdcdc这样的输入时就会出现这样的情况。新的分析器最终能够找到这个错误，实际上这个错误会在移人任何新的输人符号之前就被发现。
更一般地说，我们可以寻找具有相同核心(core)的LR(1)项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合。 比如在图4-41中，I4和I7就是这样一对项集，它们的核心是{C→d·}。类似地，I3和I6。是另一对这样的项集，它们的核心是{C→c·C,→c. C, C→.cC,C→·d}。另外,还有一对项集I8和I9,它们的公共核心是{C→cC·}。请注意，一般而言，一个核心就是当前正处理的文法的LR(0)项集，一个LR(1)文法可能产生多个具有相同核心的项集。
因为GOTO(I, X)的核心只由I的核心决定，一组被合并的项集的GOTO目标也可以被合并。因此，当我们合并项集时可以相应地修改G0T0函数。动作函数也需要加以修改，以反映出被合并的所有项集的非报错动作。
假设我们有一个LR(1)文法，也就是说，这个文法的LR(1)项集没有产生语法分析动作冲突。如果我们将所有具有相同核心的状态替换为它们的并集，那么得到的并集有可能产生冲突。但是因为下面的原因，这种情况不大可能发生:假设在并集中有一个项[A→alpha;·，a]要求按照A→alpha;进行归约，同时另一个项[B→beta;.alpha;gamma;, b]要求进行移人，那么就会出现在向前看符号a上的冲突。此时必然存在某个被合并进来的项集中包含项[A→alpha;·，a]，同时因为所有这些状态的核心都是相同的，所以这个被合并进来的项集中必然还包含项[B→beta;. alpha;gamma;, c]，其中c是某个终结符号。如果这样的话，这个状态中同样也有在输人a上的移入/归约冲突，因此这个文法不是我们假设的LR(1)文法。因此，合并具有相同核心的状态不会产生出原有状态中没有出现的移入/归约冲突，因为移人动作仅由核心决定，不考虑向前看符号。
然而，如下面的例子所示，合并项集可能会产生归约/归约冲突。
例4.58考虑文法
该文法产生四个串acd.，Ace，bcd和bce。读者可以构造出这个文法的LR(1)项集，以验证该文法是LR(1)的。完成这些工作之后，我们发现项集{[A→c·，d]},[B→c·，e]}是可行前缀ac的有效项，[A→c·，e]},[B→c·，d]是bc的有效项。这两个项集都没有冲突，并且它们的核心是相同的。然而，它们的并集，即
产生了一个归约/归约冲突，因为当输人为d或c的时候，这个合并项集既要求按照A→c 进行归约，又要求按照B→c进行归约。
我们将给出两个LALR分析表构造算法，现在来介绍其中的第一个。 这个算法的基本思想是构造出LR(1)项集，如果没有出现冲突，就将具有相同核心的项集合并。然后我们根据合并后得到的项集族构造语法分析表。我们将要描述的方法的主要用途是定义LRLA(1)文法。构造整个LR(1)项集族需要的空间和时间太多，因此很少在实践中使用。
算法4.59 一个简单，但空间需求大的LALR分析表的构造方法。
输入:一个增广文法G。
输出:文法G的LALR语法分析表函数ACTION和GOTO。
方法:
1)构造LR(1)项集族C={Io, I, .，. In}。
2)对于LR(1)项集中的每个核心，找出所有具有这个核心的项集，并将这些项集替换为它们的并集。
3)令C={Jo, J，.. J%}是得到的LR(1)项集族。状态i的语法分析动作是按照和算法4. 56中的方法根据J;构造得到的。如果存在一个分析动作冲突，这个算法就不能生成语法分析器，这个文法就不是LALR(1)的。
4) GOTO表的构造方法如下。如果J是一个或多个LR(1)项集的并集，也就是说J=I1cup;I2cup;hellip;cup;I4,那么GOTO(I1, X), GOTO(I2, X)，hellip;， GOTO(I4, X)的核心是相同的，因为I1,I2,hellip;,I4具有相同的核心。令K是所有和GOTO(I1，X)具有相同核心的项集的并集，那么GOTO(J, X) =K。
算法4.59生成的分析表称为G的LALR语法分析表。如果没有语法分析动作冲突，那么给定的文法就称为LALR(1)文法。在第(3)步中构造得到的项集族被称为LALR(1)项集族。
|例4.60 再次考虑文法(4.55)。该文法的GOTO图已经显示在图4-41中。我们前面提到过，有三对可以合并的项集。I3和I6被替换为它们的并集:
I4和I7被替换为它们的并集：
I8和I9被替换为它们的并集：
这些压缩过的项集的LALR动作和GOTO函数显示在图4-43中。
图4-43 例子4.54的文法的LALR分析表
要了解如何计算GOTO关系，考虑GOTO(I36，C)。在原来的LR(1)项集中，GOTO(I3,C)=I4，而现在I8是I89的一部分，因此我们令GOTO(I36，C)为I89。如果我们考虑I6，即I36的另一部分，我们仍然可以得到相同的结论。也就是说，GOTO(I6，C)=I9,I9现在是I89的一 部分。再举一个例子。考虑GOTO(I2, c)，即在状态I2上输人为c时执行移入之后的状态。在原来的LR(1)项集中,GOTO(I2,C)=I6。因为16现在是136的一部分， 所以GOTO(I2,c)变成了I36因此，图4-43中对应于状态2和输入c的条目被设置为s36,表示移入并将状态36压人栈中。
当处理语言c*dc*d中的一个串时，图4-42的LR语法分析器和图4-43的LALR语法分析器执行完全相同的移入和归约动作序列，尽管栈中状态的名字有所不同。比如，在LR语法分析器将I3或I6压人栈中时，LALR语法分析器将I36压人栈中。这个关系对于所有的LALR文法都成立。在处理正确的输人时，LR语法分析器和LALR语法分析器将相互模拟。
在处理错误的输人时，LALR语法分析器可能在LR语法分析器报错之后继续执行一些归约动作。然而，LALR语法分析器决不会在LR语法分析器报错之后移人任何符号。比如，在输人为ccd且后面跟有$时，图4-42的LR语法分析器将
0 3 3 4
压入栈中。并且在状态4上发现一个错误，因为下一个输入符号是$而状态4在$上的动作为报错。相应地，图4-43终得LALR语法分析器将执行对应的操作，将
- 36 36 47
压入栈中。但是状态47再输入为$时的动作为规约C→d。因此，LALR语法分析器将把栈中内容改为
- 36 36 89
现在，状态89在输入$上的动作为规约C→cC。栈中内容变为
- 36 89
此时仍要求进行一个类似的规约，得到栈
- 2
最后，状态2在输入$上的动作为报错，因此现在发现了这个错误。
4.7.5 高效构造LALR语法分析表的方法
我们可以对算法4.59进行多处修改，使得在创建LALR（1）语法分析表的过程中不需要构造出完整的规范LR（1）项集族。
首先，我们可以指使用内核项来表示任意地LR（0）或LR(1)项集。也就是说，只使用初始项[S→°·S]或[S→·S, $ ]以及那些点不在产生式体左端的项来表示项集。
我们可以使用一个“传播和自发生成”的过程(我们稍后将描述这个方法)来生成向前看符号，根据LR(0)项的内核生成LALR(1)项的内核。
如果我们有了LALR(1)内核，我们可以使用图4-40中的CLOSURE函数对各个内核求闭包，然后再把这些LALR(1)项集当作规范LR(1)项集族，使用算法4.56来计算分析表条目，从而得到LALR(1)语法分析表。
例4.61 我们将使用例子4.48中的非SLR文法作为一个例子，说明高效的LALR(1)语法分析表构造方法。下面我们重新给出这个文法的增广形式:
这个文法的完整LR(0)项集显示在图4-39中。这些项集的内核显示在图4-44中。
图4-44 文法（4.49）的LR(0)项集的内核
现在我们必须给这些用内核表示的LR(0)项加上正确的向前看符号，创建出LALR(1)项集的内核。在两种情况下，向前看符号b可以添加到某个LALR(1)项集J中的LR(0)项B→gamma;·delta;之上:
1)存在一个包含内核项[A→alpha;·beta;,a]的项集I,并且J=GOTO(I, X)。不管a为何值，在按照图4- 40的算法构造GOTO( CLOSURE( {[A→alpha;·beta;, a]}, X)图4-44 文法(4. 49)的LR(0)项集的内核
时得到的结果中总是包含[B→gamma;·delta;, b]。对于B→gamma;·delta;而言，这个向前看符号b被称为自发生成的。作为一个特殊情况，向前看符号$对于初始项集中的项[S →· S]而言是自发生成的。
2)其余条件和(1)相同，但是a=b,且按照图4- 40所示计算GOTO( CLOSURE({[A→alpha;·beta;, b]}), X)得到的结果中包含[B→gamma;·delta;, b]的原因是项A→alpha;·beta;有一个向前看符号b。在这种情况下，我们说向前看符号从I的内核中的A→alpha;·beta;传播到了J的内核中的B→gamma;·delta;上。请注意，传播关系并不取决于某个特定的向前看符号，要么所有的向前看符号都从一个项传播到另一个项，要么都不传播。
我们需要确定每个LR(0)项集中自发生成的向前看符号，同时也要确定向前看符号从哪些项传播到了哪些项。这个检测实际上相当简单。令#为一个不在 当前文法中的符号。令A→alpha;·beta;为项集I中的一个内核LR(0)项。对每个X计算J = GOTO( CLOSURE({[A→alpha;·beta;, #]}),X)。对于J中的每个内核项，我们检查它的向前看符号集合。如果#是它的向前看符号，那么向前看符号就从A→alpha;·beta;传播到了这个项。所有其他的向前看符号都是自发生成的。这个思想在下面的算法中被精确地表达了出来。这个算法还用到了一个性质: J中的所有内核项中点的左边都是X,也就是说，它们必然是形如B→gamma;X ·delta;的项。
算法4.62 确定向前看符号。
输入:一个LR(0)项集1的内核K以及一个文法符号X。
输出:由1中的项为GOTO(I, X)中内核项自发生成的向前看符号，以及I中将其向前看符号传播到GOTO(I, X)中内核项的项。
方法:算法在图4-45中给出。
图4-45 发现传播的和自发生成的向前看符号
现在我们可以把向前看符号附加到LR(0)项集的内核上，从而得到LALR(1)项集。首先，我们知道$是初始LR(0)项集中的S→·S的向前看符号。算法4. 62给出了所有自发生成的向前看符号。将所有这些向前看符号列出之后，我们必须让它们不断传播，直到不能继续传播为止。有很多方法可以实现这个传播过程。从某种意义上说，所有这些方法都跟踪已经传播到某个项但是尚未传播出去的“新”向前看符号。下面的算法描述了一个将向前看符号传播到所有项中的技术。
算法4. 63 LALR(1)项集族的内核的高效计算方法。
输入:一个增广文法G。
输出:文法G的LALR(1)项集族的内核。
方法:
1)构造G的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236553]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
