Можно ли использовать библиотеку Parsec на Haskell для реализации парсера рекурсивного спуска с резервным копированием?

Question

Я рассматривал возможность использования библиотеки синтаксического анализа Parsec на Haskell для анализа подмножества Java в качестве анализатора рекурсивного спуска в качестве альтернативы более традиционным решениям генератора-анализатора, таким как Happy.Parsec кажется очень простым в использовании, и скорость разбора для меня определенно не имеет значения.Мне интересно, однако, возможно ли реализовать «резервное копирование» с помощью Parsec, методики, которая находит правильный продукт для использования, пробуя каждый по очереди.В качестве простого примера рассмотрим начало Java-грамматики JLS:

Literal:
    IntegerLiteral  
    FloatingPointLiteral

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

literal = do {
    x <- try (do { v <- integer; return (IntLiteral v)}) <|>
         (do { v <- float; return (FPLiteral v)});
    return(Literal x)
}

не будет работать ... вводы типа «15.2» приведут к успешному выполнению целочисленного синтаксического анализатора, а затем все будет подавлено «."условное обозначение.В этом случае, конечно, очевидно, что вы можете решить проблему, переупорядочив два производства.Однако в общем случае поиск таких вещей будет кошмаром, и очень вероятно, что я пропущу некоторые случаи.В идеале, я бы хотел, чтобы Парсек разбирался с такими вещами для меня.Возможно ли это, или я просто пытаюсь сделать слишком много с библиотекой?В документации Parsec утверждается, что он может "анализировать контекстно-зависимые, бесконечные прогнозные грамматики", поэтому мне кажется, что я должен кое-что здесь сделать.

Answer 1

Один из способов сделать это - использовать комбинатор try, который позволяет синтаксическому анализатору потреблять ввод и завершать работу без сбоя всего анализа.

Другой способ - использовать Text.ParserCombinators.ReadP, в котором реализован оператор симметричного выбора, в котором доказано, что a +++ b = b +++ a, поэтому действительно не имеет значения, какой порядок. Я довольно неравнодушен к ReadP, поскольку он минимален, но обеспечивает то, что вам нужно для создания действительно мощного парсера.

Answer 2

Либо используйте парсек notFollowedBy, чтобы гарантировать, что integer потребляет все до некоторого разделителя токенов (этот подход большую часть времени будет масштабироваться до произвольного сценария), либо посмотрите на комбинаторы синтаксического анализа, которые исследуют все возможные альтернативы синтаксического анализа. Сначала на ум приходит UU_Parsing библиотека.