Was ist die übliche Vorgehensweise, wenn Compiler statisch „komplexe“ Ausdrücke prüfen?

Hinweis: Wenn ich im Titel "Komplex" verwendet habe, bedeutet dies, dass der Ausdruck viele Operatoren und Operanden enthält. Nicht, dass der Ausdruck selbst komplex wäre.

Ich habe kürzlich an einem einfachen Compiler für die x86-64-Assembly gearbeitet. Ich habe das Haupt-Frontend des Compilers fertiggestellt - den Lexer und den Parser - und kann nun eine abstrakte Syntaxbaumdarstellung meines Programms generieren. Und da meine Sprache statisch geschrieben wird, mache ich jetzt die nächste Phase: Überprüfung des Quellcodes. Ich bin jedoch auf ein Problem gestoßen und konnte es nicht vernünftigerweise selbst lösen.

Betrachten Sie das folgende Beispiel:

Der Parser meines Compilers hat diese Codezeile gelesen:

int a = 1 + 2 - 3 * 4 - 5

Und konvertierte es auf folgende AST:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Jetzt muss der AST überprüft werden. Zunächst wird der =Bediener überprüft . Zunächst wird die linke Seite des Bedieners überprüft. Es wird angezeigt, dass die Variable aals Ganzzahl deklariert ist. Daher muss jetzt überprüft werden, ob der Ausdruck auf der rechten Seite eine Ganzzahl ergibt.

Ich verstehe, wie dies getan werden könnte, wenn der Ausdruck nur ein einzelner Wert wäre, wie z. B. 1oder 'a'. Aber wie würde das für Ausdrücke mit mehreren Werten und Operanden gemacht werden - ein komplexer Ausdruck - wie der obige? Um den Wert des Ausdrucks korrekt zu bestimmen, müsste die Typprüfung anscheinend den Ausdruck selbst ausführen und das Ergebnis aufzeichnen. Dies scheint jedoch offensichtlich den Zweck der Trennung von Kompilierungs- und Ausführungsphase zu zunichte zu machen.

Die einzige andere Möglichkeit, die ich mir vorstellen kann, besteht darin, das Blatt jedes Unterausdrucks im AST rekursiv zu überprüfen und zu überprüfen, ob alle Blatttypen mit dem erwarteten Operatortyp übereinstimmen. Ausgehend vom =Operator scannt die Typprüfung dann den gesamten AST der linken Seite und überprüft, ob alle Blätter Ganzzahlen sind. Dies würde dann für jeden Operator im Unterausdruck wiederholt.

Ich habe versucht, das Thema in meinem Exemplar von "The Dragon Book" zu recherchieren , aber es scheint nicht sehr detailliert zu sein, und ich wiederhole einfach, was ich bereits weiß.

Was ist die übliche Methode, wenn ein Compiler Ausdrücke mit vielen Operatoren und Operanden prüft? Werden die oben genannten Methoden angewendet? Wenn nicht, wie lauten die Methoden und wie genau würden sie funktionieren?

Rekursion ist die Antwort, aber Sie steigen in jeden Teilbaum ab, bevor Sie die Operation ausführen:

int a = 1 + 2 - 3 * 4 - 5

zur Baumform:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Der Typ wird abgeleitet, indem zuerst die linke Seite, dann die rechte Seite und dann der Operator behandelt werden, sobald die Typen der Operanden abgeleitet werden:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> in lhs absteigen

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> schließen a. aist bekannt dafür int. Wir sind jetzt wieder im assignKnoten:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> Abstieg in rhs, dann in lhs der inneren Operatoren, bis wir etwas Interessantes treffen

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> leiten Sie den Typ von 1, der ist int, und kehren Sie zum übergeordneten Element zurück

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> gehe in die rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> leiten Sie den Typ von 2, der ist int, und kehren Sie zum übergeordneten Element zurück

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> leiten Sie den Typ von add(int, int), der ist int, und kehren Sie zum übergeordneten Element zurück

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> Abstieg in die rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

usw., bis Sie am Ende mit

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Ob die Zuweisung selbst auch ein Ausdruck mit einem Typ ist, hängt von Ihrer Sprache ab.

