Написание компиляторов... какое право и что не так?

Ответ 1

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

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

(FYI: лучшая современная технология синтаксического анализа GLR, что легко принимает неоднозначные грамматики без взлома грамматики. GLR даже легко разбирает С++, который нарушает фольклорную теорему, что С++ трудно разобрать. Фольклорная теорема пришли от людей, пытающихся использовать YACC и ANTLR для его анализа).

Чтобы создать компилятор, вам нужно много машин:

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

Мы даже не приблизились к анализу глобального потока, глобальной оптимизации или специальной обработке для современных наборов инструкций с использованием инструкций SIMD или оптимизации кеша. ... У этого списка нет конца. Книга Дракона дает хорошее введение в основные темы, но не затрагивает ни один из продвинутых. Вы хотите, чтобы Cooper "Engineering Compiler" и Muchnick "Advanced Compiler Design" были ссылками, и было бы хорошо, если бы вы хорошо их просматривали, прежде чем начать.

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

Ответ 2

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

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

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

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

A: "Ну, C - паршивый язык для написания компилятора".

Я призываю вас попробовать один из популярных функциональных языков, таких как Haskell или Standard ML. Люди, которые работают в этой области, считают, что компиляторы - это "приложение-убийца" для функциональных языков. Алгебраические типы данных и сопоставление образцов предназначены для написания абстрактного синтаксиса в промежуточный код в машинный код. Хорошим местом, чтобы увидеть силу этих методов, является книга Андрея Аппеля "Компиляция с продолжениями". (Учебник для компилятора Appel также является хорошим чтением и очень элегантным дизайном, но он не всегда объясняет, почему дизайн такой, как есть.)

Ответ 3

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

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

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

http://ellcc.org

Ответ 4

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

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

• Напишите синтаксический анализатор для некоторого достаточно стабильного подмножества ввода.
• Добавьте действия, которые создают полезное представление в памяти (как правило, дерево) и получают его для печати. ​​
• Получить его для печати в форме, которая немного похожа на целевой язык. В моем случае я печатаю дерево node для "x = y + z;" узлов как "ADD x, y, z"; "if (c) {...}" превращается в "bz c label1", тогда перевод "..." затем "label1:".
• Добавьте дополнительные этапы посередине. Это могут быть этапы оптимизации и/или проверки. Возможно, вам понадобится тот, который готовит представление для простого генерации кода: у меня есть этап, который уменьшает чрезмерно сложные выражения, добавляя временные переменные. (Это действительно необходимо для вывода, потому что команда "ADD" может работать только на простых входах.)
• Вернитесь назад и улучшите любую его часть. Например. поместите некоторые проверки в действия парсера, чтобы на этом этапе могли быть обнаружены ошибки (например, использование незадекларированных переменных).

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

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

Конечно, не человек... так много обучения происходит от ошибок. То, где вы учитесь больше всего.

ВЫ МОЖЕТЕ СДЕЛАТЬ ЭТО!

Ответ 8

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

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

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

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

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