Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

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

Можно ли написать компилятор совершенно нового языка программирования, используя только этот язык?
Раскрутка компилятора
Когда-то такая проблема не казалась высосанной из пальца. Когда появились первые компьютеры, для них не было написано ни одной программы и, естественно, для них не существовало компиляторов. Код программ вводился с пульта управления руками. Первым компилируемым языком стал язык ассемблера, и он был набран в кодах с пульта управления. И только потом появилась возможность переписать этот компилятор языка а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
    Для скриптовых языков, не претендующих на производительность, такое вполне допустимо. В остальных случаях такая схема требует доработки. Например, не полная интерпретация, а сохранение исходного кода в байт-код без повторной трансляции.
  • Невозможность использования генераторов синтаксических анализаторов. Это мы уже рассмотрели выше.

Последняя правка: 2015-01-23    06:26

ОценитеОценки посетителей
   ██████████████████████████████ 19 (70.3%)
   ████████ 5 (18.5%)
   ████ 2 (7.40%)
   ██ 1 (3.70%)

Отзывы

     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-hosted система, самодостаточная технология, не нуждающаяся в сторонних инструментах. Путь к технологической независимости.

Почему он должен воспроизводить свой собственный код? Откуда это следует?

Потому что здесь рассматриваются не все компиляторы, а только те, которые создаются методом раскрутки. На старте применяются разные методы, но на финише разработке получается компилятор, который сам себя компилирует. Берёт свой собственный исходный код и превращает его в исполняемый.

Самый распространенный способ и не указали – трансляция в программу на другом языке программирования.

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

     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 и подобные инструменты

Выбор кодировки для компилятора

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

Лексический анализатор

●  Разбор цепочек знаков операций

●  Как отличить унарный минус от бинарного

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Прочее

Последние комментарии

2018/10/11 22:29, Автор сайта
Формула расчета точности для умножения

2018/10/08 14:00, Неслучайный читатель
Сколько проходов должно быть у транслятора?

2018/10/06 12:19, Автор сайта
Тексто-графическое представление программы

2018/10/04 17:39, Автор сайта
Об исключенных командах или за что «списали» инструкцию INTO?

2018/09/29 16:52, Автор сайта
Как отличить унарный минус от бинарного

2018/09/22 20:13, Д.Ю.Караваев
Идеальный транслятор

2018/09/22 12:32, Автор сайта
Типы в инженерных задачах

2018/09/22 12:20, Д.Ю.Караваев
О русском языке в программировании