uu-parsinglib 的性能与 Parsec 中的 "try"相比

Question

问题

我知道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)

不同的是，在 Parsec , many会吃 (pa <* pb) (成对的 "ab" )贪婪直到不再匹配，而在 uu-parsinglib , pList_ng不是贪心的，所以它会在解析每个 (pa <* pb) 后将可能的回溯方式保存在内存中.

有什么办法可以写 pList(try(pa <* pb))在 uu-parsinglib ?

示例

一个很好的例子是

pExample = pTest <* (pa <* pb)

和 "ababab" 的样本输入.

与 Parsec ，我们会得到错误(因为 pTest 是 "ab" 的贪婪解析对)，但在 uu-parsinglib ，字符串将被解析没有问题。

编辑

我们无法从 pList_ng 切换至 pList , 因为它不等于 Parsec版本。例如:

pExample2 = pTest <* pa

和 "ababa" 的样本输入会在 Parsec 中取得成功，但在 uu-parsinglib 中失败, 使用贪心时 pList .

当然 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 标志编译)

Answer 1

要了解其中的微妙之处，重要的是要了解 Haskell 中的 try 构造与 uu-parsinglib 中使用的非贪婪解析策略之间的区别。实际上，后者是一种仅向前看一个符号的尝试。在这方面，它不如 Parsec 中的 try 构造强大，后者指定特定构造必须完全存在。然后是潜在的不同整体策略。 Parsec 使用带有显式尝试提交的回溯策略，而 uu-parsinglib 使用带有偶尔单个符号前瞻的广度优先策略。

因此，两者之间存在时差也就不足为奇了。在 Parsec 案例中，在看到完整的构造(两个符号)之后，决定尝试的替代方案确实适用，而贪婪的 uu-parsinglib 在成功看到第一个符号后决定这一定是正确的替代方案。而这个结论可能是不合理的。

如果一个人转向广度优先策略，uu-parsinglib 使用一个人必须同时跟踪几个备选方案，这需要时间。两次替代，两次时间等。

Parsec 的优势在于，您可以通过自由使用 try 构造和以正确的顺序放置备选方案来调整回溯解析器，但您也更有可能在邮件列表上询问为什么您的解析器无法按预期工作.你不是在写语法，而是写解析器。 uu-parsinglib 从光谱的另一端开始:我们尝试接受相当大的语法集合(以及它们所隐含的解析器)。

我的感觉也是，如果存在具有出色错误修复解析器的 try 构造，则要复杂得多。一旦一个 try 构造失败，就不可能回到那里并决定，通过一个小的修正，它比它之后的替代方案要好得多。