Учебные ресурсы по парсерам, интерпретаторам и компиляторам
Я давно хотел поиграть с написанием своего собственного языка (якобы для обучения) и поэтому должен быть относительно основан на создании синтаксических анализаторов, интерпретаторов и компиляторов. Так:
- Кто-нибудь знает какие-нибудь хорошие ресурсы по созданию парсеров, интерпретаторов и компиляторов?
РЕДАКТИРОВАТЬ: я не ищу компиляторы-компиляторы / парсеры-компиляторы, такие как Lex, Yacc и Bison...
12 ответов
Лучшая статья, которую я когда-либо читал о компиляторах, датируется 1964 г."META II - синтаксически-ориентированный язык написания компиляторов". Автор Val Schorre. ( http://doi.acm.org/10.1145/800257.808896)
На 10 страницах он показывает вам, как создать поразительно простой, но очень эффективный компилятор-компилятор, предоставляет вам грамматику компилятора-компилятора и предоставляет вам достаточно деталей, чтобы вы могли реализовать ее за день (с одним удивительным концептуальным моментом). когда понимаешь, как это повторяется), и просто ради ухмылки реализует язык, похожий на ALGOL. Эта статья - полный газ, и ее обязательно нужно прочитать всем, кто работает с технологиями компиляции.
Вот ссылка, чтобы поиграть с отличным учебником по метакомпиляции, основанном на статье. http://www.bayfronttechnologies.com/mc_tutorial.html
Это очень интересное сообщение в блоге Стива Йегге ( Rich Programmer Food) не расскажет вам всего, что вам нужно знать о том, как создать компилятор (хотя оно включает в себя немало хорошего понимания), но оно отлично справляется объясняя, почему вы хотите понять компиляторов.
Черт, этот пост почти заставил меня начать изучать компиляторы, и у меня есть постоянная работа, 3-х лет дома, и в среднем около -1,5 часов в день.
"Книга Дракона" Ахо является стандартным справочником, но еще одним хорошим выбором является Эндрю Аппель " Реализация современного компилятора на Java" (также доступна в версиях ML и C). Он шаг за шагом проведет вас через каждый из необходимых компонентов компилятора / интерпретатора и предоставит много полезного исходного кода.
Я нашел "Давайте построим компилятор" - учебник Джека Креншоу, который очень легко понять и понять. Джек с самого начала создает компилятор для Pascal с очень подробными объяснениями каждого шага.
Конструкция компилятора: Принципы и практика - лучшая книга на эту тему.
На сайте MIT OpenCourseWare(OCW) есть класс, проект которого заключается в создании компилятора... они ссылаются на книгу Дракона и книгу Аппеля, но кроме того, имеются также заметки и лекции по классам. Класс 6.035 - Компьютерный язык.
Я нашел примечания к классу очень полезными для объяснения парсеров рекурсивного спуска.
Недавно я читал языковые процессоры программирования на Java и рекомендую его вам, поскольку он начинается с базовых концепций, а затем знакомит вас с реализацией компилятора с рекурсивным спуском, включая генерацию кода, с множеством обсуждений альтернативных подходов. Я не читал другие предлагаемые книги в этой теме, поэтому не могу предложить сравнение с ними. Не стоит откладывать на части In Java, если вы не знаете java, так как концепции и их реализация достаточно хорошо объяснены, так что вы получаете суть без необходимости детального понимания Java.
Я рекомендую Compiler Design in C, который вы, к сожалению, должны найти на сайте подержанных книг. Единственная реальная проблема с книгой состоит в том, что она была написана обратно, когда скорость компиляции была важным фактором, поэтому компилятор написан на C. Этого достаточно для языка низкого уровня, что иногда теория реализации скрывается под кодом реализации.
Вы упомянули как переводчиков, так и составителей. Я бы порекомендовал начать с интерпретатора, а не с компилятора. Начать работать с переводчиком гораздо проще, и с ним, как правило, работать веселее, потому что вы можете получить немедленную обратную связь о том, как у вас дела.
На всякий случай, если вы:
- Готовы играть
- Как шанс построить что-то быстрее, а затем идти глубже
- Все в порядке с использованием.NET на базовой платформе
... тогда я бы порекомендовал вам проверить Microsoft Dynamic Language Runtime, которая предоставляется в виде исходного кода во всем Dynamic Silverlight SDK.
http://www.codeplex.com/sdlsdk
Некоторые приятные моменты в том, что он предоставляет множество готовых к использованию функций, таких как консоль, система общих типов, универсальное абстрактное синтаксическое дерево и т. Д. И пакет включает три реализации: Python, Ruby и Javascript.
Может быть, это хороший шанс реализовать краткий язык, отличный от DLR, затем начать проверять фактический код DLR, а затем начать собирать базовые элементы самостоятельно.
В любом случае, удачи от другого языкового урода!
RE: Лекс, Як, Бизон
Вы имеете в виду, что вам не нужны указатели на них или что вы не заинтересованы в их использовании? Я не рекомендую писать лексер или парсер вручную.
РЕДАКТИРОВАТЬ: у вас может быть преувеличенное представление о том, что может сделать "компилятор-компилятор": действительно сложная часть компиляции начинается после того, как вы создали AST. Книги Ахо, Лоудена и Аппеля все довольно хороши.
Это старая книга, и она довольно устарела, но я нашел Бринча Хансена о компиляторах Pascal очень практичным введением в создание языка и создание элементов компилятора. Несмотря на название, это не относится к Паскалю. Это очень полезно, если вы можете найти копию.