Jak napisać bardzo prosty kompilator

Wprowadzenie

Typowy kompilator wykonuje następujące czynności:

• Parsowanie: tekst źródłowy jest konwertowany do abstrakcyjnego drzewa składniowego (AST).
• Rozwiązanie odniesień do innych modułów (C odkłada ten krok do połączenia).
• Walidacja semantyczna: usuwanie poprawnych składniowo instrukcji to nie ma sensu, np nieosiągalny kod lub zduplikowane deklaracje.
• Równoważne transformacje i optymalizacja wysokiego poziomu: AST jest przekształcany, aby reprezentował bardziej wydajne obliczenia z tą samą semantyką. Obejmuje to m.in. wczesne obliczanie typowych podwyrażeń i stałych wyrażeń, eliminowanie nadmiernych przypisań lokalnych (patrz także SSA ), itp.
• Generowanie kodu: AST jest przekształcone w liniowy kod niskiego poziomu, ze skokami, alokacją rejestrów i tym podobnymi. Niektóre wywołania funkcji mogą być wbudowane na tym etapie, niektóre pętle rozwinięte itp.
• Optymalizacja wizjera: kod niskiego poziomu jest skanowany pod kątem 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. Do początkowego generowania kodu używają języka niskiego poziomu średnio-zaawansowanego, ale niezależnego od platformy. Następnie ten język jest konwertowany na kod specyficzny dla platformy (x86, ARM itp.) Robiąc mniej więcej to samo w sposób zoptymalizowany pod kątem platformy. Obejmuje to m.in. użycie instrukcji wektorowych, jeśli to możliwe, zmiana kolejności instrukcji w celu zwiększenia wydajności przewidywania gałęzi itd.

Następnie kod obiektowy jest gotowy do łączenia. Większość kompilatorów kodu natywnego wie, jak wywołać konsolidator w celu utworzenia pliku wykonywalnego, ale nie jest to sam w sobie krok kompilacji. W językach takich jak Java i C # łączenie może być całkowicie dynamiczne, wykonywane przez maszynę wirtualną w czasie ładowania.

Zapamiętaj podstawy

• Spraw, by działało
• Spraw, by było piękne
• Spraw, by było wydajne

Ta klasyczna sekwencja dotyczy całego rozwoju oprogramowania, ale wymaga powtórzeń.

Skoncentruj się na pierwszym kroku sekwencji. Utwórz najprostszą rzecz, która może zadziałać.

Przeczytaj książki!

Przeczytaj Dragon Book autorstwa Aho i Ullman. Jest to klasyczne i wciąż ma zastosowanie.

Nowoczesny projekt kompilatora jest również chwalony.

Jeśli te rzeczy są teraz dla Ciebie za trudne, przeczytaj najpierw kilka wstępów na temat parsowania; zwykle analizuję biblioteki dołącz wstępy i przykłady.

Upewnij się, że „czujesz się komfortowo podczas pracy z wykresami, zwłaszcza drzewami. Są to rzeczy, z których składają się programy na poziomie logicznym.

Dobrze zdefiniuj swój język

Używaj dowolnej notacji, ale upewnij się, że masz kompletny i spójny opis swojego język. Obejmuje to zarówno składnię, jak i semantykę.

Najwyższy czas napisać fragmenty kodu w nowym języku jako przypadki testowe dla przyszłego kompilatora.

Użyj swojego ulubionego języka

Całkowicie w porządku jest napisać kompilator w Pythonie, Ruby lub jakimkolwiek innym łatwym dla Ciebie języku.Używaj prostych algorytmów, które dobrze rozumiesz. Pierwsza wersja nie musi być szybka, wydajna ani kompletna. Wystarczy, że będzie wystarczająco poprawny i łatwy do modyfikacji.

W razie potrzeby można również napisać różne etapy kompilatora w różnych językach.

Przygotuj się do pisania dużo testów

Cały Twój język powinien być pokryty przypadkami testowymi; w praktyce będzie przez nie zdefiniowany . Zapoznaj się z preferowanym frameworkiem testowym. Pisz testy od pierwszego dnia. Skoncentruj się na „pozytywnych” testach, które akceptują poprawny kod, w przeciwieństwie do wykrywania nieprawidłowego kodu.

Regularnie uruchamiaj wszystkie testy. Napraw uszkodzone testy przed kontynuowaniem. Szkoda byłoby skończyć z zdefiniowany język, który nie akceptuje prawidłowego kodu.

Utwórz dobry parser

Istnieje wiele generatorów parserów . Wybierz, co chcesz Możesz też napisać własny parser od podstaw, ale warto to robić tylko wtedy, gdy składnia twojego języka jest martwa prosta.

