Bootstrapping все еще требует внешней поддержки

Есть ли способ на самом деле написать компилятор на своем собственном языке?

Вы должны иметь какой-то существующий язык, чтобы написать свой новый компилятор. Если бы вы писали новый, скажем, компилятор C++, (C++ online compiler)вы бы просто написали его в C++ и скомпилировали его сначала с существующим компилятором. С другой стороны, если бы вы создавали компилятор для нового языка, назовем его Yazzleof, вам нужно было бы сначала написать новый компилятор на другом языке. Как правило, это был бы другой язык программирования, но это не обязательно. Это может быть assembly или, если необходимо, машинный код.

Если бы вы собирались запустить компилятор для Yazzleof, вы бы вообще не писали компилятор для полного языка изначально. Вместо этого вы бы написали компилятор для Yazzle-lite, самого маленького возможного подмножества Yazzleof (ну, по крайней мере, довольно маленького подмножества). Затем в Yazzle-lite вы бы написали компилятор для полного языка. (Очевидно, что это может происходить итеративно, а не за один прыжок.) Поскольку Yazzle-lite является правильным подмножеством Yazzleof, теперь у вас есть компилятор, который может компилировать сам себя.

Есть очень хорошая запись о bootstrapping компиляторе с самого низкого возможного уровня (который на современной машине в основном является редактором hex), под названием Bootstrapping простой компилятор из ничего . Его можно найти по адресу https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

Объяснение, которое вы прочли, совершенно верно. Это обсуждается в книге " компиляторы: принципы, методы и инструменты " (The Dragon Book):

• Напишите компилятор C1 для языка X в языке Y
• Используйте компилятор С1 С2 написать компилятор для языка X на язык х
• Теперь C2-это полностью автономная среда хостинга.

Очень интересное обсуждение этого вопроса содержится в лекции Unix соавтора Кена Томпсона " премия Тьюринга ".

Он начинает с того, что:

То, что я собираюсь описать, является одной из многих проблем "chicken and egg", которые возникают, когда компиляторы пишутся на своем собственном языке. В этой простоте я буду использовать конкретный пример из компилятора C.

и далее мы покажем, как он написал версию компилятора Unix C, которая всегда позволяла ему входить в систему без пароля, потому что компилятор C распознал бы программу входа и добавил бы специальный код.

Второй паттерн направлен на компилятор C. Код замены - это самовоспроизводящаяся программа этапа I, которая вставляет в компилятор обоих троянских коней. Это требует этапа обучения, как в Примере Stage II. Сначала мы компилируем модифицированный исходный код с помощью обычного компилятора C, чтобы создать прослушиваемый двоичный файл. Мы устанавливаем этот двоичный файл как официальный C. Теперь мы можем удалить ошибки из исходного кода компилятора, и новый двоичный файл будет повторно вставлять ошибки всякий раз, когда он будет скомпилирован. Конечно, команда входа в систему останется прослушиваемой без trace в исходном коде в любом месте.

Способ, о котором я слышал, заключается в том, чтобы написать чрезвычайно ограниченный компилятор на другом языке, а затем использовать его для компиляции более сложной версии, написанной на новом языке. Затем эта вторая версия может быть использована для компиляции самой себя и следующей версии. Каждый раз, когда он компилируется, используется последняя версия.

Это и есть определение bootstrapping:

процесс простой системы активирует более сложную систему, которая служит той же цели.

EDIT: статья Википедии о компиляторе bootstrapping охватывает эту концепцию лучше, чем я.

Проверьте подкаст Software Engineering Radio episode 61 (2007-07-06), в котором обсуждаются внутренние компоненты компилятора GCC, а также процесс GCC bootstrapping.

Дональд Э. кнут фактически построил WEB , написав в нем компилятор, а затем вручную скомпилировал его в assembly или машинный код.

Насколько я понимаю, первый интерпретатор Lisp был загружен вручную-компиляцией функций конструктора и считывателем токенов. Затем rest переводчика было зачитано из источника.

Вы можете проверить это сами, прочитав оригинальную статью McCarthy, рекурсивные функции символьных выражений и их вычисление машиной, Часть I.

Каждый пример bootstrapping языка, который я могу придумать ( C , PyPy), был сделан после того, как появился рабочий компилятор. Вы должны с чего-то начать, а для того, чтобы реимплировать язык сам по себе, сначала нужно написать компилятор на другом языке.

А как еще это могло бы сработать? Я не думаю, что это даже концептуально возможно сделать иначе.

Это компьютерная версия парадокса chicken-and-egg. Я не могу придумать способ не писать исходный компилятор на ассемблере или каком-то другом языке. Если бы это можно было сделать, я бы это сделал.

На самом деле, я думаю, что Lisp почти соответствует требованиям. Проверьте его запись в Википедии . Согласно статье, функция Lisp eval может быть реализована на IBM 704 в машинном коде, а полный компилятор (написанный на самом Lisp) появится в 1962 году на MIT .

Другой альтернативой является создание машины байт - кода для вашего языка (или использование существующей машины, если ее функции не очень необычны) и написание компилятора для байт-кода, либо в байт-коде, либо на желаемом языке с использованием другого промежуточного средства-например, инструментария синтаксического анализа, который выводит AST как XML, а затем компилирует XML в байт-код, используя XSLT (или другой язык сопоставления шаблонов и древовидное представление). Это не устраняет зависимость от другого языка, но может означать, что большая часть работы bootstrapping заканчивается в конечной системе.

Некоторые загрузочные компиляторы или системы хранят исходную форму и форму объекта в своем репозитории:

• ocaml -это язык, который имеет как интерпретатор байт-кода (т. е. компилятор для байт-кода Ocaml), так и собственный компилятор (для x86-64 или ARM и т. д... ассемблер). Его репозиторий svn содержит как исходный код (файлы */*.{ml,mli}), так и байт-код (файл boot/ocamlc ) компилятора. Поэтому при сборке он сначала использует свой байт-код (предыдущей версии компилятора) для компиляции самого себя. Позже только что скомпилированный байт-код может скомпилировать собственный компилятор. Таким образом, репозиторий Ocaml svn содержит как исходные файлы *.ml[i] , так и файл байт-кода boot/ocamlc .

• Компилятор rust загружает (используя wget , поэтому вам нужно рабочее подключение к интернету) предыдущую версию своего двоичного файла для компиляции.

• MELT -это Lisp-подобный язык для настройки и расширения GCC . Он переводится в код C++ с помощью загрузочного переводчика. Сгенерированный код C++ транслятора распределен, поэтому репозиторий svn содержит как исходные файлы *.melt , так и файлы melt/generated/*.cc "object" транслятора.

• J.Pitrat's CAIA система искусственного интеллекта полностью самогенерируется. Он доступен в виде коллекции из тысяч [A-Z]*.c сгенерированных файлов (также сгенерированным dx.h заголовочным файлом) с коллекцией из тысяч _[0-9]* файлов данных.

• Несколько компиляторов Схем также являются загрузочными. Scheme48, Схема Курица ...