Чтобы узнать, как писать и анализировать контекстно-свободную грамматику, я хочу выбрать инструмент. Для Haskell существуют два больших варианта: Happy, который генерирует парсер из описания грамматики и * Parsec, что позволяет вам напрямую кодировать парсер в Haskell.
Каковы преимущества (недостатки) любого подхода?
Внешний и внутренний DSL
Формат спецификации парсера для Happy - это внешний DSL, тогда как с Parsec у вас есть полная мощность Haskell, доступная при определении ваших парсеров. Это означает, что вы можете, например, записывать функции для генерации парсеров, использовать Template Haskell и так далее.
Правила приоритета
С Happy вы можете использовать precedences для упрощения вашей грамматики, тогда как с Parsec вы должны правильно вставлять правила грамматики самостоятельно. Таким образом, изменение приоритета оператора намного более утомительно в Parsec.
Статическая проверка
Счастливые будут предупреждать вас о двусмысленности в вашей грамматике во время компиляции. (Хотя это не здорово, говоря вам, где они находятся.) С Parsec вы не получаете предупреждения, пока ваш синтаксический анализатор не будет работать во время выполнения.
Это традиционное решение: я использую lex/yacc (happy) или я пишу свой собственный (в основном рекурсивный спуск) парсер, только тот, что библиотека parsec похожа на DSL для правильной работы.
Если у вас есть опыт работы с подходом yacc/lex, использование счастливой будет меньше кривой обучения.
По моему мнению, Parsec скрывает большинство неприятных деталей грамматики и позволяет вам писать ваши парсеры более интуитивно. Если вы хотите изучить этот материал в первую очередь, пойдите с каким-то синтаксическим анализатором вроде Happy (или даже попытайтесь реализовать его самостоятельно).
Я использую библиотеку комбинаторов парсеров uu-parsinglib из университета utrecht. У вас могут быть исправления ошибок и перестановки бесплатно, а также то, что имеет парсек. Мне также нравится, потому что моя внедренная грамматика выглядит как грамматика EBNF, без так много монадических материалов и легко читается.
Счастливый позволяет полный BNF в спецификации языка, а некоторые полезные сотрудники, такие как правила приоритета. Итак, для сложных случаев генераторы Happy и parser в целом намного лучше. Однако в случае простых, глупых языков с грамматиками LL (k), я бы использовал библиотеку комбинаторов парсеров как более удобную для пользователя.