Parser powinien wykrywać i zgłaszać błędy składniowe. wiele przypadków testowych, zarówno pozytywnych, jak i negatywnych ve; użyj ponownie kodu, który napisałeś podczas definiowania języka.

Wyjście twojego parsera to abstrakcyjne drzewo składni.

Jeśli twój język ma moduły, wyjście parsera może być najprostszą reprezentacją wygenerowanego „kodu wynikowego”. Istnieje wiele prostych sposobów na zrzucenie drzewa do pliku i szybkie załadowanie go z powrotem.

Utwórz semantyczny walidator

Najprawdopodobniej twój język pozwala na składniowo poprawne konstrukcje, które mogą bez 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 rozwiąże również odniesienia do innych modułów napisanych w Twoim języku, załaduje te inne moduły i użyje ich w procesie walidacji. Na przykład ten krok zapewni, że liczba parametrów przekazanych do funkcji z innego modułu jest poprawna.

Ponownie napisz i uruchom wiele przypadków testowych. Trywialne przypadki są tak samo niezbędne do rozwiązywania problemów, jak inteligentne i złożone.

Wygeneruj kod

Użyj najprostszych technik, jakie znasz. Często można bezpośrednio przetłumaczyć konstrukcję językową (taką jak instrukcja if) na lekko sparametryzowany szablon kodu, podobnie jak szablon HTML.

Znowu , zignoruj wydajność i skoncentruj się na poprawności.

Kieruj reklamy na niezależną od platformy maszynę wirtualną niskiego poziomu

Przypuszczam, że ignorujesz rzeczy niskiego poziomu, chyba że „bardzo interesujesz się specyficznymi dla sprzętu Detale. Te szczegóły są krwawe i złożone.

Twoje opcje:

• LLVM: pozwala na wydajne generowanie kodu maszynowego, zwykle dla x86 i ARM.
• CLR : cele .NET, wieloplatformowe; ma dobry JIT.
• JVM: jest przeznaczony dla świata Java, dość wieloplatformowy, ma dobry JIT.

Ignoruj optymalizację

Optymalizacja jest trudna. Niemal zawsze optymalizacja jest przedwczesna. Generuj nieefektywny, ale poprawny kod. Zaimplementuj cały język, zanim spróbujesz zoptymalizować wynikowy kod.

Oczywiście trywialne optymalizacje można wprowadzić. Ale unikaj wszelkich przebiegłych, włochatych rzeczy, zanim kompilator będzie stabilny.

I co z tego?

Jeśli te wszystkie rzeczy nie są dla Ciebie zbyt onieśmielające, kontynuuj! W przypadku prostego języka każdy z kroków może być prostszy niż myślisz.

Zobaczenie „Witaj świecie” z programu utworzonego przez Twój kompilator może być warte wysiłku.

Komentarze

• To jedna z najlepszych odpowiedzi, które ' już widziałem.
• Myślę, że Ty przegapiłem część pytania … OP chciał napisać bardzo prosty kompilator. Myślę, że wychodzisz tutaj poza bardzo podstawowe.
• @ marco-fiset , wręcz przeciwnie, myślę, że ' to znakomita odpowiedź, która mówi OP, jak zrobić bardzo podstawowy kompilator, jednocześnie wskazując pułapki, których należy unikać i definiując bardziej zaawansowane fazy.
• To jest jedna z najlepszych odpowiedzi Widziałem kiedykolwiek w całym uniwersum Stack Exchange. Brawo!
• Zobaczenie ' Witaj świecie ' z programu utworzonego przez Twój kompilator może być warte wysiłku. – INDEED

Jack Crenshaw „s „Zbudujmy kompilator ”, choć niedokończony, jest wyjątkowo czytelnym wprowadzeniem i samouczkiem.

Nicklaus Wirth „s Budowa kompilatora jest bardzo dobrym podręcznikiem na temat podstaw konstrukcji prostych kompilatorów, skupia się na zejściu rekurencyjnym z góry na dół, które, spójrzmy prawdzie w oczy, jest DUŻO łatwiejsze niż lex / yacc czy flex / bison. Oryginalny kompilator PASCAL, który napisała jego grupa, powstał w ten sposób.

Inni ludzie wspominali o różnych książkach Dragon.

Komentarze

