Запись компиляторов …, что является правильным и что случилось? [закрытый]

Если вы не хотите писать по-настоящему простой компилятор, ваш фокус неверен.

Написание компиляторов - это лишь небольшая часть написания синтаксических анализаторов. Наличие парсера похоже на восхождение к предгорьям Гималаев, когда проблема заключается в восхождении на Эверест. Вы добираетесь до вершины холма и смотрите вверх ... всего 20 000 футов, и вы сделали только действительно легкую часть. И вы заметите, что технология, необходимая для того, чтобы добраться до вершины предгорий, радикально проще, чем технология, необходимая для того, чтобы пройти оставшуюся часть пути.

(К вашему сведению: лучшая современная технология синтаксического анализа - GLR ], что легко принимает двусмысленные грамматики, не взламывая грамматику. GLR даже легко разбирает C ++, что нарушает народную теорему о том, что C ++ трудно разобрать. Народная теорема пришло от людей, которые пытались использовать YACC и ANTLR для его анализа).

Для создания компилятора вам понадобится много оборудования:

• Построение AST
• Построение таблицы символов
• Анализ потока управления
• Анализ потока данных
• Представление программного кода по существу как вычисление потока данных (SSA или троек)
• Модель целевой машины
• Средство отображения программного кода на машинные инструкции
• Размещение регистров
• Оптимизация: константа распространение, развертывание цикла, ...

Мы даже близко не подошли к глобальному анализу потока, глобальной оптимизации или специальной обработке для современных наборов инструкций, включающих инструкции SIMD или оптимизацию кеша. ... У этого списка нет конца. Книга Дракона дает хорошее введение в основные темы, но не затрагивает ни одну из продвинутых. Вам понадобятся «Разработка компилятора» Купера и «Расширенный дизайн компилятора» Мучника в качестве справочных материалов, и было бы хорошо, если бы вы просмотрели их хорошо, прежде чем начать.

Создание современного компилятора - это настоящий инженерный подвиг.

Парсинг, хотя и хорошо изучен, является наименее важной частью компиляции. (Исключение: вы разрабатываете свой собственный конкретный синтаксис и постоянно совершенствуете и меняете язык.)

Yacc, Bison и его друзья были созданы для эпохи машин с 64 КБ памяти. Они отлично подходят для быстрой работы на машинах с ограниченной памятью. Но количество человеческих усилий, необходимых для преобразования грамматики в форму LALR (1), сегодня просто смешно. Ира Бакстер права в том, что GLR, вероятно, является лучшей и наиболее гибкой технологией синтаксического анализа, но PEG (грамматики синтаксического анализа) тоже хороши. В обоих случаях человеческая инженерия на световые годы опережает старые инструменты.

Отказавшись от синтаксического анализа, я начну новую борьбу за еду технологий :-) Компиляция в основном состоит из переписывания программы снова и снова из одной формы в другую, пока в конечном итоге вы не достигнете кода сборки или машинного кода. Для такого рода задач вы действительно не хотите использовать C или C ++:

Q: (На вопрос Дэйва Хэнсона, когда он опубликовал свою потрясающую книгу о lcc с Крисом Фрейзером) «У вас и Криса есть потратил десять лет на создание, возможно, одного из самых тщательно спроектированных компиляторов из когда-либо созданных. Что вы узнали из этого опыта? »

A:« Ну, C - плохой язык для написания компилятора »

I настоятельно рекомендую вам попробовать один из популярных функциональных языков, например Haskell или Standard ML. Люди, работающие в этой области, широко считают, что компиляторы - это «приложение-убийца» для функциональных языков. Алгебраические типы данных и сопоставление с образцом специально созданы для записи абстрактного синтаксиса в промежуточный код в машинный код. Хорошее место, где можно увидеть мощь этих методов, - это книга Эндрю Аппеля Compiling With Continuations . (Учебник по компилятору Аппеля также хорошо читается и имеет очень элегантный дизайн, но он не всегда объясняет , почему дизайн такой, какой он есть.)

Я не могу дать сравнение различных подходов, но группа ANTLR охватила широкий диапазон богатых целевых языков :

, которые включают большую часть текущих общие. ANTLR также поддерживает множество языков вывода. Мы планируем заняться языком, подобным CSS

Чтобы создать компилятор, я настоятельно рекомендую встать на плечи гигантов. Есть много хороших вещей, которые можно собрать вместе для создания компиляторов. Я подрабатываю компилятором для C / C ++. Он использует GLR для синтаксического анализа, создает AST, использует SSA в качестве промежуточной формы, выполняет межпроцедурную оптимизацию и генерирует код для X86, ARM, MIPS, PowerPC, Sparc и др.

