Jaka jest typowa procedura stosowana, gdy kompilatory sprawdzają statycznie typ „złożone” wyrażenia

Uwaga: Kiedy użyłem „złożonego” w tytule, mam na myśli, że wyrażenie ma wiele operatorów i operandów. Nie to, że samo wyrażenie jest złożone.

Niedawno pracowałem nad prostym kompilatorem do zestawu x86-64. Skończyłem główny front kompilatora - leksykon i parser - i jestem teraz w stanie wygenerować abstrakcyjne drzewo syntaktyczne mojego programu. A ponieważ mój język będzie wpisywany statycznie, teraz robię następną fazę: sprawdzanie kodu źródłowego. Jednak natknąłem się na problem i nie byłem w stanie samodzielnie go rozwiązać.

Rozważ następujący przykład:

Parser mojego kompilatora odczytał następujący wiersz kodu:

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

I przekonwertował go na następujący AST:

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

Teraz musi wpisać typ AST. zaczyna się od pierwszego sprawdzenia =operatora. Najpierw sprawdza lewą stronę operatora. Widzi, że zmienna ajest zadeklarowana jako liczba całkowita. Musi więc teraz sprawdzić, czy wyrażenie po prawej stronie jest liczbą całkowitą.

Rozumiem, jak można to zrobić, jeśli wyrażenie byłoby tylko jedną wartością, taką jak 1lub 'a'. Ale jak można to zrobić dla wyrażeń z wieloma wartościami i operandami - złożonym wyrażeniem - takim jak powyższy? Aby poprawnie określić wartość wyrażenia, wygląda na to, że sprawdzanie typu faktycznie musiałoby wykonać samo wyrażenie i zapisać wynik. Ale najwyraźniej wydaje się to sprzeczne z celem oddzielenia faz kompilacji i wykonania.

Jedynym innym sposobem, jaki mogę sobie wyobrazić, jest to, aby rekursywnie sprawdzać liść każdego podwyrażenia w AST i sprawdzać, czy wszystkie typy liści pasują do oczekiwanego typu operatora. Tak więc, zaczynając od =operatora, moduł sprawdzania typu skanuje następnie wszystkie parametry AST po lewej stronie i sprawdza, czy wszystkie liście są liczbami całkowitymi. Powtórzyłoby to następnie dla każdego operatora w podwyrażeniu.

Próbowałem zbadać ten temat w mojej kopii „Smoczej księgi” , ale wydaje się, że nie zawiera on zbyt wielu szczegółów i po prostu przypomina to, co już wiem.

Jaka jest zwykle stosowana metoda, gdy kompilator sprawdza wyrażenia sprawdzające typ z wieloma operatorami i operandami? Czy stosuje się którąkolwiek z wyżej wymienionych metod? Jeśli nie, jakie są metody i jak dokładnie będą działać?

Rekurencja jest odpowiedzią, ale przed wykonaniem operacji schodzisz do każdego poddrzewa:

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

do postaci drzewa:

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

Do wnioskowania o typie dochodzi się najpierw po lewej, a potem po prawej stronie, a następnie operując operatorem, gdy tylko zostaną określone typy operandów:

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

-> zejdź do lhs

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

-> wnioskować a. awiadomo, że jest int. Wróciliśmy teraz do assignwęzła:

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

-> zejdź w rhs, a następnie w lhs wewnętrznych operatorów, aż trafimy na coś interesującego

(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))

-> wywnioskuj typ 1, który jest int, i wróć do rodzica

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

-> przejdź do rhs

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

-> wywnioskuj typ 2, który jest int, i wróć do rodzica

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

-> wywnioskuj typ add(int, int), który jest int, i wróć do rodzica

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

-> zejdź do rhs

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

itd., dopóki nie skończysz z

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

To, czy samo zadanie jest również wyrażeniem typu, zależy od języka.

Ważna rzecz na wynos: aby określić typ dowolnego węzła operatora w drzewie, wystarczy spojrzeć na jego bezpośrednie elementy potomne, które muszą mieć przypisany już typ.

Jaka jest zwykle metoda stosowana, gdy kompilator sprawdza wyrażenia sprawdzające typ z wieloma operatorami i operandami.

Czytaj strony internetowe na temat systemu typów i wnioskowania o typach oraz na systemie typów Hindley-Milner , który korzysta z unifikacji . Przeczytaj także o semantyce denotacyjnej i semantyce operacyjnej .

Sprawdzanie typu może być prostsze, jeśli:

• wszystkie twoje zmienne jak asą jawnie zadeklarowane z typem. To jest jak C lub Pascal lub C ++ 98, ale nie tak jak C ++ 11, z którym można wnioskować o typie auto.
• wszystkie wartości literalne, takie jak 1, 2lub 'c'mają nieodłączny typ: literał int zawsze ma typ int, literał znakowy zawsze ma typ char,….
• funkcje i operatory nie są przeciążone, np. +operator zawsze ma typ (int, int) -> int. C ma przeciążenie dla operatorów ( +działa dla typów całkowitych ze znakiem i bez znaku oraz dla podwójnych), ale nie ma przeciążenia funkcji.

Zgodnie z tymi ograniczeniami wystarczający może być oddolny rekurencyjny algorytm dekoracji typu AST (dotyczy to tylko typów , a nie konkretnych wartości, więc podejście kompilacyjne):

• Dla każdego zakresu przechowujesz tabelę typów wszystkich widocznych zmiennych (zwanych środowiskiem). Po deklaracji int adodajesz wpis a: intdo tabeli.

