4

我正在阅读《Haskell 编程》，第 8 章，作者给出了一个编写解析器的例子。完整的来源在这里：http ://www.cs.nott.ac.uk/~gmh/Parsing.lhs 我无法理解以下部分：many 允许零个或多个应用程序p，而many1需要至少一个成功的应用程序：

many        ::    Parser a → Parser [a ]
many p      =     many1 p +++ return [ ]
many1       ::    Parser a → Parser [a ]
many1 p     = do v ← p
                 vs ← many p
                 return (v : vs)

递归调用如何发生在

vs <- many p

vs是 的结果值many p，但是调用了很多 p many1 p，many1在其定义中都有一个 do 表示法，并且再次有结果值v，并且vs，递归调用什么时候返回？为什么以下代码段可以返回[("123","abc")]？

> parse (many digit) "123abc"
[("123", "abc")]
4

3 回答 3

6

递归停止在该v <- p行。当无法再解析时，解析器的一元行为只会将 a 传播[]到计算结束。p

p >>= f =  P (\inp -> case parse p inp of
                        []        -> [] -- this line here does not call f
                        [(v,out)] -> parse (f v) out)

第二个函数是用 do-notation 编写的，这只是下面的一个很好的语法：

many1 p = p >>= (\v -> many p >>= (\vs -> return (v : vs)))

如果解析 p 产生一个空列表，则不会调用[]该函数，从而停止递归。\v -> many p >>= (\vs -> return (v : vs))

于 2011-05-21T10:07:01.543 回答
2

对于最后一个问题：

> parse (many digit) "123abc"
[("123", "abc")]

表示解析成功，因为答案列表中至少返回了一个结果。Hutton 解析器总是返回一个列表——空列表意味着解析失败。

结果（“123”，“abc”）意味着解析找到了三个数字“123”并停在不是数字的“a”处 - 所以“输入的其余部分”是“abc”。

请注意，这many意味着“尽可能多”而不是“一个或多个”。如果它是“一个或多个”，你会得到这个结果：

[("1", "23abc"), ("12", "3abc"), ("123", "abc")]

这种行为对于确定性解析来说不是很好，尽管有时自然语言解析可能需要它。

于 2011-05-21T10:34:36.337 回答
1

让我把它剥离到最简单的部分，以绝对清楚地说明为什么do-blocks 如果被简单地阅读为命令式代码会被误解。考虑这个片段：

doStuff :: Maybe Int
doStuff = do
    a <- Nothing
    doStuff

看起来doStuff会永远递归，毕竟，它被定义为做一系列以doStuff. 但是块中的行do序列不仅仅是按顺序执行的操作序列。如果您位于do-block 中的某个点，则处理该块其余部分的方式由>>=. 在我的示例中，第二个参数 to>>=仅在第一个参数不是时使用Nothing。所以递归永远不会发生。

类似的事情可能发生在许多不同的 monad 中。您的示例稍微复杂一点：当没有更多方法可以解析某些内容时， the 之后的内容将>>=被忽略。

于 2011-05-29T21:55:11.120 回答