Является ли анализатор лимона LALR(1) или SLR(1)?

Я читаю 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) в соответствии с тем, как он вычисляет таблицу действий, но на домашней странице лимона он демонстрирует себя как синтаксический анализатор LALR(1):

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

Это SLR(1) или LALR(1)?


parsing lemon
person yoyo    schedule 16.02.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Если бы это был чистый SLR, не было бы никаких символов предпросмотра ($this->symbol[$j]), используемых для управления сокращением. Итак, я делаю вывод, что это LALR (1).

EDIT: 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) может, и попробуйте ее. Или вы можете очень внимательно прочитать код.

См. анализ LALR на http://en.wikipedia.org/wiki/LALR_parser.

person Ira Baxter    schedule 16.02.2011