Wie genau erholt sich ein Compiler von einem Typfehler?

Ich habe mehrere Artikel, Artikel und Abschnitt 4.1.4, Kapitel 4 von Compiler: Prinzipien, Techniken und Werkzeuge (2. Ausgabe) (auch bekannt als "The Dragon Book") gelesen, in denen das Thema der syntaktischen Compiler-Fehlerbehebung behandelt wird. Nachdem ich mit mehreren modernen Compilern experimentiert habe, habe ich festgestellt, dass sie sich auch von semantischen Fehlern sowie von syntaktischen Fehlern erholen .

Ich verstehe die Algorithmen und Techniken hinter Compilern, die sich von syntaktisch verwandten Fehlern erholen, ziemlich gut, verstehe jedoch nicht genau, wie ein Compiler sich von einem semantischen Fehler erholen kann.

Ich verwende derzeit eine geringfügige Variation des Besuchermusters, um Code aus meinem abstrakten Syntaxbaum zu generieren. Stellen Sie sich vor, mein Compiler kompiliert die folgenden Ausdrücke:

1 / (2 * (3 + "4"))

Der Compiler würde den folgenden abstrakten Syntaxbaum generieren:

      op(/)
        |
     -------
    /       \ 
 int(1)    op(*)
             |
          -------
         /       \
       int(2)   op(+)
                  |
               -------
              /       \
           int(3)   str(4)

Die Codegenerierungsphase würde dann das Besuchermuster verwenden, um den abstrakten Syntaxbaum rekursiv zu durchlaufen und eine Typprüfung durchzuführen. Der abstrakte Syntaxbaum wird durchlaufen, bis der Compiler zum innersten Teil des Ausdrucks gelangt. (3 + "4"). Der Compiler überprüft dann jede Seite der Ausdrücke und stellt fest, dass sie nicht semantisch äquivalent sind. Der Compiler löst einen Typfehler aus. Hier liegt das Problem. Was soll der Compiler jetzt tun ?

Damit der Compiler diesen Fehler beheben und die äußeren Teile der Ausdrücke vom Typ überprüfen kann, muss er einen Typ ( intoder str) von der Auswertung des innersten Teils des Ausdrucks zum nächsten innersten Teil des Ausdrucks zurückgeben. Aber es gibt einfach keinen Typ, der zurückgegeben werden könnte . Da ein Typfehler aufgetreten ist, wurde kein Typ abgeleitet.

Eine mögliche Lösung, die ich postuliert habe, ist, dass, wenn ein Typfehler auftritt, ein Fehler ausgelöst werden sollte und ein spezieller Wert, der anzeigt, dass ein Typfehler aufgetreten ist, an frühere Traversal-Aufrufe des abstrakten Syntaxbaums zurückgegeben werden sollte. Wenn frühere Traversal-Aufrufe auf diesen Wert stoßen, wissen sie, dass ein Typfehler tiefer im abstrakten Syntaxbaum aufgetreten ist, und sollten vermeiden, einen Typ abzuleiten. Obwohl diese Methode zu funktionieren scheint, scheint sie sehr ineffizient zu sein. Wenn sich der innerste Teil eines Ausdrucks tief im abstrakten Syntaxbaum befindet, muss der Compiler viele rekursive Aufrufe ausführen, um zu erkennen, dass keine echte Arbeit ausgeführt werden kann, und einfach von jedem zurückkehren.

Wird die oben beschriebene Methode verwendet (ich bezweifle es). Wenn ja, ist es nicht effizient? Wenn nicht, welche Methoden werden genau verwendet, wenn Compiler semantische Fehler beheben?

Ihre vorgeschlagene Idee ist im Wesentlichen richtig.

Der Schlüssel ist, dass der Typ eines AST-Knotens nur einmal berechnet und dann gespeichert wird. Immer wenn der Typ erneut benötigt wird, wird einfach der gespeicherte Typ abgerufen. Wenn die Auflösung in einem Fehler endet, wird stattdessen ein Fehlertyp gespeichert.

Ein interessanter Ansatz besteht darin, einen speziellen Typ für Fehler zu haben. Wenn ein solcher Fehler zum ersten Mal auftritt, wird eine Diagnose protokolliert und der Fehlertyp als Typ des Ausdrucks zurückgegeben. Dieser Fehlertyp hat einige interessante Eigenschaften:

• Jede Operation, die daran ausgeführt wird, ist erfolgreich (um eine Kaskade von Fehlermeldungen zu verhindern, die alle durch denselben ursprünglichen Fehler verursacht werden).
• Das Ergebnis einer Operation, die an einem Objekt mit Fehlertyp ausgeführt wird, hat ebenfalls den Fehlertyp
• Wenn ein Fehlertyp bis zur Codegenerierung reicht, erkennt der Codegenerator die Verwendung und generiert fehlgeschlagenen Code (z. B. löst eine Ausnahme aus, bricht ab oder was auch immer für Ihre Sprache angemessen ist).

Mit dieser Kombination können Sie tatsächlich erfolgreich Code kompilieren , der Typfehler enthält. Solange dieser Code nicht tatsächlich verwendet wird, tritt kein Laufzeitfehler auf. Dies kann beispielsweise nützlich sein, um Unit-Tests für Teile des Codes durchzuführen, die nicht betroffen sind.

Wenn ein semantischer Fehler vorliegt, wird dem Benutzer eine Kompilierungsfehlermeldung ausgegeben, die darauf hinweist.

Sobald dies erledigt ist, ist es in Ordnung, das Kompilieren abzubrechen, da das Eingabeprogramm fehlerhaft ist - es ist kein legales Programm in der Sprache, daher kann es einfach abgelehnt werden.

Das ist allerdings ziemlich hart, daher gibt es weichere Alternativen. Brechen Sie die Codegenerierung und die Generierung von Ausgabedateien ab, fahren Sie jedoch mit der Suche nach weiteren Fehlern fort.

Beispielsweise kann einfach jede weitere Typanalyse für den aktuellen Ausdrucksbaum abgebrochen und die Verarbeitung von Ausdrücken aus nachfolgenden Anweisungen fortgesetzt werden.

Nehmen wir an, Ihre Sprache ermöglicht das Hinzufügen von Ganzzahlen und das Verketten von Zeichenfolgen mit dem +Operator.

Da dies int + stringnicht zulässig ist, wird bei der Auswertung des +Tests ein Fehler gemeldet. Der Compiler könnte einfach errorals Typ zurückkehren. Oder es könnte klüger sein, da int + int -> intund string + string -> stringerlaubt, könnte es "Fehler, könnte int oder string sein" zurückgeben.

Dann kommt der *Operator und wir gehen davon aus, dass nur int + interlaubt ist. Der Compiler kann dann entscheiden, dass das +tatsächlich zurückgegeben werden soll int, und der für das zurückgegebene Typ *wäre dann intohne Fehlermeldung.