這些程式碼都是使用 OCaml 實現，並使用了 algeff 與 asai 程式庫

解析器需要完成的任務就是根據規則把一系列 tokens 變成文法樹，並且回報為何解析失敗，一般大學作業等級的編譯器都會讓學生直接使用解析器生成器，如 menhir 這種工具。然而實際上開發真實語言的解析器時，往往會遇到需要錯誤恢復並繼續解析，最後再回報多個錯誤的要求，這時候生成器往往給出很差的結果，甚至乾脆就是做不到的。

然而，手工編寫的解析器通常可維護性相當差劣。一種折衷的方案是所謂的解析器組合子，我過去也曾經介紹過如何利用組合子抽象掉重複的解析規則。但這種方案有個問題，就是回溯必須手動使用 try 組合子來在失敗時恢復狀態，但實務上這創造了相當難以理解的各種 try 安插，當我意識到這是因為 API 需要是兩階段的問題時，我就發現其實 effect handler 正是解決這個問題的好方法。

我本來是直接使用 Effect.Deep 的，但後來發現這種情境直接用 algeff 就足夠了，因此改採這個方案。實際程式碼如下

module Tokens = struct
  type t = Lexer.token Asai.Range.located list
end
module TokenState = Algaeff.State.Make (Tokens)

首先，我假設了 Lexer.token 這個型別存在，並且使用者會輸入一個標記過位置的 token list。接著建立一個狀態模組，這個模組的只有三個用法：

let next_token () =
  match TokenState.get () with
  | [ eof ] -> eof
  | tok :: buf ->
      TokenState.set buf;
      tok
  | [] -> raise Impossible

let shift pos = TokenState.set pos
let current_position () = TokenState.get ()

這段程式巧妙的使用了 OCaml 的不可變 list 的特性，也就是持頭就可以保證資料不被回收

並且提供啟動函數

let run (init : Lexer.token Asai.Range.located list) (f : unit -> 'a) : 'a =
  TokenState.run ~init @@ fun () -> f ()

let catch_parse_error (p : unit -> 'a) : 'a option =
  let pos = current_position () in
  Reporter.try_with
    ~fatal:(fun d ->
      match d.message with
      | Parse_error ->
          shift pos;
          None
      | _ -> Reporter.fatal_diagnostic d)
    (fun () -> Some (p ()))

let consume (predict : Lexer.token) : unit =
  let tok = next_token () in
  if tok.value == predict then ()
  else
    (* raise ... *)

let rec many (p : unit -> 'a) () : 'a list =
  let x = catch_parse_error p in
  match x with
  | None -> []
  | Some x -> x :: many p ()

let ( <|> ) (p1 : unit -> 'a) (p2 : unit -> 'a) () : 'a =
  match catch_parse_error p1 with
  | None -> p2 ()
  | Some x -> x

此外也有更複雜的錯誤恢復機制

let rec program () =
  let x = catch_parse_error top in
  match x with
  | Some x -> x :: program ()
  | None ->
      let pos = next_start_token () in
      shift pos;
      program ()