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

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

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

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

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

• Автор языка 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 ₀ .

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

Достоинства метода раскрутки :

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

Недостатки

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

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

История

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

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

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

• (« Алгол 60 ») в 1961 году;
• « Лисп » в 1962 году.

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

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

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

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

• TypeScript
• РЕФАЛ
• « »
• « »

Примечания

Литература

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

Ссылки