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

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

2 голосов
/ 16 февраля 2011

Я читаю 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)?

1 Ответ

2 голосов
/ 16 февраля 2011

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

РЕДАКТИРОВАТЬ: yoyo прав SLR ( 1 ) действительно использует символы следующего ввода для управления сокращениями (я неправильно прочитал вопрос как [LALR (1) против] 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), и попробуйте. Или вы можете очень внимательно прочитать код.

См. Разбор LALR на http://en.wikipedia.org/wiki/LALR_parser

...