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 a
jest 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 1
lub '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ć?
źródło
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 rezultaciea = 3.5
. Od dołu do góry dokonuje podziału liczb całkowitych i przekształca dopiero w ostatnim kroku (przypisaniu), więca = 3.0
.int a = 1 + 2 - 3 * 4 - 5
int a = 5 - ((4*3) - (1+2))
int + int
staje sięint
.Odpowiedzi:
Rekurencja jest odpowiedzią, ale przed wykonaniem operacji schodzisz do każdego poddrzewa:
do postaci drzewa:
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:
-> zejdź do lhs
-> wnioskować
a
.a
wiadomo, że jestint
. Wróciliśmy teraz doassign
węzła:-> zejdź w rhs, a następnie w lhs wewnętrznych operatorów, aż trafimy na coś interesującego
-> wywnioskuj typ
1
, który jestint
, i wróć do rodzica-> przejdź do rhs
-> wywnioskuj typ
2
, który jestint
, i wróć do rodzica-> wywnioskuj typ
add(int, int)
, który jestint
, i wróć do rodzica-> zejdź do rhs
itd., dopóki nie skończysz z
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.
źródło
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:
a
są 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 typieauto
.1
,2
lub'c'
mają nieodłączny typ: literał int zawsze ma typint
, literał znakowy zawsze ma typchar
,….+
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 a
dodajesz wpisa: int
do tabeli.Wpisywanie liści to trywialny podstawowy przypadek rekurencji: typ literałów podobnych
1
jest już znany, a typy zmiennych podobnycha
moż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 * 3
i1 + 2
są wpisywane,int
ponieważ4
&3
i1
&2
zostały wcześniej wpisane,int
a twoje zasady pisania mówią, że suma lub iloczyn dwóchint
-s jestint
, 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 .
źródło
auto
nie 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. Poauto
prostu wymyśl typ prawej strony i gotowe.auto
, C #var
i 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, npint i = f(&i)
. Jeśli typi
jest wywnioskowany, powyższy algorytm się nie powiedzie: musisz znać typ,i
aby wnioskować o typiei
. Zamiast tego potrzebujesz pełnego wnioskowania typu HM ze zmiennymi typu.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:
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 == 0
ponieważ1/2
jest oceniane jako wyrażenie int.źródło
+
nie jest obsługiwane jak wywołania funkcji (ponieważ ma inne typowanie dladouble
i dlaint
operandów)operator+(int,int)
,operator+(double,double)
,operator+(char*,size_t)
, itd Parser po prostu musi śledzić których jedna jest zaznaczona.f(a,b)
jest o wiele łatwiejsze niż ustalenie rodzajua+b
.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.
źródło
To jest naprawdę dość łatwe, o ile myślisz o
+
różnorodności funkcji, a nie o pojedynczej koncepcji.Podczas etapu analizy po prawej stronie analizator analizuje
1
, wie, że toint
, następnie analizuje+
i zapisuje to jako „nierozstrzygniętą nazwę funkcji”, następnie analizuje2
, wie, że toint
, a następnie zwraca to stosu.+
Węzeł funkcja teraz zna oba rodzaje parametrów, dzięki czemu można rozwiązać+
INTOint 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.
Oto drzewo:
źródło
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:
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.
źródło