第 20 章：使用 OCamllex 与 Menhir 解析（Parsing with OCamllex and Menhir）

原文：Anil Madhavapeddy and Yaron Minsky, Real World OCaml: Functional Programming for the Masses, Second Edition, Chapter 20。维护者已确认本书为开源书籍，可翻译并发布用于学习研究。

本章包含 Jason Hickey 的贡献。

许多编程任务都始于解释某种结构化文本数据。解析（parsing）就是把这类数据转换成容易编程处理的数据结构的过程。对于简单格式，以临时方式解析数据通常就够了，比如先把数据拆成行，再用正则表达式把这些行拆成组成部分。

但在解析更复杂的数据时，这种简单方法往往会失效，尤其是解析那种带有递归结构的数据，例如完整编程语言，或 JSON、XML 这类灵活数据格式。准确、高效地解析这类格式，同时提供有用错误消息，是一项复杂任务。

很多时候，你能找到现有解析库来替你处理这些问题。但当确实需要编写解析器时，也有工具可以简化这项任务，这类工具就是解析器生成器（parser generator）。解析器生成器根据你想解析的数据格式规格创建解析器，并用它生成解析器代码。

解析器生成器有很长历史，包括 lex 和 yacc 这类可以追溯到 20 世纪 70 年代早期的工具。OCaml 有自己的替代品，包括替代 lex 的 ocamllex，以及替代 yacc 的 ocamlyacc 和 menhir。本章会通过实现一个 JSON 序列化格式解析器来探索这些工具。第 19 章“处理 JSON 数据（Handling JSON Data）”已经讨论过 JSON。

解析是一个宽泛且往往很复杂的话题。本章目的不是教授所有理论问题，而是以务实方式介绍如何在 OCaml 中构建解析器。

注：Menhir 与 ocamlyacc

Menhir 是另一种解析器生成器，通常优于历史悠久的 ocamlyacc。ocamlyacc 已经存在很多年。Menhir 大体兼容 ocamlyacc 语法，因此通常可以直接切换到 Menhir，并期望旧代码能工作（Menhir 手册中描述了一些细微差异）。

Menhir 最大的优势是错误消息通常更容易被人理解，而且它生成的解析器完全可重入，也更容易在 OCaml 模块中参数化。我们建议所有新开发代码都使用 Menhir，而不是 ocamlyacc。

Menhir 并不直接随 OCaml 发行，但可以通过 OPAM 安装：

$ opam install menhir

20.1 词法分析与解析（Lexing and Parsing）

传统上，解析会被分成两部分：词法分析（lexical analysis，也称 lexing），这是一种简化的解析阶段，会把字符流转换成逻辑 token 流；以及完整解析阶段，它会把 token 流转换成最终表示，通常是称为抽象语法树（abstract syntax tree，AST）的树状数据结构。

“解析”这个术语容易让人困惑，因为它既用于指从文本数据到结构化数据的整个过程，也更具体地用于指从 token 流到 AST 的第二阶段。因此从这里开始，我们只用“解析”指第二阶段。

我们在 JSON 格式语境下考虑词法分析和解析。下面是一段文本片段，表示一个 JSON 对象，其中包含一个标记为 title 的字符串，以及一个数组，数组中有两个对象，每个对象都有一个名称和邮政编码数组：

{
  "title": "Cities",
  "cities": [
    { "name": "Chicago",  "zips": [60601] },
    { "name": "New York", "zips": [10004] }
  ]
}

从语法层面看，可以把 JSON 文件看成一系列简单逻辑单元，例如花括号、方括号、逗号、冒号、标识符、数字和带引号字符串。因此，可以把 JSON 文本表示成下面这个类型的 token 序列：

type token =
  | NULL
  | TRUE
  | FALSE
  | STRING of string
  | INT of int
  | FLOAT of float
  | LEFT_BRACK
  | RIGHT_BRACK
  | LEFT_BRACE
  | RIGHT_BRACE
  | COMMA
  | COLON
  | EOF

注意，这种表示会丢失一些原始文本信息。例如，空白不会被表示出来。token 流忘掉某些理解含义不需要的原始文本细节，是常见且确实有用的做法。

