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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Что вперёд: курица или яйцо[править | править вики-текст]

Если Вам нужен компилятор для языка X, чтобы получить компилятор для языка X (который написан на языке X), то как написать первый компилятор? Решение проблемы курицы и яйца возможно следующими методами:

  • Создать интерпретатор или компилятор для языка X на языке Y. Никлаус Вирт написал первый компилятор Паскаля на Фортране.
  • Этот интерпретатор или компилятор для полной версии языка X уже может быть написан на языке Y кем-то другим; такая раскрутка часто применяется для языка Scheme.
  • Первая версия компилятора может быть написана на подмножестве языка X, для которого уже существует некий другой компилятор; таким способом были раскручены некоторые подмножества Java, Haskell и Free Pascal.
  • Для создания компилятора языка X можно провести кросс-компиляцию на другой платформе, на которой уже существует компилятор для X; таким способом обычно портируются компиляторы, написанные на Си. Такой же способ используется для Free Pascal после начальной раскрутки.
  • Написание компилятора на языке X; затем компилирование вручную из исходного кода (вероятно всего, без оптимизации) и выполнение полученного кода для получения оптимизированного компилятора. Дональд Кнут использовал этот метод для своей системы грамотного программирования WEB.

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

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

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

Этапы раскрутки можно сократить: после написания компилятора L0—С можно сразу писать компилятор L—L0.

Преимущества[править | править вики-текст]

У создания компиляторов методом раскрутки есть следующие преимущества: [1]

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

Недостатки[править | править вики-текст]

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

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

История[править | править вики-текст]

Первыми языковыми инструментами, которые откомпилировали сами себя методом раскрутки, были ассемблеры. Первый язык высокого уровня, для которого был использован метод раскрутки, был Neliac в 1958 г. Первыми широко используемыми языками, которые были раскручены тем же способом, были Burroughs B5000 [1] Алгол в 1961 г. и Lisp в 1962 г. Харт и Левин написали компилятор Lisp на Lisp в Массачусетском технологическом институте в 1962 г., проверяя его на уже существующем интерпретаторе Lisp. Они перешли на него, как только разработанный ими компилятор смог откомпилировать свой собственный исходный код. Компиляторами, созданными в СССР и использовавшими технику раскрутки, были РЕФАЛ, Сигма и Эпсилон.

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]