本章介绍了两个程序生成器：ocamllex，它根据一组正则表达式和相关语义操作生成词法分析器；以及 ocamlyacc，它根据语法和相关语义操作生成语法分析器。
这些程序生成器与大多数 C 编程环境中常见的 lex 和 yacc 命令非常相似。本章假设读者了解 lex 和 yacc：虽然它描述了 ocamllex 和 ocamlyacc 的输入语法以及它们与 lex 和 yacc 的主要区别，但它没有解释在 lex 和 yacc 中编写词法分析器或语法分析器描述的基本知识。不熟悉 lex 和 yacc 的读者可以参考 Aho、Lam、Sethi 和 Ullman 合著的“编译器：原理、技术和工具”（Pearson，2006），或 Levine、Mason 和 Brown 合著的“Lex & Yacc”（O’Reilly，1992）。
ocamllex 命令根据一组正则表达式和附加的语义操作生成词法分析器，其风格类似于 lex。假设输入文件为 lexer.mll，执行
ocamllex lexer.mll
将在文件 lexer.ml 中生成词法分析器的 OCaml 代码。该文件为词法分析器定义中的每个入口点定义了一个词法分析函数。这些函数与入口点的名称相同。词法分析函数接受一个词法分析器缓冲区作为参数，并返回对应入口点的语义属性。
词法分析器缓冲区是一种抽象数据类型，在标准库模块 Lexing 中实现。函数 Lexing.from_channel、Lexing.from_string 和 Lexing.from_function 分别创建从输入通道、字符字符串或任何读取函数读取的词法分析器缓冲区。（参见第 29 章中对 Lexing 模块的描述。）
当与由 ocamlyacc 生成的语法分析器结合使用时，语义操作计算属于由生成的解析模块定义的类型 token 的值。（参见下面对 ocamlyacc 的描述。）
以下命令行选项被 ocamllex 识别。
词法分析器定义的格式如下
{ header }
let ident = regexp …
[refill { refill-handler }]
rule entrypoint [arg1… argn] =
parse regexp { action }
| …
| regexp { action }
and entrypoint [arg1… argn] =
parse …
and …
{ trailer }
注释由 (* 和 *) 标记，与 OCaml 中一样。关键字 parse 可以替换为关键字 shortest，其语义结果将在下面解释。
重新填充处理程序是 4.02 中引入的最新（可选）功能，在下面的小节 17.2.7 中有介绍。
头部 和 尾部 部分是包含在花括号中的任意 OCaml 文本。可以省略其中一个或两个。如果存在，头部文本将按原样复制到输出文件的开头，尾部文本复制到结尾。通常，头部部分包含操作所需的 open 指令，以及操作中可能使用的一些辅助函数。
在头部和入口点之间，可以为经常出现的正则表达式命名。这写成 let ident = regexp。在该声明后的正则表达式中，标识符 ident 可以用作 regexp 的简写。
入口点的名称必须是 OCaml 值的有效标识符（以小写字母开头）。类似地，参数 arg1… argn 必须是 OCaml 的有效标识符。每个入口点都成为一个 OCaml 函数，它接受 n+1 个参数，最后一个隐式参数的类型为 Lexing.lexbuf。从 Lexing.lexbuf 参数中读取字符，并与规则中提供的正则表达式进行匹配，直到输入的前缀与规则中的一个匹配。然后计算相应的操作并将其作为函数的结果返回。
如果多个正则表达式与输入的前缀匹配，则应用“最长匹配”规则：选择与输入的最长前缀匹配的正则表达式。如果出现平局，则选择规则中出现较早的正则表达式。
但是，如果使用关键字 shortest 代替关键字 parse 引入词法分析器规则，则应用“最短匹配”规则：选择输入的最短前缀。如果出现平局，则仍然选择规则中出现较早的正则表达式。此功能并非用于普通的词法分析器，它可以方便 ocamllex 作为简单的文本处理工具。
正则表达式采用 lex 的风格，具有更类似于 OCaml 的语法。
|
关于运算符的优先级，# 优先级最高，其次是 *、+ 和 ?，然后是连接，然后是 | (选择)，最后是 as。
动作是任意的 OCaml 表达式。它们在一个上下文中进行评估，在该上下文中，使用 as 构造定义的标识符绑定到匹配字符串的子部分。此外，lexbuf 绑定到当前词法分析器缓冲区。以下列出了一些 lexbuf 的典型用途，以及与 Lexing 标准库模块提供的词法分析器缓冲区操作结合使用。
as 构造类似于许多正则表达式包提供的“组”。这些变量的类型可以是 string、char、string option 或 char option。
我们首先考虑线性模式的情况，即所有 as 绑定变量都不同的情况。在 regexp as ident 中，ident 的类型通常是 string (或 string option)，除非 regexp 是字符常量、下划线、长度为一的字符串常量、字符集规范或这些的交替。然后，ident 的类型是 char (或 char option)。当总体规则匹配不意味着绑定子模式的匹配时，将引入选项类型。这特别是在 ( regexp as ident ) ? 和 regexp1 | ( regexp2 as ident ) 的情况下。
对 as 绑定变量没有线性限制。当一个变量被多次绑定时，前面的规则需要扩展如下
例如，在 ('a' as x) | ( 'a' (_ as x) ) 中，变量 x 的类型为 char，而在 ("ab" as x) | ( 'a' (_ as x) ? ) 中，变量 x 的类型为 string option。
在某些情况下，成功的匹配可能不会产生唯一的一组绑定。例如，正则表达式 (('a'|"ab") as x) (("ba"|'a') as y) 对 aba 的匹配可能会导致将 x 绑定到 "ab" 并将 y 绑定到 "a"，或者将 x 绑定到 "a" 并将 y 绑定到 "ba"。在这些模棱两可的正则表达式上生成的 ocamllex 自动机将选择一组可能的绑定结果集。所选绑定结果集故意留空。
默认情况下，当 ocamllex 到达词法分析器缓冲区的末尾时，它将静默地调用 lexbuf 结构的 refill_buff 函数，并继续词法分析。有时能够控制重新填充操作非常有用；通常，如果您使用异步计算的库，您可能希望将重新填充操作包装在一个延迟函数中，以避免阻塞同步操作。
从 OCaml 4.02 开始，可以指定一个 重新填充处理程序，这是一个在重新填充发生时被调用的函数。它被传递给词法分析的延续，它对延续有完全的控制权。用作重新填充操作的 OCaml 表达式的类型应该是一个实例
(Lexing.lexbuf -> 'a) -> Lexing.lexbuf -> 'a
其中第一个参数是延续，它捕获 ocamllex 通常执行的处理（重新填充缓冲区，然后再次调用词法分析函数），并且实例化 [’a] 的结果类型应该与所有词法分析规则的结果类型统一。
例如，考虑以下词法分析器，它以任意单子为参数
{
type token = EOL | INT of int | PLUS
module Make (M : sig
type 'a t
val return: 'a -> 'a t
val bind: 'a t -> ('a -> 'b t) -> 'b t
val fail : string -> 'a t
(* Set up lexbuf *)
val on_refill : Lexing.lexbuf -> unit t
end)
= struct
let refill_handler k lexbuf =
M.bind (M.on_refill lexbuf) (fun () -> k lexbuf)
}
refill {refill_handler}
rule token = parse
| [' ' '\t']
{ token lexbuf }
| '\n'
{ M.return EOL }
| ['0'-'9']+ as i
{ M.return (INT (int_of_string i)) }
| '+'
{ M.return PLUS }
| _
{ M.fail "unexpected character" }
{
end
}
所有以 __ocaml_lex 开头的标识符都保留供 ocamllex 使用；不要在您的程序中使用任何此类标识符。
ocamlyacc 命令根据上下文无关语法规范（带有附加的语义操作）生成一个解析器，类似于 yacc。假设输入文件是 grammar.mly，执行
ocamlyacc options grammar.mly
在文件 grammar.ml 中生成解析器的 OCaml 代码，以及在文件 grammar.mli 中的接口。
生成的模块为语法中的每个入口点定义一个解析函数。这些函数的名称与入口点相同。解析函数将词法分析器（从词法分析器缓冲区到标记的函数）和词法分析器缓冲区作为参数，并返回相应入口点的语义属性。词法分析器函数通常是由 ocamllex 程序从词法分析器规范生成的。词法分析器缓冲区是标准库模块 Lexing 中实现的一种抽象数据类型。标记是来自具体类型 token 的值，该类型在由 ocamlyacc 生成的接口文件 grammar.mli 中定义。
语法定义具有以下格式
%{
header
%}
declarations
%%
rules
%%
trailer
注释由 (* 和 *) 分隔，与 OCaml 相同。此外，注释可以在“声明”和“规则”部分中用 /* 和 */ 分隔，与 C 相同。C 风格注释不会嵌套，但 OCaml 风格注释会嵌套。
头部和尾部部分是 OCaml 代码，原样复制到文件 grammar.ml 中。这两部分都是可选的。头部位于输出文件的开头；它通常包含 open 指令和规则语义操作所需的辅助函数。尾部位于输出文件的末尾。
声明每行一个。它们都以 % 符号开头。
open 指令（例如 open Modname）。这是因为头部仅复制到 .ml 输出文件，但不复制到 .mli 输出文件，而 %token 声明的 typexpr 部分被复制到两者中。%type 指令指定类型。-s 选项有效）。 typexpr 部分是一个任意的 OCaml 类型表达式，但所有类型构造函数名称都必须是完全限定的，如上文针对 %token 所述。将优先级和结合性与给定的符号相关联。同一行上的所有符号都具有相同的优先级。它们的优先级高于在 %left、%right 或 %nonassoc 行中之前声明的符号。它们的优先级低于在 %left、%right 或 %nonassoc 行中之后声明的符号。这些符号被声明为左结合 (%left)、右结合 (%right) 或非结合 (%nonassoc)。这些符号通常是标记。它们也可以是虚拟非终结符，用于在规则中使用 %prec 指令。
优先级声明在以下方式中使用，以解决规约/规约和移进/规约冲突
规则的语法与往常一样
nonterminal : symbol … symbol { semantic-action } | … | symbol … symbol { semantic-action } ;
规则也可以包含 %prec symbol 指令，位于右侧部分中，以用给定符号的优先级和结合性覆盖规则的默认优先级和结合性。
语义操作是任意的 OCaml 表达式，它们被计算以生成附加到定义的非终结符的语义属性。语义操作可以使用 $ 符号访问规则右侧符号的语义属性：$1 是第一个（最左侧）符号的属性，$2 是第二个符号的属性，等等。
规则可能包含特殊符号 error，以指示重新同步点，与 yacc 中一样。
不支持规则中间发生的的操作。
非终结符符号类似于常规的 OCaml 符号，只是它们不能以 '（单引号）结尾。
错误恢复的支持如下：当解析器进入错误状态（没有语法规则适用）时，它使用字符串 "syntax error" 作为参数调用名为 parse_error 的函数。默认的 parse_error 函数不执行任何操作并返回，因此启动错误恢复（见下文）。用户可以在语法文件的头部部分定义定制的 parse_error 函数。
如果语法操作之一引发了 Parsing.Parse_error 异常，解析器也将进入错误恢复模式。
在错误恢复模式下，解析器从堆栈中丢弃状态，直到它到达可以移进错误标记的位置。然后，它从输入中丢弃标记，直到它找到三个可以接受的连续标记，并从第一个开始进行处理。如果无法发现可以移进错误标记的状态，则解析器通过引发 Parsing.Parse_error 异常来中止。
有关如何使用错误恢复的更多详细信息和指南，请参考有关 yacc 的文档。
ocamlyacc 命令识别以下选项
在运行时，可以通过在 OCAMLRUNPARAM 环境变量中设置 p 选项来调试 ocamlyacc 生成的解析器（见第 15.2 节）。这将导致执行解析器的下推自动机打印其操作的跟踪（移进的标记、规约的规则等）。跟踪会提到规则号和状态号，可以通过查看 ocamlyacc -v 生成的文件 grammar.output 来解释这些数字。
有史以来最受欢迎的：台式计算器。此程序从标准输入读取算术表达式，每行一个，并打印其值。以下是语法定义
/* File parser.mly */
%token <int> INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS /* lowest precedence */
%left TIMES DIV /* medium precedence */
%nonassoc UMINUS /* highest precedence */
%start main /* the entry point */
%type <int> main
%%
main:
expr EOL { $1 }
;
expr:
INT { $1 }
| LPAREN expr RPAREN { $2 }
| expr PLUS expr { $1 + $3 }
| expr MINUS expr { $1 - $3 }
| expr TIMES expr { $1 * $3 }
| expr DIV expr { $1 / $3 }
| MINUS expr %prec UMINUS { - $2 }
;
以下是对应词法分析器的定义
(* File lexer.mll *)
{
open Parser (* The type token is defined in parser.mli *)
exception Eof
}
rule token = parse
[' ' '\t'] { token lexbuf } (* skip blanks *)
| ['\n' ] { EOL }
| ['0'-'9']+ as lxm { INT(int_of_string lxm) }
| '+' { PLUS }
| '-' { MINUS }
| '*' { TIMES }
| '/' { DIV }
| '(' { LPAREN }
| ')' { RPAREN }
| eof { raise Eof }
以下是将解析器与词法分析器结合在一起的主程序
(* File calc.ml *)
let _ =
try
let lexbuf = Lexing.from_channel stdin in
while true do
let result = Parser.main Lexer.token lexbuf in
print_int result; print_newline(); flush stdout
done
with Lexer.Eof ->
exit 0
要编译所有内容，请执行
ocamllex lexer.mll # generates lexer.ml
ocamlyacc parser.mly # generates parser.ml and parser.mli
ocamlc -c parser.mli
ocamlc -c lexer.ml
ocamlc -c parser.ml
ocamlc -c calc.ml
ocamlc -o calc lexer.cmo parser.cmo calc.cmo
由 ocamllex 生成的确定性自动机最多只能有 32767 个转换。上述消息表明您的词法分析器定义过于复杂，超出了此限制。这通常是由词法分析器定义引起的，这些定义对语言的每个字母关键字都有单独的规则，如下例所示。
rule token = parse
"keyword1" { KWD1 }
| "keyword2" { KWD2 }
| ...
| "keyword100" { KWD100 }
| ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] * as id
{ IDENT id}
为了使生成的自动机保持较小，请仅使用一个通用的“标识符”规则重写这些定义，然后进行哈希表查找以将关键字与标识符区分开来。
{ let keyword_table = Hashtbl.create 53
let _ =
List.iter (fun (kwd, tok) -> Hashtbl.add keyword_table kwd tok)
[ "keyword1", KWD1;
"keyword2", KWD2; ...
"keyword100", KWD100 ]
}
rule token = parse
['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] * as id
{ try
Hashtbl.find keyword_table id
with Not_found ->
IDENT id }
由 ocamlyacc 生成的解析器不是线程安全的。这些解析器依赖于一个内部工作状态，该状态由所有 ocamlyacc 生成的解析器共享。如果您需要线程安全的解析器，menhir 解析器生成器是一个更好的选择。