⚙️ Potok kompilatora

Leksator (nazywany też tokenizatorem lub skanerem) odczytuje surowe znaki źródłowe jeden po drugim i grupuje je w tokeny — najmniejsze znaczące jednostki języka. Dla prostego wyrażenia arytmetycznego jak „3 + 4 * x” tokenami są NUMBER(3), PLUS, NUMBER(4), STAR, IDENT(x). Każdy token ma typ i często wartość, a białe znaki są zazwyczaj odrzucane na tym etapie. Leksatory są zwykle implementowane jako automaty skończone wyprowadzone z wyrażeń regularnych.

AST to struktura danych w postaci drzewa reprezentująca strukturę gramatyczną kodu źródłowego, w której każdy węzeł wewnętrzny reprezentuje operator lub konstrukcję, a każdy liść reprezentuje operand lub literał. W przeciwieństwie do konkretnego drzewa rozbioru, AST pomija szum składniowy, taki jak nawiasy i średniki, zachowując wyłącznie strukturę semantyczną potrzebną do dalszej analizy. Kompilatory, interpretery, lintery i formatery kodu działają głównie na AST, a nie na surowym tekście źródłowym.

Parser zstępujący rekurencyjnie implementuje gramatykę jako zbiór wzajemnie rekurencyjnych funkcji, po jednej na regułę produkcji gramatyki. Aby przetworzyć wyrażenie, wywołuje funkcję wyrażenia, która wywołuje funkcję termu dla mnożenia, która wywołuje funkcję czynnika dla atomów — bezpośrednio odzwierciedlając hierarchię priorytetów operatorów na stosie wywołań. Parsery zstępujące rekurencyjnie są łatwe do napisania ręcznie, generują doskonałe komunikaty błędów i są używane w produkcyjnych kompilatorach, w tym GCC (front-end C) i Clang.

Kod trójadresowy (TAC) to reprezentacja pośrednia, w której każda instrukcja ma co najwyżej jeden operator i trzy operandy (dwa źródła i jeden cel): np. t1 = a * b; t2 = t1 + c. Ta prosta, jednolita struktura ułatwia analizę przepływu danych — każda zmienna tymczasowa jest definiowana tylko raz, co ułatwia postać statycznego pojedynczego przypisania (SSA). Większość nowoczesnych kompilatorów (GCC, LLVM) używa wewnętrznie pewnej formy TAC przed obniżeniem do asemblera; IR LLVM jest dobrze znanym, czytelnym dla człowieka przykładem.

Zwijanie stałych to optymalizacja, która oblicza stałe podwyrażenia w czasie kompilacji, zamiast generować kod obliczający je w czasie działania. Na przykład 2 * 3 + 1 staje się 7 przy zerowym koszcie w czasie działania. Nowoczesne kompilatory propagują też stałe przez przypisania zmiennych (propagacja stałych), umożliwiają dalsze uproszczenia, takie jak eliminacja martwego kodu, a nawet obliczają czyste wywołania funkcji, których argumenty są stałymi. Łączny efekt może drastycznie zmniejszyć liczbę instrukcji w kodzie z wieloma obliczeniami literałów.

Kompilator tłumaczy kod źródłowy na reprezentację docelową z wyprzedzeniem (AOT), tworząc artefakt — binarkę, bajtkod lub IR — który może działać niezależnie od kompilatora. Interpreter odczytuje kod źródłowy (lub bajtkod) i wykonuje go bezpośrednio, instrukcja po instrukcji, w czasie działania. Wiele nowoczesnych systemów łączy oba podejścia: Python kompiluje się do bajtkodu (.pyc), który następnie wykonuje interpreter CPython, a silniki JavaScript kompilują kod do kodu maszynowego za pomocą kompilacji just-in-time (JIT) dla często wykonywanych ścieżek kodu.

Gramatyka formalna to zbiór reguł produkcji definiujących, które ciągi tokenów są poprawne w danym języku. Gramatyki bezkontekstowe (CFG), opisane w notacji Backusa-Naura (BNF) lub rozszerzonej BNF, są używane dla większości języków programowania. Parser sprawdza, czy dane wejściowe są zgodne z gramatyką, i buduje AST. Słynna hierarchia Chomsky'ego klasyfikuje gramatyki według mocy wyrazu; gramatyki bezkontekstowe są wystarczająco potężne, by opisać zagnieżdżone struktury, takie jak zbalansowane nawiasy, czego wyrażenia regularne nie potrafią.

Analiza semantyczna sprawdza ograniczenia, których gramatyka nie potrafi wyrazić: sprawdzanie typów (czy liczba całkowita jest dodawana do napisu?), rozwiązywanie zakresu (czy ta zmienna jest zadeklarowana przed użyciem?) oraz wykrywanie użycia przed inicjalizacją. W językach statycznie typowanych ten etap buduje tabelę symboli mapującą identyfikatory na ich typy i dodaje adnotacje typów do AST. Błędy na tym etapie generują znane komunikaty „niezgodność typów” lub „niezadeklarowana zmienna”, pojawiające się po pomyślnym sparsowaniu.

Nowoczesne kompilatory stosują dziesiątki przejść optymalizacyjnych: eliminacja martwego kodu usuwa instrukcje, których wyniki nigdy nie są używane; rozwijanie pętli zmniejsza narzut skoków; inlining zastępuje miejsca wywołań funkcji ich ciałem, eliminując narzut wywołania; eliminacja wspólnych podwyrażeń (CSE) unika ponownego obliczania identycznych wyrażeń; a auto-wektoryzacja przepisuje pętle skalarne, aby używały instrukcji SIMD (Single Instruction, Multiple Data). Potok optymalizacji LLVM stosuje około 60 przejść przy -O2, a osiągane przyspieszenia zwykle wynoszą od 2x do 10x w porównaniu z niezoptymalizowanym kodem.

Kompilator JIT kompiluje kod w czasie działania, zwykle po zaobserwowaniu, że jest często wykonywany („gorące ścieżki”). Silnik V8 (używany w Chrome i Node.js) zaczyna od interpretowania bajtkodu JavaScript, profiluje, które funkcje są wywoływane najczęściej, a następnie kompiluje je do zoptymalizowanego natywnego kodu maszynowego. Jeśli wcześniej przyjęte założenie (np. że zmienna zawsze przechowuje liczbę całkowitą) zostanie później naruszone, V8 „deoptymalizuje” i wraca do wykonania interpretowanego. Skompilowany JIT-em JavaScript może działać w granicach 2-3x szybkości równoważnego kodu C dla wielu obciążeń.