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

Я рассматривал использование библиотеки парсинга Парсека Haskell для парсинга подмножества Java как синтаксический анализатор с рекурсивным спуском как альтернатива более традиционным решениям парсера-генератора как Счастливый. Парсек кажется очень простым в использовании, и скорость синтаксического анализа является определенно не фактором для меня. Я задаюсь вопросом, тем не менее, если возможно реализовать "резервное копирование" с Парсеком, техника, которая находит, что корректное производство использует путем попытки каждого в свою очередь. Для простого примера рассмотрите, очень запускаются грамматики 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" заставят целочисленный синтаксический анализатор успешно выполняться сначала, и затем все это будет дросселировать на "." символе. В этом случае, конечно, очевидно, что можно решить проблему путем переупорядочения этих двух производства. В общем случае, тем не менее, находящем вещи как это, будет кошмаром, и вероятно, что я пропущу некоторые случаи. Идеально, я хотел бы способ иметь материал фигуры Парсека как это для меня. Действительно ли это возможно, или я просто пытаюсь сделать слишком много с библиотекой? Документация Парсека утверждает, что может "проанализировать контекстно-зависимые, бесконечные предварительные грамматики", таким образом, она походит на что-то как, я должен смочь сделать что-то здесь.

11
задан Derek Thurn 20 March 2010 в 14:37
поделиться

2 ответа

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

2
ответ дан 3 December 2019 в 10:03
поделиться

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

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

8
ответ дан 3 December 2019 в 10:03
поделиться
Другие вопросы по тегам:

Похожие вопросы: