2007-12-04

あれからだいぶ直してしまったので1から説明します。YT版Parser Combinator for OCaml……どう見てもHaskellやCleanのそれの劣化版ですが。
ええと、まず、今更言うまでもないですがパーサコンビネータというのはパースする関数とパースする関数をくっつける関数のことです。できるものは単なるトップダウンの再帰下降なLLパーサです。状態遷移表を使うパーサのほうが全てにおいて優秀ですが、状態遷移表を使うパーサはプリプロセッサになっていて使い勝手が大変悪いのが普通です。パーサコンビネータはプリプロセッサをかます必要がないため、とくに@や&や'Accessを付けずに関数名だけで関数を値として使える言語では、手書きパーサの面倒な定型句を省くのに便利です。ソースの見た目を短くするためだけにクロージャ・カリー化を連発しますのでコンパイル後は典型的な「10%のコードを実行するために90%の以下略」状態になります。しかしパーサというのは手書きすると面倒なものですので、どれだけ効率が悪くても最初から書く気にならないよりマシです。
パーサコンビネータを作る/使うには、まず元となるパースする関数の型を決めないとです。相変わらず私は部屋を掃除しないため一向に使えないCleanのパーサコンビネータの解説によりますと、パーサの型は以下のようになっています。

:: Parser symbol result :== [symbol] -> [([symbol],result)]

エラー処理をするときは、結果を3つ組にするといいようです。
しかし、これでは、入力がリストになります。単方向リストなればこそ、「残り」を返せるのですが……HaskellやCleanならともかく、OCamlですと、ソースファイルをメモリマップしたBigarrayあたりを使いたいじゃないですか。従ってインデックスを使います。実際にはどうにでもできるように抽象型にします。
また、結果がリストになっていますが、これはCleanには遅延評価があるため実際には先頭1要素分しかパースされないとかそんならしいです。OCamlにもlazyはありますが、OCamlの文法でlazyなリストを作ろうと思えば、この間試したように記述が面倒になります。手間を省くためにパーサコンビネータを使おうというのにそれでは本末転倒ですので、結果はlazyなリストではなく正格なoptionで済ませてしまいます。
エラーについては、破壊的に記録していきます。
そんなこんなでパーサの型はこうなりました。

type 'a parser = unit -> p_pos -> Env.t -> ('a * p_pos) option

unitの部分は、パーサを直列にくっつける際には、前の値を受け取るために他の型に置き換えて使うことになります。あと、実際のコードは次のように書きたいのですが、文法上let recでは引数無し形式の宣言がエラーにされてしまいますので、unit型の引数を先頭に持ってくることで()を書けるようになってコンパイルが通ります。

(* ERROR *)
let rec syntax1 = ...
and syntax2 = ...

(* OK *)
let rec syntax1 () = ...
and syntax2 () = ...

こうすると、各パーサを使う箇所毎に個別に関数を作る関数が走った上でとどめにカリー化までしてしまいますのでますます効率が悪くなるのですが、手間には変えられません。かといってrecをやめると再帰できなくなりますのでそっちの方が困ります。もともと遅延評価が前提のような気がひしひしとするパーサコンビネータを、OCamlのような正格の(C++のtemplateを使ったspiritのように静的に解決されることが保証されているわけでもない)言語上で、手間のためだけに使おうというのですから……そんなわけで今のところ効率云々はもう諦めてしまっているのですが、その実私はOCamlの初心者中の初心者ですので、何か見落としているに違いない。いやこれは絶対何か手がある予感。例えばEiffelのonceみたいなものがあればいいわけですから。偉い人がもし見ておられましたらアドバイスくださいお願いします。
話の筋を元に戻して、Env.tはこんなのです。パーサ関数群はファンクタに閉じ込めて、入力元を切り替えられるようにしようという寸法。ついでにエラーもここに押し込めてます。

module type PARSING_ENV =
  sig
    type t
    type element
    type position_key
    val peek : t -> element option
    val junk : t -> unit
    val position : t -> position_key
    val rollback : t -> position_key -> unit
    val include_file : t -> string -> unit
    val message : t -> position_key -> int -> string -> unit
  end

