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

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

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

Мысли и предложения приветствуются,

Пит


haskell compiler-construction grammar representation
person Peter    schedule 25.03.2009    source источник
comment
Имея то немногое, что я знаю, я бы порекомендовал взглянуть на en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_a48_Hours > (он использует Parsec и т. д.), но я не оставляю его в качестве ответа, потому что он, скорее всего, ужасен. Надеюсь, кто-нибудь, кто знает лучше, ответит (а потом я удалю этот комментарий).   -  person ShreevatsaR    schedule 25.03.2009

Ответы (5)


arrow_upward
16
arrow_downward

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

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.

person nominolo    schedule 25.03.2009

arrow_upward
19
arrow_downward

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

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

person Norman Ramsey    schedule 25.03.2009
comment
Потрясающе .. ссылки. Вы здесь гуру языка прога. Спасибо - person Surya; 19.04.2009
comment
По иронии судьбы, я думаю, что изучение комбинаторов синтаксического анализатора - лучший способ понять монады. - person Zifre; 08.07.2009
comment
Проблема с комбинаторами синтаксического анализатора в том, что они обычно не поддерживают леворекурсивные грамматики ... - person Callum Rogers; 16.07.2013
comment
@CallumRogers то же самое и с рукописными синтаксическими анализаторами с рекурсивным спуском. Никлаус Вирт показал путь много лет назад: вместо левой рекурсии используйте последовательности. - person Norman Ramsey; 23.07.2013

arrow_upward
3
arrow_downward

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

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

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

person Jörg W Mittag    schedule 25.03.2009

arrow_upward
0
arrow_downward

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

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

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

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

person Parappa    schedule 25.03.2009
comment
Dragon Book - действительно классика, но я слышал, что текущие взгляды на реализацию компилятора прошли мимо (например, оптимизация времени выполнения JIT и т. Д.). Я сам не авторитет, просто бессовестный распространитель недомолвок. 8) - person duffymo; 25.03.2009
comment
Спасибо за ваш ответ, мне нужен совет, более конкретный для Haskell, и я бы предпочел не использовать инструмент (я пытаюсь понять, что инструмент не сделает все за меня :)). - person Peter; 25.03.2009
comment
Написание компиляторов на Haskell - совсем другое (и более приятное) упражнение по сравнению с написанием компиляторов на императивных языках. [И @duffymo: "innuendo", вероятно, не означает то, что вы думаете :)] - person ShreevatsaR; 25.03.2009

arrow_upward
0
arrow_downward

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

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

person duffymo    schedule 25.03.2009