Розкрутка компілятора

Розкрутка компілятора (англ. bootstrapping — від boot і strap) — метод створення транслятора[1] для деякої мови програмування, при якому транслятор пишеться на тій же мові програмування, для трансляції якої створюється; створення транслятором виконуваних файлів з початкового коду самого транслятора. Використовується для перенесення трансляторів на нові платформи. З'явився в середині 1950-х років. Дозволяє створити транслятор, який генерує сам себе. Застосовувався для створення трансляторів багатьох мов програмування, включаючи мови Basic, ALGOL, C, Pascal, Haskell, Оберон, 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 — діалект мови «Алгол 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.[недоступне посилання з липня 2019]

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

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.