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

23

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ć?

Christian Dean
źródło
8
Istnieje oczywisty i prosty sposób na sprawdzenie rodzaju wyrażenia. Lepiej powiedz nam, co sprawia, że ​​nazywasz to „niesmakiem”.
gnasher729
12
Zwykłą metodą jest „druga metoda”: kompilator określa typ wyrażenia złożonego na podstawie typów podwyrażeń. To był główny punkt semantyki denotacyjnej i większość systemów typów stworzonych do dziś.
Joker_vD
5
Te dwa podejścia mogą wywoływać różne zachowania: Podejście odgórne double a = 7/2 spróbuje zinterpretować prawą stronę jako podwójną, a zatem spróbuje zinterpretować licznik i mianownik jako podwójny i przekształcić je w razie potrzeby; w rezultacie a = 3.5. Od dołu do góry dokonuje podziału liczb całkowitych i przekształca dopiero w ostatnim kroku (przypisaniu), więc a = 3.0.
Hagen von Eitzen
3
Zauważ, że zdjęcie twojego AST nie odpowiada twojemu int a = 1 + 2 - 3 * 4 - 5int a = 5 - ((4*3) - (1+2))
wyrazowi,
22
Możesz „wykonać” wyrażenie na typach, a nie na wartościach; np . int + intstaje się int.

Odpowiedzi:

14

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.

Simon Richter
źródło
43

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 .

Basile Starynkevitch
źródło
2
W jaki sposób C ++ 11 autonie jest prostsze? Bez tego musisz dowiedzieć się, jaki jest typ po prawej stronie, a następnie sprawdzić, czy istnieje dopasowanie lub konwersja z typem po lewej stronie. Po autoprostu wymyśl typ prawej strony i gotowe.
nwp
3
@nwp Ogólna idea definicji zmiennych C ++ auto, C # vari Go :=jest bardzo prosta: sprawdź typ po prawej stronie definicji. Wynikowym typem jest typ zmiennej po lewej stronie. Ale diabeł tkwi w szczegółach. Na przykład, definicje C ++ mogą być referencyjne, więc możesz odwoływać się do zmiennej zadeklarowanej w rh, np int i = f(&i). Jeśli typ ijest wywnioskowany, powyższy algorytm się nie powiedzie: musisz znać typ, iaby wnioskować o typie i. Zamiast tego potrzebujesz pełnego wnioskowania typu HM ze zmiennymi typu.
amon
13

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.

maniak zapadkowy
źródło
6
Prawie prawdziwe dla C, gdzie +nie jest obsługiwane jak wywołania funkcji (ponieważ ma inne typowanie dla doublei dla intoperandów)
Basile Starynkevitch
2
@BasileStarynkevitch: to realizowane jak seria przeciążonych funkcji: operator+(int,int), operator+(double,double), operator+(char*,size_t), itd Parser po prostu musi śledzić których jedna jest zaznaczona.
Mooing Duck
3
@aschepler Nikt nie sugeruje, że w source- i specyfikacji poziomu C faktycznie jest przeciążony lub funkcje funkcji operatora
cat
1
Oczywiście nie. Po prostu wskazując, że w przypadku parsera C „wywołanie funkcji” jest czymś innym, z czym trzeba by sobie poradzić, ale tak naprawdę nie ma wiele wspólnego z „operatorami jako wywołaniami funkcji”, jak opisano tutaj. W rzeczywistości w C ustalenie rodzaju f(a,b)jest o wiele łatwiejsze niż ustalenie rodzaju a+b.
aschepler
2
Każdy rozsądny kompilator C ma wiele faz. Niedaleko frontu (za preprocesorem) znajduje się parser, który tworzy AST. Tutaj jest całkiem jasne, że operatory nie są wywołaniami funkcji. Ale podczas generowania kodu nie przejmujesz się już, który konstrukt języka utworzył węzeł AST. Właściwości samego węzła określają sposób traktowania węzła. W szczególności + może równie dobrze być wywołaniem funkcji - zwykle dzieje się to na platformach z emulowaną zmiennoprzecinkową matematyką. Decyzja o użyciu emulowanej matematyki FP następuje podczas generowania kodu; nie jest wymagana wcześniejsza różnica AST.
MSalters
6

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.

JDługosz
źródło
6

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
Mucząca Kaczka
źródło
4

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.

gnasher729
źródło