Uruchamianie prostego (chyba najprostszego) kompilatora C?

Odradzam ten tutorial:

• LLVM tutorial

Jest to mały przykład jak zaimplementować kompilator "small language". Kod źródłowy jest bardzo mały i wyjaśniany krok po kroku.

Istnieje również biblioteka przednia C dla biblioteki LLVM (niskopoziomowej maszyny wirtualnej, która reprezentuje wewnętrzną strukturę programu):

• Clang

Jeśli to coś warte, Tiny C Compiler jest całkiem w pełni funkcjonalnym kompilatorem C w stosunkowo małym pakiecie źródłowym. Możesz czerpać korzyści ze studiowania tego źródła, ponieważ prawdopodobnie jest ono znacznie łatwiejsze do zrozumienia niż próba zrozumienia na przykład całej bazy źródłowej GCC.

To jest moje zdanie (i domysły) trudno będzie napisać kompilator bez zrozumienia struktur danych normalnie objętych na studiach licencjackich (policealnych) z informatyki. Nie oznacza to, że nie możesz, ale musisz znać podstawowe struktury danych, takie jak połączone listy i Drzewa.

Zamiast pisać pełny lub zgodny ze standardami kompilator języka C (przynajmniej na początku), sugerowałbym ograniczenie się do podstawowego podzbioru języka, takiego jak common operatory, obsługuje tylko integer oraz podstawowe funkcje i wskaźniki. Jednym z klasycznych przykładów tego był utwór Rona CainaSmall-C , który stał się popularny dzięki serii artykułów napisanych wDr. Dobbs Journal w I believe the 1980s. publikują oneCD z niewydrukowaną książką Jamesa Hendrixa, kompilatorem Small-C .

To, co sugerowałbym, to podążanie za samouczkiem Crenshawa, ale napisz go dla kompilatora języka podobnego do C i niezależnie od celu procesora (Crenshaw celuje w Motorolę 68000 CPU), które chcesz skierować. Aby to zrobić, musisz znać podstawowy zestaw, na którym docelowo chcesz uruchamiać skompilowane programy. Może to obejmować emulator dla 68000 lub MIPS, które są prawdopodobnie ładniejsze zestawów instrukcji montażu niż czcigodny zestaw instrukcji CISC Intela x86 (16/32-bit).

Istnieje wiele potencjalnych książek, które mogą być wykorzystane jako punkty wyjścia do nauki teorii kompilatora / tłumacza (i praktyki). Przeczytaj comp.Kompilatory FAQ, oraz recenzje w różnych księgarniach internetowych. Większość książek wprowadzających jest pisana jako podręczniki dla klas Drugoroczniaków i maturzystów, dzięki czemu mogą być powolnym czytaniem bez tła CS. Jedna starsza książka, która może być bardziej wprowadzająca, ale łatwiejsza do przeczytania niż "Księga Smoka" na Wprowadzenie do budowy kompilatora autor: Thomas Parsons. Jest starszy, więc powinieneś być w stanie znaleźć używaną kopię od wyboru internetowych sprzedawców książek w rozsądnej cenie.

Więc powiedziałbym, spróbuj zacząć od Jacka Crenshawa zbudujmy kompilator tutorial, napisz swój własny, podążając za jego przykładami jako przewodnik i zbuduj podstawy prostego kompilatora. Gdy już to działa, możesz lepiej zdecydować, gdzie chcesz go wziąć od tego momentu.

Dodano:

W odniesieniu do procesu bootstrapowania. Ponieważ istnieją istniejące kompilatory C dostępne, nie musisz się martwić o bootstrapping. Napisz swój kompilator z oddzielnymi, istniejącymi narzędziami( GCC, Visual C++ Express, MinGW / djgpp, tcc), a możesz się martwić o samodzielną kompilację projektu na znacznie późniejszym etapie. Byłem zaskoczony tą częścią pytania, dopóki nie zdałem sobie sprawy, że wpadłeś na pomysł napisania własnego kompilatora, czytając przemówienie Kena Thomasa z nagrodą Turinga ACM, Reflections on Trust Trust , które przechodzi w proces bootstrapowania kompilatora. On moderowany temat zaawansowany, a także po prostu dużo kłopotów. Uważam nawet bootstrapowanie kompilatora GCC C pod starszymi systemami Uniksowymi (Digital OSF/1 Na 64-bitowej Alfie), który zawierał kompilator C, za powolny i czasochłonny, podatny na błędy proces.

