Haskell - Как к лучше всего для представления грамматики языка программирования?

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

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

Мысли и предложения, значительно ценившие,

Pete

21
задан Casey Jones 3 November 2019 в 04:14
поделиться

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)

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

15
ответ дан 29 November 2019 в 20:48
поделиться

Вы представляете программы с помощью взаимно рекурсивных алгебраических типов данных, и проанализировать программы, Вы используете парсинг combinators. Существует миллион разновидностей; Вы найдете три полезных учебных статьи о расписании для моего класса в течение понедельника, 23 марта 2009. Они

Статья Hutton и Meijer является самой короткой и самой простой, но она использует монады, которые не очевидны для любителя. Однако у них есть очень хорошая грамматика и синтаксический анализатор для выражений. Если Вы еще не делаете grok монад, учебное руководство Fokker является тем.

20
ответ дан 29 November 2019 в 20:48
поделиться

Возможно, можно ли посмотреть на некоторые реальные проекты видеть, как они делают это?

Меньше чем неделю назад о проекте Python языка объявили на Haskell-кафе mailinglist. Это - синтаксический анализатор Python, реализованный в Haskell, с помощью Счастливого парсера-генератора и генератора лексического анализатора Alex.

И конечно, существуют Мопсы, реализация Perl 6 в Haskell (первая реализация Perl 6, который соответствует значительному подмножеству спецификации Perl 6).

3
ответ дан 29 November 2019 в 20:48
поделиться

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

Грамматики языка программирования обычно представлены в форме BNF, которая может использоваться инструментами как Yacc или Bison для парсинга исходного кода. Я не знаю, рассчитывает ли это как Haskell-ian способ сделать это, но это - единственный способ, о котором я услышал. С некоторым рытьем вокруг Вас может, вероятно, вскопать инструмент, чтобы сгенерировать код Haskell от грамматики BNF; я нашел этот инструмент, который утверждает, что смог сделать это.

Быстрый поиск Google поднял эту грамматику BNF для Haskell, и там существуют, вероятно, другие, в случае, если Вы хотите записать компилятор для Haskell (возможно, требуется записать компилятор Haskell в Haskell?) грамматики BNF для C и Java, кажется, популярны.

Наконец при поиске книги о дизайне компилятора классический текст является "Книгой Дракона".

0
ответ дан 29 November 2019 в 20:48
поделиться

К сожалению, нет никакой грамматики Haskell для ANTLR, но возможно можно использовать ссылку, процитированную выше для создания той. ANTLR является большим основанным на Java парсером-генератором.

У Steve Yegge есть хороший блог о записи компиляторов, если Вам нужно больше мотивации. Это интересно.

0
ответ дан 29 November 2019 в 20:48
поделиться
Другие вопросы по тегам:

Похожие вопросы: