[翻译] Monadic parsing in Haskell

发表于 2025-08-27 更新于 2025-08-28 分类于 Parser Combinators

引言（Introduction）

本文是一篇关于在 Haskell 中定义递归下降解析器（recursive descent parsers）的教程。秉持“一站式服务”的精神，文章把三个领域的材料整合到一个来源中。这三个领域分别是函数式解析器（functional parsers）（Burge, 1975; Wadler, 1985; Hutton, 1992; Fokker, 1995）、使用单子（monads）来组织函数式程序（Wadler, 1990, 1992a, 1992b），以及在 Haskell 中用于单子程序的特殊语法（Jones, 1995; Peterson 等, 1996）。更具体地说，本文展示了如何在 Haskell 中使用 do 记法（do notation）来定义单子解析器。

当然，手写的递归下降解析器在效率上不如由工具生成的自底向上解析器（Aho 等, 1986; Mogensen, 1993; Gill 与 Marlow, 1995）。然而，对于许多研究型应用，一个简单的递归下降解析器已足够。此外，解析器生成器通常仅提供一套固定的组合子（combinators）来描述文法，而本文的方法则完全可扩展：解析器是第一类值（first-class values），我们可以充分利用 Haskell 的能力来为特定应用定义新的组合子。该方法也是展示函数式编程优雅性的一个极佳例子。

本文的目标读者是熟悉 Haskell 并且学过“文法与解析”课程的优秀本科生。具备一些函数式解析器的知识会有帮助，但不要求具备单子方面的经验。基于本文而来的一个 Haskell 库可在网页上获取： http://www.cs.nott.ac.uk/Department/Staff/gmh/bib.html#pearl（链接已失效）

解析器的类型（A type for parsers）

我们先为解析器（parser）定义一个类型：

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

也就是说，解析器是一个以字符字符串为参数并返回结果列表的函数。约定是：空结果列表表示解析器失败，而非空列表表示成功。成功时，每个结果是一个二元组，其第一分量是通过解析和处理参数字符串前缀得到的类型为 a 的值，第二分量是未被解析的参数字符串后缀。返回结果列表使我们能够为二义性文法（ambiguous grammars）构建解析器：当参数字符串可被多种方式解析时，将返回多个结果。

一个解析器的单子（A monad of parsers）

我们定义的第一个解析器是 item：如果参数字符串非空，它会成功地消费第一个字符；否则失败：

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

接着我们定义两个反映解析器单子本质的组合子。在 Haskell 中，“单子（monad）”这一概念由一个内置的类定义来刻画：

class Monad m where
   return :: a -> m a
   (>>=) :: m a -> (a -> m b) -> m b

也就是说，如果一个类型构造器（type constructor）m配备了具有上述类型的 return 与 (>>=) 函数，那么它就是类 Monad 的成员。类型构造器 Parser 可以如下成为 Monad 类的一个实例（instance）：

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

