1 LR语法分析器

本节介绍一个有效的自底向上的分析技术，可以用于一大类上下文无关文法的语法分析。这种技术叫做LR(k)分析法，其中L表示从左到右扫描输入串，R表示构造一个最右推导的逆过程，k指的是在决定语法分析动作时需要向前看的符号个数。(k)省略时，假设k是1。LR分析富有吸引力的原因有以下几点：

v LR语法分析器能识别几乎所有能用上下文无关文法描述的程序设计语言的结构。

v LR分析法是已知的最一般的无回溯移动归约语法分析法，而且可以和其它移动归约分析一样被有效地实现。

v LR分析法分析的文法类是预测分析法能分析的文法类的真超集。

v 在自左向右扫描输入符号串时，LR语法分析器能及时发现语法错误。

这种分析方法的主要缺点是，对典型的程序设计语言文法，手工构造LR语法分析器的工作量太大，需要专门的工具。

1.1 LR语法分析算法

规范归约（最左归约-最右推导的逆过程）的关键问题是寻找句柄。在一般的“移进-归约”过程中，当一串貌似句柄的符号串呈现于栈顶时，我们有什么方法可以确定他是否为相对于某一个产生式的句柄呢？LR分析的基本思想是，在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

从LR分析方法可以看出，其实现有一定的困难。作为归约过程的“历史”材料的积累虽不困难（实际上，这些材料都存在分析栈中），但是“展望”材料的汇集却是一件很不容易的事情。这种困难不是理论上的，而是实际实现上的。

后面所讨论的LR分析方法都是带有一定限制的。

一个LR分析器实质上十一个带先进后出内存（栈）的确定有限状态自动机。我们将把“历史”和“展望”材料综合的抽象成某些“状态”，存放在栈里。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。

LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一确定的。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放在栈里。由此，可以看到栈的结构如下：

图表 41

栈的每一项内容包括状态S和文法符号X两部分。(S0 , $)为分析开始前预先放到栈里的初始状态和句子括号（$句子$）。栈顶状态为Sm，符号串X1X2…Xm是至今已移进归约出的部分。

LR分析器模型如下图所示：

图表 42

LR分析器的核心部分是一张分析表。这张分析表包括两部分，一个是“动作”（action）表，一个是“状态转移”（goto）表。它们都是二维数组。ACTION[s ,a]规定了当前状态s面临输入符号a时应采取什么动作。GOTO[s, X]规定了状态s面对文法符号X（终结符或非终结符）时下一个状态是什么。显然GOTO[s, X]定义了一个以文法符号为字母表DFA。

每一项ACTION[s,a]所规定的动作不外是下述四种可能之一。

(1) 移进：把(s,a)的下一个状态s’=GOTO[s,a]和输入符号a推进栈，下一个输入符号变成现行输入符号

(2) 归约：指用某一个产生式A→β进行归约。假若β的长度为r，归约的动作是A，去除栈顶的r个项，使状态Sm-r变成栈顶状态，然后把（Sm-r, A）的下一个状态s’=GOTO[Sm-r, A]和文法符号A推进栈。归约动作不改变现行输入行。执行归约动作意味着β(=Xm-r+1…Xm)已经呈现于栈顶而且是一个相对于A的句柄。

(3) 接受：宣布分析成功，停止分析器的工作。

(4) 报错：发现源程序含有错误，调用出错处理程序。

LR分析器的总控程序本身的的工作是非常简单的，任何一步动作都只需按照栈顶状态s和现行输入符号a执行ACTION[s,a]所规定的动作。对不同的分析表，总控程序都是一样的工作。

对于一个LR分析器来说，栈顶状态提供了所需的一切“历史”和“展望”信息。请注意一个非常重要的事实：如果仅由栈的内容和现实的输入符号就可以识别一个句柄，那么就可以用一个有限自动机自底向上扫描栈的内容和检查现行输入符号来确定呈现于栈顶的句柄是什么（当栈顶呈现一个句柄时）。实际上，LR分析表的goto函数就是这样一个有限自动机，只是它不需要每次移动都读栈。

显然，上面提到的这种代替我们做扫描的动作不是在栈的形成过程中完成的，也不是总控程序应该完成的动作，它应该是在分析表的构造过程中实现的。那么如何为给定的文法构造LR语法分析表，就是我们下面要讲述的重点。给定文法G，如果我们能为G构造出语法分析表，则称G是LR文法。很多上下文无关文法不是LR文法，但典型的程序设计语言的结构一般都可以避免非LR文法。直观的，为了使一个文法是LR文法，只要保证句柄出现在栈顶时，自做到右扫描的移动归约分析器能够及时的识别它。

LR语法分析器不需要扫描整个栈就可以知道什么时候句柄出现在栈顶。栈顶的状态符号包含了所需要的一切信息。如果识别句柄的有穷自动机自底向上读栈中的文法符号，栈顶所存的状态符号正好是这个自动机所进入的状态，于是LR语法分析器从栈顶的状态即可确定它需要从栈中了解的一切。

能够用来帮助LR语法分析器做出移动归约决定的另一个的信息源是下k个输入符号。我们实际上感兴趣的是k=0或k=1的情况。这里我们仅讨论k≤1的情况。