Innym rodzajem pytania było to, co tak naprawdę robi narzędzie kompilatora, takie jak Yacc. Yacc (Yet Another Compiler Compiler lub Bison z GNU) jest narzędziem zaprojektowanym w celu ułatwienia pisania parsera kompilatora (lub tłumacza). Na podstawie gramatyka formalna dla języka docelowego, który wprowadzasz do yacc, generuje parser , który jest częścią ogólnego projektu kompilatora. Następnie jest Lex (lub flex z GNU), który służy do generowania analizatora leksykalnego lub skanera, który jest często używany w połączeniu z parserem generowanym przez yacc, tworząc szkielet front-end kompilatora. Narzędzia te sprawiają, że writer jest prawdopodobnie łatwiejszy niż samodzielne pisanie analizatora leksykalnego i parsera. Crenshaw ' s tutorial nie używa tych narzędzi i Ty też nie musisz, wielu kompilatorów nie zawsze ich używa. Oczywiście Crenshaw przyznaje, że Parser tutoriala jest dość podstawowy.

Samouczek Crenshawa pomija również generowanie AST (abstrakcyjnego drzewa składniowego), co upraszcza, ale także ogranicza kompilator samouczka. Brakuje mu większości, jeśli nie całej optymalizacji i jest bardzo związany z konkretnym językiem programowania i konkretnym językiem asemblowania emitowanym przez" back-end " kompilatora. Normalnie AST jest środkowym elementem, w którym można przeprowadzić pewną optymalizację i służy do oddzielenia kompilatora front-end I back-end w projektowaniu. Dla początkującego bez wykształcenia informatycznego, sugerowałbym nie martwić się o brak AST dla pierwszego kompilatora (a przynajmniej jego pierwszej wersji). Myślę, że utrzymanie go w małej i prostej formie pomoże Ci skończyć pisanie kompilatora, w jego pierwszej wersji, i wtedy możesz zdecydować, jak chcesz postępować.

Jak [zacząć pisać] prosty kompilator C?

Nie ma nic prostego w kompilacji C . Najlepszym prostym kompilatorem C jest lcc {[8] } autorstwa Chrisa Frasera i Davida Hansona. Spędzili 10 lat pracując nad projektem, aby uczynić go tak prostym, jak to tylko możliwe, jednocześnie generując rozsądnie dobry kod. Jeśli masz dostęp do Biblioteki Uniwersyteckiej, powinieneś być w stanie uzyskać ich książkę.

Czy zacznę budować kompilator C w C czy jakiś inny język?

Jakiś inny język. Pewnego razu zapytałem Hansona, jakich lekcji nauczył się z Fraserem spędzając 10 lat nad projektem lcc. Najważniejsze było

C jest kiepskim językiem do pisania kompilatora.

Chcę przeczytać artykuł napisany w tym samym duchu, co ten, który wymieniłem powyżej, ale który podkreśla przynajmniej fazy bootstrapowania...

Nie znajdziesz innego artykułu jak Ken ' s. ale Andrew Appel napisał fajny artykuł o nazwieAxiomatic Bootstrapping: a Guide for Compiler Hackers nie mogłem znaleźć darmowej wersji, ale wiele osób ma dostęp do Biblioteki Cyfrowej ACM.

Jakieś sugestie?

Jeśli chcesz napisać kompilator,

• Użyj Haskell lub ML jako języka implementacji.

• Dla pierwszego kompilatora Wybierz bardzo prosty język jak Oberon lub jak P0 z książki Niklausa Wirthaalgorytmy + struktury danych = programy . Wirth jest znany z projektowania języków, które są łatwe do skompilowania.

Możesz napisać C kompilator dla twojegodrugiego kompilatora.

Może Cię zainteresować książka / kurs elementy systemów komputerowych: budowa nowoczesnego komputera od pierwszych zasad.