Секрет? Я заимствовал код из нескольких источников.

• Препроцессор и сообщение об ошибках из clang
• Генератор компилятора Elkhound и Elsa и компилятор C / C ++
• Система LLVM для оптимизации и генерации кода

Работа неполный рабочий день I ' мне удалось собрать довольно полезную систему инструментов. Если бы я попытался начать с нуля, я бы к этому времени едва закончил парсер. ; -)

http: // ellcc. org

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

Вопреки некоторым советам, я Я бы сказал, что вы можете начать, не зная всего о вашем вводе и целевых языках. За некоторыми исключениями, языковые функции не так уж сложно добавить позже. Одно исключение, которое я обнаружил, - это поток управления: если вы напишете большинство последующих манипуляций для работы с древовидной формой, может быть трудно обслуживать такие операторы, как break , continue , и goto (даже в структурированной форме). Поэтому я бы рекомендовал переводить из дерева в CFG, прежде чем делать из этого слишком много.

1. Напишите синтаксический анализатор для некоторого достаточно стабильного подмножества входных данных.
2. Добавьте действия, которые создают его полезное представление в памяти (обычно это tree) и заставьте его напечатать это.
3. Заставьте его напечатать его в форме, которая немного похожа на целевой язык. В моем случае я печатаю узел дерева для «x = y + z;» узлы как «ADD x, y, z»; "if (c) {...}" превращается в "bz c label1", затем перевод "...", затем "label1:".
4. Добавьте дополнительные этапы посередине. Это могут быть этапы оптимизации и / или проверки. Вам может понадобиться тот, который подготавливает представление для простой генерации кода: у меня есть этап, который сокращает чрезмерно сложные выражения путем добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)
5. Вернитесь и улучшите любую его часть. Например, включите некоторые проверки в действия синтаксического анализатора, чтобы ошибки могли быть обнаружены на этом этапе (например, использование необъявленных переменных).

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

превращается в "bz c label1", затем перевод "...", затем "label1:".

Добавьте дополнительные этапы в середине. Это могут быть этапы оптимизации и / или проверки. Вам может понадобиться тот, который подготавливает представление для простой генерации кода: у меня есть этап, который сокращает чрезмерно сложные выражения путем добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

превращается в "bz c label1", затем перевод "...", затем "label1:".

Добавьте дополнительные этапы в середине. Это могут быть этапы оптимизации и / или проверки. Вам может понадобиться тот, который подготавливает представление для простой генерации кода: у меня есть этап, который сокращает чрезмерно сложные выражения путем добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

Добавьте дополнительные этапы посередине. Это могут быть этапы оптимизации и / или проверки. Возможно, вам понадобится тот, который подготавливает представление для простой генерации кода: у меня есть этап, который сокращает чрезмерно сложные выражения путем добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

Добавьте дополнительные этапы посередине. Это могут быть этапы оптимизации и / или проверки. Вам может понадобиться тот, который подготавливает представление для простой генерации кода: у меня есть этап, который сокращает чрезмерно сложные выражения путем добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

У нас есть этап, который сокращает чрезмерно сложные выражения за счет добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

У нас есть этап, который сокращает чрезмерно сложные выражения за счет добавления временных переменных. (На самом деле это необходимо для вывода, потому что инструкция «ADD» может работать только с простыми вводами.)

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

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

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

У каждой технологии (кроме, может быть, оператора goto) есть как противники, так и сторонники. Не зацикливайтесь на «выборе правильного инструментария» и изо всех сил старайтесь изучать концепции и реализовывать их разумным образом. Я имею в виду, да ладно, даже если вы выберете идеальные лучшие инструменты в мире, как вы думаете, вы бы создали что-то такое же любимое, почитаемое и уважаемое, как Фортран в наши дни ... Я имею в виду, что нам это нравится ... верно?

Конечно, не человек ... столько всего учится на ошибках.

В Flex и Bison нет ничего плохого, но если вы ищете что-то более современное (и объектно-ориентированное), вы можете подумать о библиотеке Spirit boost .

Is это для 1) большого существующего языка, такого как Java или C ++, с одной стороны, или 2) небольшого языка без причудливых типов данных, с другой?

Если 1, вам лучше освоить все технологии, о которых упоминала Ира.

Если 2, вы можете сделать это в кратчайшие сроки, если просто напишете синтаксический анализатор с рекурсивным спуском и либо а) переведете его на ваш любимый язык (YFL) во время синтаксического анализа, либо б) создадите таблицу символов и проанализируете tree, а затем пройдите по нему, чтобы сгенерировать YFL. Если вы не хотите создавать YFL, просто напишите интерпретатор, который обходит дерево синтаксического анализа.

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

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