1

我有这些功能：

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
4

2 回答 2

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
于 2018-06-27T17:45:23.120 回答
0

您的实施(+++)并没有按照您的想法进行。特别是，它只会从其参数之一返回成功解析，而不是从两者中返回。以下是如何做你想做的事：

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

尽管这不会删除重复项，但请注意，您可能会通过执行 eg 来结束解析的爆炸式增长many (many item)。

于 2018-06-27T17:46:24.197 回答