parsing - munch 和 many(满足 p)的区别？

Question

在模块 Text.ParserCombinators.ReadP , munch (和 munch1 )文档说:

Parses the first zero or more characters satisfying the predicate. Always succeds, exactly once having consumed all the characters Hence NOT the same as (many (satisfy p)).

它们有何不同？

Answer 1

首先，让我们找到一个反例，让我们使用 Haskell 工具自动完成。 QuickCheck图书馆可以很快地给我们这样一个反例:

import Data.Function (on)
import Text.ParserCombinators.ReadP
import Test.QuickCheck

prop_ParseTest :: String -> Property
prop_ParseTest input = on (===) runParser (munch pred) (many (satisfy pred))
  where
    runParser :: ReadP a -> [(a, String)]
    runParser = flip readP_to_S input -- run a given parser on a given input
    pred :: Char -> Bool
    pred = (> 'A')

main :: IO ()
main = quickCheck prop_ParseTest

我们要求它测试，两个解析器是否 much pred和 many (satisfy pred)是相同的。 QuickCheck 立即发现它们不同，并尝试生成尽可能短的反例:

*** Failed! Falsifiable (after 5 tests and 2 shrinks):    
[("a","")] /= [("","a"),("a","")]

所以 munch pred总是消耗 'a'无条件地，而 many (satisfy pred)给出一个不确定的答案 - 它可能会或可能不会消耗 'a' .

例如，考虑对字符串 "abcd" 运行以下两个解析器。 :

test1 = munch (> 'A') >> string "cd"

test2 = many (satisfy (> 'A')) >> string "cd"

第一个失败，因为 munch消耗整个字符串，然后无法匹配 "cd" .第二个成功了，因为 many (satisfy ...)创建所有可能的分支

[("","abcd"),("a","bcd"),("ab","cd"),("abc","d"),("abcd","")]

和 string "cd"在消耗 "ab" 的分支上成功.