Parser Monad

在看haskell的相关资料时，发现了一个有趣的系列，叫《functional pearl》里面的每一篇讲了函数式编程中的一个优美的小用法。我看了其中有一篇讲parser的。在这里总结一下。

haskell中可以定义一个Parser Monad。各种各样的Parser的组合可以表示BNF表达式。Parser是一个比较有意思的Monad。

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

我们定义的这个新类型是函数。这个函数输入一个字符串，从中解析出相应类型a的信息，之后返回类型为a的值和剩余待解析的字符串。函数的结果可能为多个值，所以使用数组表示。返回空数组代表解析失败。

然后我们可以将新得到的Parser类型实现为Monad。实现的思路很简单，就是依次运行两个parser。由于两个parser的结果都为数组，这边又用了数组Monad来实现多返回值的计算。

instance Monad Parser where
  return a = Parser \s -> [(a, s)]
  p >>= f = Parser (\s -> do {(a, s') <- parse p s; parse (f a) s'})

到此，我们可以使用>>=操作来顺序组合parser了。在BNF表达式中，除了顺序组合之外还用到了或运算。为了实现或运算，先让Parser实现为MonadPlus。

instance MonadPlus Parser where
  mzero = \_ -> []
  p `mplus` q = Parser (\s -> parse p s ++ parse q s)

mplus会把两个Parser的匹配都记录下来。当第一个Parser匹配失败时mplus的值就是第二个Parser。mzero是mplus的幺元。在实际使用中，常常只需要其中的一个匹配。于是就引入了+++操作：取第一个成功的结果。就相当于BNF表达式中的或运算。

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\s -> sHead $ parse (p `mplus` q) s)
  where
    sHead [] = []
    sHead (x:_) = [x]

我们现在尝试将BNF表达式翻译成Parser。

BNF表达式

expr ::= number add expr | number

Parser

expr = do {number; add; expr} +++ number

这里定义的Parser是有局限的，他无法表左递归的表达式。例如以下这个表达式使用Parser表现就会陷入无限循环。

expr ::= expr add number | number

从一个Monad出发，最后得到像BNF一样的表达式，haskell的抽象能力总是让我惊叹。如果两种语言表达同一种逻辑那他们的最简形式是否总是相同的？