Das Wichtigste zum Mitnehmen: Um den Typ eines Operator-Knotens im Baum zu bestimmen, müssen Sie nur seine untergeordneten Elemente betrachten, denen bereits ein Typ zugewiesen sein muss.

Was ist die normalerweise verwendete Methode, wenn ein Compiler Ausdrücke mit vielen Operatoren und Operanden auf Typüberprüfung überprüft.

Lesen Sie Wikipages zum Typsystem und zur Typinferenz sowie zum Hindley-Milner-Typsystem , das die Vereinheitlichung verwendet . Lesen Sie auch Informationen zur Denotationssemantik und zur operativen Semantik .

Die Typprüfung kann einfacher sein, wenn:

• Alle Ihre Variablen wie awerden explizit mit einem Typ deklariert. Dies ist wie C oder Pascal oder C ++ 98, aber nicht wie C ++ 11, das eine Art Inferenz hat auto.
• Alle Literalwerte mögen 1, 2oder 'c'haben einen inhärenten Typ: Ein Int-Literal hat immer einen Typ int, ein Zeichenliteral hat immer einen Typ char,….
• Funktionen und Operatoren sind nicht überladen, zB der +Operator hat immer Typ (int, int) -> int. C hat eine Überladung für Operatoren ( +funktioniert für Integer-Typen mit und ohne Vorzeichen und für Doubles), aber keine Überladung von Funktionen.

Unter diesen Bedingungen könnte ein rekursiver Bottom-up-Algorithmus für die Dekoration von AST-Typen ausreichen (dies betrifft nur Typen , nicht konkrete Werte, daher ist dies ein Ansatz zur Kompilierungszeit):

• Für jeden Bereich führen Sie eine Tabelle für die Typen aller sichtbaren Variablen (als Umgebung bezeichnet). Nach einer Deklaration int awürden Sie den Eintrag a: intzur Tabelle hinzufügen .

• Die Typisierung von Blättern ist der triviale Rekursionsgrundfall: Die Art der Literale 1ist bereits bekannt, und die Art der Variablen akann in der Umgebung nachgeschlagen werden.

• Um einen Ausdruck mit einigen Operatoren und Operanden gemäß den zuvor berechneten Typen der Operanden (verschachtelte Unterausdrücke) einzugeben, verwenden wir eine Rekursion für die Operanden (also geben wir zuerst diese Unterausdrücke ein) und befolgen die mit dem Operator verbundenen Eingaberegeln .

Also in Ihrem Beispiel 4 * 3und 1 + 2werden getippt, intweil 4& 3und 1& 2zuvor getippt wurden intund Ihre Tippregeln besagen, dass die Summe oder das Produkt von zwei int-s ein ist int, und so weiter für (4 * 3) - (1 + 2).

Lesen Sie dann Pierces Buch über Typen und Programmiersprachen . Ich empfehle, ein bisschen Ocaml und λ-Kalkül zu lernen

Für dynamischere Sprachen (wie Lisp) lesen Sie auch Queinnecs Lisp In Small Pieces

Lesen Sie auch Scott Programmiersprachen Pragmatik Buch

Übrigens können Sie keinen sprachunabhängigen Typisierungscode haben, da das Typensystem ein wesentlicher Bestandteil der Semantik der Sprache ist .

In C (und offen gesagt in den meisten statisch typisierten Sprachen, die auf C basieren) kann jeder Operator als syntaktischer Zucker für einen Funktionsaufruf angesehen werden.

So kann Ihr Ausdruck wie folgt umgeschrieben werden:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Dann wird die Überlastungsauflösung aktiviert und es wird entschieden, dass jede Funktion vom Typ (int, int)oder ist (const int&, const int&).

Auf diese Weise ist die Schriftauflösung leicht zu verstehen und nachzuvollziehen und (was noch wichtiger ist) leicht zu implementieren. Informationen über Typen fließen nur in eine Richtung (von den inneren Ausdrücken nach außen).

double x = 1/2;Dies ist der Grund, warum dies zur Folge hat, x == 0weil 1/2es als int-Ausdruck ausgewertet wird.

