Parsec против Yacc / Bison / Antlr: почему и когда использовать Parsec?

Question

Я новичок в Хаскеле и Парсеке. После прочтения Глава 16 Использование Parsec из реального мира на Haskell у меня возник вопрос: почему и когда Parsec лучше других генераторов синтаксических анализаторов, таких как Yacc / Bison / Antlr?

Насколько я понимаю, Parsec создает хороший DSL для написания парсеров, а Haskell делает его очень простым и выразительным. Но синтаксический анализ - это такая стандартная / популярная технология, которая заслуживает своего собственного языка, который выводит на несколько целевых языков. Так когда же мы будем использовать Parsec вместо, скажем, генерации кода на Haskell из Bison / Antlr?

Этот вопрос может выйти за рамки технологий и войти в сферу отраслевой практики. При написании парсера с нуля, какая польза от использования Haskell / Parsec по сравнению с Bison / Antlr или чем-то подобным?

Кстати: мой вопрос очень похож на этот , но там не было удовлетворительного ответа.

Answer 1

Одним из основных отличий между перечисленными вами инструментами является то, что ANTLR, Bison и их друзья являются синтаксическими анализаторами , тогда как Parsec является синтаксическим анализатором комбинатор библиотеки.

Генератор парсера читает описание грамматики и выплевывает парсер.Как правило, невозможно объединить существующих грамматик в новую грамматику, и, конечно, невозможно объединить два существующих сгенерированных синтаксических анализатора в новый синтаксический анализатор.

комбинатор синтаксического анализатора OTOH ничего не делает но объединяет существующие парсеры в новые парсеры.Обычно библиотека комбинатора синтаксического анализатора поставляется с парой тривиальных встроенных синтаксических анализаторов, которые могут анализировать пустую строку или один символ, и поставляется с набором комбинаторов, которые принимают 1 или более синтаксических анализаторов и возвращают новый, который, например,анализирует последовательность исходных синтаксических анализаторов (например, вы можете комбинировать синтаксический анализатор d и синтаксический анализатор o для формирования синтаксического анализатора do), чередование исходных синтаксических анализаторов (например, анализатор 0 и 1 парсер для 0|1 парсера) или парсинг исходного анализа несколько раз (повторение).

Это означает, что вы можете, например, взять существующий парсер для Java и существующий парсер для HTML иобъедините их в парсер для JSP.

Большинство генераторов парсеров не поддерживают это или поддерживают только ограниченным образом.Parser комбинаторы OTOH только поддерживают это и ничего больше.

Answer 2

Возможно, вы захотите увидеть этот вопрос, а также связанный вопрос в вашем вопросе.

Какая технология синтаксического анализа Haskell наиболее удобна и почему?

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

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

Айра Бакстер ответил на связанный вопрос на месте о парсере, который привел вас просто к опоре Гималаев для написания переводчика , но быть частью переводчика - только одно из применений для синтаксический анализатор, так что есть еще много областей, где вполне минималистичные системы, такие как ANTLR, Happy и Parsec, являются удовлетворительными.

Answer 3

Исходя из ответа Стивена, я думаю, что одной из наиболее распространенных альтернатив Parsec, если вы хотите придерживаться комбинаторов синтаксического анализа, является attoparsec. Основное различие заключается в том, что attoparsec был написан с большим смещением в сторону скорости, и соответственно делает компромиссы. Например, Parsec ведет бухгалтерский учет, пытаясь вернуть полезные сообщения об ошибках в случае сбоя анализа, что attoparsec не делает в той же степени. Кроме того, я думаю, что attoparsec специализируется на одном типе входного потока / токена, тогда как Parsec абстрагируется от входного типа, так что он может без проблем анализировать потоки типа String, ByteString, Text и т. Д.