Wnętrze Kompilatora: Od Tekstu Źródłowego do Kodu Maszynowego

Tekst wejściowy, kod maszynowy wyjściowy, cztery etapy pomiędzy

Praca kompilatora polega na udowodnieniu, mechanicznie, że fragment kodu źródłowego ma precyzyjne znaczenie, a następnie generowaniu sekwencji instrukcji o tym samym dokladnym znaczeniu. Pomimo dziesięcioleci dodawanych zaawansowań, prawie każdy kompilator nadal realizuje to zadanie w czterech etapach: przekształcenie znaków w tokeny, przekształcenie tokenów w drzewo, przekształcenie drzewa w proste instrukcje liniowe oraz ulepszenie tych instrukcji bez zmiany ich znaczenia.

Analiza leksykalna: znaki do tokenów

Analizator (lub skaner) odczytuje surowe znaki i grupuje je w tokeny – najmniejsze znaczące jednostki: liczby, identyfikatory, operatorzy, słowa kluczowe, znakodawstwo. Spacja i komentarze są zazwyczaj usuwane tutaj. Analizator jest prawie zawsze równoważny maszynie stanowej wyższego rzędu, odpowiadającej dużemu wyrażeniu regularnemu: może rozpoznawać 42.5 jako pojedynczy token LICZBY w jednym przejściu bez konieczności sprawdzania dalszych znaków, ponieważ składnia liczb jest regularna.

input:   "12 + 3 * x"
tokens:  NUM(12)  PLUS  NUM(3)  STAR  IDENT(x)

Analiza: tokeny do drzewa

Analizator przetwarza płaski strumień tokenów i narzuca strukturę: Drzewo Reprezentacji Abstrakcyjnej (DRA), które odzwierciedla priorytety i asocjacyjność, dwie rzeczy, których nie można wyrazić w prostym liście tokenów. W przypadku obliczeń powszechnie stosowaną techniką jest parsowanie rekurencyjne z wspinaniem się priorytetów (znane również jako parser Pratt): każdy operator otrzymuje moc wiązania, a analizator rekursywnie przetwarza podwyrażenia tylko wtedy, gdy następny operator wiąże się z aktualnym przynajmniej tak ściśle.

12 + 3 * x analizuje się jako (+ 12 (* 3 x)) nie (* (+ 12 3) x) ponieważ mnożenie ma wyższy priorytet niż dodawanie, więc analizator pobiera się do głębi "3 * x" przed powrotem i zakończeniem dodawania. Dwuzdzinne gramatyki – słynny problem „wisiącego else”, gdzie jeśli (a) if (b) s1; else s2; mógłby być przypisany do któregokolwiek z if, można rozwiązać dzięki ustalonej konwencji (przypisywać się do najbliższego niezwiązania if), zamiast polegać na losowości.

12 + 3 * x   parses as   (+ 12 (* 3 x))     not   (* (+ 12 3) x)

because * has higher binding power than +, so the parser
descends into "3 * x" before returning to finish the addition

Kodegen: drzewo do kodu trójadresowego

Po zbudowaniu drzewa AST, generowanie kodu przechodzi przez nie i emituje proste, liniowe instrukcje, zwykle w postaci kodu trójadresowego: każda instrukcja ma maksymalnie jeden operator i zapisuje się w maksymalnie jednej zmiennej tymczasowej.

AST: (+ 12 (* 3 x)) dokładny kod trójadresowy: t1 = 3 * x t2 = 12 + t1 Każda instrukcja w kodzie trójadresowym mapuje się niemal bezpośrednio na kilka rzeczywistych instrukcji maszynowych (load, multiply, add, store), dlatego właśnie ten format pośredni jest standardowym punktem przekazania między front-endem kompilatora (specyficznym dla języka) a back-endem (specyficznym dla docelowej architektury): ponowne targetowanie do nowej jednostki centralnej oznacza przepisywanie tylko niewielkiego końcowego kroku z kodu trójadresowego na instrukcje tej jednostki centralnej.

AST:  (+ 12 (* 3 x))

three-address code:
  t1 = 3 * x
  t2 = 12 + t1

Optymalizacja: skumulowanie stałe i więcej

Pomiędzy kodowaniem a ostatecznym emitowaniem znajdują się przejścia optymalizacyjne, które poprawiają kod bez zmiany jego znaczenia. Najprostsze i najbardziej uniwersalne to skumulowanie stałego: jeśli operandy instrukcji są znane w czasie kompilacji, oblicz je raz podczas kompilacji zamiast na każdym uruchomieniu.

przed: po skumulowaniu stałego: t1 = 3 * 4 t1 = 12 t2 = t1 + x t2 = 12 + x (dodatkowe skumulowania, jeśli x również jest stałe) Prawdziwe kompilatory łańcuchowo wykonują dziesiątki takich przejść — eliminacja martwego kodu, eliminacja wspólnych wyrażeń, redukcja siły, wstawianie funkcji, alokacja rejestrów — każde z nich to niewielkie, zachowujące znaczenie przekształcenie, wykonywane wielokrotnie, dopóki nic się nie zmienia. Interaktywna demonstracja powyżej implementuje tylko niezbędne elementy — lexer, parser rekurencyjny-opadający, kodowanie trzyadresowe i jeden przechodz skumulowania stałego — ale każdy pełnowymiarowy kompilator, od silnika JavaScript JIT po GCC, jest zbudowany z tych czterech etapów, tylko z znacznie większą ich liczbą łańcuchowo połączoną.

before:                  after constant folding:
  t1 = 3 * 4               t1 = 12
  t2 = t1 + x               t2 = 12 + x   (further folds if x is also constant)

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Compiler Pipeline i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.