本章描述兩個程式產生器：ocamllex，它從一組具有相關語意動作的正規表示式產生詞法分析器；以及 ocamlyacc，它從具有相關語意動作的文法產生剖析器。
這些程式產生器與大多數 C 程式設計環境中常見的 lex 和 yacc 命令非常相似。本章假設讀者已具備 lex 和 yacc 的基本知識：雖然本章會描述 ocamllex 和 ocamlyacc 的輸入語法以及與 lex 和 yacc 的主要差異，但不會說明在 lex 和 yacc 中撰寫詞法分析器或剖析器描述的基本概念。不熟悉 lex 和 yacc 的讀者可以參考 Aho、Lam、Sethi 和 Ullman 的「Compilers: principles, techniques, and tools」（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 中說明。
header 和 trailer 區段是任意的 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 是字元常數、底線、長度為 1 的字串常數、字元集規格或這些的選擇。然後，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 符號 指令，以使用給定符號的優先順序和結合性覆蓋規則的預設優先順序和結合性。
語義動作是任意的 OCaml 表達式，它們會被求值以產生附加到已定義的非終端符號的語義屬性。語義動作可以使用 $ 符號表示法來訪問規則右側符號的語義屬性：$1 是第一個 (最左邊) 符號的屬性，$2 是第二個符號的屬性，依此類推。
規則可以包含特殊的符號 error 來指示重新同步點，如同 yacc。
不支援在規則中間發生的動作。
非終端符號如同常規的 OCaml 符號，除了它們不能以 ' (單引號) 結尾。
錯誤恢復支援如下：當解析器到達錯誤狀態 (沒有文法規則可以應用) 時，它會呼叫一個名為 parse_error 的函式，並以字串 "syntax 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剖析器產生器是更好的選擇。