Parsec解析和分离不同的结构

Question

假设我有不同的解析器.我想定义一个函数在哪里.p1, ..., pkpk :: Parser ([t1], ..., [tk])pi :: Parser ti

这将解析匹配任何p ₁ ... p _k的字符串集合(一个接一个),并将它们分隔在相应的列表中.为简单起见,假设所有字符串都不匹配两个解析器.

我设法做到了,但我真的很难找到一种优雅的方式(最好使用许多或任何其他内置的parsec解析器).

Answer 1

第一步是将每个解析器转换为大类型的解析器:

p1 :: Parser t1
p2 :: Parser t2
p3 :: Parser t3
p1 = undefined
p2 = undefined
p3 = undefined

p1', p2', p3' :: Parser ([t1], [t2], [t3])
p1' = fmap (\x -> ([x], [], [])) p1
p2' = fmap (\x -> ([], [x], [])) p2
p3' = fmap (\x -> ([], [], [x])) p3

现在,我们反复从这些最后的解析器中进行选择,并在最后连接结果:

parser :: Parser ([t1], [t2], [t3])
parser = fmap mconcat . many . choice $ [p1', p2', p3']

有些Monoid元组最大为5; 除此之外,您可以使用嵌套元组或更合适的数据结构.

Answer 2

将解析器表示为列表使这很容易.使用:

choice :: [Parser a] -> Parser a
many :: Parser a -> Parser [a]

我们可以写:

combineParsers :: [Parser a] -> Parser [a]
combineParsers = many . choice

这不太对,因为它将它们全部捆绑到一个列表中.让我们将每个解析器与唯一标识符相关联:

combineParsers' :: [(k, Parser a)] -> Parser [(k, a)]
combineParsers' = many . choice . combine
  where combine = map (\(k,p) -> (,) k <$> p)

然后我们可以将其转换回列表形式:

combineParsers :: [Parser a] -> Parser [[a]]
combineParsers ps = map snd . sortBy fst <$> combineParsers' (zip [0..] ps)

你也许可以通过combineParsers' :: [(k, Parser a)] -> Parser (Map k [a])使用例如写作来提高效率combine = map $ \(k,p) -> fmap (\a -> Map.insertWith (++) k [a]) p.

这要求所有解析器具有相同的结果类型,因此您需要将每个结果包装在Cons <$> p每个p的数据类型中.然后,您可以从每个列表中解包构造函数.不可否认,这是相当丑陋的,但要与元组异构地进行它将需要更加丑陋的类型级别的黑客攻击.

对于您的特定用例,可能有一个更简单的解决方案,但这是我能想到的最简单的方法.

Answer 3

不幸的是,如果没有类型级别的欺骗,你无法完全做到这一点.然而,根据Daniel Wagner的建议,可以使用多态组合器和一些预先存在的递归实例以DIY风格构建一种方法.我将提供一个简单的示例来演示.

首先,一些简单的解析器进行测试:

type Parser = Parsec String ()

parseNumber :: Parser Int
parseNumber = read <$> many1 digit

parseBool :: Parser Bool
parseBool = string "yes" *> return True
        <|> string "no" *> return False

parseName :: Parser String
parseName = many1 letter

接下来,我们创建一个"基本案例"类型来标记可能性的结束,并给它一个总是在没有输入的情况下成功的解析器.

data Nil = Nil deriving (Eq, Ord, Read, Show, Enum, Bounded)
instance Monoid Nil where 
    mempty = Nil
    mappend _ _ = Nil

parseNil :: Parser Nil
parseNil = return Nil

()当然,这相当于- 我只是创建一个新类型来消除歧义,以防我们真正想要解析().接下来,将解析器链接在一起的组合器:

infixr 3 ?|>
(?|>) :: (Monoid b) => Parser a -> Parser b -> Parser ([a], b)
p1 ?|> p2 = ((,) <$> ((:[]) <$> p1) <*> pure mempty)
        <|> ((,) <$> pure [] <*> p2)

这里发生的是p1 ?|> p2尝试p1,如果它成功包装在单例列表中并填写mempty元组的第二个元素.如果p1失败,则填写空列表并使用p2第二个元素.

parseOne :: Parser ([Int], ([Bool], ([String], Nil)))
parseOne = parseNumber ?|> parseBool ?|> parseName ?|> parseNil

将解析器与新组合器组合很简单,结果类型非常明显.

parseMulti :: Parser ([Int], ([Bool], ([String], Nil)))
parseMulti = mconcat <$> many1 (parseOne <* newline)

我们依赖于Monoid元组的递归实例和列表的通常实例来组合多行.现在,为了证明它有效,请定义一个快速测试:

runTest = parseTest parseMulti testInput

testInput = unlines [ "yes", "123", "acdf", "8", "no", "qq" ]

哪个成功解析为Right ([123,8],([True,False],(["acdf","qq"],Nil))).