• Jedną z fajnych rzeczy w Pascalu jest to, że wszystko musi być zdefiniowane lub zadeklarowane przed użyciem. Dlatego można go skompilować w jednym przejściu. Turbo Pascal 3.0 jest jednym z takich przykładów, a istnieje wiele dokumentacji na temat elementów wewnętrznych tutaj .
• PASCAL został specjalnie zaprojektowany z jednym pamiętaj o kompilacji i linkowaniu. Książka kompilatora Wirtha ' wspomina o kompilatorach wieloprzebiegowych i dodaje, że wiedział o kompilatorze PL / I, który wymagał 70 (tak, siedemdziesiąt) przebiegów.
• Obowiązkowa deklaracja przed użyciem sięga ALGOLU. Tony Hoare został przypięty do tyłu przez komisję ALGOL, kiedy próbował zasugerować dodanie domyślnych reguł typu, podobnych do tych, które miał FORTRAN. Wiedzieli już o problemach, jakie może to spowodować, z błędami typograficznymi w nazwach i domyślnymi regułami powodującymi interesujące błędy.
• Oto bardziej zaktualizowana i ukończona wersja książki autorstwa samego autora: stack.nl/~marcov/compiler.pdf Edytuj swoją odpowiedź i dodaj ją 🙂

Jeśli naprawdę chcesz napisać tylko kod do odczytu maszynowego i nie jest przeznaczony dla maszyny wirtualnej, musisz przeczytać podręczniki firmy Intel i zrozumieć

• a. Łączenie i ładowanie kodu wykonywalnego

• b. Formaty COFF i PE (dla Windows), alternatywnie zrozum format ELF (dla Linuksa)

• c. Zrozumieć formaty plików .COM (łatwiejsze niż PE)
• d. Zrozumienie asemblerów
• e. Zrozum kompilatory i mechanizm generowania kodu w kompilatorach.

O wiele trudniejsze niż powiedziane. Proponuję przeczytać Compilers and Interpreters in C ++ jako punkt wyjścia (autor: Ronald Mak). Alternatywnie, „Zbudujmy kompilator” Crenshawa jest OK.

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

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

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

Powodzenia!

Komentarze

• Myślę, że kierowanie na LLVM, a nie prawdziwy kod maszynowy jest obecnie najlepszym dostępnym sposobem.
• Zgadzam się, śledzę LLVM od jakiegoś czasu i powinienem powiedzieć, że była to jedna z najlepszych rzeczy, jakie widziałem od lat pod względem wysiłku programisty trzeba go namierzyć!
• A co z MIPS i użyj spim , aby go uruchomić? Lub MIX ?
• @MichaelT Nie używałem MIPS, ale jestem pewien, że będzie dobrze.
• Zestaw instrukcji @PrototypeStark RISC, rzeczywisty procesor, który jest nadal w użyciu (zrozumienie, że będzie można go przetłumaczyć na systemy wbudowane). Pełny zestaw instrukcji znajduje się na wikipedii . W sieci można znaleźć wiele przykładów i jest on używany na wielu zajęciach akademickich jako cel programowania w języku maszynowym. Jest na nim trochę aktywności w SO .

Zacząłbym właściwie od napisania kompilatora dla Brainfuck . Jest to dość tępy język programowania, ale ma tylko 8 instrukcji do wdrożenia. Jest to tak proste, jak to tylko możliwe, a istnieją równoważne instrukcje w języku C dla odpowiednich poleceń, jeśli uznasz, że składnia jest odrażająca.

Komentarze

• Ale kiedy już masz gotowy kompilator BF, musisz napisać w nim swój kod 🙁
• @ 500-InternalServerError użyj metody podzbioru C

Samodzielne podejście do prostego kompilatora mogłoby wyglądać tak (przynajmniej tak wyglądał mój projekt uni):

1. Zdefiniuj gramatykę języka. Bezkontekstowe.
2. Jeśli twoja gramatyka nie jest jeszcze „t LL (1)”, zrób to teraz. Zauważ, że niektóre reguły wyglądały dobrze w zwykłym CF gramatyka może okazać się brzydka. Być może twój język jest zbyt złożony …
3. Napisz Lexer, który tnie strumień tekstu na tokeny (słowa, liczby, literały).
4. Zapisuj od góry do dołu rekurencyjny parser zejścia dla twojej gramatyki, który akceptuje lub odrzuca dane wejściowe.
5. Dodaj generowanie drzewa składni do swojego parsera.
6. Napisz ma generator kodu chine z drzewa składni.
7. Zysk & Piwo, alternatywnie możesz zacząć myśleć, jak zrobić mądrzejszy parser lub wygenerować lepszy kod.

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

Komentarze

• O siódmym punkcie pyta OP.
• 1-5 są nieistotne i nie zasługują na takie uważną uwagę. 6 to najciekawsza część.Niestety, większość książek podąża za tym samym wzorcem, po niesławnej książce o smokach, zwracając zbyt dużą uwagę na analizowanie i pozostawianie przekształceń kodu poza zakresem.