Konzentrieren Sie sich auf Ihren Algorithmus und versuchen Sie, ihn auf Bottom-up umzustellen. Sie kennen den Typ von Variablen und Konstanten. Kennzeichnen Sie den Knoten mit dem Operator mit dem Ergebnistyp. Lassen Sie das Blatt den Typ des Bedieners bestimmen , auch das Gegenteil Ihrer Idee.

Es ist eigentlich ganz einfach, solange man +sich eine Vielzahl von Funktionen vorstellt und nicht nur ein einziges Konzept.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

Während der Analysephase auf der rechten Seite ruft der Parser ab 1, weiß, dass es sich um einen handelt int, analysiert diesen +und speichert ihn als "nicht aufgelösten Funktionsnamen". Anschließend analysiert er den 2, weiß, dass es sich um einen handelt int, und gibt ihn auf dem Stapel zurück. Der +Funktionsknoten kennt nun beide Parametertypen, so das auflösen kann +in int operator+(int, int), so jetzt ist es die Art dieser Unterausdruck kennt, und der Parser weiter auf seine fröhliche Art und Weise.

Wie Sie sehen, kennt jeder Knoten, einschließlich der Funktionsaufrufe, seine Typen, sobald der Baum vollständig aufgebaut ist. Dies ist von entscheidender Bedeutung, da damit Funktionen möglich sind, die andere Typen als ihre Parameter zurückgeben.

char* ptr = itoa(3);

Hier ist der Baum:

    char* itoa(int)
     /           \
  ptr(char*)      3

Die Grundlage für die Typprüfung ist nicht das, was der Compiler tut, sondern das, was die Sprache definiert.

In der Sprache C hat jeder Operand einen Typ. "abc" hat den Typ "array of const char". 1 hat den Typ "int". 1L hat den Typ "long". Wenn x und y Ausdrücke sind, gibt es Regeln für den Typ von x + y und so weiter. Der Compiler muss sich also offensichtlich an die Regeln der Sprache halten.

In modernen Sprachen wie Swift sind die Regeln viel komplizierter. Einige Fälle sind einfach wie in C. In anderen Fällen sieht der Compiler einen Ausdruck, hat zuvor erfahren, welchen Typ der Ausdruck haben soll, und legt die Typen der Unterausdrücke darauf basierend fest. Wenn x und y Variablen unterschiedlichen Typs sind und ein identischer Ausdruck zugewiesen wird, wird dieser Ausdruck möglicherweise auf andere Weise ausgewertet. Wenn Sie zum Beispiel 12 * (2/3) zuweisen, wird einem Double 8.0 und einem Int 0 zugewiesen. Und es gibt Fälle, in denen der Compiler weiß, dass zwei Typen zusammenhängen, und herausfindet, auf welchen Typen sie basieren.

Schnelles Beispiel:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

druckt "8.0, 0".

In der Zuweisung x = 12 * (2/3): Die linke Seite hat einen bekannten Typ Double, daher muss die rechte Seite den Typ Double haben. Es gibt nur eine Überladung für den Operator "*", der Double zurückgibt, und das ist Double * Double -> Double. Daher muss 12 den Typ Double haben und 2 / 3. 12 unterstützt das Protokoll "IntegerLiteralConvertible". Double hat einen Initialisierer, der ein Argument vom Typ "IntegerLiteralConvertible" verwendet, sodass 12 in Double konvertiert wird. 2/3 muss vom Typ Double sein. Es gibt nur eine Überladung für den Operator "/", der Double zurückgibt, und das ist Double / Double -> Double. 2 und 3 werden zu Double konvertiert. Das Ergebnis von 2/3 ist 0.6666666. Das Ergebnis von 12 * (2/3) ist 8.0. 8.0 ist x zugeordnet.

In der Zuweisung y = 12 * (2/3) hat y auf der linken Seite den Typ Int, daher muss die rechte Seite den Typ Int haben, sodass 12, 2, 3 mit dem Ergebnis 2/3 = in Int konvertiert werden 0, 12 * (2/3) = 0.