parsing - Monadic 解析函数珍珠 - 将多个解析器粘合在一起

Question

我正在研究功能性珍珠纸 Monadic parsing in Haskell (在 haskellforall.com 推荐阅读该论文以了解解析)。我在第 3 页的第 4 节之前编写了一个实现，如下所示:

newtype Parser a = Parser (String -> [(a,String)])

parse (Parser p) = p

instance Monad Parser where
  return a = Parser (\cs -> [(a,cs)])
  p >>= f  = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])

item :: Parser Char
item = Parser (\cs -> case cs of
                      ""     -> []
                      (c:cs) -> [(c,cs)])

p :: Parser (Char,Char)
p = do { a <- item; item; b <- item; return (a,b)}

根据论文， p是一个解析器，它消耗三个字符，跳过中间一个，并返回一对第一个和第二个。我想不通的是如何将修改后的输入字符串传递给 item 的第二个和第三个定义。在 p .我们没有将第一个解析器的结果传递给第二个解析器，依此类推(因为 ; ，使用了 >> 的语法糖，它丢弃了类型签名 (>>) :: Monad m => m a -> m b -> m b 所示的结果)。我将感谢在 item 的最后两次调用中如何传递修改后的函数。在 p .

让我感到困惑的另一件事是 cs 的处理。在 item - 它不返回 (head,tail) 对。自从 item 之后，它不应该被重新定义如下吗？ parser 根据论文消耗一个字符:

item :: Parser Char
item = Parser (\cs -> case cs of
                      ""     -> []
                      (c:cs') -> [(c,cs')]) -- redefinition - use cs' to denote tail

Answer 1

语法 ;并不总是 >> 的语法糖.

相反，我们有:

do    m ; n  =  m >> n
do x<-m ; n  =  m >>= \x -> n

(上面的翻译是简化的， the full gory details可以在Haskell Report中找到)

所以，你对 p 的定义相当于:

p = item >>= \a -> ( item >> (item >>= \b -> return (a,b) ))

在这里，您可以看到第一个和第三个 item s 不会丢弃它们的结果(因为 >>= 将它们分别绑定(bind)到 a 和 b)，而中间的 item做。

还要注意代码

\cs -> case cs of
        ""     -> []
       (c:cs) -> [(c,cs)]

具有误导性，因为它定义了变量 cs两次:一次在 \cs并且一旦在
图案 (c:cs) .它相当于

\cs -> case cs of
        ""     -> []
       (x:xs) -> [(x,xs)]

这阐明了最终的 String是输出不是原始的 cs一个，而是它的尾部 xs .

在评论中，发帖人想知道为什么 item 的三种用途不返回相同的结果，即为什么在 return (a,b)人物 a不等于 b .这是由于 >>=一元运算符，在此 Parser monad 自动提供输出字符串 xs每个 item发生到下一个。实际上，这个 monad 的全部意义在于帮助将每个解析器的“剩余”输出作为下一个解析器的“待使用”输入提供。这有两个优点:它使程序员不必编写代码来传递这个字符串，并且它确保字符串不会意外地“倒回”到以前的状态。为了说明后一点，这里有一些错误的代码:

let [(c1,s1)] = someParser someInitialString
    [(c2,s2)] = anotherParser1 s1
    [(c3,s3)] = anotherParser2 s2
    [(c4,s4)] = anotherParser3 s3
    [(c5,s5)] = anotherParser4 s2  -- Whoops! Should have been s4
    in [c1,c2,c3,c4,c5]

在最后一步中，字符串在多次使用后被错误地回滚到之前的状态，就好像解析器 anotherParser2和 anotherParser3根本没有消耗任何东西。通过 >>= 组合解析器可以防止此错误。反而。