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

  1. Переваги методу розкрутки
  2. Недоліки методу розкрутки і причини його не використовувати:
  3. Відгуки

Чи можна написати компілятор абсолютно нової мови програмування, використовуючи тільки цю мову?

Колись така проблема не здавалося, висмоктувала з пальця. Коли з'явилися перші комп'ютери, для них не було написано жодної програми і, природно, для них не існувало компіляторів. Код програм вводився з пульта управління руками. Першим компільовані мовою стала мова асемблера, і він був набраний в кодах з пульта управління. І тільки потім з'явилася можливість переписати цей компілятор мови аcсемблера на мові асемблера. Створення компілятора для мови «ікс» на мові «ікс» - це і є метод розкрутки. При знайомстві з ідеєю написання компілятора на цільовому мовою програмування у багатьох виникає подив: «А як таке можливо?». Як барон Мюнхаузен може витягнути сам себе з болота за волосся? Це дуже красива ідея, типу вічного двигуна, але чим може бути корисний такий підхід?

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

Авторитетні джерела (в термінах Вікіпедії) описують їх так:
  • це - нетривіальна перевірка мови, для якого робиться компілятор. Дійсно, це ґрунтовна перевірка мови на несуперечливість його концепцій.
  • розробнику досить знати тільки ця мова. Насправді, це вірно не для всіх способів втілення.
  • подальші поліпшення компілятора можна робити на мові високого рівня. Але мови Сі, Паскаль, Оберон (потрібне підкреслити) теж непогані, і компіляторів для них маса.
  • поліпшення згенерованого компілятором коду покращує не тільки код програм взагалі, а й код самого компілятора. Компілятори Сі вже добре оптимізовані, і код, ними генерується, теж непоганий.
  • це - всебічна перевірка компілятора на несуперечливість, оскільки він повинен бути в змозі відтворити свій власний код. З цим важко посперечатися. Якщо компілятор, який має один розмір виконуваного коду, видасть при власній компіляції інший розмір коду, то тут є привід задуматися. І взагалі, добре порівнювати код на етапі N і на етапі N + 1.

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

Опустимо ті способи, які до нас не мають відношення. Адже ми придумуємо нову мову програмування. Тому рада «скористайся компілятором для цієї мови, вже написаний кимось» нам не підходить. І так, способи:
  • Написати компілятор, а першу компіляцію в код зробити вручну. Далі маєш готовий компілятор. У першопрохідців не було іншого способу, вони зробили саме так, «з нічого». Але наскільки він практичний? Компілятор - все-таки складна річ, і написати кілька тисяч рядків коду, не допустивши жодної помилки, а потім без єдиної помилки вручну відкомпілювати - це науковий подвиг. Але оскільки помилок уникнути навряд чи вдасться, ручну компіляцію доведеться неодноразово повторювати. Ні, звичайно герої йдуть в обхід.
  • Написати перший компілятор на іншій мові програмування. Написати не для всієї мови, а лише для деякого підмножини. Так простіше. Це підмножина має охоплювати ті частини мови, які є достатніми для написання компілятора. Потім, використовуючи перший компілятор, можна писати компілятор на підмножині своєї мови. І крок за кроком рухаючись, приходимо від мінімального підмножини до повної версії. Кількість етапів можна звести до одного.

Метод розкрутки використовувався при створенні багатьох мов, але перший раз - для розробки мови асемблера. Перелік мов і компіляторів до них, розроблених таким способом, є в в англійській Вікіпедії . До цього переліку можна додати реалізації мов Епсілон , Сигма і Рефал в радянську епоху. З сучасності можна згадати одну з версій компілятора мови Context авторства Андрія Хохлова, яка так само була написана на самій мові. Утиліта транслітерації російського C / C ++ в стандартний теж була написана методом розкрутки: перший версія була написана на звичайному Сі, інші - на русифікованому Сі.
Тепер наступне питання. Чи можна застосовувати сторонні інструменти типу YACC і LEX при розробці методом розкрутки? Можна, але тільки на першому етапі, коли пишеться перша версія компілятора на сторонньому мовою. Генератор синтаксичних аналізаторів YACC видає код на Сі, bison - для Сі, С ++ і Java, ANTLR - для C ++, Java, C #, Python, Ruby. Але немає такого генератора парсеров, який би видавав код для ще невідомої мови програмування!