peekとかjunkはStreamのそれです。messageはエラーを記録します。positionで現在位置を得て、rollbackでそこに戻ります。rollbackでは位置を戻すほか、messageで追加したエラーのうち、戻った位置以降のエラーを捨てなければなりません。実際にはパースは先頭から行いますので、当然エラーは位置の順に追加されていくわけですので、stackにでもpushしていって、rollbackでは戻った位置以降のものをpopするだけでOKです。順不同でエラーを追加していく場合は優先順位付きdouble-ended queueみたいなものが必要になりますが、どの道OCamlはそういうのは短く書けちゃいます。
パーサ関数群のファンクタはこんな感じで。

module Parser = functor (Env: PARSING_ENV with type element = char) -> struct
  type p_pos = Env.position_key
  ...

この中にパーサ関数を書いていくわけです。
まずは基本となる、特定の1文字を受け付けるパーサ関数が必要です。

val p_char : Env.element -> unit -> p_pos -> Env.t -> (Env.element * p_pos) option

実装はこんな。

let p_char (c: char) () (p: p_pos) e = (
  match Env.peek e with
  | Some r -> 
    if r = c then (
      Env.junk e;
      Some (r, p)
    ) else (
      None
    )
  | None -> None
);;

これを使ってp_char 'A'のように部分適用しますと、char parser型の関数になります。
あとはp_char_rangeやp_char_not、EOF判定するp_endとかそんなのがあればいいでしょう。
基本的なパーサができたら、以降はそれを組み合わせて複雑なパーサを作っていきます。つまりここからがパーサコンビネータです。
HaskellやCleanではパーサコンビネータとして演算子<&>や<|>が使われていますが、OCamlでは右結合の演算子が、**... lsl lsr asr @... ^...しかない現実があります。この中から選ぶなら@...だと思うのは私だけでしょうか。
というわけでまず@&&と@||を定義します。この@&&と@||は、OCamlの&&と||を真似たのであって、C言語の&&と||とはきっと何の関係もありませんことをねがっています。しかしねがいはかなわなかった。ふざけるな3000ギタン返せ。ねがいがかなわない条件あれいまいちわからないです。壷持ってないときに壷増大効果が出たあたりでしょうか。

val ( @&& ) :
  ('a -> p_pos -> Env.t -> ('b * p_pos) option) ->
  (unit -> p_pos -> Env.t -> ('c * p_pos) option) ->
  'a -> p_pos -> Env.t -> (('b * 'c) * p_pos) option
val ( @|| ) :
  ('a -> p_pos -> Env.t -> ('b * p_pos) option) ->
  ('a -> p_pos -> Env.t -> ('b * p_pos) option) ->
  'a -> p_pos -> Env.t -> ('b * p_pos) option

最近鬼月を使えば影法師系を手軽に倒せることに気付きましたなんてのはどうでもよくて、先のparser型でunitになっている箇所が多相になっていますが、これは他のパーサの後ろにくっついて値を変換するパーサ、というものを使うためです。@&&は単に2つのパーサの結果をタプルで返しますが、実際にはこんなもの役に立たないわけです。char parserとchar parserを合成するとstring parserやBuffer.t parserになって欲しいわけです。今からくり白蛇なんですけどペリカン2世の出現率が低くて困ります。
そこで、1階からずっと召喚の罠を集めているのですが……じゃなくて、@&&と似て少し違う@=>演算子も用意します。モナドの>>=のノリです。

val ( @=> ) :
  ('a -> p_pos -> Env.t -> ('b * p_pos) option) ->
  ('b -> p_pos -> Env.t -> ('c * p_pos) option) ->
  'a -> p_pos -> Env.t -> ('c * p_pos) option

