Учимся писать компилятор

Большой список ресурсов:

• В рамках Nanopass для образования компилятора ¶
• Усовершенствованная разработка и реализация компилятора $
• Инкрементный подход к построению компилятора ¶
• ANTLR 3.x Видеоурок
• Основы проектирования компилятора
• Построение компилятора Parrot
• Основы Компилятора
• Построение Компилятора $
• Проектирование и конструирование компилятора $
• Создание компилятора с C $
• Крафт Переводчиков
• Дизайн компилятора в C ¶
• Компиляторы: принципы, методы и инструменты $ - aka "The Dragon Book"; широко рассматривается "the book" для написания компилятора.
• Разработка компилятора $
• Основы языков программирования
• Flipcode Article Archive (ищите "реализация скриптового движка Яна Ништадта")
• Мастерство Написания Сценариев Игр $
• Как построить виртуальную машину с нуля в C# ¶
• Реализация Функциональных Языков
• Реализация языков программирования (с BNFC)
• Реализация языков программирования с использованием C# 4.0
• Шаблон интерпретатора (описанный в Design Patterns $) определяет способ оценки предложений на языке
• Шаблоны реализации языка: создайте свой собственный доменный и общий языки программирования
• Давайте построим компилятор от Джека Креншоу-версия PDF ¶ (примеры находятся в Pascal, но информация в целом применима)
• Линкеры и загрузчики $ (Google Books)
• Lisp мелкими кусочками (LiSP) $
• LLVM учебник
• Современная реализация компилятора в ML $ - есть также версия Java $ и C $ - широко считается очень хорошей книгой
• Объектно-Ориентированное Построение Компилятора $
• Методы Анализа: Практическое Руководство
• Проект Оберон ¶ - посмотрите на Главу 13
• Программирование персонального компьютера $
• Языки программирования: применение и интерпретация
• Кролик: компилятор для схемы ¶
• Размышления о доверии доверие — краткое руководство
• Откатите свой собственный компилятор для фреймворка .NET — краткое руководство из MSDN
• Структура и интерпретация компьютерных программ
• Типы и языки программирования
• Хотите написать компилятор? - краткое руководство
• Написание компилятора в Ruby снизу вверх

Легенда:

• ¶ Ссылка на файл PDF
• $ Ссылка на печатную книгу

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

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

Просто выполнение верхней половины позволяет вам получить опыт написания лексического анализатора и парсера и перейти к созданию некоторого "code" (это промежуточное представление, о котором я упоминал). Таким образом, он возьмет вашу исходную программу и преобразует ее в другое представление и сделает некоторую оптимизацию (если вы хотите), которая является сердцем компилятора. Нижняя половина будет затем принимать это промежуточное представление и генерировать байты, необходимые для запуска программы на определенной архитектуре. Например, нижняя половина примет ваше промежуточное представление и создаст исполняемый файл PE.

Некоторые книги на эту тему, которые я нашел особенно полезными, были составителями принципов и методов (или книга дракона, из-за симпатичного дракона на обложке). У него есть отличная теория, и он определенно охватывает контекстно-свободные грамматики в действительно доступной форме. Кроме того, для построения лексического анализатора и парсера вы, вероятно, будете использовать инструменты *nix lex и yacc. И довольно неинтересно, что книга под названием "Лекс и Якк" начала с того места, где Драконья книга остановилась на этой части.

Я думаю, что современная реализация компилятора в ML -это лучший вводный компилятор, пишущий текст. Есть версия Java и версия C, каждая из которых может быть более доступной, учитывая ваш языковой фон. Книга содержит много полезного базового материала (сканирование и синтаксический анализ, семантический анализ, записи активации, выбор инструкций, генерация нативного кода RISC и x86) и различные темы "advanced" (компиляция OO и функциональные языки, полиморфизм, сбор мусора, оптимизация и одна статическая форма задания) в относительно небольшом пространстве (~500 страниц).

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

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

Я согласен со справочником книги Дракона; IMO, это окончательное руководство по построению компилятора. Однако приготовьтесь к какой-нибудь жесткой теории.