Недоліки методу розкрутки і причини його не використовувати:

При створенні нових мов програмування відмова від методу розкрутки і використання вже існуючих мов може бути обгрунтований з наступних причин:
  • Компілятори вже існуючих мов надійні. Вони перевірені часом. Шукати помилки в готовому компіляторі, швидше за все, не доведеться.
  • Для них є IDE, отладчики і інші корисні інструменти. Для новостворюваного мови цих зручностей немає.
  • Використання методу розкрутки для створення інтерпретатора - не найбільш вдала ідея. Уявімо схему розробки такого інтерпретатора.
    1. на мові Y розроблений інтерпретатор підмножини мови X, є виконуваний код;
    2. на підмножині мови X написаний інтерпретатор, що інтерпретує сам себе;
    3. при інтерпретації користувальницької програми запускається інтерпретатор мовою Y (виконуваний код), який інтерпретує інтерпретатор повної версії мови X, який, в свою чергу, інтерпретує призначену для користувача програму на мові X
    Для скриптових мов, що не претендують на продуктивність, таке цілком допустимо. В інших випадках така схема вимагає доопрацювання. Наприклад, не повна інтерпретація, а збереження вихідного коду в байт-код без повторної трансляції.
  • Неможливість використання генераторів синтаксичних аналізаторів. Це ми вже розглянули вище.

Опубліковано: 2013.03.18, остання правка: 2015.01.23 6:26


Відгуки

2014/03/18 18:26, Noname #

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

2015/09/23 15:50, rst256 #

це - всебічна перевірка компілятора на несуперечливість, оскільки він повинен бути в змозі відтворити свій власний код.

Джерела точно авторитетні, а то дане формулювання тхне самопріменімості?

2015/09/24 18:35, Автор сайту #

Авторитетніше не буває. Хоча текст в Вікіпедії мій більш, ніж наполовину, джерела, проте, вельми шановані в академічних колах.

2016/09/17 14:07, rst256 #

Генератор синтаксичних аналізаторів YACC видає код на Сі, bison - для Сі, С ++ і Java, ANTLR - для C ++, Java, C #, Python, Ruby. Але немає такого генератора парсеров, який би видавав код для ще невідомої мови програмування!

А власне в чому проблема то? Подібний згенерований код складається з набору шаблонних конструкцій. Головне, щоб в новому мовою знайшлися для них аналоги.
Звичайно, якщо парсер генерує код, в якому використовується ООП, це може бути проблемою, але якщо парсер генерує код, наприклад на Сі, то переробити його на будь-який інший процедурний мову з підтримкою оператора goto не займе багато часу.

2016/10/27 18:25, Автор сайту #

Робити генерацію на Сі можна. Але ж мета розкрутки - написати компілятор мови на самій мові. Як проміжний етап - так. Але не як кінцевий.

2017/05/05 20:34, utkin #

це - нетривіальна перевірка мови, для якого робиться компілятор. Дійсно, це ґрунтовна перевірка мови на несуперечливість його концепцій.

Незрозуміло звідки це слід.

розробнику досить знати тільки ця мова. Насправді, це вірно не для всіх способів втілення.

Брехня. Якщо це компілятор, то, як мінімум, треба знати мову тієї системи, куди транслюється. Якщо Ви для Андроїда пишіть компілятор Паскаля, то знати Ява просто зобов'язані. Друге - розробка компілятора традиційно має високий поріг входження, людині потрібно знати купу сторонніх відомостей і якщо створюється нова мова програмування, а не черговий клон С ++, то знати реальний мову програмування просто необхідно.

