Jak napisać bardzo prosty kompilator

Zaawansowane kompilatory, takie jak gcckompilowanie kodów do plików odczytywalnych maszynowo zgodnie z językiem, w którym kod został napisany (np. C, C ++ itp.). W rzeczywistości interpretują znaczenie każdego kodu zgodnie z biblioteką i funkcjami odpowiednich języków. Popraw mnie, jeśli się mylę.

Chcę lepiej zrozumieć kompilatory, pisząc bardzo prosty kompilator (prawdopodobnie w C) do kompilacji pliku statycznego (np. Hello World w pliku tekstowym). Próbowałem kilka samouczków i książek, ale wszystkie są przeznaczone do praktycznych przypadków. Zajmują się kompilowaniem kodów dynamicznych o znaczeniach związanych z odpowiednim językiem.

Jak napisać podstawowy kompilator do konwersji tekstu statycznego na plik do odczytu maszynowego?

Następnym krokiem będzie wprowadzenie zmiennych do kompilatora; wyobraźmy sobie, że chcemy napisać kompilator, który kompiluje tylko niektóre funkcje języka.

Bardzo cenne jest wprowadzenie praktycznych samouczków i zasobów :-)

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.

Mimo że niedokończony kompilator Jacka Crenshawa Let's Build a Compiler jest znakomicie czytelnym wprowadzeniem i tutorialem.

Nicklaus Wirth's Compiler Construction to bardzo dobry podręcznik na temat podstaw prostej budowy kompilatora. Koncentruje się na rekurencyjnym zejściu z góry, które, spójrzmy prawdzie w oczy, jest o wiele łatwiejsze niż lex / yacc lub flex / bizon. Oryginalny kompilator PASCAL napisany przez jego grupę został stworzony w ten sposób.

Inni wspominali różne książki o smokach.

Zacznę od napisania kompilatora dla Brainfuck . Jest to dość tępy język do programowania, ale ma tylko 8 instrukcji do wdrożenia. Jest to tak proste, jak to tylko możliwe, i istnieją równoważne instrukcje C dla zaangażowanych poleceń, jeśli uważasz, że składnia jest odkładająca.

Jeśli naprawdę chcesz pisać tylko kod odczytywalny maszynowo, a nie kierowany do maszyny wirtualnej, musisz przeczytać instrukcje Intela i zrozumieć

• za. Łączenie i ładowanie kodu wykonywalnego

• b. Formaty COFF i PE (dla systemu Windows) lub alternatywnie zrozumienie formatu ELF (dla systemu Linux)

• do. Zrozumienie formatów plików .COM (łatwiejsze niż PE)
• re. Zrozumieć asemblery
• mi. Zrozumienie kompilatorów i silnika generowania kodu w kompilatorach.

Znacznie trudniejsze niż powiedziane. Sugeruję przeczytanie kompilatorów i tłumaczy w C ++ jako punktu wyjścia (autor: Ronald Mak). Alternatywnie „budowanie kompilatora” przez Crenshaw jest OK.

Jeśli nie chcesz tego robić, równie dobrze możesz napisać własną maszynę wirtualną i napisać generator kodu skierowany na tę maszynę wirtualną.

• Kolejny punkt wyjścia: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Wielka książka Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Wskazówki: Naucz się Flex i Bison PIERWSZY. Następnie zbuduj własny kompilator / maszynę wirtualną.

Powodzenia!

Podejście DIY do prostego kompilatora może wyglądać tak (przynajmniej tak wyglądał mój projekt uni):

1. Zdefiniuj gramatykę języka. Bezkontekstowy.
2. Jeśli Twoja gramatyka nie jest jeszcze LL (1), zrób to teraz. Zauważ, że niektóre reguły, które wyglądały dobrze w zwykłej gramatyce CF, mogą okazać się brzydkie. Być może twój język jest zbyt skomplikowany ...
3. Napisz Lexer, który tnie strumień tekstu na tokeny (słowa, liczby, literały).
4. Napisz z góry na dół rekursywny analizator składni dla swojej gramatyki, który akceptuje lub odrzuca dane wejściowe.
5. Dodaj generowanie drzewa składni do parsera.
6. Napisz generator kodu maszynowego z drzewa składni.
7. Zysk i piwo, alternatywnie możesz zacząć myśleć, jak zrobić mądrzejszy parser lub wygenerować lepszy kod.

Powinno być mnóstwo literatury opisującej szczegółowo każdy krok.