Wprowadzenie
Typowy kompilator wykonuje następujące kroki:
- Analiza: tekst źródłowy jest konwertowany na abstrakcyjne drzewo składniowe (AST).
- Rozdzielanie odniesień do innych modułów (C odracza ten krok do połączenia).
- Walidacja semantyczna: wyeliminowanie poprawnych składniowo instrukcji, które nie mają sensu, np. Nieosiągalny kod lub zduplikowane deklaracje.
- Równoważne transformacje i optymalizacja wysokiego poziomu: AST przekształca się, aby reprezentować bardziej wydajne obliczenia z tą samą semantyką. Obejmuje to np. Wczesne obliczanie typowych podwyrażeń i wyrażeń stałych, eliminowanie nadmiernych przypisań lokalnych (patrz także SSA ) itp.
- Generowanie kodu: AST przekształca się w liniowy kod niskiego poziomu, ze skokami, alokacją rejestru i tym podobnymi. Na tym etapie można wprowadzić niektóre wywołania funkcji, rozwinąć niektóre pętle itp.
- Optymalizacja wizjera: kod niskiego poziomu jest skanowany w poszukiwaniu prostych lokalnych nieefektywności, które są eliminowane.
Większość współczesnych kompilatorów (na przykład gcc i clang) powtarza dwa ostatnie kroki jeszcze raz. Używają pośredniego języka niskiego poziomu, ale niezależnego od platformy do początkowego generowania kodu. Następnie język ten jest konwertowany na kod specyficzny dla platformy (x86, ARM itp.), Robiąc mniej więcej to samo w sposób zoptymalizowany dla platformy. Obejmuje to np. Użycie instrukcji wektorowych, jeśli to możliwe, zmianę kolejności instrukcji w celu zwiększenia wydajności przewidywania gałęzi i tak dalej.
Następnie kod obiektowy jest gotowy do połączenia. Większość kompilatorów kodu rodzimego wie, jak wywołać konsolidator, aby utworzyć plik wykonywalny, ale nie jest to sam krok kompilacji. W językach takich jak Java i C # łączenie może być całkowicie dynamiczne, wykonywane przez maszynę wirtualną podczas ładowania.
Zapamiętaj podstawy
- Niech to zadziała
- Zrób to pięknie
- Zrób to wydajnie
Ta klasyczna sekwencja dotyczy wszystkich programów, ale jest powtarzana.
Skoncentruj się na pierwszym etapie sekwencji. Stwórz najprostszą rzecz, która może działać.
Czytaj książki!
Przeczytaj książkę o smokach autorstwa Aho i Ullmana. Jest to klasyczne i do dziś jest całkiem aktualne.
Chwalony jest również nowoczesny projekt kompilatora .
Jeśli te rzeczy są dla ciebie teraz zbyt trudne, najpierw przeczytaj kilka wstępnych analiz. biblioteki parsujące zwykle zawierają informacje wstępne i przykłady.
Upewnij się, że wygodnie pracujesz z wykresami, zwłaszcza drzewami. Są to rzeczy, z których programy są tworzone na poziomie logicznym.
Dobrze zdefiniuj swój język
Używaj dowolnej notacji, ale upewnij się, że masz pełny i spójny opis swojego języka. Obejmuje to zarówno składnię, jak i semantykę.
Najwyższy czas pisać fragmenty kodu w nowym języku jako przypadki testowe dla przyszłego kompilatora.
Użyj swojego ulubionego języka
Pisanie kompilatora w języku Python, Ruby lub innym języku jest dla Ciebie w porządku. Używaj prostych algorytmów, które dobrze rozumiesz. Pierwsza wersja nie musi być szybka, wydajna ani pełna. To musi być tylko poprawne i łatwe do modyfikacji.
W razie potrzeby można także pisać różne etapy kompilatora w różnych językach.
Przygotuj się do napisania wielu testów
Twój cały język powinien być objęty przypadkami testowymi; faktycznie zostaną przez nich zdefiniowane . Zapoznaj się z preferowaną strukturą testowania. Napisz testy od pierwszego dnia. Skoncentruj się na „pozytywnych” testach, które akceptują poprawny kod, a nie na wykrywaniu nieprawidłowego kodu.
Regularnie przeprowadzaj wszystkie testy. Napraw zepsute testy przed kontynuowaniem. Szkoda byłoby skończyć z źle zdefiniowanym językiem, który nie akceptuje poprawnego kodu.
Utwórz dobry parser
Generatorów parsera jest wiele . Wybierz cokolwiek chcesz. Możesz także napisać własny parser od zera, ale to tylko warto, jeśli składnia języku jest martwy prosta.
Analizator składni powinien wykrywać i zgłaszać błędy składniowe. Napisz wiele przypadków testowych, zarówno pozytywnych, jak i negatywnych; użyj ponownie kodu, który napisałeś podczas definiowania języka.
Dane wyjściowe analizatora składni są abstrakcyjnym drzewem składni.
Jeśli twój język ma moduły, wynikiem parsera może być najprostsza reprezentacja wygenerowanego „kodu obiektowego”. Istnieje wiele prostych sposobów na zrzucenie drzewa do pliku i szybkie załadowanie go z powrotem.
Utwórz weryfikator semantyczny
Najprawdopodobniej twój język pozwala na konstrukcyjnie poprawne konstrukcje, które mogą nie mieć sensu w pewnych kontekstach. Przykładem jest zduplikowana deklaracja tej samej zmiennej lub przekazanie parametru niewłaściwego typu. Walidator wykryje takie błędy patrząc na drzewo.
Walidator rozpozna również odniesienia do innych modułów napisanych w twoim języku, załaduje te inne moduły i użyje w procesie walidacji. Na przykład ten krok upewni się, że liczba parametrów przekazanych do funkcji z innego modułu jest poprawna.
Ponownie napisz i uruchom wiele przypadków testowych. Trywialne przypadki są równie niezbędne przy rozwiązywaniu problemów, jak inteligentne i złożone.
Wygeneruj kod
Użyj najprostszych technik, jakie znasz. Często można bezpośrednio tłumaczyć konstrukcję języka (np. ifInstrukcję) na lekko sparametryzowany szablon kodu, podobnie jak szablon HTML.
Ponownie zignoruj wydajność i skoncentruj się na poprawności.
Kieruj na niezależną od platformy maszynę wirtualną niskiego poziomu
Podejrzewam, że ignorujesz rzeczy niskiego poziomu, chyba że interesują Cię szczegóły dotyczące sprzętu. Te szczegóły są krwawe i złożone.
Twoje opcje:
- LLVM: pozwala na wydajne generowanie kodu maszynowego, zwykle dla x86 i ARM.
- CLR: atakuje .NET, głównie oparty na architekturze x86 / Windows; ma dobry JIT.
- JVM: atakuje świat Java, dość wieloplatformowy, ma dobre JIT.
Zignoruj optymalizację
Optymalizacja jest trudna. Prawie zawsze optymalizacja jest przedwczesna. Wygeneruj nieefektywny, ale poprawny kod. Zaimplementuj cały język, zanim spróbujesz zoptymalizować wynikowy kod.
Oczywiście można wprowadzić trywialne optymalizacje. Ale unikaj sprytnych, owłosionych rzeczy, zanim kompilator się ustabilizuje.
Więc co?
Jeśli to wszystko nie jest dla ciebie zbyt przerażające, kontynuuj! W przypadku prostego języka każdy z kroków może być prostszy niż myślisz.
Warto zobaczyć „Witaj świecie” z programu stworzonego przez kompilator.