解析器 return a 在不消费任何参数字符串的情况下成功，并返回单个值 a。操作符 (>>=) 是解析器的一个“序列操作符（sequencing operator）”。使用由 parse (Parser p) = p 定义的解析器解构函数（deconstructor），解析器 p >>= f 首先将解析器 p 应用于参数字符串 cs，得到形如 (a,cs') 的结果列表，其中 a 是一个值，cs' 是一个字符串。对每个这样的二元组，f a 是一个解析器，被应用到字符串 cs' 上。结果是一个列表的列表，随后被拼接（concatenate）为最终的结果列表。

用于解析器的 return 与 (>>=) 满足一些简单的定律：

           return a >>= f ＝ f a
             p >>= return ＝ p
p >>= (\a -> (f a >>= g)) ＝ (p >>= (\a -> f a)) >>= g

事实上，这些定律对任何单子都必须成立，而不仅仅是解析器这个特例。这些定律断言 —— 忽略右参数传给 (>>=) 时涉及绑定（binding）这一事实 —— return 是 (>>=) 的左、右单位（单位律），并且 (>>=) 具有结合律。单位律允许我们对某些解析器进行化简，而结合律允许在多次串接时省略括号。

do 记法（The do notation）

使用 (>>=) 构造的典型解析器具有如下结构：

p1 >>= \a1 ->
p2 >>= \a2 ->
...
pn >>= \an ->
f a1 a2 ... an

这样的解析器有一个很自然的操作性解读：先应用解析器 p1 并把其结果值记为 a1；然后应用 p2，把其结果值记为 a2；……；接着应用 pn，把其结果值记为 an；最后通过应用一个语义动作（semantic action）f 来组合所有结果。对大多数解析器而言，语义动作通常为 return (g a1 a2 ... an)（其中 g 是某个函数），但并不总是如此。例如，可能需要在返回结果之前解析更多的参数字符串，稍后定义的组合子 chainl1 就是这种情况。

Haskell 为上述形状的解析器提供了特殊语法，使它们可以用如下更易读的形式来表达：

do a1 <- p1
   a2 <- p2
   ...
   an <- pn
   f a1 a2 ... an

如果愿意，这种记法也可以写在单行里，通过使用圆括号与分号来实现：

do {a1 <- p1; a2 <- p2; ...; an <- pn; f a1 a2 ... an}

实际上，Haskell 中的 do 记法可以用于任何单子，不仅仅是解析器。子表达式 ai <- pi 被称为“生成器（generator）”，因为它们为变量 ai 生成值。在一个特殊情形下，如果我们并不关心生成器 ai <- pi 产生的值，那么这个生成器可以简写为仅仅 pi。

示例（Example）。一个消费三个字符、丢弃第二个字符，并把另外两个作为一对返回的解析器可以定义如下：

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

选择组合子（Choice combinators）

我们现在定义两个扩展解析器单子特性的组合子。在 Haskell 中，“带零元的单子（monad with a zero）”以及“带零元与加法的单子（monad with a zero and a plus）”由两个内置类定义来刻画：

class Monad m => MonadZero m where
   zero :: m a
class MonadZero m => MonadPlus m where
   (++) :: m a -> m a -> m a

也就是说，如果一个类型构造器 m 是类 Monad 的成员，且还配备了类型如上所示的值 zero，那么 m 就是类 MonadZero 的成员。类似地，类 MonadPlus 在 MonadZero 的基础上添加了一个具有所示类型的 (++) 运算。类型构造器 Parser 可以如下成为这两个类的实例：

instance MonadZero Parser where
   zero = Parser (\cs -> [])
instance MonadPlus Parser where
   p ++ q = Parser (\cs -> parse p cs ++ parse q cs)

解析器 zero 对所有参数字符串都失败，返回空结果。操作符 (++) 是解析器的（非确定性（non-deterministic））选择操作符（choice operator）。解析器 p ++ q 将两个解析器 p 与 q 都应用到参数字符串上，并把它们的结果列表相连接。

用于解析器的 zero 与 (++) 满足一些简单的定律：

    zero ++ p ＝ p
    p ++ zero ＝ p
p ++ (q ++ r) ＝ (p ++ q) ++ r

事实上，这些定律对任何“带零元与加法的单子”都必须成立。这些定律断言 zero 是 (++) 的左、右单位元，且 (++) 具有结合律。对于解析器这一特例，还可以表明 —— 忽略与 (>>=) 相关的绑定 —— zero 是 (>>=) 的左、右零元，(>>=) 在右侧对 (++) 满足分配律，并且（如果我们忽略解析器返回结果的顺序）(>>=) 在左侧对 (++) 也满足分配律：

              zero >>= f ＝ zero
        p >>= const zero ＝ zero
          (p ++ q) >>= f ＝ (p >>= f) ++ (q >>= f)
p >>= (\a -> f a ++ g a) ＝ (p >>= f) ++ (p >>= g)

零元律允许我们化简某些解析器，而分配律允许我们提升某些解析器的效率。

使用 (++) 构造的解析器，如果参数字符串可以用多种方式解析，将返回多个结果。实际上，我们通常只对第一个结果感兴趣。因此，我们定义一个（确定性的（deterministic））选择操作符 (+++)，其行为与 (++) 相同，但至多返回一个结果：

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p ++ q) cs of
                            [] -> []
                            (x:xs) -> [x])

上面给出的关于 (++) 的所有定律同样也适用于 (+++)。此外，对于 (+++)，左分配律的前提条件会自动满足。

解析器 item 无条件地消费单个字符。为了支持条件解析，我们定义一个组合子 sat，它接受一个谓词（predicate），并产生一个解析器：若单个字符满足该谓词则消费之，否则失败：

sat :: (Char -> Bool) -> Parser Char
sat p = do {c <- item; if p c then return c else zero}

示例（Example）。一个用于特定字符的解析器可以如下定义：

char :: Char -> Parser Char
char c = sat (c ==)

以类似方式，通过给 sat 提供合适的谓词，我们可以定义针对数字、小写字母、大写字母等的解析器。

递归组合子（Recursion combinators）

许多有用的解析器组合子可以通过递归来定义。其中大多数组合子事实上可以为任意“带零元与加法的单子”来定义，但为了清晰起见，下面仅针对解析器这一特例来定义。

解析特定字符串：

string :: String -> Parser String
string "" = return ""
string (c:cs) = do {char c; string cs; return (c:cs)}

解析解析器 p 的重复应用；many 允许零次或多次应用 p，而 many1 允许一次或多次：

many :: Parser a -> Parser [a]
many p = many1 p +++ return []

many1 :: Parser a -> Parser [a]
many1 p = do {a <- p; as <- many p; return (a:as)}

解析解析器 p 的重复应用，应用之间由解析器 sep 的应用分隔，且 sep 的结果值被丢弃：

sepby :: Parser a -> Parser b -> Parser [a]
p `sepby` sep = (p `sepby1` sep) +++ return []

sepby1 :: Parser a -> Parser b -> Parser [a]
p `sepby1` sep = do a <- p
                    as <- many (do {sep; p})
                    return (a:as)