Zauważ, że nie chodzi o budowanie " pc " z rzeczy, które kupiłeś od newegga. Zaczyna się od opisu podstaw logiki logicznej i buduje wirtualny komputer od najniższych poziomów abstrakcji do stopniowo wyższych poziomów abstrakcji. Materiały szkoleniowe są dostępne online, a sama książka jest dość niedroga z Amazonii.

W trakcie, oprócz "budowania sprzętu", zaimplementujesz również asembler, maszynę wirtualną, kompilator i podstawowy system operacyjny, w sposób stopniowy. Myślę, że dałoby ci to wystarczająco dużo doświadczenia, aby zagłębić się głębiej w Temat z niektórymi bardziej zalecanymi zasobami wymienionymi w innych odpowiedziach.

W środowisku programowania Unix , Kernighan i Pike przechodzą przez 5 iteracji tworzenia kalkulatora działającego od prostej analizy leksykalnej opartej na C i natychmiastowego wykonania po parsowanie yacc/lex i generowanie kodu dla maszyny abstrakcyjnej. Ponieważ piszą tak cudownie, że nie mogę zasugerować płynniejszego wprowadzenia. Z pewnością jest mniejszy niż C, ale jest to prawdopodobnie na Twoją korzyść.

Kompilator jest złożonym przedmiotem, który obejmuje aspekty

• przetwarzanie danych wejściowych obejmujące Lexing, Parsing
• budowanie magazynu symboli dla każdej zmiennej używanej, np. abstrakcyjnego drzewa składniowego (Ast)
• z drzewa AST TRANSPONUJ i buduj binarny kod maszynowy oparty na składni

Nie jest to bynajmniej wyczerpujące, ponieważ jest to abstrakcyjny widok z lotu ptaka ze szczytu góry, sprowadza się do poprawienia zapisu składniowego i zapewnienia, że zniekształcone wejścia nie rzucają go, w rzeczywistości dobre przetwarzanie danych wejściowych nigdy nie powinno spaść na kolana, bez względu na to, jak zniekształcone, straszne, nadużywane przypadki wejścia, które zostanie rzucone na niego. A także decydując i wiedząc, jakie wyjście będzie, Jest to w kodzie maszynowym, co sugerowałoby, że być może będziesz musiał dokładnie poznać instrukcje procesora...w tym adresowanie pamięci dla zmiennych i tak dalej...

Oto kilka linków na początek:

• Był sobie Jack Crenshaw ' s port jego kodu Na C....(Przypominam sobie ściąganie go miesiące temu...)
• Oto link do podobnego pytania tutaj NA SO.
• ponadto, oto kolejny mały samouczek kompilatora dla kompilatora asemblera Basic do x86.
• Tiny C Compiler
• Mały kompilator C Hendrixa znalazł tutaj .

Warto też nauczyć się programowania funkcyjnego. Języki funkcyjne dobrze nadają się do pisania kompilatora zarówno w, jak i dla . Moja szkolna Klasa kompilatorów intro zawierała intro do języków funkcyjnych, a zadania były w OCaml.

Zabawne, że dziś o to pytasz, bo kilka dni temu napisałem interpreter rachunku lambda. Rachunek Lambda jest odpowiednikiem wszystkich języków funkcyjnych. To tylko 200 linijek (w C++, incl. raportowanie błędów, trochę ładnego drukowania, trochę unicode) i ma strukturę dwufazową, z formatem pośrednim, który mógłby być użyty do generowania kodu.

Nie tylko zaczyna od małych i buduje najbardziej praktyczne podejście do kompilatorów, ale także zachęca do dobrych, modułowych, organizacyjnych praktyk.

Kompilator jest bardzo dużym projektem, chociaż przypuszczam, że nie zaszkodzi spróbować.

Znam przynajmniej jeden kompilator C napisany w Pascalu, więc nie jest to najbardziej szalona rzecz, jaką można zrobić. Osobiście wybrałbym bardziej nowoczesny język, w którym zaimplementuje mój projekt kompilatora C, zarówno dla prostoty (łatwo jest d/L pakietów dla Pythona, Ruby, C, C++ lub Java), jak i dlatego, że będzie wyglądał lepiej w Twoim CV.

Aby zrobić kompilator jako początkujący projekt, jednak trzeba będzie wypić wszystkie Agile kool-aid .

