Pisanie kompilatora we własnym języku

Przypominam sobie słuchanie Software Engineering Radio podcast , w którym Dick Gabriel mówił o bootstrapowaniu oryginalnego interpretera Lispu przez napisanie wersji gołej kości w Lispie na papierze i ręcznym złożeniu go w kod maszynowy. Od tego czasu pozostałe funkcje Lispu były zarówno pisane, jak i interpretowane za pomocą Lispu.

Dodanie ciekawostki do poprzednich odpowiedzi.

Oto cytat z podręcznika Linux od podstaw , na etapie, w którym zaczyna się budować kompilator GCC z jego źródła. (Linux From Scratch to sposób instalacji Linuksa, który różni się radykalnie od instalacji dystrybucji, ponieważ musisz skompilować naprawdę każdy pojedynczy binarny system docelowy.)

make bootstrap

Cel 'bootstrap' nie tylko kompiluje GCC, ale kompiluje go kilka razy. Wykorzystuje programy skompilowane w pierwszej rundzie po raz drugi i po raz trzeci. Następnie porównuje te drugie i trzecie kompiluje, aby upewnić się, że może odtworzyć się bezbłędnie. Oznacza to również, że został poprawnie skompilowany.

To użycie celu "bootstrap" jest motywowane faktem, że kompilator, którego używa się do budowania systemu docelowego, może nie mieć tej samej wersji kompilatora docelowego. Postępowanie w ten sposób można na pewno uzyskać, w systemie docelowym, kompilator, który może się skompilować.

Kiedy piszesz swój pierwszy kompilator dla C, piszesz go w innym języku. Masz kompilator C w asemblerze. W końcu dojdziesz do miejsca, w którym będziesz musiał parsować ciągi, w szczególności sekwencje escape. Napiszesz kod, aby przekonwertować \n na znak z kodem dziesiętnym 10 (i {[4] } na 13, itd.).

Gdy kompilator będzie gotowy, zaczniesz go ponownie implementować w C. proces ten nazywa się"bootstrapping".

The string parsowanie kodu stanie się:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Kiedy to kompiluje, masz binarny, który rozumie "\n". Oznacza to, że możesz zmienić kod źródłowy:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Więc gdzie jest informacja, że "\n " jest kodem dla 13? Jest w pliku binarnym! To tak jak DNA: kompilacja kodu źródłowego C z tym kodem binarnym dziedziczy te informacje. Jeśli kompilator sam się skompiluje, przekaże tę wiedzę potomstwu. Od tego momentu, nie ma sposobu, aby zobaczyć z samego źródła, co kompilator zrobi się.

Jeśli chcesz ukryć wirusa w źródle jakiegoś programu, możesz to zrobić w następujący sposób: Pobierz źródło kompilatora, Znajdź funkcję, która kompiluje funkcje i zastąp ją tą:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Interesujące części to A i B. A to kod źródłowy compileFunction łącznie z wirusem, prawdopodobnie zaszyfrowany w jakiś sposób, więc nie jest to oczywiste z przeszukiwania wynikowego pliku binarnego. Daje to pewność, że kompilowanie do kompilatora z samym sobą zachowa zastrzyk wirusa kod.

B jest taka sama dla funkcji, którą chcemy zastąpić naszym wirusem. Na przykład może to być funkcja " login "w pliku źródłowym" login.c", który prawdopodobnie pochodzi z jądra Linuksa. Możemy zastąpić go wersją, która będzie akceptować hasło "joshua" dla konta root oprócz normalnego hasła.

Jeśli skompilujesz to i rozpowszechnisz jako plik binarny, nie będzie możliwości znalezienia wirusa patrząc na źródło.

Oryginalne źródło pomysłu: http://cm.bell-labs.com/who/ken/trust.html

Nie możesz napisać kompilatora samego w sobie, ponieważ nie masz nic do skompilowania początkowego kodu źródłowego. Istnieją dwa podejścia do rozwiązania tego problemu.

Najmniej korzystne jest następujące. Piszesz minimalny kompilator w asemblerze (yuck) dla minimalnego zestawu języka, a następnie używasz tego kompilatora do implementacji dodatkowych funkcji języka. Budując swoją drogę do uzyskania kompilatora ze wszystkimi funkcjami języka dla siebie. Bolesny proces, który zwykle odbywa się tylko wtedy, gdy nie masz innego wyboru.

