Parser-Fehler - Muster zur automatischen Fehlerbehandlung

Question

Gibt es eine bekannte Möglichkeit, eine gute Fehlerbehandlung für maschinengenerierte Parser zu implementieren? Gibt es ein "Muster" oder einen bekannten Algorithmus für diese Art von Problem? Für "gut" meine ich etwas, das den Ergebnissen ähnelt, die mit handgefertigten rekursiven Abstiegsparsern und modernen Compilern erzielt werden: Parser hört beim ersten Fehler nicht auf, kann dazu gebracht werden, "bedeutungsvolle" Fehler und nicht nur "unerkannte Token" zu emittieren Zeile xyz "ein Fehler nach dem anderen.

Idealerweise sollte dieser Ansatz auch automatisiert werden, nicht handgefertigt.

Ich bin nicht auf der Suche nach einer Bibliothek, ich brauche einen Ansatz, der in verschiedenen Plattformen verwendet werden kann und idealerweise so sprachunabhängig wie möglich wäre.

Answer 1

Mit einem traditionellen YACC/Bison-Generator erhalten Sie das yyerror/YYERROR Framework, mit dem es nicht einfach ist, sehr nützliche Fehlermeldungen zu erzeugen, aufgrund der ungeordneten Backtracking-Natur von LALR-Parsern. Sie können dort sogar Regeln zur Fehlerwiederherstellung hinzufügen, weil Sie sie möglicherweise benötigen, um falsche Fehlermeldungen in fehlgeschlagenen Regeln zu unterdrücken, in denen Sie nur die Parser-Regeln abschneiden wollten.

Mit einem PEG-basierten Parser haben Sie die viel bessere ~{} Postfix-Fehler Aktionsblock-Syntax mit zu arbeiten. Siehe z. die peg manual.

rule = e1 e2 e3 ~{ error("e[12] ok; e3 has failed"); } 
     | ... 

    rule = (e1 e2 e3) ~{ error("one of e[123] has failed"); } 
     | ... 

Sie erhalten ausgezeichnete Fehlermeldungen an der tatsächlichen Stelle des Fehlers. Aber Sie müssen PEG-Regeln schreiben, die nicht so einfach zu schreiben sind, insbes. bei der Behandlung der Vorrangstellung des Betreibers. Dies ist mit einem LALR-Parser einfacher.

Mit einem vereinfachten recursive descent parser Generator haben Sie die gleichen Fehlerbericht Vorteile von PEG, aber mit einer viel langsameren Parse-Geschwindigkeit.

Siehe die gleiche Diskussion bei http://lambda-the-ultimate.org/node/4781

Answer 2

Seit dem ersten Versuch haben Benutzer versucht, Syntaxfehler zu melden und zu reparieren. Es gibt viele technische Papiere, wie man das macht. Die Suche nach der Zeichenfolge "syntax error repair" unter scholar.google.com führt zu 57 Treffern.

Es gibt wirklich einige Probleme:

1) Wie einen sinnvollen Fehler an den Leser zu melden. Zu Beginn gibt es ist, wo der Parser den Fehler erkennt, und wo der Benutzer tatsächlich den Fehler gemacht. Zum Beispiel könnte hat ein C-Programm einen ‚++‘ Betreiber in einem fremden Ort:

void p { 
x = y ++ 
    z = 0; 
<EOF> 

meisten Parser werden ersticken, wenn „z“ wird angetroffen, und es als der Ort des Fehlers melden. Wenn der Fehler jedoch "++" verwendet, wenn "+" gemeint war, ist dieser Bericht falsch. Um dies richtig zu machen, müssen Sie in der Lage sein, die Gedanken des Programmierers zu lesen.

Sie haben auch das Problem, den Fehlerkontext zu melden. Melden Sie den Fehler in einem Ausdruck [auf den ersten Blick, scheint so]? in einer Stellungnahme? In einer Linie? In einem Funktionskörper? In Funktionsdeklaration? Wahrscheinlich möchten Sie in der engsten syntaktischen Kategorie berichten, die den Fehlerpunkt umgibt. (Beachten Sie, dass Sie den Funktionskörper oder die Deklaration nicht als "umgebende" Fehlerstelle angeben können, da auch diese nicht vollständig sind!) Was, wenn der Fehler wirklich ein fehlendes Semikolon nach dem ++ war? Dann waren die Fehlerorte nicht wirklich "im Ausdruck". Was ist, wenn die Reparatur das Einfügen eines fehlenden String-Zitats erfordert? Ein Makrofortsetzungszeichen?

Also müssen Sie irgendwie entscheiden, was den tatsächlichen Fehler ausmacht, und das bringt uns zur Fehlerreparatur.

2) Fehler Reparatur: Damit das Werkzeug auf sinnvolle Weise fortfahren kann, muss es den Fehler beheben. Dies bedeutet vermutlich, dass der Strom der Input-Tokens gepatcht wird, um ein legales Programm zu erstellen (das Sie möglicherweise nicht ausführen können, wenn die Quelle mehrere Fehler aufweist). Was ist, wenn es mehrere mögliche Patches gibt? Es sollte offensichtlich sein, dass der beste Fehlerbericht "JJJJ ist falsch, ich vermute, dass du xxxx benutzt haben solltest" ist. Wie groß sollte ein Patch für eine Reparatur sein: nur das Token, das den Fehler ausgelöst hat, Token, die ihm folgen, wie ist es mit Token, die ihm vorausgehen?

Ich bemerke, es ist schwer, automatische, allgemeine Fehler Reparatur Vorschlag auf handgeschriebenen Parsern zu tun, weil die Grammatik, die zur Führung solcher Reparatur benötigt wird, nirgendwo explizit verfügbar ist. Sie würden also erwarten, dass die automatische Reparatur am besten auf Tools funktioniert, für die die Grammatik ein explizites Artefakt war.

