Haskell - Как к лучше всего для представления грамматики языка программирования?
Я смотрел на Haskell, и я вполне хотел бы записать компилятор (как осуществление изучения) в нем, начиная со многое из, его - врожденные функции, может быть с готовностью применен к компилятору (особенно рекурсивный достойный компилятор).
Что я не могу вполне получить, моя голова вокруг - то, как представить грамматику языка в Haskell-ian путь. Моя первая мысль состояла в том, чтобы использовать рекурсивные определения типа данных, но я не вижу, как я использую их для соответствия против ключевых слов на языке ("если"), например.
Мысли и предложения, значительно ценившие,
Pete
5 ответов
Рекурсивный тип данных хорошо для этого. Например, учитывая язык:
expr ::= var
| "true"
| "false"
| "if" expr "then" expr "else" expr
| "(" expr ")"
выражение в качестве примера на этом языке было бы:
if true then x else (if false then y else true)
Ваш тип данных Haskell выглядел бы примерно так:
data Expr = Var String
| Lit Bool
| If Expr Expr Expr
Ваш синтаксический анализатор затем заботится для перевода, например, x в Var "x", и true в Lit True, и т.д. Т.е.:
parse "if x then false else true"
== If (Var "x") (Lit False) (Lit True)
Для записи синтаксических анализаторов можно прокрутить собственное использование методов, упомянутых в ответе нормандца или использовании Парсека, или использовать парсеры-генераторы как Счастливый.
Вы представляете программы с помощью взаимно рекурсивных алгебраических типов данных, и проанализировать программы, Вы используете парсинг combinators. Существует миллион разновидностей; Вы найдете три полезных учебных статьи о расписании для моего класса в течение понедельника, 23 марта 2009. Они
- Graham Hutton и Erik Meijer, Функциональный Pearl: Одноместный парсинг в Haskell (1998)
- Graham Hutton, функции высшего порядка для парсинга (1992)
- Jeroen Fokker, функциональные синтаксические анализаторы (1995)
Статья Hutton и Meijer является самой короткой и самой простой, но она использует монады, которые не очевидны для любителя. Однако у них есть очень хорошая грамматика и синтаксический анализатор для выражений. Если Вы еще не делаете grok монад, учебное руководство Fokker является тем.
Возможно, можно ли посмотреть на некоторые реальные проекты видеть, как они делают это?
Меньше чем неделю назад о проекте Python языка объявили на Haskell-кафе mailinglist. Это - синтаксический анализатор Python, реализованный в Haskell, с помощью Счастливого парсера-генератора и генератора лексического анализатора Alex.
И конечно, существуют Мопсы, реализация Perl 6 в Haskell (первая реализация Perl 6, который соответствует значительному подмножеству спецификации Perl 6).
Я не могу сказать от тона Вашего вопроса, является ли это первым разом, когда Вы пытаетесь записать компилятор, или если Вы записали компиляторы прежде и ищете совет, характерный для Haskell. Если Вы уже - гуру компилятора, чему мало совета, который я должен дать, не собирается помогать.:)
Грамматики языка программирования обычно представлены в форме BNF, которая может использоваться инструментами как Yacc или Bison для парсинга исходного кода. Я не знаю, рассчитывает ли это как Haskell-ian способ сделать это, но это - единственный способ, о котором я услышал. С некоторым рытьем вокруг Вас может, вероятно, вскопать инструмент, чтобы сгенерировать код Haskell от грамматики BNF; я нашел этот инструмент, который утверждает, что смог сделать это.
Быстрый поиск Google поднял эту грамматику BNF для Haskell, и там существуют, вероятно, другие, в случае, если Вы хотите записать компилятор для Haskell (возможно, требуется записать компилятор Haskell в Haskell?) грамматики BNF для C и Java, кажется, популярны.
Наконец при поиске книги о дизайне компилятора классический текст является "Книгой Дракона".
К сожалению, нет никакой грамматики Haskell для ANTLR, но возможно можно использовать ссылку, процитированную выше для создания той. ANTLR является большим основанным на Java парсером-генератором.
У Steve Yegge есть хороший блог о записи компиляторов, если Вам нужно больше мотивации. Это интересно.