Запись компилятора на его собственном языке

Я вспоминаю слушание подкаст Радио Разработки программного обеспечения , где Dick Gabriel говорил о начальной загрузке исходного интерпретатора LISP путем записи базовой версии в LISP на бумаге и рука, собирающая его в машинный код. С тех пор остальная часть функций LISP была и записана в и интерпретирована с LISP.

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

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

строковый код парсинга станет:

...
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? Это находится в двоичном файле! Это похоже на DNA: Компиляция 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.c", который является, вероятно, от ядра Linux. Мы могли заменить его версией, которая примет пароль "joshua" для корневой учетной записи в дополнение к нормальному паролю.

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

первоисточник идеи: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95 /

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

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

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

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

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

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

make bootstrap

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

то, Что использование цели 'начальной загрузки' мотивировано тем, что компилятор каждый использует для создания набора инструментальных средств целевой системы, не может иметь той же самой версии целевого компилятора. Продолжение таким образом, которое каждый, несомненно, получит в целевой системе, компилятор, который может скомпилировать себя.

Обычно у Вас должна быть работа (если примитивный) сокращение компилятора, работающего сначала - тогда можно начать думать о создании его самохостинг. Это на самом деле считают важной вехой в некоторых языках.

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

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

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

Обновление 1

я только что смотрел это видео из Anders в PDC, и (приблизительно час в) он действительно приводит некоторым намного больше допустимых причин - все о компиляторе как услуга. Только для справки.

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

• Smalltalk

• C

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

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

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

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

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

Моно компилятор C# проекта был "саморазмещен" в течение долгого времени теперь, что это означает, то, что это было записано в самом C#.

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

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

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

Возможно, можно записать BNF, описывающий BNF.