解析解析器 p 的重复应用，应用之间由解析器 op 的应用分隔，其中 op 的结果值是一个被假定为左结合（associate to the left）的运算符，并用于组合来自 p 的结果：

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

假定解析到的运算符右结合（associate to the right）的组合子 chainr 与 chainr1 也可用类似方式定义。

词法组合子（Lexical combinators）

传统上，解析通常由一个词法阶段（lexical phase）先行，该阶段把参数字符串转换为一串记号（tokens）。然而，我们可以通过定义合适的组合子来避免单独的词法阶段。本节我们定义处理参数字符串中各记号之间空白（space）的组合子。用于处理其它词法问题（例如注释与关键字）的组合子也很容易定义。

解析由空格、制表符与换行组成的字符串：
space :: Parser String
space = many (sat isSpace)
使用解析器 p 解析一个记号，并丢弃任何“尾随（trailing）”空白：
token :: Parser a -> Parser a
token p = do {a <- p; space; return a}

解析一个符号记号：

symb :: String -> Parser String
symb cs = token (string cs)

应用解析器 p，并丢弃任何“前导（leading）”空白：

apply :: Parser a -> String -> [(a,String)]
apply p = parse (do {space; p})

示例（Example）

我们用一个简单示例来说明本文定义的组合子。考虑由单个数字与运算符 +、-、*、/ 以及圆括号构成的算术表达式的标准文法（Aho 等, 1986）：

expr ::= expr addop term | term
term ::= term mulop factor | factor
factor ::= digit | ( expr )
digit ::= 0 | 1 | ... | 9
addop ::= + | -
mulop ::= * | /

使用 chainl1 组合子来实现 expr 与 term 的左递归产生式规则，这个文法可以被直接翻译成一个 Haskell 程序，该程序解析表达式并把它们求值为整数：

expr :: Parser Int
addop :: Parser (Int -> Int -> Int)
mulop :: Parser (Int -> Int -> Int)

expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = digit +++ do {symb "("; n <- expr; symb ")"; return n}
digit = do {x <- token (sat isDigit); return (ord x - ord '0')}

addop = do {symb "+"; return (+)} +++ do {symb "-"; return (-)}
mulop = do {symb "*"; return (*)} +++ do {symb "/"; return (div)}

例如，对 apply expr " 1 - 2 * 3 + 4 " 求值将得到单元素结果列表 [(-1,"")]，这正是我们期望的行为。

致谢（Acknowledgements）

感谢 Luc Duponcheel、Benedict Gaster、Mark P. Jones、Colin Taylor 以及 Philip Wadler 对本文诸多草稿提出的宝贵意见。

参考文献（References）

Aho, A., Sethi, R. and Ullman, J. (1986) Compilers – Principles, Techniques and Tools. Addison-Wesley.
Burge, W, H. (1975) Recursive Programming Techniques. Addison-Wesley.
Fokker, J. (1995) Functional parsers. Lecture Notes of the Baastad Spring School on Functional Programming.
Gill, A. and Marlow, S. (1995) Happy: the parser generator for Haskell. University of Glasgow. Hutton, G. (1992) Higher-order functions for parsing. J. Functional Programming, 2(3), 323–343.
Jones, M. P. (1995) A system of constructor classes: overloading and implicit higher-order polymorphism. J. Functional Programming, 5(1), 1–35.
Mogensen, T. (1993) Ratatosk: A parser generator and scanner generator for Gofer. University of Copenhagen (DIKU).
Peterson, J. et al. (1996) The Haskell Language Report, version 1.3. Research report YALEU/DCS/RR-1106, Yale University.
Wadler, P. (1985) How to replace failure by a list of successes. Proc. Conf. on Functional Programming and Computer Architecture. Springer-Verlag.
Wadler, P. (1990) Comprehending monads. Proc. ACM Conf. on Lisp and Functional Pro- gramming.
Wadler, P. (1992a) The essence of functional programming. Proc. Principles of Programming Languages.
Wadler, P. (1992b) Monads for functional programming. In: Broy, M. (ed.), Proc. Marktober- dorf Summer School on Program Design Calculi. Springer-Verlag.

术语对照表（Glossary）

单子（monad）
do 记法（do notation）
解析器（parser）
组合子（combinator）
递归下降解析器（recursive descent parser）
二义性文法（ambiguous grammar）
非确定性（non-deterministic）
确定性（deterministic）
生成器（generator）
语义动作（semantic action）
序列操作符（sequencing operator）
选择操作符（choice operator）
左结合（associate to the left）/ 右结合（associate to the right）
词法阶段（lexical phase）
记号（token）/ 符号记号（symbolic token）
尾随空白（trailing space）/ 前导空白（leading space）
类型构造器（type constructor）
解构函数（deconstructor）
带零元的单子（monad with a zero）
带零元与加法的单子（monad with a zero and a plus）
单位律（unit law）
结合律（associativity law）
分配律（distributivity law）