解析器组合子:招牌手艺

解析器的类型:失败乃兵家常事,剩饭也要打包

从零推导。「解析器」是什么?第一版:吃字符串,吐结构——String -> a。立刻发现两个不够:输入可能非法(要能失败),而且一个小解析器通常只消化输入的开头一段,剩下的要留给下一个解析器。两个修正打包进类型:

newtype Parser a = Parser (String -> Maybe (a, String))
--                          ↑输入      ↑失败   ↑结果 ↑没吃完的剩饭

-- 最小积木:满足条件就吃掉一个字符
satisfy :: (Char -> Bool) -> Parser Char
satisfy p = Parser $ \s -> case s of
  (c:rest) | p c -> Just (c, rest)
  _              -> Nothing

digit = satisfy isDigit
char c = satisfy (== c)

就这点东西——一个函数类型加两个小积木。接下来是本章的魔法时刻:因为 Parser 是值,峡谷卷的全部机器直接对它生效。「先解析 A 再解析 B」?那是 Monad 的 do。「解析出来顺手加工一下」?那是 fmap。「A 不行就试 B」?加一个新算子 <|>(左边失败就用右边,来自 Alternative 类)。「零个或多个」?many,many1 要求至少一个:

number :: Parser Int
number = read <$> many1 digit          -- 「至少一个数字,读成 Int」——代码即语法描述

-- 整数:可选负号 + 数字串
integer = do
  sign <- (char '-' >> pure negate) <|> pure id
  sign <$> number

盯着 number 的定义读一遍:「number 是至少一个 digit,fmap read」。代码和你嘴里说出来的语法规则几乎逐词对应——这是组合子对正则的第一记重拳:语法长在有名字、有类型、可单测的定义里,而不是一串 (?:-?\d+) 的密文里。

组合的机器从哪来:亲手给 Parser 装引擎

「峡谷卷机器直接生效」不是黑魔法,是三个 instance,每个都短得可以背下来。装一遍,你对「解析器为什么能组合」的理解就落到实处了:

instance Functor Parser where
  fmap g (Parser p) = Parser $ \s ->
    case p s of
      Nothing        -> Nothing
      Just (a, rest) -> Just (g a, rest)      -- 结果加工一下,剩饭原样传

instance Monad Parser where
  (Parser p) >>= f = Parser $ \s ->
    case p s of
      Nothing        -> Nothing               -- 前一个失败,整体失败
      Just (a, rest) -> runParser (f a) rest  -- 剩饭喂给下一个解析器!

(<|>) :: Parser a -> Parser a -> Parser a
(Parser p) <|> (Parser q) = Parser $ \s ->
  case p s of
    Nothing -> q s                            -- 左边不行,原始输入喂右边
    ok      -> ok

看 >>= 的最后一行:「剩饭喂给下一个」——输入流的推进被藏进了 bind,这正是第 12 章 State 的手法(解析器本质是 State String 加上失败,你可以验证这个说法)。而 <|> 的「失败就用原始输入重试」就是回溯。三十行,一个解析框架的地基打完;正则引擎你写不出来,这个你现在就写得出来——这是两种工具在「可理解性」上的差距。

优先级:chainl1 一招收平

表达式语言的经典难题——「乘除优先于加减、同级左结合」——在组合子世界是一个高阶函数的事。chainl1 p op 读作:「一个或多个 p,用 op 左结合地连起来」:

expr   = term   `chainl1` addop        -- 表达式 = 项 用加减连接
term   = factor `chainl1` mulop        -- 项 = 因子 用乘除连接
factor = between (symbol "(") (symbol ")") expr
     <|> number                        -- 因子 = 括号表达式 | 数

addop  = (node "+" <$ symbol "+") <|> (node "-" <$ symbol "-")
mulop  = (node "*" <$ symbol "*") <|> (node "/" <$ symbol "/")

六行,一门带优先级、带括号、带负号、可扩展的算术语言。优先级藏在哪?藏在调用层级里:expr 由 term 组成、term 由 factor 组成,所以乘除天然比加减「绑得紧」——语法书上的 BNF 分层,一比一翻译成函数分层。下面的工作台跑的就是这套代码的 JS 直译(每个组合子逐个对应),看语法树怎么长、错误怎么报:

先跑好输入看树的形状(乘法节点为什么在加法节点下面?),再试预置的两个坏输入。注意报错的列号:组合子库的标准策略是报告走得最远的那次失败——`2 + * 3` 里,加号后面试过了「括号表达式」和「数字」都不成,失败位置和期望集合(「期望 ( 或数字」)自动汇总。这份报错质量是正则给不了的(正则只会说 no match),也是手写递归下降要额外费力维护的。

为什么说它是「招牌」:pandoc 们的证词

这门手艺在 Haskell 生态里不是玩具,是承重墙。pandoc——你可能用它转过 Markdown——要解析二十几种标记格式,全部构建在组合子上;ShellCheck 解析 Bash 这种「语法灾难现场」级别的语言,靠的是组合子的灵活(Bash 的语法上下文相关,parser generator 反而难伺候);Cardano 的链上数据、Facebook Sigma 的规则语言,同款。生产级的库是 megaparsec(错误信息达到编译器级)和 attoparsec(网络协议级性能),本章的 Maybe 版是它们的教学骨架——真实的库在同一骨架上加了错误累积、状态、回溯控制。

组合子还有一个 parser generator 给不了的能力:解析中途可以跑任意逻辑。「先读一个长度字段 n,再精确读 n 个字节」——这是二进制协议的日常,写出来就是一行 do(n <- length字段; count n byte);而它本质上是上下文相关文法,yacc/ANTLR 的静态文法表达不了,得靠语义动作打补丁。Monad 的「下一步依赖上一步的结果」(第 10 章),在这里变成了真金白银的表达力。

加餐:JSON 解析器,一屏写完

算术只是热身。用同一批积木拼 JSON——语法规则和代码继续逐词对应,整个骨架一屏放得下:

json :: Parser JValue
json = jNull <|> jBool <|> jNumber <|> jString <|> jArray <|> jObject

jNull   = JNull <$ symbol "null"
jBool   = (JBool True <$ symbol "true") <|> (JBool False <$ symbol "false")
jString = JString <$> stringLit                    -- 引号串,处理转义
jArray  = JArray  <$> between (symbol "[") (symbol "]")
                        (json `sepBy` symbol ",")   -- 递归:数组元素又是 json!
jObject = JObject <$> between (symbol "{") (symbol "}")
                        (pair `sepBy` symbol ",")
  where pair = (,) <$> stringLit <* symbol ":" <*> json

两处点睛:jArray 里的递归——json 出现在自己的定义里,毫无特殊处理,因为解析器只是值,值当然可以递归引用(第 7 章惰性的又一次免费午餐);sepBy(逗号分隔列表)这种「语法惯用块」一旦写成组合子,以后所有语言的所有「逗号分隔」全部复用,连同 <*(「两边都解析,只留左边的值」——丢弃冒号的那记)一起进入你的永久工具箱。真实世界的 aeson(Haskell 的 JSON 标准库)骨架与此相同,再加性能工程。面试写 JSON 解析器时,这一屏就是你的地图。