更强大的LR语法分析器

在输入中向前看一个符号，来扩展前面的LR语法分析技术。有两种不同的方法。

“规范LR”方法。它充分利用了向前看符号。这个方法使用了一个很大的项集，称为LR(1)项集。
“向前看LR”，或称为LALR方法。它基于LR(0)项集族。和基于LR(1)项的典型语法分析器相比，它的状态要少很多。

通过向LR(0)项中小心地引入向前看符号，我们使用LALR方法处理的文法比使用SLR方法时处理的文法更多，同时构造得到的语法分析表却不比SLR分析表大。很多情况下，LALR方法是最合适的选择。

LALR(1)形式上和LR(1)相同，采用的是LR(1)项。
LALR(1)大小上和LR(0)/SLR相当。
LALR(1)分析能力低于LR(1)但高于SLR。（CRE:分析能力代表延迟发现的错误更少）

规范LR(1)项

如果在状态中包含更多的信息，我们就可以排除一些不正确的A->α规约。在必要时，我们可以通过分裂某些状态，设法让LR语法分析器的每个状态精确地指明哪些输入符号可以跟在句柄α后面，从而使α可能被规约为A。

将这个额外的信息加入状态的方法是对项进行精化，使它包含第二个分量，这个分量的值是一个终结符。项的一般形式变为了$[A→α·β, a]$，我们称其为LR(1)项。其中的”1”指的是第二个分量的长度，第二个分量称为这个项的向前看符号。

在形如$[A→α·β,a]$且β≠ε的项中，向前看符号没有任何作用，但是一个形如$[A→α·,a]$的项只有在下一个输入符号等于a时才会要求按照A→α进行规约。因此，只有才栈顶状态中包含一个LR(1)项$[A→α·,a]$，我们才会在输入为a进行A→规约。
这样a的集合总是FOLLOW(A)的子集，而且很可能是一个真子集。

构造LR(1)项集

构造有效LR(1)项集族的方法实质上和构造规范LR(0)项集族的方法相同。我们只需要修改CLOSURE和GOTO两个过程。

SetOfItems CLOSURE(I)
{
    repeat
        for(I中的每个项[A->α·Bβ,a])
            for(G'中每个产生式B->γ)
                for(FIRST(βa)中的每个终结符b)
                    将[B->·γ, b]加入到集合I中;
    until(不能向I中加入更多项);  
    return I;
}

SetOfItems GOTO(I, X)
{
    将J初始化为空集;
    for(I中的每个项[A->α·Xβ, a])
        将项[A->αX·β, a]加入到集合J中;
    return CLOSURE(J);
}

void items(G')
{
    将C初始化为{CLOSURE}({[S' -> ·S, $]});
    repeat
        for(C中每个项集I)
            for(每个文法符号X)
                if(GOTO(I,X)非空且不在C中)
                    将GOTO(I,X)加入C中;
    until(不再有新的项集加入到C中);
}

规范LR(1)语法分析表

1) 构造项G’的LR(1)项集族。
2) 语法分析器的状态i根据$I_i$构造得到。状态i的语法分析动作按下面的规则确定：
+ 如果$[A->α·aβ, b]$在$I_i$中，并且$GOTO(I_i, a) = I_j$，那么将$ACTION[i,a]$设置为“移入j”。（a必须是一个终结符号）
+ 如果$[A->α·, a]$在$I_i$中且A≠S’，那么将$ACTION[i,a]$设置为“规约A->α”。
+ 如果$[S’->S·, $]$在$I_i$中，那么将$ACTION[i,$]$设置为“接受”。
+ 如果上述规则会产生任何冲突动作，我们就说这个文法不是LR(1)的，这个算法无法为这个文法生成语法分析器。

3) 状态i相对于各个非终结符号A的goto转换按照下面的规则构造得到：如果$GOTO(I_i,A)=I_j$，那么$GOTO[i,A]=j$。
4) 所有没有按照规则(2)和(3)定义的分析表条目都设置为“报错”。
5) 语法分析器的初始状态是由包含$[S’->·S,$]$的项集构造得到的状态。

每个SLR(1)文法都是LR(1)文法。但是对于一个SLR(1)文法而言，规范LR(1)语法分析器的状态要比同一文法的SLR语法分析器的状态多。

构造LALR语法分析器

