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

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

19 голосов
/ 25 марта 2009

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

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

Мысли и предложения с благодарностью,

Пит

Ответы [ 5 ]

20 голосов
/ 25 марта 2009

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

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

14 голосов
/ 25 марта 2009

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

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)

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

3 голосов
/ 25 марта 2009

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

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

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

0 голосов
/ 25 марта 2009

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

У Стива Йегге есть хороший блог о написании компиляторов, если вам нужна дополнительная мотивация. Это интересно.

0 голосов
/ 25 марта 2009

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

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

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

Наконец, если вы ищете книгу о дизайне компилятора, классический текст будет «Книга Дракона» .

...