みたび頭の悪いパーサコンビネータ

Parser OCaml

こないだsheracyさんにパーサの演算子は右結合であるべきか左結合であるべきかと訊ねる機会を持てました。結論としては、>>がHaskellで左結合なのはdo構文のためとかそんなでparsecの<&>が右結合なのも含め深い意味は無いらしくて、結局は使いやすい方を選ぶしかないとのこと。

  • 左結合
    • do構文との相性(でも>>=は右結合風味ですよね？)
    • 左の型推論が先に行われるからエラーメッセージが自然(ホント？)
    • OCamlでは<や>で始まる演算子は全部左結合になるので選択の余地がないとか
    • a <&> b <&> cの結果が((a, b), c)になって(a, b)までパースした段階でなんかできる
  • 右結合
    • 右辺は末尾呼び出しできるので効率的
    • a <&> b <&> cの結果が(a, (b, c))になってリスト構造っぽい

……というわけで両方用意することにしました。(←このへん頭の悪いとこです何よりPascal系にTMTOWTDIは似合わない)

>> 左結合
@>> 右結合

さて、あれからだいぶ直してしまったので1から説明します。
前回までリンク。
http://d.hatena.ne.jp/ytqwerty/20071129#p1
http://d.hatena.ne.jp/ytqwerty/20071204#p1
前回、パーサの型はこうでした。単純でした。

type 'a parser = 
  unit -> (* それまでの計算結果 *)
  p_pos -> (* 位置 *)
  Env.t -> (* 入力 *)
  ('a * p_pos) option

それがこんな風になってしまいました。

type 'a parsed = ('a * Source.index) option;;
type ('a, 'b) progress_parser_forced =
  'a parsed -> (* それまでの計算結果と位置 *)
  (Error.t * Source.index) list -> (* それまでのエラー *)
  Source.t -> (* 入力 *)
  'b parsed * (Error.t * Source.index) list;;
type ('a, 'b) progress_parser = ('a, 'b) progress_parser_forced lazy_t;;
type 'a parser = (unit, 'a) progress_parser;;

位置情報を明示的に持ち運ぶの面倒だぞということで常に抱き合わせちゃえ。
これまでエラーは別キューに追加していたのですがエラー処理の自動化を推し進めて考えるとバラの方が便利だからバラに。引数にもあるのは、末尾呼び出しができるようにするためです。
lazy_tは、let rec対策。前回はlet rec parser () = p_do (...)としてましたが、これですと毎回パーサの組み立てから全部やり直すことになっていました。let rec parser = lazy (...)ですと、1度組み立てられたパーサがキャッシュされている寸法。
使用例はこんなです。

module CalcParser (Error: CHAR_ERROR) (Source: SOURCE with type element = char) = struct
  open ValueCombinator;; (* v_XXXX等のユーティリティ *)
  module U = ParserCombinator (Error) (Source);;
  open U;;
  module C = CharParser (Error) (Source);;
  open C;;
  let sign: int parser = (
    p_char '+' // v_constant 1 @|| 
    p_char '-' // v_constant (-1)
  );;
  let digit: int parser = (
    p_char_range '0' '9' // (fun () x -> Char.code x - Char.code '0')
  );;
  let number: int parser = (
    digit >>
    (digit // (fun x y -> x * 10 + y)) /*/ v_identity
  );;
  let rec term: int parser = lazy (Lazy.force (
    number @||
    (p_char '(' // v_ignore |>> (sum |>> p_char ')' // v_ignore)) @||
    (sign |>> term // ( * ))
  ))
  and prod: int parser = lazy (Lazy.force (
    term >> (
      (p_char '*' // v_ignore |>> term // ( * )) @||
      (p_char '/' // v_ignore |>> term // ( / ))
    ) /*/ v_identity
  ))
  and sum: int parser = lazy (Lazy.force (
    prod >> (
      (p_char '+' // v_ignore |>> prod // ( + )) @||
      (p_char '-' // v_ignore |>> prod // ( - ))
    ) /*/ v_identity
  ));;
  let start: int parser = sum >> p_char '\n' // v_ignore;;
end;;

parsecがdo構文を使って結果の計算ができるのに比べたら、ひたすらそれまでの値を今取ってきた値で更新する関数を細切れに渡しているのは不恰好かもしれません。OCamlでもdo構文モドキができるのはご存知の通りです。
なぜdo構文モドキを採用しないかといいますと、エラー処理のためです。
仮にこんな風に書いたとします。

  and sum: int parser = lazy (Lazy.force (
    prod >>= fun x -> (
      (p_char '+' >>= fun _ -> prod >>= fun y -> return (x + y)) @||
      (p_char '-' >>= fun _ -> prod >>= fun y -> return (x - y))
    ) /*/ v_identity
  ));;

すると、xやyの値が取れなかったときはfunが呼べませんから、その先を空実行することができなくなります。そう、このパーサコンビネータライブラリは、エラーを一度に複数箇所見つけることができるようになりました。
上のCalcParserそのままの実行例です。

...>test_parser.exe
(1+)*(2+)
(1,4):error: '(','+','-',0-9 was expected.
(1,9):error: '(','+','-',0-9 was expected.
Error !!

...>

特にエラー処理を意識しなくても、こんな風にエラーをかき集めてきてくれます。orになっている箇所は両方実行してエラーをマージします。上記ソースでは説明していない|>>というのを使っています。|>>は通常時は>>と同じですが、エラー時はそこから先に進みません。再帰しているところではエラー時にそれ以上進まないようにしておかないと、終わらなくなっちゃいます。
ソースはhttp://panathenaia.halfmoon.jp/hila/に置いておきます。Ada Hackathonまでにパーサーぐらい書いておきたいところですが……。