Написание компилятора на своем родном языке - PullRequest
178 голосов
/ 11 октября 2008

Интуитивно кажется, что компилятор для языка Foo сам по себе не может быть написан на Foo. В частности, компилятор first для языка Foo не может быть написан на Foo, но любой последующий компилятор может быть написан для Foo.

Но так ли это на самом деле? У меня есть очень смутные воспоминания о чтении языка, первый компилятор которого был написан «сам по себе». Возможно ли это, и если да, то как?

Ответы [ 11 ]

209 голосов
/ 11 октября 2008

Это называется "начальной загрузкой". Сначала вы должны построить компилятор (или интерпретатор) для вашего языка на каком-либо другом языке (обычно Java или C). Как только это будет сделано, вы можете написать новую версию компилятора на языке Foo. Вы используете первый компилятор начальной загрузки для компиляции компилятора, а затем используете этот компилированный компилятор для компиляции всего остального (включая будущие версии самого себя).

Большинство языков действительно создаются таким образом, отчасти потому, что разработчикам языков нравится использовать язык, который они создают, а также потому, что нетривиальный компилятор часто служит полезным эталоном для определения того, насколько «полным» может быть язык. 1003 *

Примером этого может быть Scala. Его первый компилятор был создан в Pizza, экспериментальном языке Мартином Одерским. Начиная с версии 2.0, компилятор был полностью переписан в Scala. С этого момента старый компилятор Pizza может быть полностью удален из-за того, что новый компилятор Scala можно использовать для компиляции для будущих итераций.

68 голосов
/ 13 октября 2008

Я помню, как слушал подкаст Software Engineering Radio , в котором Дик Габриэль говорил о начальной загрузке оригинального интерпретатора LISP, написав простую версию на LISP на бумаге и вручную собрав ее в Машинный код. С тех пор остальные функции LISP были написаны и интерпретированы с помощью LISP.

42 голосов
/ 11 октября 2008

Добавление любопытства к предыдущим ответам.

Вот цитата из руководства Linux From Scratch , на шаге, когда начинается сборка компилятора GCC из его источника. (Linux From Scratch - это способ установить Linux, который радикально отличается от установки дистрибутива тем, что вам нужно скомпилировать каждый отдельный двоичный файл целевой системы.)

make bootstrap

Цель 'bootstrap' не только компилирует GCC, но и компилирует его несколько раз. Он использует программы, скомпилированные в первом раунд, чтобы скомпилировать себя во второй раз, а затем снова в третий раз. Затем он сравнивает эти второй и третий компилируется, чтобы убедиться, что он может воспроизводить себя безупречно. Это также означает, что он был скомпилирован правильно.

То, что использование цели «bootstrap» мотивировано тем фактом, что компилятор, используемый для построения набора инструментов целевой системы, может не иметь ту же версию целевого компилятора. Поступая таким образом, вы обязательно получите в целевой системе компилятор, который может скомпилировать себя.

39 голосов
/ 28 января 2009

Когда вы пишете свой первый компилятор для C, вы пишете на другом языке. Теперь у вас есть компилятор для C, скажем, на ассемблере. В конце концов, вы придете к тому месту, где вам придется анализировать строки, особенно экранирующие последовательности. Вы напишите код для преобразования \n в символ с десятичным кодом 10 (и \r в 13 и т. Д.).

После того, как этот компилятор готов, вы начнете переопределять его в C. Этот процесс называется " bootstrapping ".

Код разбора строки станет:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Когда это компилируется, у вас есть двоичный файл, который понимает '\ n'. Это означает, что вы можете изменить исходный код:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Так где же информация о том, что \ n - это код для 13? Это в двоичном коде! Это похоже на ДНК: компиляция исходного кода C с этим двоичным файлом унаследует эту информацию. Если компилятор сам компилируется, он передает эти знания своим потомкам. С этого момента нет никакого способа увидеть из одного источника, что будет делать компилятор.

Если вы хотите спрятать вирус в исходном коде какой-либо программы, вы можете сделать это следующим образом: получить исходный код компилятора, найти функцию, которая компилирует функции, и заменить ее следующим:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Интересными частями являются A и B. A является исходным кодом для compileFunction, включая вирус, вероятно, каким-то образом зашифрованным, так что это не очевидно из поиска в полученном двоичном файле. Это гарантирует, что компиляция с самим компилятором сохранит код внедрения вируса.

