Начинаясь простое (самое простое, возможно) компилятор C?

Я советую вам это руководство:

• Руководство по LLVM

Это небольшой пример того, как реализовать компилятор "малого языка". Исходный код очень маленький и объясняется пошагово.

Существует также внешняя библиотека C для библиотеки LLVM (виртуальная машина низкого уровня, которая представляет внутреннюю структуру программы):

• Clang

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

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

Вместо того, чтобы писать полный компилятор языка C или соответствующий стандартам (по крайней мере, вначале), я бы предложил ограничиться базовым подмножеством языка, таким как общие операторы, поддержка только целых чисел, а также базовые функции и указатели. Классическим примером этого был Small-C Рона Кейна, ставший популярным благодаря серии статей, написанных в Dr.Dobbs Journal , я полагаю, 1980-е годы. Они издают компакт-диск с вышедшей из печати книгой Джеймса Хендрикса A Small-C Compiler .

Я бы посоветовал следовать руководству Креншоу, но писать его для компилятора языка C и любого целевого процессора (Креншоу нацелен на ЦП Motorola 68000), на который вы хотите ориентироваться. Для этого вам нужно знать базовую сборку, на какой целевой машине вы хотите запускать скомпилированные программы. Сюда может входить эмулятор для 68000 или MIPS, которые, возможно, лучше наборов инструкций сборки, чем почтенный набор инструкций CISC Intel x86 (16/32-бит).

Существует множество потенциальных книг, которые можно использовать в качестве отправных точек для изучения теории (и практики) компиляторов / переводчиков. Прочтите часто задаваемые вопросы о comp.compilers и обзоры на различных онлайн-продавцах книг. Большинство вводных книг написаны как учебники для второкурсников и старших курсов бакалавриата по информатике, поэтому они могут быть медленными при чтении без опыта в области компьютерных наук. Одна из более старых книг, которая может быть более вводной, но более легкой для чтения, чем « Книга Дракона » , - это Введение в конструкцию компиляторов Томаса Парсонса. Он старше, поэтому вы сможете найти подержанный экземпляр у онлайн-продавцов книг по разумной цене.

Я бы сказал, попробуйте начать с учебника Джека Креншоу Let's Build a Compiler , напишите свой собственный, следуя его примерам в качестве руководства, и создайте основы простого компилятор.После того, как у вас это получится, вы можете лучше решить, где вы хотите начать с этого момента.

Добавлено:

Что касается процесса начальной загрузки. Поскольку существующие компиляторы C доступны в свободном доступе, вам не нужно беспокоиться о начальной загрузке. Напишите свой компилятор с помощью отдельных существующих инструментов (GCC, Visual C ++ Express, Mingw / djgpp, tcc), и вы можете беспокоиться о самокомпилировании проекта на более позднем этапе. Я был удивлен этой частью вопроса, пока не понял, что вы пришли к идее написания собственного компилятора, прочитав речь Кена Томаса о награждении ACM Turing, Размышления о доверии , которая действительно входит в компилятор процесс начальной загрузки. Это модерируемая продвинутая тема, которая также доставляет массу хлопот. Я считаю, что даже загрузка компилятора GCC C в старых системах Unix (Digital OSF / 1 на 64-битной Alpha), которые включали компилятор C, является медленным и трудоемким, подверженным ошибкам процессом.

Другой вопрос, что на самом деле делает такой компилятор, как Yacc. Yacc (еще один компилятор компилятора или Bison от GNU) - это инструмент, предназначенный для упрощения написания анализатора компилятора (или переводчика). Основываясь на формальной грамматике для вашего целевого языка, которую вы вводите в yacc, он генерирует синтаксический анализатор , который является частью общей конструкции компилятора. Далее идет Lex (или flex из GNU), который используется для создания лексического анализатора или сканера, который часто используется в сочетании с синтаксическим анализатором, сгенерированным yacc, для формирования скелета внешнего интерфейса компилятора.Эти инструменты делают писателя проще, чем писать лексический анализатор и парсер самостоятельно. В учебнике Креншоу эти инструменты не используются, да и вам это не нужно,многие разработчики компиляторов не всегда их используют. Конечно, Креншоу признает, что синтаксический анализатор учебника довольно прост.

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

Возможно, вас заинтересует книга / курс Элементы вычислительных систем: построение современного компьютера из первых принципов .

Обратите внимание, что речь не идет о создании «ПК» из вещей, которые вы купили на newegg. Он начинается с описания основ логической логики и строит виртуальный компьютер от самых низких уровней абстракции до все более высоких уровней абстракции. Все материалы курса доступны в Интернете, а сама книга на Amazon стоит довольно недорого.

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

