解析器组合子

定义

解析器组合子(Parser Combinator)是一种构建解析器的函数式技术:把"解析器"表示为普通的一等函数(输入流到解析结果的映射),再用高阶函数(组合子)把小解析器组合成大解析器,如顺序连接、多选一、重复若干次等。

原理

最简模型中,解析器是类型为"字符串到(结果与剩余输入)列表"的函数。组合子库通常将其组织为 Monad 或 Applicative,使解析逻辑可以用 do 语法或组合算子自然书写,语法定义与可执行代码合一,无需独立的语法文件与代码生成步骤。

实现

Haskell 的 Parsec 及其后继 Megaparsec、attoparsec 是经典实现;Scala 的 fastparse、Rust 的 nom、Python 的 parsy 等把该技术带到各语言。与 yacc/ANTLR 等解析器生成器相比,组合子即写即用、可嵌入宿主语言任意逻辑。

优缺点

优点是类型安全、易组合、错误信息可定制;缺点是朴素实现对左递归文法无能为力,回溯控制不当会引发性能问题,需要借助 try/cut 等原语精细管理。