1

我正在阅读有关构建解析器组合器库的教程,并且遇到了一种我不太了解的方法。

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

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) <|> return a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do {a <- p; rest a}
  where rest a = (do f <- op
                     b <- p
                     rest (f a b))
                 <|> return a

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s

是操作符bind的实现(>>=)。我不太明白这个chainl1功能是如何工作的。从我可以看到你从中提取f然后op将其应用于f a b并递归,但是我不知道当它应该返回元组列表时如何从解析器中提取函数?

4

1 回答 1

1

首先查看 的定义Parser

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

AParser a实际上只是一个函数(我们可以稍后运行parse)的包装器,它接受 aString并返回一个对列表,其中每对包含a在处理字符串时遇到的一个,以及其余待处理的字符串.

现在看一下chainl1让您感到困惑的代码部分:您从中提取的f部分op

f <- op

你说:“我不明白你是如何从解析器中提取一个函数时它应该返回一个元组列表的。”

确实,当我们使用字符串(使用)运行a时,我们会得到一个类型列表作为结果。但是这段代码没有说。相反,我们在这里使用(使用 do-notation 语法糖)。问题是您正在考虑数据类型的定义,但您并没有过多考虑具体做什么。Parser aparse[(a,String)]parse op sbindParserbind

让我们更仔细地看看monadbind在做什么。Parser

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s

做什么p >>= f?它返回一个Parser,当给定一个字符串时s,它会执行以下操作:首先,它使用要解析的字符串运行解析器。正如您正确指出的那样,这将返回一个类型列表:即遇到的类型值的列表,以及遇到每个值后剩余的字符串。然后它获取这个对列表并对每一对应用一个函数。具体来说,此列表中的每一对都通过 (1) 应用于解析的值(返回一个新的解析器),然后 (2)使用剩余的字符串运行这个新的解析器来进行转换。这是一个从元组到元组列表的函数:ps[(a, String)]a(a, s')faf as'(a, s') -> [(b, s'')]...并且由于我们将此函数映射到由 . 返回的原始列表中的每个元组上parse p s,这最终给了我们一个元组列表列表[[(b, s'')]]:所以我们将这个列表连接(或连接)成一个列表[(b, s'')]。总而言之,我们有一个函数 from sto [(b, s'')],然后我们将其包装在一个Parser新类型中。

关键的一点是,当我们说f <- op,或者op >>= \f -> ...将名称分配给f由 解析的值op,但f不是元组列表时,b/c 不是运行的结果parse op s

一般来说,你会看到很多定义一些数据类型的 Haskell 代码SomeMonad a,以及一个bind为你隐藏很多脏细节的方法,并让你可以a使用 do-notation 访问你关心的值,如下所示:a <- ma. State a查看monad 以了解如何bind在幕后为您传递状态可能会很有启发性。同样,在这里,当组合解析器时,您最关心解析器应该识别的值......bind隐藏了所有涉及在识别类型值时保留的字符串的脏工作a

于 2016-08-17T03:37:48.387 回答