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

Ответ 1

Компилятор состоит из трех частей:

• Парсер
• Абстрактное синтаксическое дерево (AST)
• Генератор кода

Есть много хороших генераторов парсеров, которые начинаются с языковых грамматик. Возможно, ANTLR будет хорошим местом для вас. Если вы хотите придерживаться корней C, попробуйте lex/yacc или bison.

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

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

Это выполнимо, но не тривиально.

Я также проверял Amazon на книги о написании компиляторов. Книга Дракона - классика, но есть более современные.

UPDATE: были проблемы с переполнением стека, например этот. Проверьте эти ресурсы.

Ответ 2

Я советую вам этот учебник:

• Учебник LLVM

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

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

• Clang

Ответ 3

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

Ответ 4

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

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

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

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

Итак, я бы сказал, попробуйте начать с Jack Crenshaw Let Build the Compiler, написать свой собственный, следуя его примерам в качестве руководства, и построить основы простого компилятора. Как только вы начнете работать, вы можете лучше решить, где вы хотите взять это с этой точки.

Добавлено:

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

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

Учебник Crenshaw также пропускает создание AST (абстрактное синтаксическое дерево), которое упрощает, но также ограничивает компилятор учебника. В нем отсутствует большая часть, если не вся оптимизация, и очень привязана к конкретному языку программирования и конкретному языку ассемблера, испускаемому "back-end" компилятора. Обычно AST - это средняя часть, в которой может быть выполнена какая-то оптимизация, и служит для устранения параграфа компилятора переднего плана и внешнего интерфейса в дизайне. Для новичков, не имеющих опыта в области компьютерных наук, я бы посоветовал не беспокоиться о том, что у вас нет АСТ для вашего первого компилятора (или, по крайней мере, первой версии). Я думаю, что держать его маленьким и простым, поможет вам закончить запись компилятора в его первой версии, и вы можете решить оттуда, как вы хотите продолжить.

Ответ 5

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

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

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

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

C является паршивым языком для написания компилятора.

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

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

Вы не найдете другую статью, такую ​​как Кен. Но Andrew Appel написал хорошую статью под названием Аксиоматическая загрузка: руководство для хакеров-компиляторов Я не смог найти бесплатную версию, но многие люди имеют доступ к Цифровая библиотека ACM.

Любые предложения?

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

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

• Для вашего первого компилятора выберите очень простой язык, например Oberon или как P0 из книги Niklaus Wirth Algorithms + Data Structures = Программы. Вирт славится разработкой языков, которые легко компилируются.

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

Ответ 6

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

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

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

Ответ 7

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

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

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

Вот несколько ссылок для начала:

• В качестве кода для кода C был найден Jack Crenshaw порт (я помню, как он загружал его несколько месяцев назад...)
• Здесь ссылка на аналогичный вопрос здесь на SO.
• Кроме того, здесь еще один небольшой учебник компилятора для компилятора ассемблера Basic to x86.
• Tiny C Compiler
• Hendrix Small C Compiler нашел здесь.

Ответ 8

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

Ответ 9

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

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

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

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

Ответ 10

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

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

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

Ответ 11

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

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

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

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

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

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

10 страниц!

Ответ 12

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

Инструменты для составления компиляторов и парсеров великолепны, но проблема состоит в том, что они представляют собой сокращенную нотацию. Если вы не знаете, как создать компилятор в longhand, стенография будет казаться загадочной, бесполезной ограничительной и т.д. Поэтому сначала напишите свой собственный простой компилятор, а затем продолжите оттуда. Я также рекомендую вам не начинать генерировать фактический машинный код, если вы не едите и не дышите ассемблером. Создайте собственный интерпретатор байт-кода с помощью виртуальной машины.

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

Я много писал о языках программирования, поэтому здесь вы можете найти полезные сообщения: http://orangejuiceliberationfront.com/category/language-design/

В частности, http://orangejuiceliberationfront.com/how-to-write-a-compiler/ является стартером по деталям разбора общих конструкций и создания чего-то полезного из этого, а также http://orangejuiceliberationfront.com/generating-machine-code-at-runtime/, в котором говорится о фактическом изъятии инструкций Intel, которые что-то делают.

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

В любом случае, получайте удовольствие!