Розкрутка компілятора англ bootstrapping від boot і strap метод створення транслятора для деякої мови програмування при

Розкрутка компілятора (англ. bootstrapping — від boot і strap) — метод створення транслятора для деякої мови програмування, при якому транслятор пишеться на тій же мові програмування, для трансляції якої створюється; створення транслятором виконуваних файлів з початкового коду самого транслятора. Використовується для перенесення трансляторів на нові платформи. З'явився в середині 1950-х років. Дозволяє створити транслятор, який генерує сам себе. Застосовувався для створення трансляторів багатьох мов програмування, включаючи мови Basic, ALGOL, C, Pascal, Haskell, Оберон, OCaml, Common Lisp, Scheme, Java, Python, Scala, Nemerle та інші.

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

Нехай створена нова мова програмування L. Нехай на мові L написано початковий код транслятора для мови L. Як отримати транслятор, здатний з цього коду створити виконуваний файл?

Методи вирішення (проблеми) перераховані нижче.

Автор мови L може вручну виконати трансляцію початкового коду з мови L на машинну мову або на мову асемблера. Потім можна виконати отриманий код для створення виконуваного файлу компілятора. Так діяли Ніклаус Вірт з учнями при створенні першого компілятора для мови Pascal, а також Дональд Кнут при створенні своєї системи WEB.

Автор мови L може написати початковий код транслятора на мові, для якої вже існує транслятор. Спробу такого роду (втім, невдалу) здійснив Ніклаус Вірт при створенні першого компілятора для мови Pascal на мові «Фортран».

Те ж, але автор мови L сам не пише початковий код, а доручає цю операцію іншій особі. Такий спосіб часто застосовується при створенні трансляторів для мови Scheme.

Перша версія компілятора може бути написана на підмножині мови L, для якої вже існує якийсь інший компілятор. Таким способом були отримані компілятори для підмножини мов Java, Haskell і Free Pascal.

Створити транслятор для нової платформи можна шляхом крос-компіляції — створення виконуваного файлу транслятора для нової платформи на платформі, для якої транслятор вже існує. Таким способом зазвичай портують компілятори, написані на мовах C і Free Pascal .

Розкрутка компілятора з використанням компілятора існуючої мови

Створення транслятора мови L методом розкрутки передбачає виконання деяких кроків.

На першому кроці з мови L виділяється підмножина L_0, яка не вимагає великих зусиль для реалізації, але є достатньою для написання транслятора самої себе. Потім, використовуючи будь-яку існуючу для цієї платформи мову (наприклад, C), складається початковий код транслятора для L_0.
Потім на мові L₀ складається транслятор для самої мови L_0. Виконуваний файл транслятора створюється за допомогою транслятора, отриманого на першому кроці. Після цього у програміста є транслятор L_0, здатний обробити свій початковий код.
Далі починається поступове розширення L₀ до L: додається якась раніше не реалізована можливість мови L, після чого попередньою версією транслятора створюється нова, а знову додану можливість можна використовувати в трансляторі для подальшого розширення мови.

Саме цей процес і називають розкручуванням.

Число кроків можна зменшити, якщо після складання транслятора L₀ на мові С відразу починати складати транслятор L на підмножині L_0.

Переваги

Переваги методу розкрутки:

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

Недоліки

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

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

Історія

Асемблери були першими компіляторами, здатними компілювати самі себе методом розкрутки.

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

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

Burroughs B5000 («Алгол 60») в 1961 році;
Lisp в 1962 році.

У 1962 році Тім Гарт (англ. Tim Hart) і Марк Левін (англ. Mark Levin) в Массачусетському технологічному інституті написали перший компілятор Lisp на мові Lisp і перевірили його на вже існуючому інтерпретаторі мови Lisp. Вони перейшли на нього, як тільки розроблений ними компілятор зміг відкомпілювати свій власний початковий код.

Список мов, що мають компілятори, які самокомпілюються

Примітки

Транслятор — компілятор або інтерпретатор.

Джерела

Patrick D. Terry. Compilers and Compiler Generators: An Introduction With C++. — International Thomson Computer Press, 1997. — .
. Архів оригіналу за 9 серпня 2020. Процитовано 13 червня 2019.
У деяких випадках при подвійний інтерпретації продуктивність виконуваного файлу може збільшитися. Див. PyPy.
Tim Hart and Mike Levin. AI Memo 39-The new compiler (PDF). Процитовано 13 жовтня 2006.^{[недоступне посилання з липня 2019]}

Література

Альфред Ахо, Рави Сети, Джеффри Ульман. Раскрутка // = Compilers: Principles, Techniques, and Tools. — М. : Вильямс, 2003. — С. 681—684. — .
Свердлов С. З. Самокомпилятор. Раскрутка // Языки программирования и методы трансляции. — СПб. : , 2007. — С. 427—431. — .
Вирт Н. Построение компиляторов, Москва, ДМК Пресс, 2010, ,

Посилання

http://www.compiler.su/raskrutka-kompilyatora.php [ 9 серпня 2020 у Wayback Machine.]

[1] Транслятор — компілятор або інтерпретатор.

[2] Patrick D. Terry. Compilers and Compiler Generators: An Introduction With C++. — International Thomson Computer Press, 1997. — .

[3] . Архів оригіналу за 9 серпня 2020. Процитовано 13 червня 2019.

[4] У деяких випадках при подвійний інтерпретації продуктивність виконуваного файлу може збільшитися. Див. PyPy.

[5] Tim Hart and Mike Levin. AI Memo 39-The new compiler (PDF). Процитовано 13 жовтня 2006.^{[недоступне посилання з липня 2019]}