it-swarm-eu.dev

Was sind die wichtigsten Vor- und Nachteile der LL- und LR-Analyse?

Was verdiene ich beim Erstellen eines Parsers für eine Programmiersprache und was habe ich bei der Auswahl der einen oder anderen verloren?

29
Maniero

Ich werde das Parsen von LL und LR anhand einer Reihe von Kriterien gegenüberstellen:

Komplexität

LL gewinnt hier zweifellos. Sie können einen LL-Parser einfach von Hand schreiben. Tatsächlich geschieht dies häufig: Der Microsoft C # -Compiler ist ein handgeschriebener Parser für rekursiven Abstieg (Quelle hier , suchen Sie nach einem Kommentar von Patrick Kristiansen - der Blog-Beitrag ist ebenfalls sehr interessant).

Die LR-Analyse verwendet eine eher kontraintuitive Methode, um einen Text zu analysieren. Es funktioniert, aber ich habe einige Zeit gebraucht, um mich darum zu kümmern, wie es genau funktioniert. 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 einige Belästigungen, die Sie bei der Implementierung nahezu jeder Programmiersprache stören werden. Siehe hier für eine Übersicht.

Es gibt eindeutige Sprachen, die keine LR-Sprachen sind, aber diese sind ziemlich selten. Solche Sprachen begegnet man fast nie. LALR hat jedoch einige Probleme.

LALR ist mehr oder weniger ein Hack für LR-Parser, um die Tabellen kleiner zu machen. Die Tabellen für einen LR-Parser können normalerweise enorm wachsen. LALR-Parser geben die Möglichkeit auf, alle LR-Sprachen im Austausch gegen kleinere Tabellen zu analysieren. Die meisten LR-Parser verwenden LALR tatsächlich (allerdings nicht heimlich, Sie können normalerweise genau das finden, was es implementiert).

LALR kann sich über Schichtreduzierungs- und Reduktionsreduzierungskonflikte beschweren. Dies wird durch den Tabellen-Hack verursacht: Er faltet ähnliche Einträge zusammen, was funktioniert, da die meisten Einträge leer sind. Wenn sie jedoch nicht leer sind, entsteht ein Konflikt. 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 auszugeben, insbesondere bei handgeschriebenen Parsern. Sie wissen, was Sie als Nächstes erwarten. Wenn es also nicht auftaucht, wissen Sie normalerweise, was schief gelaufen ist und was der vernünftigste Fehler wäre.

Außerdem ist beim LL-Parsing die Fehlerbehebung viel einfacher. Wenn eine Eingabe nicht korrekt analysiert wird, können Sie versuchen, ein wenig zu überspringen 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 druckt, in denen Fehler aufgetreten sind. Dies ist jedoch normalerweise ziemlich schwierig. Die Wahrscheinlichkeit, dass Sie eine Nicht-LR oder Nicht-LALR-) Grammatik erhalten, steigt ebenfalls.

Geschwindigkeit

Geschwindigkeit ist nicht wirklich ein Problem bei der Art und Weise, wie Sie Ihre Eingabe 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 unten.

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

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

44
Alex ten Brink