B - то же самое для функции, которую мы хотим заменить нашим вирусом. Например, это может быть функция «login» в исходном файле «login.c», которая, вероятно, из ядра Linux. Мы могли бы заменить его версией, которая будет принимать пароль «joshua» для учетной записи root в дополнение к обычному паролю.

Если вы скомпилируете это и распространите в виде бинарного файла, вы не сможете найти вирус, посмотрев на источник.

Первоначальный источник идеи: http://cm.bell -labs.com / who / ken / trust.html

18 голосов
/ 11 октября 2008

Вы не можете написать компилятор сам по себе, потому что вам не с чем компилировать исходный код. Есть два подхода к решению этой проблемы.

Наименее предпочтительным является следующее. Вы пишете минимальный компилятор на ассемблере (yuck) для минимального набора языка, а затем используете этот компилятор для реализации дополнительных возможностей языка. Создайте свой путь до тех пор, пока у вас не будет компилятора со всеми возможностями языка для себя. Болезненный процесс, который обычно выполняется только тогда, когда у вас нет другого выбора.

Предпочтительным подходом является использование кросс-компилятора. Вы изменяете серверную часть существующего компилятора на другом компьютере, чтобы создать выходные данные, которые запускаются на целевом компьютере. Тогда у вас есть хороший полноценный компилятор, работающий на целевой машине. Наиболее популярным для этого является язык Си, так как существует множество существующих компиляторов с подключаемыми бэкэндами, которые можно заменить.

Малоизвестный факт, что компилятор GNU C ++ имеет реализацию, которая использует только подмножество C. Причина в том, что обычно легко найти компилятор C для новой целевой машины, который позволит вам затем собрать из него полный компилятор GNU C ++. Теперь вы загрузились, установив компилятор C ++ на целевой машине.

14 голосов
/ 02 ноября 2008

Как правило, сначала вам нужно, чтобы компилятор работал (если он был примитивным), и тогда вы можете начать думать о том, чтобы сделать его автономным. На самом деле это считается важной вехой в некоторых языках.

Из того, что я помню из "моно", вполне вероятно, что им потребуется добавить несколько вещей к размышлению, чтобы заставить его работать: команда моно продолжает указывать, что некоторые вещи просто невозможны с Reflection.Emit; Конечно, команда MS может доказать, что они не правы.

Это имеет несколько реальных преимуществ: это довольно хороший модульный тест для начинающих! И у вас есть только один язык для беспокойства (то есть, возможно, эксперт по C # может не очень хорошо знать C ++; но теперь вы можете исправить компилятор C #). Но мне интересно, нет ли здесь какой-то профессиональной гордости: они просто хотят , чтобы это был хостинг.

Не совсем компилятор, но я недавно работал над системой, которая работает самостоятельно; генератор кода используется для генерации кода ... поэтому, если схема меняется, я просто запускаю ее на себя: новая версия. Если есть ошибка, я просто возвращаюсь к более ранней версии и пытаюсь снова. Очень удобно и очень просто в обслуживании.


Обновление 1

Я только что посмотрел это видео об Андерсе в PDC, и (примерно через час) он приводит несколько более веских причин - все о компиляторе как сервисе. Просто для записи.

4 голосов
/ 11 октября 2008

Вот дамп (на самом деле трудная тема для поиска):

Это также идея PyPy и Rubinius :

(я думаю, это также может относиться к Forth , но я ничего не знаю о Forth.)

1 голос
/ 02 ноября 2008

На самом деле, большинство компиляторов написаны на языке, который они компилируют, по причинам, указанным выше.

Первый загрузочный компилятор обычно пишется на C, C ++ или Assembly.

1 голос
/ 02 ноября 2008

Компилятор C # проекта Mono уже давно "самодостаточен", что означает, что он написан на самом C #.

Что я знаю, так это то, что компилятор был запущен как чистый код на C, но как только были реализованы «основные» функции ECMA, они начали переписывать компилятор на C #.

Мне не известно о преимуществах написания компилятора на одном языке, но я уверен, что это связано, по крайней мере, с возможностями, которые может предложить сам язык (например, C не поддерживает объект ориентированное программирование).

Вы можете найти больше информации здесь .

1 голос
/ 11 октября 2008

GNAT, компилятор GNU Ada, требуется компилятор Ada для полной сборки. Это может быть проблемой при переносе его на платформу, где нет готового двоичного файла GNAT.

...