Was sind die wichtigsten Vor- und Nachteile des LL- und LR-Parsings?

Wenn ich einen Parser für eine Programmiersprache erstelle, was verdiene ich und was habe ich verloren, als ich mich für die eine oder andere entschieden habe?

Ich werde LL- und LR-Analyse für eine Reihe von Kriterien gegenüberstellen:

Komplexität

LL gewinnt hier zweifellos. Sie können einen LL-Parser ganz einfach von Hand schreiben. Tatsächlich geschieht dies häufig: Der Microsoft C # -Compiler ist ein handgeschriebener rekursiver Abstiegsparser (Quelle: hier ein Kommentar von Patrick Kristiansen - der Blog-Beitrag ist ebenfalls sehr interessant).

Bei der LR-Analyse wird eine eher kontraintuitive Methode zum Parsen eines Texts verwendet. Es funktioniert, aber ich habe einige Zeit gebraucht, um mich mit der genauen Funktionsweise auseinanderzusetzen. Das Schreiben eines solchen Parsers von Hand ist daher schwierig: Sie würden mehr oder weniger einen LR-Parser-Generator implementieren.

Allgemeinheit

LR gewinnt hier: Alle LL-Sprachen sind LR-Sprachen, aber es gibt mehr LR-Sprachen als LL-Sprachen (eine Sprache ist eine LL-Sprache, wenn sie mit einem LL-Parser analysiert werden kann, und eine Sprache ist eine LR-Sprache, wenn sie analysiert werden kann ein LR-Parser).

LL hat eine Reihe von Unannehmlichkeiten, die Sie bei der Implementierung nahezu jeder Programmiersprache stören werden. Sehen Sie hier für einen Überblick.

Es gibt eindeutige Sprachen, die keine LR-Sprachen sind, aber diese sind ziemlich selten. Sie begegnen solchen Sprachen fast nie. LALR hat jedoch einige Probleme.

LALR ist mehr oder weniger ein Hack für LR-Parser, um die Tabellen zu verkleinern. Die Tabellen für einen LR-Parser können normalerweise sehr groß werden. LALR-Parser geben die Möglichkeit auf, alle LR-Sprachen im Austausch für kleinere Tabellen zu analysieren. Die meisten LR-Parser verwenden tatsächlich LALR (nicht geheim, Sie können jedoch in der Regel genau herausfinden, was es implementiert).

LALR kann sich über Verschiebungs- und Reduzierungskonflikte beschweren. Dies wird durch den Tabellen-Hack verursacht: Es faltet ähnliche Einträge zusammen, was funktioniert, weil die meisten Einträge leer sind, aber wenn sie nicht leer sind, wird ein Konflikt erzeugt. Diese Art von Fehlern ist nicht natürlich, schwer zu verstehen und die Korrekturen sind normalerweise ziemlich seltsam.

Compilerfehler und Fehlerbehebung

LL gewinnt hier. Bei einer LL-Analyse ist es normalerweise ziemlich einfach, nützliche Compilerfehler zu melden, insbesondere bei handgeschriebenen Parsern. Sie wissen, was Sie als nächstes erwarten, und wenn es nicht auftaucht, wissen Sie normalerweise, was schief gelaufen ist und was der vernünftigste Fehler wäre.

Bei der LL-Analyse ist die Fehlerbehebung außerdem viel einfacher. Wenn eine Eingabe nicht korrekt analysiert wird, können Sie versuchen, einen Schritt weiterzugehen und herauszufinden, ob der Rest der Eingabe korrekt analysiert wird. Wenn beispielsweise eine Programmieranweisung fehlerhaft ist, können Sie die nächste Anweisung überspringen und analysieren, sodass Sie mehr als einen Fehler abfangen können.

Mit einem LR-Parser ist dies viel schwieriger. Sie können versuchen, Ihre Grammatik so zu erweitern, dass sie fehlerhafte Eingaben akzeptiert und Fehler in den Bereichen ausgibt, in denen Fehler aufgetreten sind. Dies ist jedoch normalerweise recht schwierig. Die Wahrscheinlichkeit, dass Sie eine Nicht-LR-Grammatik (oder Nicht-LALR-Grammatik) haben, steigt ebenfalls.

Geschwindigkeit

Geschwindigkeit ist nicht wirklich ein Problem bei der Art und Weise, in der Sie Ihre Eingaben analysieren (LL oder LR), sondern bei der Qualität des resultierenden Codes und der Verwendung von Tabellen (Sie können Tabellen sowohl für LL als auch für LR verwenden). LL und LR sind daher in dieser Hinsicht vergleichbar.

Links

Hier ist ein Link zu einer Site, die auch LL und LR gegenüberstellt. Suchen Sie nach dem Abschnitt in der Nähe des Bodens.

Hier finden Sie ein Gespräch über die Unterschiede. Es ist keine schlechte Idee, die dort geäußerten Meinungen kritisch zu betrachten, da ist ein bisschen ein heiliger Krieg im Gange.

Für weitere Informationen, hier und hier sind zwei meiner eigenen Beiträge über Parser, obwohl es nicht ausschließlich um den Kontrast zwischen LL und LR geht.