Preferowanym podejściem jest użycie kompilatora krzyżowego. Zmieniasz tylny koniec istniejącego kompilatora na innej maszynie, aby utworzyć wyjście, które działa na maszynie docelowej. Następnie masz ładny pełny kompilator i pracujesz na docelowej maszynie. Najbardziej popularny jest język C, ponieważ istnieje wiele istniejących kompilatorów, które mają wtykowe końcówki, które można wymienić.

Mało znanym faktem jest to, że kompilator GNU C++ ma implementacja wykorzystująca tylko podzbiór C. Powodem jest zwykle Ĺ 'atwo znaleĹşÄ ‡ kompilator C dla nowej docelowej maszyny, ktĂłry pozwala na zbudowanie z niego peĹ' nego kompilatora GNU C++. Masz teraz boot przywiązany do posiadania kompilatora C++ na komputerze docelowym.

Ogólnie rzecz biorąc, najpierw musisz mieć działające (jeśli pierwotne) cięcie kompilatora - wtedy możesz zacząć myśleć o zrobieniu z niego samodzielnego hostingu. Jest to w rzeczywistości uważane za ważny kamień milowy w niektórych langauges.

Z tego, co pamiętam z "mono", jest prawdopodobne, że będą musieli dodać kilka rzeczy do refleksji, aby to działało: zespół mono ciągle wskazuje, że niektóre rzeczy po prostu nie są możliwe z Reflection.Emit; oczywiście zespół MS może udowodnić, że się mylą.

To ma kilkaprawdziwych zalet: jest to dość dobry test jednostkowy, na początek! I masz tylko jeden język do zmartwień (tzn. jest możliwe, że ekspert C# może nie znać zbyt wiele C++; ale teraz możesz naprawić kompilator C#). Ale zastanawiam się, czy nie ma tu dumy zawodowej: po prostu chcą , aby to był własny hosting.

Nie do końca kompilator, ale ostatnio pracowałem nad systemem, który jest sam hosting; generator kodu służy do generowania kodu generator... więc jeśli schemat zmienia się po prostu uruchomić go na sobie: nowa wersja. Jeśli jest błąd, po prostu wrócić do wcześniejszej wersji i spróbować ponownie. Bardzo wygodny i bardzo łatwy w utrzymaniu.

Update 1

Właśnie obejrzałem ten filmik Andersa w PDC i (około godziny) podaje kilka ważniejszych powodów - wszystko o kompilatorze jako usłudze. Tak dla jasności.

W teorii kompilatorów można użyć T-diagramów do opisania procesu bootstrapowania. Na przykład zobacz TUTAJ .

W mojej pracy licencjackiej wykorzystałem te T-diagramy do opisania procesu konwersji i pokazywania dokumentów podczas przechowywania dużych ilości dokumentów elektronicznych w różnych formatach z różnych platform.

Oto śmietnik (trudny temat do przeszukiwania):

• Smalltalk

• C

Jest to również idea PyPy i Rubinius :

(myślę, że może to dotyczyć również Forth , ale nic nie wiem o Forth.)

GNAT, kompilator GNU Ada, wymaga kompilatora Ada do pełnego zbudowania. Może to być bolesne przy przenoszeniu go na platformę, na której nie ma łatwo dostępnych binarnych GNAT.

Właściwie, większość kompilatorów jest napisana w języku, który kompilują, z powodów podanych powyżej.

Pierwszy kompilator bootstrap jest zwykle napisany w języku C, C++ lub Assembly.

Kompilator C# projektu Mono jest "samo-hostowany" przez długi czas, co oznacza, że został napisany w samym C#.

Wiem, że kompilator został uruchomiony jako czysty kod C, ale po zaimplementowaniu "podstawowych" funkcji ECMA zaczęli przepisywać kompilator w C#.

Nie jestem świadomy zalet pisania kompilatora w tym samym języku, ale jestem pewien, że ma to związek przynajmniej z funkcjami, które sam język może zaoferować (C, dla przykład, nie obsługuje programowania obiektowego).

Więcej informacji znajdziesz tutaj .

Może mógłbyś napisać BNF opisujący BNF.