Ist der Zitronenparser LALR(1) oder SLR(1)?

Question

Ich lese gerade die PHP-Portierung des Lemon-Parsers:

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);
                }
            }
        }
    }
}

Es scheint mir, dass der Parser ein SLR(1)-Parser ist, wenn man bedenkt, wie er die Aktionstabelle berechnet, aber auf der Homepage von Lemon wird er als LALR(1)-Parser dargestellt:

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

Ist es SLR(1) oder LALR(1)?

Answer 1

Wäre es ein reines SLR, gäbe es keine Vorausschau-Symbole ($this->symbol[$j]), die zur Steuerung einer Reduzierung verwendet würden. Daraus schließe ich, dass es sich um LALR(1) handelt.

EDIT: yoyo hat recht SLR( 1 ) verwendet Next-Input-Symbole zur Kontrolle von Reduktionen (ich habe die Frage falsch verstanden, nämlich als [LALR(1) vs.] SLR(0), das sich einfach nicht darum kümmert); ich habe mich korrigiert. Bei der Überprüfung verwendet SLR(1) den (produktionsregelkontextfreien) FOLLOW-Satz zur Steuerung von Reduktionen; LALR(1) verwendet den (linkskontextabhängigen) LOOKAHEAD-Satz. Beide haben also einen "Lookahead"-Satz für jede Reduktion. Das bedeutet, dass man aus diesem Codefragment nicht erkennen kann, um welche Art es sich handelt; bestenfalls können wir hoffen, dass der Programmierer wirklich "eine" Vorausschau-Menge berechnet. Man müsste sich den Rest des Codes ansehen, um zu wissen, um welche Art es sich handelt.

Wenn Sie einen Bottom-up-Parser-Generator bauen wollen, können Sie wählen, ob Sie SLR(0) (was ich einmal getan habe, und so hat mein Gehirn die Frage falsch verstanden), SLR(1), LALR(1) und LR(1) Parser-Generatoren bauen wollen, wobei Sie fast genau die gleiche Technik verwenden. 30 Jahre Erfahrung haben gezeigt, dass LALR(1) der praktischste von ihnen ist, daher ist die Voreinstellung ... LALR(1); SLR(x) ist eine reine Untermenge, also warum sollte man sich die Mühe machen, wenn man mit nur ein bisschen mehr Aufwand LALR(1) erhält? Wenn der Lemon-Implementierer der Tradition folgt, würde ich einen LALR(1)-Parsergenerator erwarten. So jetzt haben Sie Art von ihr Wort für es nehmen.

Sie können natürlich ein einfaches Experiment durchführen, um sich selbst zu überzeugen. Erstellen Sie einfach eine Grammatik, die SLR(1) nicht richtig parsen kann, LALR(1) aber schon, und versuchen Sie es. Oder Sie können den Code wirklich genau lesen.

Siehe LALR-Parsing unter http://en.wikipedia.org/wiki/LALR_parser