如果把前面的示例转换成这些 token 的列表，它大概会像这样：

[ LEFT_BRACE; STRING("title"); COLON; STRING("Cities");
  COMMA; STRING("cities"); ... ]

这种表示比原始文本更容易处理，因为它去掉了一些不重要的语法细节，并加入了有用结构。但它仍然比第 19 章用于表示 JSON 数据的简单 AST 低层得多：

type value =
  [ `Assoc of (string * value) list
  | `Bool of bool
  | `Float of float
  | `Int of int
  | `List of value list
  | `Null
  | `String of string ]

这种表示比 token 流丰富得多，捕获了 JSON 值可以彼此嵌套这一事实，也捕获了 JSON 拥有多种值类型，包括数字、字符串、数组和对象。我们将要编写的解析器会把 token 流转换成这个 AST 类型的值。对于前面的 JSON 示例，结果如下：

`Assoc
  ["title", `String "Cities";
   "cities", `List
     [`Assoc ["name", `String "Chicago"; "zips", `List [`Int 60601]];
      `Assoc ["name", `String "New York"; "zips", `List [`Int 10004]]]]

20.2 定义解析器（Defining a Parser）

解析器规格文件的后缀是 .mly，包含两个部分，中间由单独一行 %% 字符组成的分隔线隔开。文件第一部分用于声明，包括 token 与类型规格、优先级指令以及其他输出指令；第二部分用于指定待解析语言的语法。

先声明 token 列表。token 使用语法 %token <type> uid 声明，其中 <type> 是可选的，uid 是大写标识符。对 JSON 来说，需要数字、字符串、标识符和标点符号的 token：

%token <int> INT
%token <float> FLOAT
%token <string> ID
%token <string> STRING
%token TRUE
%token FALSE
%token NULL
%token LEFT_BRACE
%token RIGHT_BRACE
%token LEFT_BRACK
%token RIGHT_BRACK
%token COLON
%token COMMA
%token EOF

<type> 规格表示 token 携带一个值。INT token 携带整数值，FLOAT 携带 float 值，STRING 携带 string 值。其余 token，例如 TRUE、FALSE 或标点符号，不关联任何值，因此可以省略 <type> 规格。

20.2.1 描述语法（Describing the Grammar）

接下来需要指定 JSON 表达式的语法。和许多解析器生成器一样，menhir 使用上下文无关语法（context-free grammar）表达语法。（更准确地说，menhir 支持 LR(1) 语法，但这里会忽略这个技术区别。）可以把上下文无关语法看成一组抽象名称，称为非终结符（non-terminal symbols），以及一组规则，用来把非终结符转换成 token 和非终结符组成的序列。如果可以从一个特殊的起始符号出发，应用语法规则产生一系列转换，并生成目标 token 序列，那么该 token 序列就可以被这个语法解析。

我们先声明 JSON 语法的起始符号是非终结符 prog，并声明解析后 prog 值应该转换成 Json.value option 类型的 OCaml 值。然后用 %% 结束解析器声明部分：

%start <Json.value option> prog
%%

有了这些之后，就可以开始指定产生式。在 menhir 中，产生式被组织成规则；每条规则列出给定非终结符的所有可能产生式。例如，下面是 prog 的规则：

prog:
  | EOF       { None }
  | v = value { Some v }
  ;

这段语法让人联想到 OCaml 的 match 表达式。竖线分隔各个产生式，花括号中包含语义动作：生成与相关产生式对应的 OCaml 值的 OCaml 代码。语义动作是任意 OCaml 表达式，会在解析期间求值，生成附加到规则中非终结符上的值。

prog 有两种情况：要么出现 EOF，这意味着文本为空，所以没有 JSON 值可读，于是返回 OCaml 值 None；要么出现一个 value 非终结符实例，它对应格式良好的 JSON 值，于是把相应的 Json.value 包在 Some 标签中。注意，在 value 情况中，我们写了 v = value，把对应的 OCaml 值绑定到变量 v，随后可在该产生式花括号中使用。

现在看一个更复杂的例子：value 符号的规则。