Компилятор - это сложный предмет, который охватывает аспекты

• Обработка входных данных, включая лексирование, синтаксический анализ
• Создание хранилища символов для каждой используемой переменной, такой как абстрактное синтаксическое дерево (AST)
• Из дерева AST , транспонировать и построить двоичный код машинного кода на основе синтаксиса

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

Вот несколько ссылок, чтобы вы могли начать:

• Там был порт Джека Креншоу его кода для C .... (я помню, как загружал его несколько месяцев назад ...)
• Вот это ссылка на аналогичный вопрос здесь по SO.
• Также, вот еще одно небольшое руководство по компилятору для компилятора ассемблера с базового уровня на x86.
• Tiny C Compiler
• Небольшой компилятор C Хендрикса можно найти здесь .

Возможно, стоит также узнать о функциональном программировании. Функциональные языки хорошо подходят для написания компилятора как в , так и для . В моей школе вводный класс компиляторов содержал введение в функциональные языки, и все задания выполнялись в OCaml.

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

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

В Среда программирования Unix Керниган и Пайк рассматривают 5 итераций, как заставить калькулятор работать от простого лексического анализа на основе C и немедленного выполнения до синтаксического анализа yacc / lex и генерации кода для абстрактной машины. Они так прекрасно пишут, что не могу предложить более плавного вступления. Он, конечно, меньше, чем C, но это, вероятно, в ваших интересах.

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

Я знаю по крайней мере один компилятор C, написанный на Паскале, так что это не самая самая безумная вещь, которую вы могли бы сделать. Лично я бы выбрал более современный язык для реализации моего проекта компилятора C, как для простоты (легко д / л пакеты для Python, Ruby, C, C ++ или Java), так и потому, что он посмотрите лучше в своем резюме.

Однако, чтобы создать компилятор в качестве проекта для начинающих, вам нужно будет выпить все Agile kool-aid .

Всегда есть что-то работающее, даже если оно ни на что не влияет. Добавляйте вещи в свой компилятор только небольшими шагами. («Частые выпуски».) Выберите крайне крошечное подмножество языка и внедрите его в первую очередь. (Сначала поддерживайте только i = 0; и расширяйте оттуда.)

Как мне [начать писать] простой компилятор Си?

В компиляции Си нет ничего простого. Лучший простой компилятор языка Си - lcc Криса Фрейзера и Дэвида Хэнсона. Они потратили 10 лет на разработку, чтобы сделать его настолько простым, насколько это возможно, и при этом генерировать достаточно хороший код. Если у вас есть доступ к университетской библиотеке, вы должны быть в состоянии получить их книгу.

Начинать ли мне создание компилятора C на C или на каком-то другом языке?

На каком-то другом языке. Однажды я спросил Хэнсона, какие уроки они с Фрейзером извлекли, потратив 10 лет на проект lcc. Главное, что сказал Хэнсон:

Си - паршивый язык для написания компилятора.

Лучше использовать Haskell или какой-нибудь диалект ML. Оба языка предлагают функции над алгебраическими типами данных, что идеально подходит для решения проблем, с которыми сталкивается автор компилятора. Если вы все еще хотите изучать C, вы можете начать с CIL Джорджа Некулы, который представляет собой большой кусок компилятора C, написанного на ML.

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

Вы не найдете другой статьи, подобной статье Кена. Но Эндрю Аппель написал хорошую статью под названием Axiomatic Bootstrapping: A Guide for Compiler Hackers Я не смог найти бесплатную версию, но у многих есть доступ к электронной библиотеке ACM.

Есть предложения?

Если вы хотите написать компилятор,

• используйте Haskell или ML в качестве языка реализации.

• Для своего первого компилятора выберите очень простой язык, например Oberon или P0 из книги Никлауса Вирта Алгоритмы + структуры данных = программы. Вирт известен тем, что разрабатывает языки, которые легко компилируются.

Вы можете написать компилятор языка C для своего второго компилятора.

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

META II - синтаксически ориентированный язык написания компиляторов Вал Шорре.

На 10 страницах он рассказывает вам, как писать компиляторы, как писать мета-компиляторы, предоставляет набор инструкций виртуального метакомпилятора и пример компилятора, созданного с помощью метакомпилятора.

Я научился писать компиляторы из этой статьи еще в конце 60-х и использовал эти идеи для создания C-подобных языков для нескольких миникомпьютеров и микропроцессоров.

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

И если получить статью по исходной ссылке неудобно, потому что вы не являетесь членом ACM, вы обнаружите, что в руководстве все равно есть все подробности. (ИМХО, по цене сама бумага вааааа стоит).

10 страниц!