Если вы хотите книгу, которая легче по теории, мастерство написания сценариев игр может быть лучшей книгой для вас. Если вы полный новичок в теории компиляторов, она обеспечивает более мягкое введение. Он не охватывает более практичные методы парсинга (выбор в пользу непрогнозируемого рекурсивного спуска без обсуждения парсинга LL или LR), и, насколько я помню, он даже не обсуждает какую-либо теорию оптимизации. Кроме того, вместо компиляции в машинный код он компилируется в байт-код, который должен выполняться на VM, который вы также пишете.

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

"Let's Build a Compiler" -это круто, но он немного устарел. (Я не говорю, что это делает его даже немного менее действительным.)

Или проверить SLANG . Это похоже на "Let's Build a Compiler", но гораздо лучший ресурс, особенно для начинающих. Это поставляется с учебником pdf, который использует 7-шаговый подход при обучении вас компилятору. Добавление ссылки quora, поскольку она имеет ссылки на все различные порты SLANG, в C++, Java и JS, а также интерпретаторы в python и java, первоначально написанные с использованием платформы C# и .NET.

Если вы хотите использовать мощные инструменты более высокого уровня, а не строить все самостоятельно, то просмотр проектов и чтений для этого курса -довольно хороший вариант. Это языковой курс автора Java parser engine ANTLR. Вы можете получить книгу для курса в качестве PDF от прагматичных программистов .

Курс проходит через стандартные компиляторы компилятора, которые вы увидите в других местах: синтаксический анализ, типы и проверка типов, полиморфизм, таблицы символов и генерация кода. В значительной степени единственное, что не охвачено, - это оптимизация. Окончательный проект - это программа, которая компилирует подмножество C . Поскольку вы используете такие инструменты, как ANTLR и LLVM, можно написать весь компилятор за один день (у меня есть доказательство существования этого, хотя я имею в виду ~24 часов). Это тяжело для практического проектирования с использованием современных инструментов, немного легче для теории.

LLVM, кстати, это просто фантастика. Во многих ситуациях, когда вы обычно компилируете до assembly, вам было бы гораздо лучше компилировать до промежуточного представления LLVM вместо этого. Это более высокий уровень, кросс-платформенный, и LLVM довольно хорошо генерирует оптимизированный assembly из него.

Если у вас мало времени, я рекомендую книгу Никлауса Вирта "Compiler Construction" (Addison-Wesley. 1996), крошечный буклет, который вы можете прочитать за день, но он объясняет основы (в том числе, как реализовать лексеры, рекурсивные Парсеры спуска и ваши собственные виртуальные машины на основе стека). После этого, если вы хотите глубоко погрузиться, нет никакого способа обойти книгу Дракона, как предлагают другие комментаторы.

Возможно, вы захотите посмотреть на Lex/Yacc (или Flex/Bison,, как бы вы их ни называли). Flex-это лексический анализатор, который будет анализировать и идентифицировать семантические компоненты ("tokens") вашего языка, и Bison будет использоваться для определения того, что происходит, когда каждый токен анализируется. Это может быть, но определенно не ограничивается распечаткой кода C для компилятора, который будет компилироваться до C, или динамическим запуском инструкций.

Это FAQ должно помочь вам, и этот учебник выглядит довольно полезным.

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

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

Первый шаг-написать формальное описание языка, grammar вашего языка программирования. Затем вам нужно преобразовать исходный код, который вы хотите скомпилировать или интерпретировать в соответствии с grammar, в абстрактное синтаксическое дерево, внутреннюю форму исходного кода, которую компьютер понимает и может использовать. Этот шаг обычно называется синтаксическим анализом, а программное обеспечение, которое анализирует исходный код, называется синтаксическим анализатором. Часто синтаксический анализатор генерируется генератором синтаксического анализатора, который преобразует формальный grammar в исходный машинный код oder. Для хорошего, нематематического объяснения парсинга я рекомендую технику парсинга-практическое руководство. В Википедии есть сравнение генераторов парсеров, из которых вы можете выбрать тот, который вам подходит. В зависимости от выбранного вами генератора парсеров, вы найдете учебные пособия в Интернете, а для действительно популярных генераторов парсеров (таких как GNU bison) также есть книги.