Es kann auch sein, dass die Fehlerreparatur häufige Fehler berücksichtigen sollte. Wenn Menschen dazu neigen, ";" Off-Anweisungen, und das Einfügen von einem behebt die Datei, könnte es eine gute Reparatur sein. Wenn sie das selten tun und es mehr als eine Reparatur gibt (zB "++" durch "+" ersetzen), ist eine alternative Reparatur wahrscheinlich ein besserer Vorschlag.

3) Semantische Auswirkungen der Reparatur Sie beheben die Syntaxfehler, das reparierte Programm ist möglicherweise nicht sinnvoll Wenn Ihr Fehler das Einfügen eines Bezeichners erfordert, welcher Bezeichner sollte verwendet werden?

FWIW, unser DMS Software Reengineering Toolkit führt eine automatische Reparatur durch, die vollständig von der Grammatik gesteuert wird. Es geht von der Annahme aus, dass das Token am Fehlerpunkt gelöscht werden sollte oder dass ein anderes einzelnes Token nach links eingefügt werden sollte, das fehlende ";" und zusätzliche Pluszeichen fängt an, es gelingt oft eine rechtliche Reparatur ist nicht der "richtige". Zumindest lässt es den Parser zum re weitergehen st des Quellcodes.

Ich denke, die Jagd nach guten, automatisierten Fehler Reparatur wird für eine lange Zeit fortgesetzt.

FWIW, das Papier Syntaxfehler Reparatur für einen Java-basierten Parser Generator berichtet, dass Burke Ph.D. Diplomarbeit:

M.G. Burke, 1983, Eine praktische Methode für LR und LL syntaktische Fehlerdiagnose und Wiederherstellung, Dissertation, Abteilung für Informatik, New York University

ist ziemlich gut. Insbesondere werden Fehler repariert, indem der linke Kontext des Fehlers und der Fehlerumfang berücksichtigt und überarbeitet werden. Sieht aus wie man kann get it from ACM

Answer 3

Dies ist wahrscheinlich nicht das, was Sie hören möchten, aber Ihre bessere Hand aus dem Parser und Lexer.

Dies ist keine besonders schwierige Aufgabe (besonders im Vergleich zum Schreiben des Semantik-Analysators und des Codegenerators) und wird die besten Ergebnisse bei der Fehlerbehandlung liefern.

Aber trau mich nicht, vertraue Walter Bright dem Autor des ersten nativen C++ - Compilers und Erfinders der D-Programmiersprache.

Er hat einen Artikel über genau dies auf Dr.Dobbs here. (Fehlerwiederherstellung ist auf Seite 2)

Answer 4

Ich habe eine ziemlich andere Perspektive auf dieses Problem, das ist, dass Sie Syntaxfehler nicht als interne Compilerfehler behandeln sollten. Jede praktische Compiler setzt tatsächlich drei Sprachen:

1. Die Sprache L, die die bezeichnete Zielsprache ist. Korrekte Programme sind Mitglieder dieser Sprache.
2. Die Sprache M besteht aus L plus alle Fehler, die vom Compiler erkannt werden. Mitglieder von M \ L erhalten informative Fehler.
3. Die Sprache Z, dass der Compiler normal beendet wird. Dieser Satz sollte die Menge aller möglichen Eingabezeichenfolgen sein, aber wenn der Compiler bei einigen Eingaben abstürzt, ist dies nicht der Fall.Mitglieder von Z \ M erhalten generische Nachrichten darüber, wie der Compiler fehlgeschlagen ist, in der Regel der Form "Parser bei Zeile x fehlgeschlagen, char y".

können Sie die automatische Parser-Generator-Tools verwenden, wie Sie suchen, wenn Sie die Sprache M in Ihrem Parser anstelle der Sprache L angeben. Das Problem bei diesem Ansatz besteht darin, dass Sprachentwickler immer L und nicht M angeben. Ich kann mir keinen einzigen Fall vorstellen, in dem es so etwas wie einen Standard für M gibt.

Dies ist nicht nur abstrakter Unsinn. Es gibt kürzlich eine Änderung in C++, die diese Unterscheidung sehr gut veranschaulicht. Früher war es so, dass

template< class T > class X; 
template< class T > class Y; 
X<Y<int>> foo; // syntax in M 

einen Fehler in Zeile drei hatten, da die Zeichen „>>“ das Token für die rechte Shift-Operator waren. Diese Zeile musste geschrieben werden

Der Standard wurde geändert, um den zusätzlichen Platz nicht zu benötigen. Der Grund war, dass alle wichtigen Compiler bereits Code zur Erkennung dieses Falls geschrieben hatten, um eine sinnvolle Fehlermeldung zu generieren. Mit anderen Worten, sie fanden heraus, dass die Sprache M bereits überall implementiert war. Sobald der Ausschuss dies festgestellt hatte, übertrugen sie die M -Syntax in die neue Version L.

würden wir insgesamt ein besseres Sprachdesign haben, wenn Designer die M Sprache zugleich betrachtet, da sie auf der L Sprache arbeiten. Aus Gründen der eigenen Gesundheit würden sie sich bemühen, die Größe der Spezifikation für M zu minimieren, was für alle eine gute Sache wäre. Leider ist die Welt noch nicht da.

Das Ergebnis ist, dass Sie Ihre eigene Sprache M entwerfen müssen. Das ist das schwere Problem. Ob Sie ein automatisiertes Werkzeug dafür verwenden, ist etwas neben diesem Punkt. Es hilft, aber es wird den zeitaufwendigsten Teil nicht los.