value:
  | LEFT_BRACE; obj = object_fields; RIGHT_BRACE
    { `Assoc obj }
  | LEFT_BRACK; vl = array_values; RIGHT_BRACK
    { `List vl }
  | s = STRING
    { `String s }
  | i = INT
    { `Int i }
  | x = FLOAT
    { `Float x }
  | TRUE
    { `Bool true }
  | FALSE
    { `Bool false }
  | NULL
    { `Null }
  ;

根据这些规则，JSON value 可以是：

• 由花括号括起来的对象
• 由方括号括起来的数组
• 字符串、整数、浮点数、布尔值或 null 值

每个产生式中，花括号里的 OCaml 代码展示了相关对象应转换成什么。注意，这里仍然依赖两个尚未定义的非终结符：object_fields 和 array_values。接下来会看看它们如何解析。

20.2.2 解析序列（Parsing Sequences）

下面是 object_fields 规则。它实际上只是一个很薄的包装，会反转后续 rev_object_fields 规则返回的列表。注意，rev_object_fields 的第一个产生式左侧为空，因为这次匹配的是空 token 序列。注释 (* empty *) 用于明确说明这一点：

object_fields: obj = rev_object_fields { List.rev obj };

rev_object_fields:
  | (* empty *) { [] }
  | obj = rev_object_fields; COMMA; k = ID; COLON; v = value
    { (k, v) :: obj }
  ;

这些规则之所以这样组织，是因为 menhir 会生成左递归解析器，也就是说，构造出的下推自动机在使用左递归定义时需要更少栈空间。下面这个右递归规则接受相同输入，但解析对象字段定义时，需要线性栈空间：

(* Inefficient right-recursive rule *)
object_fields:
  | (* empty *) { [] }
  | k = STRING; COLON; v = value; COMMA; obj = object_fields
    { (k, v) :: obj }

另一种方式是保留左递归定义，并直接按从左到右顺序构造返回值。这甚至更低效，因为以这种方式逐步构建列表的复杂度是列表长度的二次方：

(* Quadratic left-recursive rule *)
object_fields:
  | (* empty *) { [] }
  | obj = object_fields; COMMA; k = STRING; COLON; v = value
    { obj @ [k, v] }
  ;

像这样组装列表是大多数真实语法中的常见需求，而前面的规则（虽然有助于说明解析如何工作）相当啰嗦。Menhir 拥有扩展标准库，提供了一些内置规则来简化这种处理。这些规则在 Menhir 手册中有详细说明，包括可选值、带可选分隔符的值对，以及元素列表（也带可选分隔符）。

下面是使用这些更简洁 Menhir 规则的 JSON 语法版本。注意，separated_list 同时用于用一条规则解析 JSON 对象和列表。

%token <int> INT
%token <float> FLOAT
%token <string> STRING
%token TRUE
%token FALSE
%token NULL
%token LEFT_BRACE
%token RIGHT_BRACE
%token LEFT_BRACK
%token RIGHT_BRACK
%token COLON
%token COMMA
%token EOF
%start <Json.value option> prog
%%

prog:
  | v = value { Some v }
  | EOF       { None   } ;

value:
  | LEFT_BRACE; obj = obj_fields; RIGHT_BRACE { `Assoc obj  }
  | LEFT_BRACK; vl = list_fields; RIGHT_BRACK { `List vl    }
  | s = STRING                                { `String s   }
  | i = INT                                   { `Int i      }
  | x = FLOAT                                 { `Float x    }
  | TRUE                                      { `Bool true  }
  | FALSE                                     { `Bool false }
  | NULL                                      { `Null       } ;

obj_fields:
    obj = separated_list(COMMA, obj_field)    { obj } ;

obj_field:
    k = STRING; COLON; v = value              { (k, v) } ;

list_fields:
    vl = separated_list(COMMA, value)         { vl } ;

可以在 dune 文件中添加 (menhir) stanza 接入 menhir。这会告诉构建系统改用 menhir 而不是 ocamlyacc 处理后缀为 .mly 的文件：

(menhir
 (modules parser))

