Jak napisać bardzo prosty kompilator

214

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 :-)

Googlebot
źródło
Próbowałeś już lex / flex i yacc / bison?
mouviciel
15
@mouviciel: To nie jest dobry sposób na naukę budowania kompilatora. Te narzędzia wykonują dla Ciebie znaczną część ciężkiej pracy, więc nigdy tak naprawdę nie robisz tego i nie uczysz się, jak to się robi.
Mason Wheeler,
11
@Mata co ciekawe, pierwszy z twoich linków daje 404, a drugi jest teraz oznaczony jako duplikat tego pytania.
Ruslan

Odpowiedzi:

326

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.

9000
źródło
45
To jedna z najlepszych odpowiedzi, jakie widziałem.
gahooa,
11
Myślę, że przeoczyłeś część pytania ... OP chciał napisać bardzo prosty kompilator. Myślę, że wychodzisz poza bardzo podstawowe.
marco-fiset,
22
@ marco-fiset , wręcz przeciwnie, uważam, że jest to wybitna odpowiedź, która mówi OP, jak zrobić bardzo prosty kompilator, wskazując pułapki, aby unikać i definiować bardziej zaawansowane fazy.
smci
6
To jedna z najlepszych odpowiedzi, jakie kiedykolwiek widziałem w całym świecie Stack Exchange. Sława!
Andre Terra,
3
Warto zobaczyć „Witaj świecie” z programu stworzonego przez kompilator. - INDEED
bardziej
27

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.

John R. Strohm
źródło
1
Jedną z miłych rzeczy w Pascalu jest to, że wszystko musi zostać zdefiniowane lub zadeklarowane przed użyciem. Dlatego można go skompilować w jednym przebiegu. Turbo Pascal 3.0 jest jednym z takich przykładów, a tam jest sporo dokumentacji na temat wewnętrznych tutaj .
tcrosley,
1
PASCAL został specjalnie zaprojektowany z myślą o kompilacji i łączeniu jednoprzebiegowym. Książka kompilatora Wirtha wspomina o kompilatorach wielościennych i dodaje, że wiedział o kompilatorze PL / I, który zajął 70 (tak, siedemdziesiąt) przejść.
John R. Strohm,
Obowiązkowa deklaracja przed użyciem pochodzi z ALGOL. Tony Hoare został przypięty do uszu przez komitet ALGOL, gdy próbował zasugerować dodanie domyślnych reguł typu, podobnych do tego, co miał FORTRAN. Wiedzieli już o problemach, jakie może to powodować, z błędami typograficznymi w nazwach i domyślnymi regułami tworzącymi ciekawe błędy.
John R. Strohm,
1
Oto bardziej zaktualizowana i ukończona wersja książki samego autora: stack.nl/~marcov/compiler.pdf Edytuj swoją odpowiedź i dodaj ją :)
sonnet
16

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.

Inżynier świata
źródło
7
Ale potem, gdy masz już gotowy kompilator BF, musisz napisać w nim swój kod :(
500 - Błąd wewnętrznego serwera
@ 500-InternalServerError użyj metody podzestawu C
Inżynier światowy
12

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ą.

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

Powodzenia!

Aniket Inge
źródło
7
Myślę, że celowanie w LLVM, a nie prawdziwy kod maszynowy, to najlepszy dostępny obecnie sposób.
9000
Zgadzam się, od jakiegoś czasu śledzę LLVM i powinienem powiedzieć, że była to jedna z najlepszych rzeczy, jakie widziałem od lat pod względem wysiłku programisty potrzebnego do jej ukierunkowania!
Aniket Inge
2
Co z MIPS i użyj spim, aby go uruchomić? Czy MIX ?
@MichaelT Nie korzystałem z MIPS, ale jestem pewien, że będzie dobrze.
Aniket Inge
@PrototypeStark Zestaw instrukcji RISC, rzeczywisty procesor, który jest nadal używany (zrozumienie, że będzie można go przetłumaczyć na systemy wbudowane). Pełny zestaw instrukcji znajduje się na wikipedii . Patrząc na sieć, istnieje wiele przykładów i jest ona wykorzystywana w wielu klasach akademickich jako cel programowania w języku maszynowym. W SO jest trochę aktywności .
10

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.

Zniszczyć
źródło
Siódmy punkt jest tym, o co prosi OP.
Florian Margaine,
7
1-5 są nieistotne i nie zasługują na tak ścisłą uwagę. 6 jest najbardziej interesującą częścią. Niestety, większość książek ma ten sam wzór, po niesławnej książce o smokach, zwracając zbyt dużą uwagę na parsowanie i pozostawienie kodu poza zakresem.
SK-logic,