檸檬解析器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）？

回答

相關問題