上面的描述可能较为抽象，下面我们来举一个LR分析的例子，该例子来自《编译原理以及实现》。

首先，我们添加一条新的开始符号S’ 。在规则中增加S’  ->  S.增加了规则的文法叫做扩充文法。

考虑下面给出成对括号的扩充文法：

S’ - > S

S – > ( S ) S

S - > 

依据我们先前文法表示规定，S - > ε我们使用 S – > 表示，在后面这两种表示是等效的。

下表给出使用该文法的串（）的自底向上的分析。

图表 43

我们判断是否为接受状态，是根据分析栈顶是否为S’，而待输入的符号是否为$ 。在3.1节的CLanguage定义中，我们看到CLanguage构造了一个gensymbol 值为0，名字为$。产生符号gensymbol就是现在的$，在这里算是有了一个注脚。

本章可能是全书的最难的部分，建议学习本章的时候还是要好好复习一下《编译原理》的教材。在表图表 43中，共4个规约，它们与最右推导的4个步骤对应的顺序恰好相反：

S’ = > S = > (S)S = > (S) = > ( )

在分析栈中出现的符号序列称为右句型的可行前缀。例如（，（S 是右句型（S）的可行前缀。

1.2 LR(0)项目集族和LR(0)分析表的构造

1.2.1 LR（0）项

上下文无关的文法LR（0）项（LR(0) item）（或简写为item）是在右边带有区分位置的产生式。可以使用一个圆点来指出这个区分位置。例如产生式A→XYZ对应有四个项目：

A→?XYZ

A→X?YZ

A→XY?Z

A→XYZ?

但是，产生式A→ε只对应一个项目A→?。在计算机中，每一个项目可以用一对整数表示，第一个整数代表产生式编号，第二个整数指出圆点的位置。在WACC中，我们可以看到：

class CItem  

{

public:

    int RuleInd;//项目所需的rule

    int Dot;    //圆点位置

    int Isetind ;// 所在的专案集序号

    CFirstSet precs; //先行符号集 

    CItem();

    CItem(int RuleInd, int Dot);

    virtual ~CItem();

    void getBeforeDot(CLanguage &L,vector<CSymbol*> &vect); 

    //waiter is the first unterminate symbol after dot

    void getAfterWaiter(CLanguage &L,vector<CSymbol*> &vect); 

    void ComputerEClosure(CLanguage &L, vector<CItem> &Ivec);

    void setRuleInd(int RuleInd);

    void setDot(int Dot);

    void setI(int Isetind);

    void ComputerEPrecs(CLanguage &L, vector<CItem> &Ivec);

    CSymbol* Go(CItem & goItem,CLanguage &L);//Go(I,X), return X,J注意同时将precs传播出去

private:

    int getRule(CSymbol* LeftPart, CLanguage &L,int& section);

    int UnionClosure(vector < CItem > & Ivec, CLanguage &L);

    bool checkFresh(CItem item, vector< CItem > &Ivec);

};

注意框住的部分，WACC正是使用两个整数RuleId 来表示规则编号，Dot表示圆点的位置。其它函数我们会依次慢慢解释。

4.1节我们举的例子:

S’ - > S

S – > ( S ) S

S - > 

这个文法存在有3个产生式8个项目：

S’ - > ?S

S’ - > S?

S – >? ( S ) S

S – > (?S ) S

S – > ( S ?) S 

S – > ( S ) ?S

S - > ( S ) S?

S - >?

项目的概念的思想就是指项目记录了特定的文法规则右边识别的中间步骤。项目A -> β?γ是由文法规则A - > α构成（其中α=βγ），这一点意味着β已经出现在栈顶。项目A - > ?α称为初始项，A - > α? 称为完整项。

我们可以用项目状态构造一个NFA，用来识别这个文法所有的可行前缀。文法的开始符号S’仅在第一个产生式左部出现。使用这个事实，我们对文法进行拓广，加入一个新的开始符号S’。状态之间转换规则依照如下两条：

(1) 如果状态i和j来自同一个产生式，而且状态j的圆点只落后于状态i的原点一个位置，如状态i为X→X1 …Xi-1 ?Xi…Xn，而状态j为X→X1 …Xi ?Xi+1…Xn，那么就从状态i画一条标志为Xi的弧到状态j。

图表 44

(2) 假若状态i的圆点之后的那个符号为非终结符，如i为X→α?Aβ，A为非终结符，那么就从状态i画ε弧到所有A→?γ状态。即，所有这些圆点出现在最左边的A的项目。

图表 45

(3) NFA的接受状态呢？NFA仅仅用于了解分析状态，由分析程序来决定何时接受，因此不必包含接受状态。

然后对这个NFA进行确定化，就得到了一个以项目集合为状态的DFA，在这个DFA中，我们对状态进行了重新编号，并且把每个状态所含的项目都列在其中。

这里提及了两个名词，NFA和DFA。所谓DFA就是Deterministic finite automaton,即确定性有穷自动机，NFA就是Nondeterministic finite automaton ,即非确定性有穷自动机。他们实际上是等价的，NFA可以通过epsilon闭包计算转换成DFA，而DFA则可以十分方便地转换成分析程序。