• Wpisywanie liści to trywialny podstawowy przypadek rekurencji: typ literałów podobnych 1jest już znany, a typy zmiennych podobnych amożna wyszukać w środowisku.

• Aby wpisać wyrażenie za pomocą niektórych operatorów i operandów zgodnie z wcześniej obliczonymi typami operandów (zagnieżdżonych podwyrażeń), używamy rekurencji na operandach (więc najpierw wpisujemy te podwyrażenia) i postępujemy zgodnie z regułami pisania dotyczącymi operatora .

Więc w twoim przykładzie, 4 * 3i 1 + 2są wpisywane, intponieważ 4& 3i 1& 2zostały wcześniej wpisane, inta twoje zasady pisania mówią, że suma lub iloczyn dwóch int-s jest int, i tak dalej (4 * 3) - (1 + 2).

Następnie przeczytaj książkę Pierce's Types and Programming Languages . Polecam nauczyć się trochę Ocamla i rachunku λ

Dla bardziej dynamicznie pisanych języków (jak Lisp) przeczytaj także Lisp In Small Pieces Queinnec

Przeczytaj także książkę Scott's Programming Languages ​​Pragmatics

BTW, nie możesz mieć agnostycznego kodu do pisania, ponieważ system typów jest istotną częścią semantyki języka .

W języku C (i szczerze mówiąc w najbardziej typowych językach typowanych na podstawie C) każdy operator może być postrzegany jako cukier składniowy dla wywołania funkcji.

Twoje wyrażenie może zostać przepisane jako:

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

Następnie uruchomi się rozdzielczość przeciążenia i zdecydujesz, że każda funkcja jest typu (int, int)lub (const int&, const int&)typu.

W ten sposób rozdzielczość typu jest łatwa do zrozumienia i śledzenia oraz (co ważniejsze) łatwa do wdrożenia. Informacje o typach przepływają tylko w 1 kierunku (od wewnętrznych wyrażeń na zewnątrz).

To jest powód, dla którego to double x = 1/2;spowoduje, x == 0ponieważ 1/2jest oceniane jako wyrażenie int.

Koncentrując się na algorytmie, spróbuj zmienić go na oddolny. Znasz zmienne i stałe typu pf; oznacz węzeł noszący operator typem wyniku. Pozwól, aby liść określił typ operatora, a także przeciwieństwo Twojego pomysłu.

To jest naprawdę dość łatwe, o ile myślisz o +różnorodności funkcji, a nie o pojedynczej koncepcji.

    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

Podczas etapu analizy po prawej stronie analizator analizuje 1, wie, że to int, następnie analizuje +i zapisuje to jako „nierozstrzygniętą nazwę funkcji”, następnie analizuje 2, wie, że to int, a następnie zwraca to stosu. +Węzeł funkcja teraz zna oba rodzaje parametrów, dzięki czemu można rozwiązać +INTO int operator+(int, int), więc teraz to zna tego typu sub-wypowiedzi, a parser kontynuuje To wesoły sposób.

Jak widać, po pełnym zbudowaniu drzewa każdy węzeł, w tym wywołania funkcji, zna jego typy. Jest to kluczowe, ponieważ pozwala na funkcje, które zwracają inne typy niż ich parametry.

char* ptr = itoa(3);

Oto drzewo:

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

Podstawą sprawdzania typu nie jest to, co robi kompilator, lecz to, co definiuje język.

W języku C każdy operand ma swój typ. „abc” ma typ „tablica const char”. 1 ma typ „int”. 1L ma typ „długi”. Jeśli xiy są wyrażeniami, wówczas istnieją reguły dla typu x + y i tak dalej. Tak więc kompilator oczywiście musi przestrzegać reguł języka.

W nowoczesnych językach, takich jak Swift, zasady są znacznie bardziej skomplikowane. Niektóre przypadki są proste, jak w C. Inne przypadki, kompilator widzi wyrażenie, został wcześniej poinformowany, jaki typ powinien mieć to wyrażenie, i na tej podstawie określa typy podwyrażeń. Jeśli xiy są zmiennymi różnych typów i przypisane jest identyczne wyrażenie, to wyrażenie może być ocenione w inny sposób. Na przykład przypisanie 12 * (2/3) spowoduje przypisanie 8,0 do Double i 0 do Int. I masz przypadki, w których kompilator wie, że dwa typy są powiązane i dowiedzieć się, jakie typy są na nich oparte.

Szybki przykład:

var x: Double
var y: Int

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

print (x, y)

drukuje „8.0, 0”.

W przydziale x = 12 * (2/3): Lewa strona ma znany typ Double, dlatego prawa strona musi mieć typ Double. Jest tylko jedno przeciążenie dla operatora „*” zwracającego wartość Double, a mianowicie Double * Double -> Double. Dlatego 12 musi mieć typ Double, a także 2/3. 12 obsługuje protokół „IntegerLiteralConvertible”. Double ma inicjalizator pobierający argument typu „IntegerLiteralConvertible”, więc 12 jest konwertowany na Double. 2/3 musi mieć typ Double. Jest tylko jedno przeciążenie dla operatora „/” zwracającego Double, a mianowicie Double / Double -> Double. 2 i 3 są konwertowane na Double. Wynik 2/3 to 0,66666666. Wynik 12 * (2/3) wynosi 8,0. 8.0 jest przypisany do x.

W przypisaniu y = 12 * (2/3), y po lewej stronie ma typ Int, więc prawa strona musi mieć typ Int, więc 12, 2, 3 są konwertowane na Int z wynikiem 2/3 = 0, 12 * (2/3) = 0.