Раскрутка компилятора

Раскрутка компилятора (англ. 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;
• постоянное улучшение качества кода (улучшение кода транслятора приводит к улучшению качества кода всех программ, создаваемых транслятором, включая сам транслятор);
• всесторонняя проверка транслятора на непротиворечивость (транслятор должен быть способен воспроизвести свой собственный код).

Недостатки Править

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

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

История Править

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

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

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

• Burroughs B5000^[en] («Алгол 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
• Urn

История

Первый компилятор для языка ML, как для самостоятельного языка (после его выделения из LCF как встроенного и интерпретируемого) был написан Лукой Карделли^[en] целиком на языке «Паскаль» (включая среду выполнения (англ. runtime)). Вскоре компилятор был переписан на диалекте «VAX ML» и получил название «Edinburgh ML». Этот компилятор служил платформой для исследования языка, постепенно приблизив ML к виду SML’90. Далее на нём был написан SML/NJ^[en], в то время как среда исполнения была переписана на языке Си. Затем был раскручен SML/NJ, и далее на его основе раскручивались все остальные реализации языка. В настоящее время существует более десятка компиляторов и несколько интерпретаторов, в том числе с нестандартными расширениями, все из которых написаны на SML и обычно способны компилировать друг друга. Единственным исключением является неактуальный для SML инкрементальный компилятор Poplog, написанный на Lisp-подобном языке POP-11, не поддерживающий современные стандарты языка SML и его библиотеки.

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

Литература Править

• Альфред Ахо, Рави Сети, Джеффри Ульман. Раскрутка // Компиляторы: принципы, технологии и инструменты = 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