非貪婪重複與秒差距

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