(ocamllex lexer)

(library
 (name json_parser)
 (modules parser lexer json)
 (libraries core))

20.3 定义词法分析器（Defining a Lexer）

现在可以用 ocamllex 定义词法分析器，把输入文本转换成 token 流。词法分析器的规格放在后缀为 .mll 的文件中。

20.3.1 OCaml 前言（OCaml Prelude）

我们逐段走读词法分析器定义。第一段是可选的 OCaml 代码片段，由一对花括号包围：

{
open Lexing
open Parser

exception SyntaxError of string
}

这段代码用于定义后续 OCaml 代码片段所需的工具函数，也用于通过打开有用模块和定义异常 SyntaxError 来设置环境。你在这里定义的任何 OCaml 函数，随后都可以在词法分析器定义的余下部分中使用。

20.3.2 正则表达式（Regular Expressions）

词法分析文件的下一部分，是一组具名正则表达式。它们在语法上看起来像普通 OCaml let 绑定，但实际上这是声明正则表达式的专用语法。下面是一个例子：

let int = '-'? ['0'-'9'] ['0'-'9']*

这里的语法是 OCaml 语法与传统正则表达式语法的混合体。int 正则表达式指定一个可选的前导 -，后跟一个从 0 到 9 的数字，再后跟任意数量从 0 到 9 的数字。问号用于表示正则表达式中的可选组成部分；方括号用于指定范围；* 运算符用于表示（可能为空的）重复。

浮点数的指定方式类似，但需要处理小数点和指数。我们通过构建一系列具名正则表达式让表达式更容易阅读，而不是创建一个庞大且难以穿透的表达式：

let digit = ['0'-'9']
let frac = '.' digit*
let exp = ['e' 'E'] ['-' '+']? digit+
let float = digit* frac? exp?

最后，定义空白、新行和标识符：

let white = [' ' '\t']+
let newline = '\r' | '\n' | "\r\n"
let id = ['a'-'z' 'A'-'Z' '_'] ['a'-'z' 'A'-'Z' '0'-'9' '_']*

newline 引入了 | 运算符，它允许多个可选正则表达式之一匹配（在这里是 CR、LF 或 CRLF 等各种回车换行组合）。

20.3.3 词法分析规则（Lexing Rules）

词法分析规则本质上是消费数据并产生 OCaml 表达式的函数，这些表达式会求值为 token。这些 OCaml 表达式可以相当复杂，可以使用副作用，也可以在规则主体中调用其他规则。我们来看用于解析 JSON 表达式的 read 规则：

rule read =
  parse
  | white    { read lexbuf }
  | newline  { next_line lexbuf; read lexbuf }
  | int      { INT (int_of_string (Lexing.lexeme lexbuf)) }
  | float    { FLOAT (float_of_string (Lexing.lexeme lexbuf)) }
  | "true"   { TRUE }
  | "false"  { FALSE }
  | "null"   { NULL }
  | '"'      { read_string (Buffer.create 17) lexbuf }
  | '{'      { LEFT_BRACE }
  | '}'      { RIGHT_BRACE }
  | '['      { LEFT_BRACK }
  | ']'      { RIGHT_BRACK }
  | ':'      { COLON }
  | ','      { COMMA }
  | _ { raise (SyntaxError ("Unexpected char: " ^ Lexing.lexeme lexbuf)) }
  | eof      { EOF }

这些规则的结构与模式匹配非常相似，只是左侧的变体被替换成了正则表达式。右侧子句是该规则解析得到的 OCaml 返回值。规则中的 OCaml 代码有一个名为 lexbuf 的参数，它定义输入，包括输入文件中的位置，以及被正则表达式匹配到的文本。

第一个 white { read lexbuf } 会递归调用词法分析器。也就是说，它跳过输入空白并返回后续 token。动作 newline { next_line lexbuf; read lexbuf } 类似，但我们用它通过文件顶部定义的工具函数推进词法分析器的行号。直接看第三个动作：

| int { INT (int_of_string (Lexing.lexeme lexbuf)) }

