Рекурсивный парсер

Question

Мне нужно разобрать, используя Megaparsec структуру данных вроде

data Foo
    = Simple String
    | Dotted Foo String

где я могу иметь буквенно-цифровые строки, разделенные точками.

Например abc должен быть проанализирован Simple "abc" а также abc.def в Dotted (Simple "abc") "def",

Мой парсер на данный момент похож

fooParser :: Parser Foo
fooParser
    = Simple <$> alphaNum
    <|> do
        foo <- fooParser
        constant "."
        end <- alphaNum
        pure $ Dotted foo end

Это прекрасно работает для Simple, но это не разбирает любой Dottedпотому что первый параметр всегда успешно разбирает первый фрагмент строки.

Какой лучший вариант исправить мой парсер?

Answer 1

он не анализирует любые Dotted, потому что первый параметр всегда успешно разбирает первый фрагмент строки.

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

Однако это приведет вас только к следующей проблеме: Dotted parser является леворекурсивным, что parsec не поддерживает, то есть он приведет к бесконечной рекурсии, как только он действительно достигнут.

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

foo ::= alphanum
      | foo "." alphanum

Мы можем переписать его, используя повторение так:

foo ::= alphanum ("." alphanum)*

Теперь самый прямой перевод на Parsec будет использовать many для * и затем сверните влево полученный список. Тем не менее, мы могли бы заметить, что шаблон rule ("seperator" rule)* может быть проще сопоставлено sepBy1, Итак, это дает нам:

fooParser =
  do
    first : rest <- sepBy1 alphanum $ constant "."
    return $ foldl Dotted (Simple first) rest