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

Question

Это эволюция этого вопроса.

Мне нужно разобрать с мегапарсек такую ​​структуру данных как

data Foo =
    Simple String
    Dotted Foo String
    Paren String Foo

и я хотел бы разобрать в нем строки вроде

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

Например, строка "a(b.c).d" должен быть проанализирован Dotted (Paren "a" (Dotted (Simple "b") "c")) "d",

Проблема у меня заключается в том, что это одновременно левая и правая рекурсия.

У меня нет проблем с написанием парсеров для первого и третьего случая:

parser :: Parser Foo
parser 
    = try (do
        prefix <- alphanum
        constant "("
        content <- parser
        constant ")"
        pure $ Paren prefix content
        )
    <|> Simple alphanum

но я не могу собрать также парсер для второго случая. Я пытался подойти к нему с sepBy1 или с makeExprParser но я не мог понять это правильно

Answer 1

Чтобы выделить левую рекурсию в этом:

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

Вы можете начать с переписывания этого:

foo ::= alphanum ("(" foo ")")?
      | foo "." alphanum

Затем вы можете выделить левую рекурсию, используя стандартный прием замены:

x ::= x y | z

С:

x ::= z x'

x' ::= y x' | ∅

Другими словами:

x ::= z y*

С x знак равно foo, y знак равно "." alphanum, а также z знак равно alphanum ("(" foo ")")?, это становится:

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

Тогда я считаю, что ваш парсер может быть примерно таким, так как ? ~ ноль или один ~ Maybe ~ optional а также * ~ ноль или более ~ [] ~ many:

parser = do
  prefix <- Simple <$> alphanum
  maybeParens <- optional (constant "(" *> parser <* constant ")")
  suffixes <- many (constant "." *> alphanum)
  let
    prefix' = case maybeParens of
      Just content -> Paren prefix content
      Nothing -> prefix
  pure $ foldl' Dotted prefix' suffixes