非贪婪重复与秒差距

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: combinator 'many' is applied to a parser that accepts an empty string. - 好吧，容易固定：

parseC = makeC <$> many1 anyToken 

但是现在parseC消耗了整个输入（开始于我不想要的东西），忽略了任何应该产生的模式A或B！

如果我的模式是正则表达式，我现在已经改变了+运营商的非贪婪+?运营商。我怎么能为many1解析器组合器做同样的事情？

_{1：我不能用，因为我对令牌运行时，字符}

---

一个解决方案，我发现这是

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

但看起来，嗯，不理想的。这不是通用的。必须有更好的东西。

我也看了一下Parsec how to find "matches" within a string其中建议是定义一个递归解析，但是这看起来像一个hazzle如果我不想丢弃中间的标记，并收集他们在一个列表来代替。

Answer 1

您可以让PARSEC在一个时间消耗只有一个令牌：

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] -> StringC 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))