подальші поліпшення компілятора можна робити на мові високого рівня. Але мови Сі, Паскаль, Оберон (потрібне підкреслити) теж непогані, і компіляторів для них маса.

Ну, можна і можна, в чому плюс то? У відсутності прикладів, документації, бібліотек і фреймворків?

поліпшення згенерованого компілятором коду покращує не тільки код програм взагалі, а й код самого компілятора. Компілятори Сі вже добре оптимізовані, і код, ними генерується, теж непоганий.

Компілятори Сі добре оптимізовані, тому що за ними купа часу еволюції

це - всебічна перевірка компілятора на несуперечливість, оскільки він повинен бути в змозі відтворити свій власний код. З цим важко посперечатися. Якщо компілятор, який має один розмір виконуваного коду, видасть при власній компіляції інший розмір коду, то тут є привід задуматися. І взагалі, добре порівнювати код на етапі N і на етапі N + 1.

Чому він повинен відтворювати свій власний код? Ось зовсім необґрунтоване твердження - повинен. Чому? Звідки це випливає?

Опустимо ті способи, які до нас не мають відношення. Адже ми придумуємо нову мову програмування. Тому рада «скористайся компілятором для цієї мови, вже написаний кимось» нам не підходить. І так, способи:

Найпоширеніший спосіб і не вказали - трансляція в програму на іншій мові програмування.

2017/05/15 11:08, Автор сайту #

Незрозуміло звідки це слід.

Зробити робота, який буде будувати таких же роботів, вельми нетривіально. Адже у нього завдання не просто зробити, а зробити безпомилково. Інакше з кожним новим поколінням роботів буде накопичуватися помилка. Те ж саме з самокомпілірующімся компілятором.

треба знати мову тієї системи, куди транслюється

Да ви праві. Але справа не тільки і не стільки в цьому. Можливість не знати ніяких інших мов, крім того, на якому пишеться компілятор - це можливість нереальна і утопічна. І не має якоїсь цінності. Хіба це погано - знати інші мови? Та й чи можна собі уявити, що людина настільки хороший в програмуванні, що береться за складну задачу - розробку компілятора, але при цьому спромігся не знати жодної мови програмування. Це щось: бути асом в програмуванні і не знати мов програмування.

в чому плюс то? У відсутності прикладів, документації, бібліотек і фреймворків?

У тому, то виникає self-hosting система, самодостатня технологія, яка не потребує сторонніх інструментах. Шлях до технологічної незалежності.

Чому він повинен відтворювати свій власний код? Звідки це випливає?

Тому що тут розглядаються в повному обсязі компілятори, а тільки ті, які створюються методом розкрутки. На старті застосовуються різні методи, але на фініші розробці виходить компілятор, який сам себе компілює. Бере свій власний вихідний код і перетворює його в виконуваний.

Найпоширеніший спосіб і не вказали - трансляція в програму на іншій мові програмування.

Для компіляторів, створених методом розкрутки, найпоширеніший спосіб - компіляція в машинний код.

2018/05/28 19:22, Олександр Коновалов aka Маздайщік #

Для компіляторів, створених методом розкрутки, найпоширеніший спосіб - компіляція в машинний код.