@=>は基本的には@&&と同じですが、結果をタプルにする代わりに、右辺を、元々parser型がunitに固定していた位置に左辺が返した結果を取る関数とします。
そうするとp_charの他に@=>の右辺用のp_char_addみたいなものが必要になります。が、ここでcharとcharをくっつけてstringにする処理というのは、yaccで言うところのアクションに相当するわけですので、パーサ関数と一緒にするのはあまり嬉しくありません。似たようなパーサ関数を量産するのも手間ですし、何よりアクションはその場で匿名関数でも使って書きたいじゃないですか。折角匿名関数あるんですから。
というわけで次の演算子を作りました。/...は@...よりも優先順位が高いためちょうどいいです。//なのは、見た目に煩くないからであって、C++のコメント//とはきっと何の関係もありませんことをねがっています。ちなみにAdaやHaskellの--は左右対称っぽいので避けました。ところで通路でしおいやんになめられた直後に店で特製おにぎり買ったら力+1効果が出て、ねがいの腕輪よりも特製おにぎりの方がありがたく思えました。しおいやんになめられるのは死ぬより嫌なのは私だけでしょうか。毒矢やおばけ大根は特に気にしないんですが、なんででしょうね。

val ( // ) :
  'a parser ->
  ('b -> 'a -> 'c) -> 'b -> p_pos -> Env.t -> ('c * p_pos) option

これを使えばp_char 'A' @=> p_char 'B' // (fun a b -> ... ) @=> ...と続けていけます。
こうしてパーサからパーサを作っていくわけですが、先のlet rec中では引数無しの宣言ができない問題がありますので、次のようなものはエラーになります。

(* SYNTAX ERROR *)
let rec syntax1 = syntax2 @&& syntax2
and syntax2 = p_char 'A' @=> p_char 'B' // (fun a b -> ...)

かといって()だけ付けても型が変わってしまいます。

(* TYPE ERROR *)
let rec syntax1 () = syntax2 @&& syntax2
and syntax2 () = p_char 'A' @=> p_char 'B' // (fun a b -> ...)

ですので、次のようなものを使って、無理やり型を合わせます。

let p_do (s: 'a parser) = (
  s ()
);;

(* OK *)
let rec syntax1 () = p_do (syntax2 @&& syntax2)
and syntax2 () = p_do (p_char 'A' @=> p_char 'B' // (fun a b -> ...))

parse等ではなくてdoなのは、やはりこれもモナドのノリです。
これで大体説明したかな……/*/や/?/なんかは単にバリエーションですし想像つくと思いますので省略させてください。
後は位置情報とエラー処理ですね。
parser型の返値のタプル上の右側のp_posは、現在位置ではなくて、最初の位置を延々保持し続けます。これは、エラーメッセージを表示するとき、"source:line:column:Unknown idenfifier XYZ"のcolumnとして、XYZの右端ではなく左端を表示させたいからです。
"X * Y"をエラーにするときに、Xではなく*の位置を表示させたいときは、"*"をパースするところでp_set_positionを挟んでおけばOKです。本当の現在位置は、Env.tが破壊的に覚えてくれていますので、関数の引数や返値にする必要は無いです。破壊的に覚えてくれていますのでって凄い日本語ですね。考えてみれば破壊的に更新するなんて言われたら、意味のある値は残らないと取るほうが普通かも。誰ですか破壊的なんて使い始めたのは。「上書き」でいいじゃんねえ。
そうやって渡されてきた位置を結果の値の方に含めたいときは、p_positionか/%/ v_with_positionかパーサ関数を演算子ではなくて手動で合成するとか、まあ適当に。
エラー処理は、/~/を使います。左辺のパーサがNoneを返したら、右辺の(匿名)関数でそれを適当な有効な値に挿げ替えれば、エラーを検出しながらパースを続けることができます。/~/の右辺の匿名関数にはEnv.messageに現在のEnv.tが部分適用されたものも渡されてきますので、必要に応じて呼び出せばエラーメッセージも記録できます。

http://d.hatena.ne.jp/kmaebashi/20071203#p1
手続き名をlexerが認識するとかどこのBASICでしょうか。Pascalはそんな事してないと思……いやまてよ。

WriteLn(x: 10);

↑こんな、Write/WriteLn中でしか使えない特殊構文がある以上、手続き名をlexerが認識してるのか？
いや、決してlexerでは無いはず。
何故ならvar WriteLn: Integer;とすればSystem.WriteLnを隠蔽できます。その場合でもSystem.WriteLnと書けば上記構文が使えます。
ですので、手続き名をparserが認識している、が正解かな……
……みずしまさんが例示されたBNFの中のPascalは、formal-parameter-sectionにprocedureやfunctionが入っているあたり、実はクロージャが使えるいにしえの教科書のPascalっぽく、unitの仕様が入ってないため当然Systemユニットも無いはずで、こんな例は該当しないのでした。そもそもWrite/WriteLnのフォーマット構文が定義されてない。これって後の拡張でしたっけ？
むしろ、1トークン読んだ時点で手続き呼び出しか代入か区別つける必要あるのかが疑問。まず関数呼び出しもありえる左辺値っぽい式として読んで、後に:=が続いていたらその時点で代入文とすればいいのでは。実際問題Pascalではこんな風に書けます。

nanika^ := 100;

ここでnanikaは「^Integer」と「引数の無い^Integerを返す関数」の両方の可能性があり、後者なら関数呼び出しが発生……
……BNFにははっきりとこうかかれているのでした。

variable := expression  

variable:  
   identifier  
   variable [ subscript-list ]  
   variable . fieldid  
   variable ^

先生、左辺に関数呼び出しが来れないです。
むむ教科書Pascalは手ごわいな。
まぁ、正直なところを言えば、私の知っているPascalについて言えば、真面目にやるならLL(1)では無いです。断言します。
手続き呼び出しも代入もとりあえず式として読めば一緒くたに扱えるのでこちらは問題ではないです。私の知っているPascalでは関数呼び出しの結果に代入できますから。
問題なのはラベル。

name:

nameを読んだ時点ではラベルか式なのかわかりません。そして、とりあえず式として読む方法ですと、ラベル名のところに左辺値が来れてしまいますからpointer^:なんて書けてしまうことに。え？とりあえず式として読む方法ではラベルを持ちだすまでもなく代入文として明らかに不正なproc(1) := 10;と書けてしまうって？それは現在のPascalにたまたま参照型が無いだけですよ。例えばfunc(1).field := 10;は合法ですし、この手のものはparserではなく意味解析でエラーにすべきかと。
閑話休題、ラベルと式の区別でした。
教科書Pascalではラベル名を数字に限定することでこれを回避しています。
ちなみにAdaではgoto用のラベルは<>ですがブロックに名前を付けるときはname: loopのように書きますので同じ問題があります。
で、これに関しては私の中で有名な(……どこで読んだか忘れましたごめんなさい……)解決方法があって、lexerをちょっと弄って、identifierと、identifierの後ろに(空白やコメントは読み飛ばして)コロンが付いたものを別扱いにしてしまえば、すっきり解決します。

identifier [A-Za-z_][A-Za-z_0-9]*
label_identifier [A-Za-z_][A-Za-z_0-9]*(\(\*.*\*\)|\{.*\}|\x20\t\r\n)*:

こうしてPascalは無理矢理にLL(1)になったのでした。めでたしめでたし。
DelphiやFreePascalはname{$IFDEF X}:と書げふんげふん。……実際のところは少なくともFreePascalはlexerもparserも手書きですので……
http://www.freepascal.org/cgi-bin/viewcvs.cgi/trunk/compiler/pstatmnt.pas?view=markup
……いったん式として読んで、読んだ式が単体のidentifierで後にコロンが続いていたらラベルにしてるなあ。うーん、手書きparserは好きにif文挟んで文法捻じ曲げられるのが強みだなあ。
ま、これもLL(1)には間違いありますまい！？別に構文解析表が静的でなければならないなんてルールも無いことですし。(←屁理屈)

- LL(2)とかLALR(1)というのは「構文定義」の性質であって、「言語」の性質じゃないので、
　・「PascalはLL(1)じゃない」という言い方は厳密にはおかしい。
　・「Pascalの言語仕様に書いてあるBNFはLL(1)じゃない」とかいう言い方なら正しい。
参照もとより引用(リンク自粛)

ごめんなさい。

Note

続・頭の悪いパーサコンビネータ

PascalはLL(1)じゃないよね