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

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

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

Проблема курицы и яйца[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Транслятор — компилятор или интерпретатор.
  2. Patrick D. Terry. Compilers and Compiler Generators: An Introduction With C++. — International Thomson Computer Press, 1997. — ISBN 1850322988.
  3. Раскрутка компилятора
  4. В некоторых случаях при двойной интерпретации производительность исполняемого файла может увеличиться. См. PyPy.
  5. Tim Hart and Mike Levin. AI Memo 39-The new compiler. Проверено 13 октября 2006.
  6. MacQueen D. Luca Cardelli and the Early Evolution of ML.
  7. История языка Сигма.
  8. История языка Эпсилон.

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

Ссылки[править | править вики-текст]