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

Ответ 1

Рекурсивный тип данных подходит для этого. Например, с учетом языка:

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 и т.д. I.e.:

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

Для написания парсеров вы можете использовать свои собственные, используя методы, упомянутые в ответе Нормана, или используя Parsec или использовать генераторы синтаксического анализатора, такие как Happy.

Ответ 2

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

• Грэм Хаттон и Эрик Мейер, Функциональная жемчужина: монодический синтаксический анализ в Haskell (1998)
• Грэм Хаттон, Функции более высокого порядка для анализа (1992)
• Jeroen Fokker, Функциональные парсеры (1995)

Бумага Хаттона и Мейера является самой короткой и простой, но в ней используются монады, которые не очевидны для любителя. Однако у них очень хорошая грамматика и парсер для выражений. Если вы еще не собираете монады, учебник Fokker - это тот.

Ответ 3

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

Менее недели назад проект Language-Python был анонсирован в рассылке Haskell-Cafe. Это Python парсер, реализованный в Haskell, используя Happy и Alex генератор lexer.

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

Ответ 4

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

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

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

Наконец, если вы ищете книгу о дизайне компилятора, классический текст "The Dragon Book" .

Ответ 5

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