Написать парсер для вашего языка может быть очень трудно, но это зависит от вашего grammar. Поэтому я предлагаю сохранить ваш grammar простым (в отличие от C++); хорошим примером для этого является LISP.

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

Если вы создаете интерпретатор, вам просто придется интерпретировать промежуточное представление. Вы также можете just-in-time-compile это. Я рекомендую LLVM и libjit для just-in-time-compilation. Чтобы сделать язык удобным для использования, вам также придется включить некоторые функции ввода и вывода и, возможно, небольшую стандартную библиотеку.

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

Есть несколько книг на эту тему, но я не могу рекомендовать ни одну из них для общего использования. Большинство из них слишком академичны или слишком практичны. Там нет "Teach yourself compiler writing in 21 days" и, таким образом, вам придется купить несколько книг, чтобы получить хорошее понимание всей этой темы. Если вы поищете в интернете, вы столкнетесь с некоторыми онлайн-книгами и конспектами лекций. Может быть, поблизости есть университетская библиотека, где вы можете взять книги о компиляторах.

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

Взгляните на книгу ниже. Автор является создателем ANTLR .

Шаблоны реализации языка: создайте свой собственный доменный и общий языки программирования .

Одна книга, еще не предложенная, но очень важная, - это "Linkers and Loaders" Джона Левина. Если вы не используете внешний ассемблер, вам понадобится способ вывода объектного файла, который можно связать с вашей окончательной программой. Даже если вы используете внешний ассемблер, вам, вероятно, нужно будет понять перемещения и то, как работает весь процесс загрузки программы, чтобы сделать рабочий инструмент. Эта книга собирает много случайных знаний об этом процессе для различных систем, включая Win32 и Linux.

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

Я бы добавил книгу Оберона , которая содержит полный источник удивительно быстрого и простого проекта компилятора Oberon Oberon .

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

Я был очень осторожен, когда спрашивал, и удивительно, что я не получил столько критики, сколько вы получаете здесь. Однако они указали мне на направление "книги Дракона", которая, по моему мнению, действительно отличная книга, которая объясняет все, что вам нужно знать, чтобы написать компилятор (вам, конечно, придется освоить один или два языка. Чем больше языков вы знаете, тем веселее.).

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

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

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

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

В заключение скажу, что книга о драконе-это великий "tutorial". Но потратьте некоторое время на овладение одним или двумя языками, прежде чем пытаться написать компилятор. Однако не рассчитывайте стать гуру компиляторов в течение следующего десятилетия или около того.

Книга также хороша, если вы хотите научиться писать parsers/interpreters.

Если вы хотите использовать LLVM, проверьте это: http://llvm.org/docs/tutorial/ . Он учит вас, как написать компилятор с нуля, используя фреймворк LLVM, и не предполагает, что у вас есть какие-либо знания об этом предмете.

Учебник предлагает вам написать свой собственный парсер и лексер и т. д., Но я советую вам заглянуть в bison и flex, как только вы поймете эту идею. Они делают жизнь намного проще.

Книга Дракона определенно является книгой "building compilers", но если ваш язык не так сложен, как нынешнее поколение языков, вы можете посмотреть на шаблон интерпретатора из шаблонов дизайна .

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

"... Давайте создадим компилятор ..."

Я бы поставил на второе место http://compilers.iecc.com/crenshaw/ на @sasb . Забудьте на время о покупке новых книг.

Почему? Инструменты & язык.

Требуемый язык-Pascal и, если я правильно помню, основан на Turbo-Pascal. Это просто так происходит, если вы идете в http://www.freepascal.org/ и загружаете компилятор Pascal все примеры работают прямо со страницы ~ http://www.freepascal.org/download.var самое прекрасное в бесплатном Pascal - это то, что вы можете использовать его почти на любом процессоре или OS, который вам нужен.

После того, как вы освоили уроки, попробуйте более продвинутую "книгу Дракона" ~ http://en.wikipedia.org/wiki/Dragon_book

Я изучаю ту же концепцию и нашел эту многообещающую статью Джоэла Побара,

Создайте компилятор языка для фреймворка .NET - не уверен, куда это пошло

Создайте компилятор языка для .NET Framework-pdf копии исходного документа

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

1. Определение языка
2. Сканер
3. Парсер (бит им в основном интересен)
4. Ориентируясь на фреймворк .Net
5. генератор кода

есть и другие темы, но вы получите справедливое.

Его предназначение для начинающих людей, написанных в C# (не совсем Java)

HTH

кости

От comp.compilers FAQ :

"Programming a Personal Computer" Пер бринч Хансен Прентис-Холл 1982 ISBN 0-13-730283-5

Эта к сожалению-титульная книга объясняет проектирование и создание однопользовательской среды программирования для micros используется Pascal-подобный язык, называемый Edison. Автор представляет весь исходный код и пояснения для step-by-step реализации Компилятор Edison и простая поддерживающая операционная система, все написанные в Сам Эдисон (за исключением небольшого поддерживающего kernel, написанного в символической форме ассемблер для PDP 11/23; полный исходный код также можно заказать для IBM ПЕРСОНАЛЬНЫЙ КОМПЬЮТЕР).

Наиболее интересными моментами в этой книге являются: 1) ее способность продемонстрируйте, как создать полный, самодостаточный, самоподдерживающийся, полезный компилятор и операционная система, а также 2) интересное обсуждение проблемы языкового проектирования и спецификации и компромиссы в главе 2.

"Brinch Hansen on Pascal Compilers" Пер бринч Хансен Прентис-Холл 1985 ISBN 0-13-083098-4

Другой light-on-theory heavy-on-pragmatics здесь ' s-how-to-code-it книга. Автор представляет следующие материалы: проектирование, реализация и полный исходный код для компилятора и p-кода интерпретатор для Pascal- (Pascal "minus"), подмножества Pascal с логическим и целочисленные типы (но без символов, реалов, подстрочных или перечисляемых типов), определения констант и переменных, а также типы массивов и записей (но не упакованные, вариант, набор, указатель, безымянный, переименована, или типы файлов), выражения, операторы присваивания, определения вложенных процедур со значением и переменной параметры, операторы if, while и блоки begin-end (но нет определения функций, процедурные параметры, операторы goto и метки, случае заявления, повторяйте высказывания, за заявления, а с заявления).

Компилятор и интерпретатор написаны на языке Pascal* (Pascal "star"), а Pascal подмножество расширено с некоторыми функциями в стиле Эдисона для создания системы разработки программного обеспечения. Компилятор Pascal* для IBM PC продается компанией автор, но легко портировать Pascal-компилятор книги на любой удобная платформа Pascal.

В этой книге Дизайн и реализация компилятора выглядят очень просто. Я особенно нравится то, как автор относится к качеству, надежность и тестирование. Компилятор и интерпретатор могут быть легко использованы в качестве основы для более активного проекта языка или компилятора, особенно если вы нажаты, чтобы быстро что-то поднять и запустить.

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

Генерация кода C так же проста, как и генерация кода HTML (просто используйте печать или эквивалент), что, в свою очередь, намного проще, чем написание парсера C или парсера HTML.

Вы должны проверить "ichbins" Дариуса Бэкона, который является компилятором для небольшого диалекта Lisp, нацеленного на C, всего на 6 страницах кода. Его преимущество перед большинством игрушечных компиляторов состоит в том, что язык достаточно полон, чтобы компилятор был написан на нем. (Тарбол также включает в себя интерпретатор для загрузки этой вещи.)

Есть еще кое-что о том, что я нашел полезным в обучении написанию компилятора на моей веб-странице Ur-Scheme .

Python поставляется в комплекте с компилятором python онлайн, написанным на языке Python. Вы можете видеть исходный код, и он включает в себя все этапы, начиная от синтаксического анализа, абстрактного синтаксического дерева, выделения кода и т.д.

Компилятор LCC (Википедия) (главная страница проекта) Фрейзера и Хэнсона описан в их книге "A Retargetable C Compiler: Design and Implementation". Он вполне читаем и объясняет весь компилятор, вплоть до генерации кода.