Jeśli chcesz mieć oszałamiające doświadczenie, które nauczy Cię pisać Kompilatory, które kompilują się same, musisz przeczytać ten artykuł z 1964.

META II zorientowany na składnię kompilator języka pisania autorstwa Val Schorre.

Na 10 stronach mówi, jak pisać Kompilatory, jak pisać meta Kompilatory, dostarcza wirtualny zestaw instrukcji metacompilera i przykładowy kompilator zbudowany z metacompilera.

Nauczyłem się pisać Kompilatory z tego paper pod koniec lat 60-tych i wykorzystywał pomysły do konstruowania C-podobnych langauges dla kilku minikomputerów i mikroprocesorów.

Jeśli papier jest zbyt duży sam w sobie (nie jest!) jest internetowy samouczek , który przeprowadzi Cię przez całą sprawę.

A jeśli uzyskanie papieru z oryginalnego linku jest niezręczne, ponieważ nie jesteś członkiem ACM, przekonasz się, że samouczek zawiera wszystkie szczegóły i tak. (IMHO, za tą cenę sam papier jest waaaaay wart it).

10 strony!

Nie polecam zaczynać od C jako języka do implementacji, ani od żadnego z narzędzi generatora kompilatora lub parsera. C jest bardzo skomplikowanym językiem i prawdopodobnie lepszym pomysłem jest stworzenie własnego języka. Może być trochę podobny do C (np. użyj kręconych backetów jeśli chcesz wskazać ciało funkcji, Użyj tych samych nazw typów, więc nie musisz pamiętać, jak wszystko nazwałeś).

Narzędzia do tworzenia kompilatorów i parserów są świetne, ale mają problem bycia zapisem stenograficznym. Jeśli nie wiesz, jak utworzyć kompilator w longhand, skrót będzie wydawał się tajemniczy, niepotrzebnie restrykcyjny itp. Więc najpierw napisz swój własny prosty kompilator, a potem kontynuuj. Zalecam również, aby nie zacząć generować rzeczywistego kodu maszynowego, chyba że jesz i oddychasz asemblerem. Utwórz własny interpreter kodu bajtowego za pomocą maszyny wirtualnej.

Co do tego, jakiego języka należy użyć do stworzenia pierwszego kompilatora: to naprawdę nie ma znaczenia, o ile język jest dość kompletny. Będziesz czytał tekst wejściowy, budował z nich struktury danych i zapisywał dane binarne. Więc jeśli język ułatwia te rzeczy w jakikolwiek sposób, to jest punkt na korzyść tego. Wybierz język, który dobrze znasz, więc możesz skupić się na tworzeniu kompilatora, a nie na nauce języka. Zwykle używam języka OO, co ułatwia pisanie drzewa składni, język funkcjonalny prawdopodobnie też by zadziałał, gdybyś był z tym zaznajomiony.

Dużo blogowałem o językach programowania, więc możesz znaleźć kilka przydatnych postów tutaj: http://orangejuiceliberationfront.com/category/language-design/

W szczególności http://orangejuiceliberationfront.com/how-to-write-a-compiler/{[8] } jest przystawką do analizowania wspólnych konstrukcji i generowania z nich czegoś użytecznego, a także http://orangejuiceliberationfront.com/generating-machine-code-at-runtime / który mówi o wypluwaniu Intela instrukcje, które coś robią.

Oh, jeśli chodzi o bootstrapowanie kompilatora: prawdopodobnie nie będziesz w stanie tego zrobić od samego początku. Tworzenie kompilatora wymaga sporo pracy. Więc nie tylko pisanie kompilatora bootstrapującego wymaga napisania kompilatora (w innym języku), ale gdy już go posiadasz, będziesz musiał napisać drugą wersję kompilatora używając samego siebie. To dwa razy więcej pracy, Plus debugowanie potrzebne w istniejących i bootstrapped nowy kompilator, dopóki wszystko nie zadziała. To powiedziawszy, gdy już masz działający kompilator, jest to dobry sposób na sprawdzenie jego kompletności. OK, może nie dwa razy więcej pracy, ale więcej pracy. Najpierw stawiałbym na łatwe sukcesy, a potem ruszyłbym dalej.

W każdym razie, baw się dobrze!