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

Розкрутка компілятора (англ. bootstrapping — від boot і strap) — метод створення транслятора^[a] для деякої мови програмування, при якому транслятор пишеться на тій же мові програмування, для трансляції якої створюється; створення транслятором виконуваних файлів з початкового коду самого транслятора. Використовується для перенесення трансляторів на нові платформи. З'явився в середині 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 методом розкрутки передбачає виконання деяких кроків.

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

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

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

Переваги методу розкрутки^[1]:

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

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

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

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

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

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

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

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

• BASIC
• ALGOL
• C
• C++
• Common Lisp
• Eiffel
• F Sharp
• Haskell
• Go
• Java
• Mercury
• Modula-2
• Nemerle
• Oberon
• OCaml
• Pascal
• Perl 6
• PL/I
• Python
• Rust
• Scheme
• Scala
• Standard ML
• TypeScript
• XPL
• РЕФАЛ

• Альфред Ахо, Рави Сети, Джеффри Ульман. Раскрутка // Компиляторы: принципы, технологии и инструменты = 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

• http://www.compiler.su/raskrutka-kompilyatora.php [Архівовано 9 серпня 2020 у Wayback Machine.]