一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。 自下而上分析方法是一种移进-归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自下而上分析法的关键问题是在分析过程中如何确定句柄。LR分析法根据分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K≥0）符号就可惟一地确定分析器的动作是移进还是归约以及用哪个产生式归约，因而也就能惟一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR的分析过程是一种规范归约过程。 LR分析方法的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号这3方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。 LR分析法的基本思想是符合哲理的。所以，这种分析法也是非常一般的。因此，实现起来也就非常困难。作为归约过程的“历史”材料的积累虽不困难（实际上，这些材料都保存在分析栈中），但是，“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的，而是实际实现上的。因为，根据历史推测未来，即使是推测未来的一个符号，也常常存在着很多可能性 。所以，当把“历史”和“展望”材料综合在一起时，复杂性就大大增加。如果简化对“展望”材料的要求，我们就可能获得实际可行的分析算法。 LR分析法比起自上向下的LL分析法和自下向上的优先分析方法对文法的限制要少得多，也就是说，对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快、准确、及时地指出出错位置的优点。LR分析法的一个主要缺点是，若用手工构造分析程序，则工作量相当大，因此，必须求助于自动产生这种分析程序的产生器。这种产生器称为LR分析程序自动产生器。本章我们将讨论这样一类产生器，利用这种产生器，我们不仅能自动产生一大类上下文无关文法的LR分析程序，还能指出文法含二义的情形或难于分析的特殊结构。 二、实验目的要求 输入：任意的压缩了的上下文无关文法。 输出：相应的LR（0）分析表。 三、实验原理 对于LR文法，我们可以自动构造相应的LR分析表。为了构造LR分析表，我们需要定义一个重要概念——文法的规范句型“活前缀”。 这种句柄之后不含任何符号的前缀称为活前缀。
在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。 对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。 假若一个文法G的拓广文法G?的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。该自动机的状态集合即为该文法的LR（0）项目集规范族。 构造识别文法活前缀DFA有3种方法： （1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA再确定为DFA； （2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA； （3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。 符号串的前缀是指该符号串的任意首部，包括空串ε。例如，对于符号串abc，其前缀有ε，a，ab，abc。如果输入串没有错误的话，一个规范句型的活前缀是该句型的一个前缀，但它不含句柄之后的任何符号。之所以称为活前缀，是因为在该前缀后联接尚未输入的符号串可以构成一个规范句型。 活前缀与句柄的关系如下： （1）活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。 （2）活前缀只含句柄的一部分符号，表明A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。 （3）活前缀不含有句柄的任何符号，此时期望A→β的右部所推出的符号串。 在文法G的每个产生式的右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR（0）项目。如产生式A? xyz有如下项目：A?.xyz，A?x.yz，A?xy.z，A?xyz.。为刻划分析过程中的文法的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶），可以用这种标有圆点的产生式来确定。 （1）A→β.刻划产生式A→β的右部β已出现在栈顶。
（2）A→β1.β2 刻划A→β1β2的右部子串β1已出现在栈顶，期待从输入串中看到β2推出的符号。 （3）A→.β 刻划没有句柄的任何符号在栈顶，此时期望A→β的右部所推出的符号串。 （4）对于A→ε的LR(0)项目只有A→．。 设文法G=（VT，VN，S，P）是一个上下文无关文法，若存在一个规范推导S?错误!未找到引用源。Awrm*错误!未找到引用源。错误!未找到引用源。1错误!未找到引用源。2w（其中A错误!未找到引用源。错误!未找到引用源。1错误!未找到引用源。2错误!未找到引用源。P），则称项目A错误!未找到引用源。错误!未找到引用源。1?错误!未找到引用源。2对活前缀错误!未找到引用源。=错误!未找到引用源。错误!未找到引用源。1是有效的，即LR(0) 有效项目。 从直观意义上讲，一个LR(0)项目指明了在分析过程中的某一步我们看到产生式的多大部分被识别，LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。 不同的LR(0)项目，反映了分析栈顶的不同情况。我们根据LR(0)项目的作用不同，将其分为四类： （1）归约项目： 表现形式：A→a. 这类LR(0)项目表示句柄a恰好包含在栈中，即当前栈顶的部分内容构成了所期望的句柄，应按A→a进行归约。 （2）接受项目： 表现形式：S→a. 其中S是文法惟一的开始符号。这类LR(0)项目实际是特殊的归约项目，表示分析栈中内容恰好为a，用S→a进行归约，则整个分析成功。 （3）移进项目： 表现形式：A→a.b?（b?VT） 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前级，需将b移进分析栈。 （4）待约项目： 表现形式：A→α.Bβ （B?VN） 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为构成恰好有句柄的活前缀，应把当前输入字符串中的相应内容先归约到B。 在给出LR(0)项目的定义和分类之后，我们从这些LR(0)项目出发，来构造能识别文法所有前缀的有限自动机。其步骤是：首先构造能识别文法所有活前缀的非确定的有限自动机，再将其确定化和最小化，最终得到所需的确定的有限自动机。
由文法G的LR(0)项目构造识别文法G的所有活前缀的非确定有限自动机的方法： （1）规定含有文法开始符号的产生式（设S?→A）的第一个LR(0)项目（即S?→.A）为NFA的惟一初态。 （2）令所有LR(0)项目分别对应NFA的一个状态且LR(0)项目为归约项目的对应状态为终态。 （3）若状态i和状态j出自同一文法G的产生式且两个状态LR(0)项目的圆点只相差一个位置，即： 若i为X→X1X2·…Xi-1·Xi…Xn， j为 X→X1X2…Xi·Xi+1…Xn，则从状态i引一条标记为Xi的弧到状态j。 （4）若状态i为待约项目（设X→α·Aβ），则从状态i引ε弧到所有A→·r的状态。 为了使“接受”状态易于识别，我们通常将文法G进行拓广。 假定文法G是一个以S为开始符号的文法，我们构造一个G?，它包含了整个G，但它引进了一个不出现在G中的非终结符S?，并加进一个新产生式S?→S，以S?→SG?为开始符号。那么，我们称G?是G的拓广文法。 这样，便会有一个仅含项目S?→S的状态，这就是惟一的“接受”态。 如果I是文法G＇的一个项目集，定义和构造I的闭包CLOSURE(I)如下： （1） I的项目都在CLOSURE(I)中。 （2） 若A→?.B?属于CLOSURE(I)，则每一形如B→.?的项目也属于CLOSURE(I)。 （3） 重复（2）直到CLOSURE(I)不再扩大。 定义转换函数如下： GO（I，X）= CLOSURE（J） 其中：I为包含某一项目集的状态，X为一文法符号，J={ A→?X .? | A→?.X ?∈I}。 圆点不在产生式右部最左边的项目称为核，惟一的例外是S′→.S，因此用GOTO（I，X）状态转换函数得到的J为转向后状态闭包项目集的核。 使用闭包函数（CLOSURE）和转换函数(GO(I,X))构造文法G’的LR(0)的项目集规范族，步骤如下： （1） 置项目S′→.S为初态集的核，然后对核求闭包CLOSURE（{S′→.S}）得到初态的闭包项目集。 （2） 对初态集或其他所构造的项目集应用转换函数GO(I，X)= CLOSURE(J)求出新状态J的闭包项目集。 （3） 重复（2）直到不出现新的项目集为止。
计算LR（0）项目集规范族C={I0，I1 , ... In }的算法伪代码如下： Procedure itemsets(G’); Begin C := { CLOSURE ({S’?.S})} Repeat For C 中每一项目集I和每一文法符号X Do if GO(I,X) 非空且不属于C Then 把 GO(I,X) 放入C中 Until C 不再增大 End; 一个项目集可能包含多种项目，若移进和归约项目同时存在，则称移进-归约冲突，若 归约和归约项目同时存在，则称归约-归约冲突。下面看一个具体的例子： 我们希望能根据识别文法的活前缀的DFA建立LR分析器，因此，需要研究这个DFA的每个项目集（状态）中的项目的不同作用。 我们说项目A→β1.β2对活前缀αβ1是有效的，其条件是存在规范推导S???A????1?2?。一般而言，同一项目可能对几个活前缀都是有效的（当一个项目出现在几个不同的集合中时便是这种情形）。若归约项目A→β1.对活前缀??1是有效的，则它告诉我们应把符号串?1归约为A，即把活前缀??1变成αA。若移进项目A→β1.β2对活前缀??1是有效的，则它告诉我们，句柄尚未形成，因此，下一步动作应是移进。但是，可能存在这样的情形，对同一活前缀，存在若干项目对它都是有效的。而且它们告诉我们应做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许能够获得解决。 对于每个活前缀，我们可以构造它的有效项目集。实际上，一个活前缀γ的有效项目集正是从上述的DFA的初态出发，经读出γ后而到达的那个项目集（状态）。换言之，在任何时候，分析栈中的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一条基本定理。实际上，栈顶的项目集（状态）体现了栈里的一切有用信息——历史。 前面我们已经对LR（0）文法进行了定义,下面我们来看一下LR（0）分析表是如何构造的。 对于LR（0）文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。下面是构造LR（0）分析表的算法。
编译原理实验课程教案 - 图文
