2

我正在阅读柠檬解析器的 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) 解析器，根据它如何计算动作表，但是@the home page of lemon，它证明自己是一个 LALR(1) 解析器：

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

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

4

1 回答 1

2

如果它是纯 SLR，则不会有任何前瞻符号 ($this->symbol[$j]) 用于控制缩减。所以我断定它是 LALR(1)。

编辑： yoyo 是对的 SLR( 1 ) 确实使用下一个输入符号来控制减少（我将问题误读为 [LALR(1) vs] SLR(0)，这根本不关心）；我站得更正了。在检查中，SLR(1) 使用（生产规则上下文无关的）FOLLOW 集来控制归约；LALR(1) 使用（依赖于左上下文的）LOOKAHEAD 集。因此，两者都在每次减少时设置了“前瞻”。这意味着您无法从该代码片段中分辨出它是哪种类型。充其量我们希望编码器真的在计算“一个”前瞻集。您必须查看其余代码才能知道它是什么类型。

实际上，如果您要构建一个自下而上的解析器生成器，您可以选择构建 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 解析

于 2011-02-16T10:29:59.383 回答