问题
我知道Parsec并且uu-parsinglib我已经在它们中编写了解析器。最近我发现 中存在一个问题uu-parsinglib，这可能会严重影响其性能，我没有找到解决方法。
让我们考虑以下 Parsec 解析器：
pa = char 'a'
pb = char 'b'
pTest = many $ try(pa <* pb)
什么是等价的uu-parsinglib？它不会是以下内容：
pa = pSym 'a'
pb = pSym 'b'
pTest = pList_ng (pa <* pb)
不同之处在于， in Parsec,many会贪婪地吃(pa <* pb)（对"ab"）直到不再匹配，而 in uu-parsinglib,pList_ng不是贪婪的，因此在解析每个 后它将保留在内存中可能的回溯方式(pa <* pb)。
有没有办法写类似pList(try(pa <* pb))in 的东西uu-parsinglib？
例子
一个很好的例子是
pExample = pTest <* (pa <* pb)
和一个样本输入"ababab"。
使用Parsec，我们会得到错误（因为pTest贪婪地解析一对"ab"），但是在 中uu-parsinglib，字符串将被解析而没有问题。
编辑
我们不能从 切换pList_ng到pList，因为它不等同于Parsec版本。例如：
pExample2 = pTest <* pa
以及在使用 greedy 时"ababa"会成功Parsec但失败的示例输入。uu-parsinglibpList
如果我们在这里使用当然uu-parsinglib会成功pList_ng，但是对于某些输入和规则可能会慢很多。例如，考虑到输入"ababab",Parsec会简单地失败，因为pTest会消耗整个字符串并且pa不会被匹配。uu-parsinglib也会失败，但检查更多步骤 - 它将匹配整个字符串并失败，然后丢弃最后"ab"一对并再次失败，等等。如果我们有一些嵌套规则和有趣的输入文本，它将产生巨大的差异。
一个小基准
为了证明问题确实存在，请考虑以下语法（在伪代码中 - 但我认为它非常直观）：
pattern = many("ab") + "a"
input = many(pattern)
因此，作为我们程序的输入，我们得到一个包含模式的字符串，例如“abababaaba”包含 2 个模式“abababa”和“aba”。
让我们在两个库中制作解析器！
uu-parsinglib：
import Data.Char
import qualified Text.ParserCombinators.UU as UU
import Text.ParserCombinators.UU hiding(parse)
import Text.ParserCombinators.UU.BasicInstances hiding (Parser)
import System.TimeIt (timeIt)
pa = pSym 'a'
pb = pSym 'b'
pTest = pList $ pList_ng ((\x y -> [x,y]) <$> pa <*> pb) <* pa
main :: IO ()
main = do
timeIt maininner
return ()
maininner = do
let (x,e) = UU.parse ((,) <$> pTest <*> pEnd) (createStr (LineColPos 0 0 0) (concat $ replicate 1000 (concat (replicate 1000 "ab") ++ "a")))
print $ length x
Parsec：
import Control.Applicative
import Text.Parsec hiding (many, optional, parse, (<|>))
import qualified Text.Parsec as Parsec
import System.TimeIt (timeIt)
pa = char 'a'
pb = char 'b'
pTest = many $ many (try ((\x y -> [x,y]) <$> pa <*> pb)) <* pa
main :: IO ()
main = do
timeIt maininner2
return ()
maininner2 = do
let Right x = Parsec.runParser pTest (0::Int) "test" $ (concat $ replicate 1000 (concat (replicate 1000 "ab") ++ "a"))
print $ length x
结果？uu-parsinglib比300% 慢：
uu-parsinglib - 3.19s
Parsec - 1.04s
ghc -O3（用标志编译）