Рекурсивный парсер - PullRequest
Новая
       13

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

0 голосов
/ 06 сентября 2018

Мне нужно разобрать, используя 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, потому что первый параметр всегда успешно разбирает первый фрагмент строки.

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

1 Ответ

0 голосов
/ 06 сентября 2018

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

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

Однако это приведет вас только к следующей проблеме: ваш Dotted синтаксический анализатор является леворекурсивным, что 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
...