Słyszałem o pomyśle bootstrapowania języka, czyli napisania kompilatora / interpretera dla samego języka. Zastanawiałem się, jak można to osiągnąć i rozejrzałem się trochę dookoła i zobaczyłem, że ktoś powiedział, że można to zrobić tylko
- napisanie początkowego kompilatora w innym języku.
- ręczne kodowanie początkowego kompilatora w asemblerze, co wydaje się być specjalnym przypadkiem pierwszego
Wydaje mi się, że żaden z nich nie wydaje się w rzeczywistości ładować języka w tym sensie, że oba wymagają zewnętrznego wsparcia. Czy istnieje sposób na napisanie kompilatora w swoim własnym języku?
Odpowiedzi:
Ci mają mieć jakiś istniejący język do pisania nowego kompilatora. Jeśli chcesz napisać nową, powiedzmy, kompilator C ++, to po prostu napisać w C ++ i skompilować go z istniejącym kompilatora pierwszy. Z drugiej strony, gdybyś tworzył kompilator dla nowego języka, nazwijmy go Yazzleof, musiałbyś najpierw napisać nowy kompilator w innym języku. Generalnie byłby to inny język programowania, ale nie musi. Może to być kod montażowy lub w razie potrzeby kod maszynowy.
Gdybyś miał załadować kompilator dla Yazzleof, generalnie nie napisałbyś początkowo kompilatora dla pełnego języka. Zamiast tego napisałbyś kompilator dla Yazzle-lite, najmniejszego możliwego podzbioru Yazzleof (cóż, przynajmniej całkiem małego podzbioru). Następnie w Yazzle-lite napisałbyś kompilator dla pełnego języka. (Oczywiście może to nastąpić iteracyjnie zamiast w jednym skoku). Ponieważ Yazzle-lite jest właściwym podzbiorem Yazzleof, masz teraz kompilator, który może się skompilować.
Jest naprawdę dobry artykuł o ładowaniu kompilatora z najniższego możliwego poziomu (który na nowoczesnej maszynie jest w zasadzie edytorem szesnastkowym), zatytułowany Bootstrapping a simple compiler from none . Można go znaleźć pod adresem https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .
źródło
Wyjaśnienie, które przeczytałeś, jest poprawne. Jest to omówione w Compilers: Principles, Techniques, and Tools (Dragon Book):
źródło
Super ciekawe omówienie to jest w Unix współtwórcą Ken Thompson „s Nagroda Turinga wykładu.
Zaczyna od:
i pokazuje, jak napisał wersję kompilatora Unix C, która zawsze pozwalała mu logować się bez hasła, ponieważ kompilator C rozpoznałby program logowania i dodałby specjalny kod.
źródło
Słyszałem o napisaniu bardzo ograniczonego kompilatora w innym języku, a następnie użycie go do skompilowania bardziej skomplikowanej wersji, napisanej w nowym języku. Ta druga wersja może następnie zostać użyta do skompilowania siebie i następnej wersji. Za każdym razem, gdy jest kompilowany, używana jest ostatnia wersja.
Oto definicja ładowania początkowego:
EDYCJA: artykuł Wikipedii o ładowaniu kompilatora lepiej niż ja opisuje tę koncepcję.
źródło
Sprawdź podcast Software Engineering Radio, odcinek 61 (2007-07-06), w którym omówiono wewnętrzne funkcje kompilatora GCC, a także proces ładowania GCC.
źródło
Donald E. Knuth faktycznie zbudował WEB , pisząc w nim kompilator, a następnie ręcznie skompilował go do asemblera lub kodu maszynowego.
źródło
Jak rozumiem, pierwszy interpreter Lisp został załadowany przez ręczne skompilowanie funkcji konstruktora i czytnika tokenów. Reszta tłumacza została następnie odczytana ze źródła.
Można to sprawdzić na własne oczy czytając oryginalnego papieru McCarthy rekurencyjnych funkcji symbolicznych wyrażeniach i obliczeniach przez maszyny, część I .
źródło
Inną alternatywą jest utworzenie maszyny z kodem bajtowym dla swojego języka (lub użycie istniejącego, jeśli jego funkcje nie są zbyt niezwykłe) i napisanie kompilatora do kodu bajtowego, albo w kodzie bajtowym, albo w wybranym języku przy użyciu innego języka pośredniego - takiego jak parser toolkit, który wyprowadza AST jako XML, a następnie skompiluj XML do kodu bajtowego za pomocą XSLT (lub innego języka dopasowywania wzorców i reprezentacji opartej na drzewie). Nie usuwa zależności od innego języka, ale może oznaczać, że więcej pracy związanej z ładowaniem początkowym kończy się w ostatecznym systemie.
źródło
To komputerowa wersja paradoksu jajka i kury. Nie mogę wymyślić sposobu, aby nie napisać początkowego kompilatora w asemblerze lub innym języku. Gdyby można było to zrobić, powinienem zrobić to Lisp.
Właściwie myślę, że Lisp prawie się kwalifikuje. Sprawdź jego wpis w Wikipedii . Zgodnie z artykułem, funkcja eval Lispa mogłaby zostać zaimplementowana na IBM 704 w kodzie maszynowym, a kompletny kompilator (napisany w samym Lispie) powstał w 1962 roku w MIT .
źródło
Każdy przykład ładowania języka , jaki przychodzi mi do głowy ( C , PyPy ), został wykonany po tym, jak działał kompilator. Musisz gdzieś zacząć, a ponowne zaimplementowanie samego języka wymaga najpierw napisania kompilatora w innym języku.
Jak inaczej by to działało? Nie sądzę, żeby było nawet koncepcyjnie możliwe, aby postąpić inaczej.
źródło
Niektóre bootstrapowane kompilatory lub systemy przechowują zarówno formę źródłową, jak i formę obiektową w swoim repozytorium:
ocaml to język, który ma zarówno interpreter kodu bajtowego (tj. kompilator kodu bajtowego Ocaml), jak i natywny kompilator (do x86-64 lub ARM, itp ... asembler). Jego repozytorium svn zawiera zarówno kod źródłowy (pliki
*/*.{ml,mli}
), jak iboot/ocamlc
postać kodu bajtowego (plik ) kompilatora. Więc kiedy budujesz, najpierw używa swojego kodu bajtowego (poprzedniej wersji kompilatora) do kompilacji. Później świeżo skompilowany kod bajtowy jest w stanie skompilować natywny kompilator. Zatem repozytorium Ocaml svn zawiera zarówno*.ml[i]
pliki źródłowe, jak iboot/ocamlc
plik kodu bajtowego.W rdza pliki do pobrania (za pomocą kompilatora
wget
, więc trzeba połączenia internetowego roboczy) poprzednią wersję swojego binarnego skompilować sobie.MELT to język podobny do Lispa do dostosowywania i rozszerzania GCC . Jest tłumaczony na kod C ++ przez bootstrapowanego translatora. Wygenerowany kod C ++ translatora jest dystrybuowany, więc repozytorium svn zawiera zarówno
*.melt
pliki źródłowe, jak i plikimelt/generated/*.cc
„obiektowe” translatora.System sztucznej inteligencji CAIA firmy J.Pitrat jest całkowicie samoczynny. Jest dostępny jako zbiór tysięcy
[A-Z]*.c
wygenerowanych plików (także z wygenerowanymdx.h
plikiem nagłówkowym) z kolekcją tysięcy_[0-9]*
plików danych.Kilka kompilatorów Scheme jest również uruchomionych. Schemat 48, program dotyczący kurczaków, ...
źródło