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

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

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

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

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

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, но я не мог понять это правильно

1 Ответ

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

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

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
...