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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая Larry Holst (обсуждение | вклад) в 00:04, 5 августа 2022 (→Проблема курицы и яйца: Перенос внутренней ссылки в начало. Удаление повторяющихся внутренних ссылок. Оформление (точка → двоеточие).). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску

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

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

См. также: Проблема курицы и яйца

Пусть создан новый язык программирования L. Пусть на языке 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[англ.] — диалект языка «Алгол 58» и одноимённый компилятор, разработанные в 1958 году; первый язык высокого уровня, для которого был использован метод раскрутки.

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

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

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

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

История

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

Примечания

  1. ↑ Транслятор — компилятор или интерпретатор.
  2. ↑ Patrick D. Terry. Compilers and Compiler Generators: An Introduction With C++. — International Thomson Computer Press, 1997. — ISBN 1850322988.
  3. ↑ Раскрутка компилятора. Дата обращения: 20 марта 2013. Архивировано 9 августа 2020 года.
  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. ↑ История языка Сигма Архивная копия от 20 июля 2013 на Wayback Machine.
  8. ↑ История языка Эпсилон Архивная копия от 20 июля 2013 на Wayback Machine.

Литература

Ссылки

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Раскрутка_компилятора&oldid=124567082