这个动作指定：当输入匹配 int 正则表达式时，词法分析器应该返回表达式 INT (int_of_string (Lexing.lexeme lexbuf))。表达式 Lexing.lexeme lexbuf 返回正则表达式匹配到的完整字符串。在本例中，该字符串表示一个数字，所以用 int_of_string 函数把它转换成数字。

每种不同 token 都有对应动作。像 "true" { TRUE } 这样的字符串表达式用于关键字，特殊字符也有动作，例如 '{' { LEFT_BRACE }。

其中一些模式会重叠。例如，正则表达式 "true" 也能被 id 模式匹配。当输入前缀被多个模式匹配时，ocamllex 使用下面的消歧规则：

• 最长匹配总是获胜。例如，输入开头 trueX: 167 会让正则表达式 "true" 匹配四个字符，也会让 id 匹配五个字符。更长的匹配获胜，返回值是 ID "trueX"。
• 如果所有匹配长度相同，则第一个动作获胜。如果输入是 true: 167，那么 "true" 和 id 都匹配前四个字符；"true" 在前，所以返回值是 TRUE。

注：未使用的词法分析值

在我们的解析器中，并没有使用词法分析器里定义的所有 token 正则表达式。例如，id 未使用，因为我们不解析对象标识符的未加引号字符串（JavaScript 允许这种写法，但 JSON 这个子集不允许）。如果在词法分析器中为它包含一个 token 模式匹配，就必须相应调整解析器，添加 %token <string> ID。这又会触发“unused”警告，因为解析器从不构造类型为 ID 的值：

File "parser.mly", line 4, characters 16-18:
Warning: the token ID is unused.

像这里这样定义未使用的正则表达式完全没问题，并可以按需把它们接入解析器。例如，如果为解析器添加支持未加引号字符串标识符的非标准 JSON 扩展，就可能会用到 ID。

20.3.4 递归规则（Recursive Rules）

与许多其他词法分析器生成器不同，ocamllex 允许在同一个文件中定义多个词法分析器，而且这些定义可以递归。在本例中，我们使用递归通过下面这条规则定义匹配字符串字面量：

and read_string buf =
  parse
  | '"'       { STRING (Buffer.contents buf) }
  | '\\' '/'  { Buffer.add_char buf '/'; read_string buf lexbuf }
  | '\\' '\\' { Buffer.add_char buf '\\'; read_string buf lexbuf }
  | '\\' 'b'  { Buffer.add_char buf '\b'; read_string buf lexbuf }
  | '\\' 'f'  { Buffer.add_char buf '\012'; read_string buf lexbuf }
  | '\\' 'n'  { Buffer.add_char buf '\n'; read_string buf lexbuf }
  | '\\' 'r'  { Buffer.add_char buf '\r'; read_string buf lexbuf }
  | '\\' 't'  { Buffer.add_char buf '\t'; read_string buf lexbuf }
  | [^ '"' '\\']+
    { Buffer.add_string buf (Lexing.lexeme lexbuf);
      read_string buf lexbuf
    }
  | _ { raise (SyntaxError ("Illegal string character: " ^ Lexing.lexeme lexbuf)) }
  | eof { raise (SyntaxError ("String is not terminated")) }

这条规则接收一个 buf : Buffer.t 参数。如果遇到终止双引号 "，就把缓冲区内容作为 STRING 返回。

其他情况用于处理字符串内容。动作 [^ '"' '\\']+ { ... } 匹配不包含双引号或反斜杠的普通输入。以反斜杠 \ 开头的动作定义如何处理转义序列。在每种情况下，最后一步都包含对词法分析器的递归调用。

这样就覆盖了词法分析器。接下来需要把词法分析器和解析器组合起来。

注：处理 Unicode

这里略过了一个重要细节：解析 Unicode 字符，以处理世界上各种书写系统的完整范围。OCaml 有几个第三方 Unicode 处理方案，它们在灵活性和复杂度上各不相同：