По різному. Компілятори РЕФАН, написані в СРСР, компілювали в інтерпретується код RASL (Refal assembly language). Паскаль компілювався в стековий П-код. Про Java я взагалі не говорю.
Метод розкрутки ні скільки не визначає мову перекладу.
Я розробляю компілятори двох діалектів РЕФАН (Модульний Рефал - github.com/Mazdaywik/mrefal.git, Простий Рефал - github.com/bmstu-iu9/simple-refal.git), обидва самопріменімості.
Першим був Модульний Рефал, написаний на Рефале-5, компілював в Рефал-5 (будував дерево і назад Плющ в вихідний код). Потім препроцесором (вже написаним на модульні Рефале) конвертувати вихідні РЕФАН-5 в Модульний Рефал.
Потім написав препроцесор Простого РЕФАН в Модульний Рефал і, користуючись ним, написав самопріменімості компілятор Простого РЕФАН в Сі ++.
Зараз Модульний Рефал компілюється в Сі ++, а Простий Рефал (перейменований в Рефал-5λ) - в інтерпретується код.
З досвіду своєї розробки самопріменімості компіляторів можу сказати ось що.
  • По-перше, простіше з тестуванням. Якщо писати компілятор на іншій мові, то потрібні тестові приклади, а їх писати лінь. Та й зазвичай довгі не напишеш. А самопріменімості компілятор - це вже велика нетривіальна програма на мові компілятора.
  • По-друге, практика роботи з мовою сама підказує, що треба в мову додати. Яких не вистачає бібліотечних функцій. Які були б зручні синтаксичні конструкції. Який додатковий інструментарій потрібен, зокрема, засоби налагодження.
Мова розвивається не умоглядно, а на практиці. Звичайно, практика, в деякому сенсі, однобока - розробку компілятора не назвеш типовою завданням програміста. Але це краще, ніж відсутність практики, коли є тільки умоглядні міркування.
Про синтаксичні аналізатори скажу ось що. Для Простого РЕФАН був написаний (звичайно, на Простому Рефале) примітивний генератор лексичного аналізатора. Звичайно, можна було без нього обійтися, просто мені було цікаво цим зайнятися.
Підсумовуючи: розкрутка корисна перш за все тим, що з самого народження двигуном мови і компілятора не є умоглядні міркування, а практика. Крім того, самопріменімості компілятор викликає довіру вже тим, що він достовірно тестувався нема на прикладах рівня Hello, World !, а вже може зібрати нетривіальну програму.
Недолік можу виділити один: розкрутка привчає до аскетизму. Для Модульного РЕФАН немає ні IDE, ні покрокового отладчика, обходжуся Vim'ом (раніше обходився Far manager'ом), налагоджування печаткою і докладної трасуванням стека при падіннях. Для Простого РЕФАН обидва інструменту є, оскільки я їх порахував хорошими темами для курсових проектів (я викладаю курс «Конструювання компіляторів» в Бауманке) - але вони поки сирі.

2018/05/30 16:53, Автор сайту #

Метод розкрутки ні скільки не визначає мову перекладу

Ви маєте рацію. Хоча машинний код залишається, ймовірно, поширеним варіантом. Ну і проекти у Вас, звичайно, цікаві. А чому Рефал? Чим він Вам сподобався?

розкрутка привчає до аскетизму

Напевно, правильніше було б сказати «примушує» :)

2018/05/30 18:57, Олександр Коновалов aka Маздайщік #

А чому Рефал? Чим він Вам сподобався?

Синдром гусеняти. Перший функціональний мову, з яким я познайомився. Тільки і всього.

розкрутка привчає до аскетизму
Напевно, правильніше було б сказати «примушує» :)

Спочатку примушує, а потім і привчає :-) Зараз я вже не бачу сенсу ні в IDE для РЕФАН, ні в покроковому отладчике.

Додати свій відгук

Написати автору можна на електронну пошту mail (аt) compiler.su

При знайомстві з ідеєю написання компілятора на цільовому мовою програмування у багатьох виникає подив: «А як таке можливо?
Як барон Мюнхаузен може витягнути сам себе з болота за волосся?
Це дуже красива ідея, типу вічного двигуна, але чим може бути корисний такий підхід?
Але наскільки він практичний?
Чи можна застосовувати сторонні інструменти типу YACC і LEX при розробці методом розкрутки?
Джерела точно авторитетні, а то дане формулювання тхне самопріменімості?
А власне в чому проблема то?
Ну, можна і можна, в чому плюс то?
У відсутності прикладів, документації, бібліотек і фреймворків?
Чому?