Przez większość grudnia pisałem kompilator na studia w ramach przedmiotu Metody Realizacji Języków Programowania. Skoro czegoś się dowiedziałem, to stwierdziłem że opiszę nowo nabytą wiedzę na moim blogu.

Note: W zamyśle będzie to seria postów, ale mam złe doświadczenia z seriami postów, więc postaram się, aby każdy post był w miarę niezależny.

Co to jest kompilator?

Kompilatorem nazwiemy program przetwarzający instrukcje, napisane w pewnym języku programowania, na instrukcje innego typu - często kod maszynowy, który można wykonać bezpośrednio jako nowy program.

Chcielibyśmy na przykład powiedzieć:

„Daj mi program, który wczyta dwie liczby od użytkownika, a następnie wypisze ich sumę.”

Co przełożymy na język programowania, który w odróżnieniu od języka naturalnego ma pewne własności swojej gramatyki, które pozwalają na łatwe przetwarzanie przez komputer.

x = wczytajLiczbę()
y = wczytajLiczbę()
wypisz(x + y)

Kompilator zna gramatykę tego języka i za pomocą procesu „parsowania” przetwarza plik tekstowy (np. zrobiony w notatniku), żeby zobaczyć czy jego zawartość jest zgodna z gramatyką, a jeśli tak to jakie „wyrazy” zostały użyte.

Na przykład powyższy program moglibyśmy opisać przez taką gramatykę:

Program             := Lista poleceń
Polecenie           := Przypisanie LUB Wywołanie procedury
Przypisanie         := Zmienna "=" Wyrażenie
Wywołanie procedury := Nazwa "(" Lista wyrażeń ")"
Wyrażenie           := Operacja LUB Wywołanie procedury
Operacja            := Zmienna "+" Zmienna
Zmienna             := Nazwa

To jest oczywiście uproszczenie, żeby lepiej zrozumieć o co chodzi.

Mamy opis gramatyki, mamy program, to teraz dochodzi do parsowania i nasz kompilator dowiaduje się, że plik z programem opisuje coś takiego:

Program:
    1. Przypisanie:
        "x"
         =
        Wyrażenie:
            Wywołanie procedury:
                "wczytajLiczbę"
                []
    2. Przypisanie:
        "y"
         =
        Wyrażenie:
            Wywołanie procedury:
                "wczytajLiczbę"
                []
    3. Wywołanie procedury:
        "wypisz"
        1. Wyrażenie:
            Operacja:
                "x"
                 +
                "y"

Jest to reprezentacja programu w postaci grafu, a konkretniej drzewa, który nazywany jest abstrakcyjnym drzewem składni (AST). Taka struktura jest bardziej wygodna dla komputera niż forma tekstowa.

Następnie kompilator może dokonywać pewnych modyfikacji drzewa AST np. optymalizując program albo upraszczając niektóre elementy.

Jeśli język programowania ma statyczne typowanie, t.j. każda zmienna i funkcja ma przypisany pewien niezmienny typ (np. liczba, słowo, funkcja z liczb rzeczywistych w liczby całkowite) to kompilator będzie również te typy sprawdzał lub nawet się ich domyślał (proces inferencji typów).

No i w zależności od kompilatora i języka, będą zachodzić różne dodatkowe procesy, aż na końcu zostaną wyprodukowane instrukcje w języku docelowym. Może to być kod maszynowy, może to być kod pośredni, może to być inny język programowania, który ma swój własny kompilator.

Najczęściej używanym kompilatorem jest pewnie gcc, czyli GNU C Compiler, który kompiluje programy napisane w języku C do kodu maszynowego.

Jaki język ja kompiluję?

Moim zadaniem było napisanie kompilatora dla języka Latte, który jest pewnym podzbiorem języka Java. Jego pełny opis znajdziesz tutaj. Mamy zmienne, funkcje, przypisania, warunki, pętle, a w wersji rozszerzonej również tablice, obiekty i dziedziczenie.

Dostałem gramatykę w formacie LBNF do podstawowej wersji Latte, którą musiałem rozszerzyć. Taką gramatykę następnie mogłem dać do programu BNFC, który wyprodukował dla mnie kod parsera. Innym przykładem takiego generatora jest ANTLR, który ma nieco inny format gramatyk.

Mógłbym opisać jak przebiega parsowanie, ale nie jest to wiedza niezbędna do napisania kompilatora, a raczej ciekawostka. Oczywiście są prace nad coraz wydajniejszymi parserami i tam takie informacje jak klasy gramatyk są bardziej potrzebne.

Kod źródłowy mojego kompilatora jest dostępny na moim GitHubie.

W następnym poście postaram się napisać o odsładzaniu (desugaring), czyli uproszczaniu kodu z gramatyki, którą posługuje się użytkownik kompilatora do gramatyki używanej przez kompilator.