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是一个消费三个字符的解析器,跳过中间的一个,并返回一对第一和第二.我无法弄清楚的是修改后的输入字符串如何传递给itemin的第2和第3个定义p.我们没有将第一个解析器的结果传递给第二个解析器,依此类推(因为;,使用了语法糖,>>它丢弃了类型签名所示的结果(>>) :: Monad m => m a -> m b -> m b).我将理解如何在最后两次调用itemin中传递修改后的函数p.

令我困惑的另一件事是处理csin item- 它不返回(头部,尾部)对.不应该重新定义如下,因为item解析器根据文件消耗一个字符:

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

Answer 1

我将尝试提供更多关于 的信息>>。\n正如您在其他答案中看到的那样，您应该将 do 的糖化为>>=，以便更好地理解正在发生的情况。

\n\n

例如，让我们编写一个解析器来解析两个字符并返回它们。

\n\n

twoChars :: Parser (Char,Char)\ntwoChars = do\n  i <- item\n  j <- item\n  return (i,j)\n

\n\n

现在，脱糖do语法进行脱糖处理：

\n\n

twoChars :: Parser (Char,Char)\ntwoChars =\n  item >>= (\\i ->\n  item >>= (\\j ->\n  return (i,j) ) )\n

\n\n

为了清楚起见，我加了括号。如您所见，第二个解析器item接收匿名函数中第一个解析器的结果item，结果绑定到i. 这>>=函数接受一个解析器、一个函数，并返回一个解析器。理解它的最好方法是将其插入定义中：

\n\n

f = \\i \xe2\x86\x92 item \xc2\xbb= \\j \xe2\x86\x92 return (i,j)\ntwoChars = item >>= f\ntwoChars = Parser (\\cs -> concat [parse (f a) cs\' | (a,cs\') <- parse item cs])\n

\n\n

所以我们得到了一个新的解析器。尝试想象它对输入“abc”会做什么。cs绑定到“abc”，项目解析器用于返回[(\'a\',"bc")]。现在，我们申请f到\'a\'，以获取新的解析器：

\n\n

item >>= \\j -> return (\'a\',j)\n

\n\n

该解析器将把剩下的字符串传递给处理 ( )，并且当上面绑定到时"bc"，它将使用item解析器取出。然后我们得到一条语句，该语句放入解析器中，然后返回b\\jbreturn (\'a\',\'b\')(\'a\',\'b\')(\'a\',\'b\')。

\n\n

我希望这能澄清信息流是如何发生的。现在，假设您想忽略一个字符。你可以这样做。

\n\n

twoChars :: Parser (Char,Char)\ntwoChars =\n  item >>= \\i ->\n  item >>= \\j ->\n  item >>= \\k ->\n  return (i,k)\n

\n\n

对于示例“abc”来说，j绑定到它是可以的，你从不使用它。\'b\'我们可以这样替换j为_.

\n\n

twoChars :: Parser (Char,Char)\ntwoChars =\n  item >>= \\i ->\n  item >>= \\_ ->\n  item >>= \\k ->\n  return (i,k)\n

\n\n

但我们也知道>> :: m a -> m b -> m b可以定义为：

\n\n

p >> q = p >>= \\_ -> q\n

\n\n

所以我们剩下

\n\n

twoChars :: Parser (Char,Char)\ntwoChars =\n  item >>= \\i ->\n  item >>\n  item >>= \\k ->\n  return (i,k)\n

\n\n

最后，您可以将其重新糖化为do. 将简单的糖应用>>到无边界的单行语句中。其结果是：

\n\n

twoChars :: Parser (Char,Char)\ntwoChars = do\n  i <- item\n  item\n  j <- item\n  return (i,j)\n

\n\n

希望这能澄清一些事情。

\n