• Uutf 是一个非阻塞、流式 Unicode 编解码器，可作为独立库使用。它还伴随 Uunf 文本归一化库和 Uucd Unicode 字符数据库库。还有一个健壮的 JSON 解析器，展示了如何在自己的库中使用 Uutf。
• Camomile 支持完整范围的 Unicode 字符类型、约 200 种编码转换，以及排序和区域设置敏感的大小写映射。
• sedlex 是一个 Unicode 词法分析器生成器，可以作为具备 Unicode 感知能力的 ocamllex 替代品。

所有这些库都可以通过 opam 以各自名称安装。

20.4 合并到一起（Bringing It All Together）

最后一部分，需要组合词法分析器和解析器。正如 parser.mli 的类型定义所示，解析函数期望一个类型为 Lexing.lexbuf -> token 的词法分析器，以及一个 lexbuf：

val prog : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> Json.value option

开始词法分析之前，先定义一些处理解析错误的函数。目前有两种错误：Parser.Error 和 Lexer.SyntaxError。遇到错误时，一个简单方案是打印错误并放弃：

open Core
open Lexer
open Lexing

let print_position outx lexbuf =
  let pos = lexbuf.lex_curr_p in
  fprintf outx "%s:%d:%d" pos.pos_fname
    pos.pos_lnum (pos.pos_cnum - pos.pos_bol + 1)

let parse_with_error lexbuf =
  try Parser.prog Lexer.read lexbuf with
  | SyntaxError msg ->
    fprintf stderr "%a: %s\n" print_position lexbuf msg;
    None
  | Parser.Error ->
    fprintf stderr "%a: syntax error\n" print_position lexbuf;
    exit (-1)

“遇到第一个错误就放弃”的方法很容易实现，但并不友好。一般来说，错误处理可能相当复杂，这里不会讨论。不过，Menhir 解析器定义了额外机制，可以用于尝试从错误中恢复。这些机制在其参考手册中有详细说明。

标准词法分析库 Lexing 提供了 from_channel 函数，用于从通道读取输入。下面的函数描述了整体结构：使用 Lexing.from_channel 函数构造 lexbuf，然后把它与词法分析函数 Lexer.read 一起传给 Parser.prog 函数。Parsing.prog 到达文件末尾时返回 None。这里还定义了一个未展示的函数 Json.output_value，用于打印 Json.value：

let rec parse_and_print lexbuf =
  match parse_with_error lexbuf with
  | Some value ->
    printf "%a\n" Json.output_value value;
    parse_and_print lexbuf
  | None -> ()

let loop filename () =
  let inx = In_channel.create filename in
  let lexbuf = Lexing.from_channel inx in
  lexbuf.lex_curr_p <- { lexbuf.lex_curr_p with pos_fname = filename };
  parse_and_print lexbuf;
  In_channel.close inx

let () =
  Command.basic_spec ~summary:"Parse and display JSON"
    Command.Spec.(empty +> anon ("filename" %: string))
    loop
  |> Command_unix.run

下面是一个可用于测试刚写代码的测试输入文件：

true
false
null
[1, 2, 3., 4.0, .5, 5.5e5, 6.3]
"Hello World"
{ "field1": "Hello",
  "field2": 17e13,
  "field3": [1, 2, 3],
  "field4": { "fieldA": 1, "fieldB": "Hello" }
}

现在使用这个文件构建并运行示例，就能看到完整解析器在工作：

$ dune exec ./test.exe test1.json
true
false
null
[1, 2, 3.000000, 4.000000, 0.500000, 550000.000000, 6.300000]
"Hello World"
{ "field1": "Hello",
  "field2": 170000000000000.000000,
  "field3": [1, 2, 3],
  "field4": { "fieldA": 1,
  "fieldB": "Hello" } }

在这个简单错误处理方案中，错误是致命的，会让程序以非零退出码终止：

$ cat test2.json
{ "name": "Chicago",
  "zips": [12345,
}
{ "name": "New York",
  "zips": [10004]
}
$ dune exec ./test.exe test2.json
test2.json:3:2: syntax error
[255]

至此，解析教程就结束了。顺便注意，本章定义的 JSON 多态变体类型，实际上与第 19 章解释的 Yojson 表示在结构上兼容。这意味着你可以拿这个解析器与 Yojson 的辅助函数一起使用，构建更复杂的应用。