柠檬解析器LALR（1）还是SLR（1）？

我读柠檬解析器的PHP portation：柠檬解析器LALR（1）还是SLR（1）？

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主页它表现为LALR（1）解析器本身：

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

它是SLR（1）还是LALR（1）？

来源

2011-02-16 yoyo

如果它是纯SLR，则不会有任何用于控制缩小的前瞻符号（$ this-> symbol [$ j]）。所以我认为它是LALR（1）。（我错误地将[LALR（1）vs] SLR（0）这个问题误解了，它根本不在意）;但是，我立场纠正。在检查中，SLR（1）使用（生产规则上下文无关）FOLLOW集来控制减少量; LALR（1）使用（左上下文相关）LOOKAHEAD集。所以，每个缩减都有一个“前瞻”。这意味着你不能从这个代码片断中知道它是哪种类型;我们最好希望编码器真的计算出“一个”前瞻集。您必须查看代码的其余部分才能知道它是什么类型。作为一个实际的问题，如果你打算建立一个自下而上的语法分析器生成器，你可以选择构建单反（0）[这是我曾经做过的，这就是我的大脑如何误读这个问题），SLR（ 1），LALR（1）和LR（1）解析器生成器使用几乎完全相同的机器。 30年的经验表明，LALR（1）是这些中最实用的，所以默认是... LALR（1）; SLR（x）是严格意义上的子集，所以如果只有更多的努力让你获得LALR（1），为什么还要这么做呢？如果柠檬实现者遵循传统，我期望一个LALR（1）解析器生成器。所以，现在你可以听取他们的意见。

当然，您可以构建一个简单的实验来说服自己。只需构建一个SLR（1）不能分析LALR（1）就可以尝试的语法。或者你可以仔细阅读代码。

见LALR解析在http://en.wikipedia.org/wiki/LALR_parser

来源

2011-02-16 10:29:59

@yoyo：你说得对，我修改我的答案。 – 2011-02-17 16:14:21

柠檬解析器LALR（1）还是SLR（1）？

回答

相关问题