WikiSort.ru - Не сортированное

Раскрутка компилятора (англ. bootstrapping — от boot и strap) — метод создания транслятора^[1] для некоторого языка программирования, при котором транслятор пишется на том же языке программирования, для трансляции которого создаётся; создание транслятором исполняемых файлов из исходного кода самого транслятора. Используется для переноса трансляторов на новые платформы. Появился в середине 1950-х годов. Позволяет создать транслятор, который генерирует сам себя. Применялся для создания трансляторов многих языков программирования, включая языки «Бейсик», «Алгол», «Си», «Паскаль», «ПЛ/1», Factor, Haskell, «Модула-2», «Оберон», OCaml, Common Lisp, Scheme, Java, Python, Scala, Nemerle и другие.

Проблема курицы и яйца

Пусть создан новый язык программирования L. Пусть на языке L составлен исходный код транслятора для языка L. Как получить транслятор, способный из этого кода создать исполняемый файл?

Методы решения проблемы перечислены ниже.

• Автор языка L может вручную выполнить трансляцию исходного кода с языка L на машинный язык или на язык ассемблера. Затем можно выполнить полученный код для создания исполняемого файла компилятора. Так поступили Никлаус Вирт с учениками при создании первого компилятора для языка «Паскаль», а также Дональд Кнут при создании своей системы грамотного программирования WEB^[en].

• Автор языка L может составить исходный код транслятора на языке, для которого уже существует транслятор. Попытку такого рода (впрочем, неудачную) предпринимал Никлаус Вирт при создании первого компилятора для языка «Паскаль» на языке «Фортран».

• То же, но автор языка L сам не составляет исходный код, а поручает эту операцию другому лицу. Такой способ часто применяется при создании трансляторов для языка Scheme.

• Первая версия компилятора может быть написана на подмножестве языка L, для которого уже существует некий другой компилятор. Таким способом были получены компиляторы для подмножества языков Java, Haskell и Free Pascal.

• Создать транслятор для новой платформы можно путём кросс-компиляции — создания исполняемого файла транслятора для новой платформы на платформе, для которой транслятор уже существует. Таким способом обычно портируются компиляторы, написанные на языках C и Free Pascal.

Раскрутка компилятора с использованием компилятора существующего языка

Создание транслятора языка L методом раскрутки подразумевает выполнение некоторых шагов.

1. На первом шаге из языка L выделяется подмножество L₀, которое не требует больших усилий для реализации, но является достаточным для написания транслятора самого себя. Затем, используя какой-либо существующий для этой платформы язык (например, C), составляется исходный код транслятора для L₀.
2. Затем на языке L₀ составляется транслятор для самого языка L₀. Исполняемый файл транслятора создаётся с помощью транслятора, полученного на первом шаге. После этого у программиста имеется транслятор L₀, способный обработать свой исходный код.
3. Далее начинается постепенное расширение L₀ до L: добавляется какая-либо ранее не реализованная возможность языка L, после чего предыдущей версией транслятора создаётся новая, а вновь добавленную возможность можно использовать в трансляторе для последующего расширения языка.

Именно этот процесс и называют раскруткой.

Число шагов можно уменьшить, если после составления транслятора L₀ на языке С сразу начинать составлять транслятор L на подмножестве L₀.

Преимущества

Достоинства метода раскрутки^[2]:

• проверка возможностей языка L;
• отсутствие необходимости изучения других языков (порою разработчику достаточно знать только язык L);
• возможность дальнейшего улучшения транслятора на языке высокого уровня L;
• постоянное улучшение качества кода (улучшение кода транслятора приводит к улучшению качества кода всех программ, создаваемых транслятором, включая сам транслятор);
• всесторонняя проверка транслятора на непротиворечивость (транслятор должен быть способен воспроизвести свой собственный код).

Недостатки

При создании новых языков программирования использование уже существующих языков может быть вполне оправданным по следующим причинам^[3]:

• компиляторы уже существующих языков, как правило, надёжны (отлажены, изучены, стабильны);
• для уже существующих языков имеются отладчики, статические анализаторы и другие инструменты;
• невозможность использования генераторов синтаксических анализаторов;
• использование интерпретатора для самоинтерпретации нового языка может отрицательно сказаться на скорости: старый интерпретатор интерпретирует код нового интерпретатора, который интерпретирует код сценария пользователя (двойная интерпретация)^[4].

История

Ассемблеры были первыми компиляторами, способными компилировать сами себя методом раскрутки.

Neliac^[en] — диалект языка «Алгол 58» и одноимённый компилятор, разработанные в 1958 году; первый язык высокого уровня, для которого был использован метод раскрутки.

Первыми широко используемыми языками, которые были раскручены тем же способом, стали:

• Burroughs B5000^[en] («Алгол 60») в 1961 году;
• «Лисп» в 1962 году.

В 1962 году Тим Харт (англ. Tim Hart) и Марк Левин (Mark Levin) в Массачусетском технологическом институте написали первый компилятор «Лиспа» на языке Lisp^[5] и проверили его на уже существующем интерпретаторе языка Lisp. Они перешли на него, как только разработанный ими компилятор смог откомпилировать свой собственный исходный код.

В СССР метод раскрутки использовался для создания компиляторов РЕФАЛ, «Сигма» и «Эпсилон».

Список языков, имеющих самокомпилирующиеся компиляторы

Список примеров в этом разделе не основывается на авторитетных источниках, посвящённых непосредственно предмету статьи или её раздела. Добавьте ссылки на источники, предметом рассмотрения которых является тема настоящей статьи (или раздела) в целом, а не отдельные элементы списка. В противном случае раздел может быть удалён.

• «Бейсик»
• «Алгол»
• C
• C++
• Common Lisp
• Eiffel
• F Sharp
• Factor
• Haskell
• Go
• Java
• Mercury
• «Модула-2»
• Nemerle
• Oberon
• OCaml
• «Паскаль»
• Perl 6
• «ПЛ/1»
• Python
• Rust
• Scheme
• Scala
• Standard ML

• TypeScript
• XPL
• РЕФАЛ
• «Сигма»^[7]
• «Эпсилон»^[8]

Примечания

Литература

• Альфред Ахо, Рави Сети, Джеффри Ульман. Раскрутка // Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — М.: Вильямс, 2003. — С. 681—684. — 768 с. — ISBN 5-8459-0189-8.
• Свердлов С. З. Самокомпилятор. Раскрутка // Языки программирования и методы трансляции. — СПб.: Питер, 2007. — С. 427—431. — 638 с. — ISBN 5-469-00378-7.
• Вирт Н. Построение компиляторов, Москва, ДМК Пресс, 2010, ISBN 978-5-94074-585-3, ISBN 0-201-40353-6

Ссылки

• http://www.compiler.su/raskrutka-kompilyatora.php