lemon解析器是LALR(1)还是SLR(1)？

Question

我正在阅读lemon解析器的PHP移植：

for ($i = 0; $i < $this->nstate; $i++) {   /* Loop over all states */
    $stp = $this->sorted[$i]->data;
    for ($cfp = $stp->cfp; $cfp; $cfp = $cfp->next) {
        /* Loop over all configurations */
        if ($cfp->rp->nrhs == $cfp->dot) {        /* Is dot at extreme right? */
            for ($j = 0; $j < $this->nterminal; $j++) {
                if (isset($cfp->fws[$j])) {
                    /* Add a reduce action to the state "stp" which will reduce by the
                    ** rule "cfp->rp" if the lookahead symbol is "$this->symbols[j]" */
                    PHP_ParserGenerator_Action::Action_add($stp->ap, PHP_ParserGenerator_Action::REDUCE,
                                            $this->symbols[$j], $cfp->rp);
                }
            }
        }
    }
}

在我看来，根据如何计算动作表，解析器是一个SLR(1)解析器，但在lemon的主页上，它演示了自己是一个LALR(1)解析器：

http://www.hwaci.com/sw/lemon/

是SLR(1)还是LALR(1)？

Answer 1

如果它是纯SLR，就不会有任何先行符号($this->符号$j)用于控制缩减。因此，我得出结论是LALR(1)。

编辑: yoyo是对的，SLR(1)确实使用下一个输入符号来控制缩减(我将问题误读为LALR(1) vs SLR(0)，这根本不在乎)；我接受更正。在检查中，SLR(1)使用(生产规则上下文无关) FOLLOW集合来控制缩减；LALR(1)使用(左上下文相关)前视集合。因此，两者在每次缩减时都有一个“先行”设置。这意味着你不能从这段代码中分辨出它是哪种类型的；充其量，我们希望编码器真的在计算“一个”先行的集合。你必须看到代码的其余部分才能知道它是什么类型的。

实际上，如果您要构建一个自下而上的解析器生成器，您可以选择使用几乎完全相同的机制构建SLR(0) (我以前就是这么做的，我的大脑就是这样理解这个问题的)、SLR(1)、LALR(1)和LR(1)解析器生成器。30年的经验表明，LALR(1)是其中最实用的，因此默认值是...LALR(1)；SLR(x)是严格意义上的一个子集，所以只要多花一点力气就能得到LALR(1)，为什么还要费心这么做呢？如果Lemon实现器遵循传统，我希望有一个LALR(1)解析器生成器。所以现在你在某种程度上相信了他们的话。

当然，您可以构建一个简单的实验来说服自己。只需构建SLR(1)不能正确解析LALR(1)语法，并尝试它。或者，您可以非常仔细地阅读代码。

请参阅http://en.wikipedia.org/wiki/LALR_parser上的LALR解析