我们可以寻找具有相同核心(core)的项集，并将这些项集合并为一个项集。

所谓项集的核心就是其第一分量的集合。一般而言，一个核心就是当前正在处理文法的LR(0)项集，一个LR(1)文法可能产生多个具有相同核心的项集。

向前看符号和移入操作没有关系，移入操作仅由核心决定。所以：①合并时只会有归约-归约冲突。②LALR分析法可能会做多余的归约动作，但是绝不会做错误的移进动作。

如果一个LR(1)项集没有语法分析动作冲突，如果我们将所有具有相同核心的状态替换为它们的并集，那么得到的并集可能产生冲突，但是这种情况不大可能发生。

CRE：不大可能发生的原因简单总结为：如果有移入-归约冲突，那也是从合并前的某个项集继承来的。

LALR分析表构造方法之一

这是一个简单的，但是空间需求大的构造方法。

1) 构造LR(1)项集族$C={I_0, I_1, …, I_n}$。

2) 对于LR(1)项集中每个核心，找出所有具有这个核心的项集，并将这些项集替换为它们的并集。

3) 令$C’={J_0, J_1,…,Jm}$是得到的LR(1)项集族。状态i的语法分析动作是按照之前的规范LR(1)语法分析表构造算法根据$J_i$构造得到的。如果存在一个分析动作冲突，这个文法就不是LALR(1)的。
4) GOTO表的构造方法如下。如果J是一个或多个LR(1)项集的并集，也就是说$J=I_1∪I_2….∪I_k$，那么$GOTO(I_1,X)$,$GOTO(I_2,X)$,…,$GOTO(I_k,X)$的核心是相同的，因为$I_1$、$I_2$…$I_k$具有相同核心。令K是所有和$GOTO(I_1,X)$具有相同核心的项集的并集，那么$GOTO(J,X)=K$。

如果没有语法分析动作冲突，那么给定的文法就称为LALR(1)文法。第三步构造的项集族称为LALR(1)项集族。

高效构造LALR语法分析表的方法

我们可以对上面的算法进行多处修改，使得在创建LALR(1)分析表的过程中不需要构造完整的规范LR(1)项集族。

首先，我们可以只使用内核项来表示任意的LR(0)或LR(1)项集。也就是说，只使用初始项$[S’->·S]$或$[S’->·S,$]$以及那些点不在产生式体左端的项来表示项集。

我们可以使用一个“传播和自发生成”的过程来生成向前看符号，根据LR(0)项的内核生成LALR(1)项的内核。

如果我们有了LALR(1)的内核，我们可以使用构造LR1项集所用的CLOSURE函数对各个内核求闭包，然后再把这些LALR(1)项集当作规范LR(1)项集族，使用规范LR(1)分析表构造算法来计算分析表条目，从而得到LALR(1)语法分析表。

（具体算法见编译原理p173-175）

LR语法分析表的压缩

对于小型设备，有一个比二维数组更加高效的编码方法是很重要的。

一个可用于压缩ACTION字段的技术所基于的原理是ACTION表中通常有很多相同的行。这些行存储为一维数组，然后使用一个指向一维数组的指针，就可以节约很多空间。

一个状态最频繁的动作可以放在列表的结尾处，把它对应的终结符改为”any”。如果没有在列表中找到对应的输入符号，那么不管输入是什么，我们都选择”any”的动作。

CRE：any很多时候都对应err。

我们也可以把GOTO表编码为一个列表。但是更高效的方法是为每个非终结符A构造一个数对的列表。A的列表中每个对形如(当前状态,下一状态)。

使用二义性文法

实际上，每个二义性文法都不是LR的。然而，有些类型的二义性文法在语言的规约和实现中很有用。
对于像表达式这样的语言构造，二义性文法能提供比任何等价的非二义性文法更短更自然的规约。
虽然使用的文法是二义性的，但我们在所有情况下都会给出消除二义性的规则，使得每个句子只有一棵语法树。
要保守地使用二义性文法，并且在严格控制下使用。

使用优先级和结合性解决冲突。（比如算式表达式的某些二义性文法）
使用就近原则。（比如if-then-else语句的二义性文法）

ChatGPT:二义性文法通常发生移入-规约冲突。移入-移入冲突和规约-规约冲突发生的情况少，也容易解决。

LR语法分析中的错误恢复

（详见《编译原理》p181）

（END）