Для начальной загрузки по-прежнему требуется внешняя поддержка

Question

Я слышал об идее начальной загрузки языка, то есть написания компилятора / интерпретатора для самого языка.Мне было интересно, как этого можно достичь, и я немного огляделся, и увидел, как кто-то сказал, что это может быть сделано только одним из двух

• написание начального компилятора на другом языке.
• ручное кодирование начального компилятора на ассемблере, что кажется частным случаем первого

Мне кажется, что ни то, ни другое на самом деле не является начальная загрузка язык в том смысле, что они оба требуют поддержки извне.Есть ли способ на самом деле написать компилятор на его собственном языке?

Answer 1

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

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

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

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

Answer 2

Объяснение, которое вы прочитали, является правильным.Об этом есть обсуждение в Компиляторы:Принципы, Методы и инструменты (книга Дракона):

• Напишите компилятор C1 для языка X на языке Y
• Используйте компилятор C1, чтобы написать компилятор C2 для языка X на языке X
• Теперь C2 - это полностью автономная среда размещения.

Answer 3

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

Он начинает с:

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

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

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

Answer 4

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

Это определение начальная загрузка:

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

Редактировать:Тот Самый Статья в Википедии о начальной загрузке компилятора описывает концепцию лучше, чем я.

Answer 5

Посмотрите подкаст Программная инженерия Радио эпизод 61 (2007-07-06), в котором обсуждаются внутренние компоненты компилятора GCC, а также процесс начальной загрузки GCC.

Answer 6

Дональд Э.Кнут фактически построенный ПАУТИНА написав в нем компилятор, а затем вручную скомпилировав его в ассемблер или машинный код.

Answer 7

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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

Answer 11

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

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

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

• РАСПЛАВИТЬ это лиспоподобный язык для настройки и расширения ССАГПЗ.Он переведен в код C ++ с помощью загрузочного транслятора.Сгенерированный C++-код транслятора распространяется, поэтому репозиторий svn содержит оба *.melt исходные файлы и melt/generated/*.cc "объектные" файлы транслятора.

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

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