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-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旗帜编译)

Answer 1

要理解细微之处,理解Haskell中的try构造与uu-parsinglib中使用的非贪婪解析策略之间的差异是很重要的.实际上后者是一个尝试,只是向前看一个符号.在这方面,它不如Parsec的try构造强大,在Parsec中,您指定必须完全存在特定构造.然后是潜在的不同整体战略.Parsec使用具有显式尝试提交的反向跟踪策略,而uu-parsinglib使用广度优先策略,偶尔使用单符号前瞻.

因此,两者之间存在时差并不令人意外.在Parsec案例中,在看到完整构造(两个符号)之后,确定尝试的替代方案确实适用,而贪婪的uu-parsinglib在成功看到第一个符号后决定这必须是正确的替代方案.这个结论可能是不合理的.

如果一个人转向广度优先策略,uu-parsinglib使用一个必须同时跟踪几个备选方案,这需要时间.两种选择,两倍的时间等

Parsec的优点是你可以通过自由使用try结构和以正确的顺序放置备选方案来调整反向跟踪解析器,但是你也更有可能在邮件列表上询问你的解析器为什么不能按预期工作的问题.你写的语法并不像编写解析器那么多.uu-parsinglib从频谱的另一端开始:我们尝试接受相当多的语法集合(以及它们隐含的解析器).

我的感觉是,在存在具有出色错误修复解析器的try构造时要复杂得多.一旦尝试构造失败,就不可能回到那里并决定通过一个小的修正,它比它之后的替代品好得多.