haskell - 秒差距非贪婪重复

Question

我试图将我的输入分成与特定模式匹配的部分和其余部分，比方说

data Data = A Int | B Char | C String
parseDatas :: Parsec [Token] () a [Data]

我已经编写了两个或多或少复杂的解析器

parseA :: Parsec [Token] () Data
parseB :: Parsec [Token] () Data

与我正在寻找的东西相匹配。现在显而易见的解决方案是

parseDatas = many (parseA <|> parseB <|> parseC)

中间部分的解析器如下所示:

makeC :: [Token] -> Data
makeC = C . concatMap show -- or something like this
parseC :: Parsec [Token] () Data
parseC = makeC <$> many anyToken

嗯，这会引发运行时[ERROR] Text.ParserCombinators.Parsec.Prim.many:组合器“many”应用于接受空字符串的解析器。 - 好的，很容易修复:

parseC = makeC <$> many1 anyToken

但是现在 parseC 消耗整个输入(以我不寻找的内容开头)，忽略任何应该产生 A 或 B 的模式!

如果我的模式是正则表达式¹，我现在会将 + 运算符更改为非贪婪 +? 运算符。如何对 many1 解析器组合器执行相同操作？

_{1:我无法使用它，因为我正在操作 token 而不是字符}

---

我找到的解决方案是

parseC = makeC <$> many1 (notFollowedBy (parseA <|> parseB) >> anyToken)

但这看起来确实，呃，不太理想。这并不是很通用。一定有更好的东西。

我还查看了Parsec how to find "matches" within a string其中建议是定义一个递归解析器，但如果我不想删除中间标记并将它们收集在列表中，这看起来会很困惑。

Answer 1

您可以让 parseC 一次只消耗一个 token :

parseDatas = many $ parseA <|> parseB <|> (C . show <$> anyToken)

然后，如果需要，将相邻的 C 分组s 合二为一以保存语义:

groupCs (C c) (C c':xs) = C (c ++ c') : xs
groupCs x xs = x : xs
parseDatas = foldr groupCs [] <$> many (parseA <|> parseB <|> (C . show <$> anyToken))

如果你想应用一些操作make :: [Token] -> String连续 C s:

data Data c = A Int | B Char | C c deriving Functor

groupCs :: [Data a] -> [Data [a]] -> [Data [a]]
groupCs (C c) (C cs:xs) = C (c:cs) : xs
groupCs (C c) xs = C [c] : xs
groupCs x xs = x : xs

parseDatas = (map.fmap) make . foldr groupCs [] <$> many (parseA <|> parseB <|> (C <$> anyToken))