字符串中的函数循环太长

Question

我有这些功能：

item :: Parser Char
item  = Parser i
        where i []     = []
              i (x:xs) = [(x,xs)] 

many  :: Eq a=> Parser a -> Parser [a]
many p = many1 p +++ return []

many1  :: Eq a=> Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             returns (v:vs)

我在应用不同的字符串时得到了奇怪的结果。如果我执行：

parse (many item) "x:=0"

我得到

[('x',0)]

而如果我使用另一个像 "if x=0 then x:=0 else x:=1" 这样更长的字符串，它看起来就像进入循环。做了一些尝试，似乎如果字符串超过 19 个字符，函数就不会结束。这很奇怪，因为在其他长度少于 19 个字符的字符串上效果很好。它可能是什么？

其他定义：

newtype Parser a = Parser { parse :: String -> [(a, String)] }


instance Monad Parser where
    return t = Parser $ \s -> [(t, s)]
    m >>= k  = Parser $ \s -> [(x, y) | (u, v) <- parse m s, (x, y) <- parse (k u) v]

(+++) :: Eq a => Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> if((parse p s)==[]) then parse q s else parse p s

Answer 1

您的代码工作正常，只是您将解析器编写为具有无限回溯，因此 O(2^n) 运行时。您添加的每个字符都会使完成所需的时间加倍：

$ time hugs foo.hs <<< 'parse (many item) "if x=0 then x:=0 els"'
[...]
Main> [("if x=0 then x:=0 els","")]
Main> [Leaving Hugs]

real    0m11.076s
user    0m10.578s
sys     0m0.016s

对

$ time hugs foo.hs <<< 'parse (many item) "if x=0 then x:=0 else"'
[...]
Main> [("if x=0 then x:=0 else","")]
Main> [Leaving Hugs]

real    0m22.346s
user    0m22.048s
sys     0m0.036s

Answer 2

您对 (+++) 的实现与您认为的不同。特别是，它只会 return 从它的一个参数中成功解析，而不是从两个参数中解析。以下是如何做你想做的事：

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser $ \s -> parse p s ++ parse q s

虽然这不会删除重复项，但请注意，您可能会通过执行 many (many item).

等方式导致解析爆炸式增长

字符串中的函数循环太长

Function Loop in string too long

haskell

hugs