頭の悪いぱーさめも

Parser

LLとか言われても「再帰下降」、LALRとか言われても「表引くやつ」と言い直さないとぴんと来ないのでまとめる。

あるごりずむ

  • LL……トップダウン
    • LL(1)……JavaCC他、手書きできる
    • LL(k)……ANTLR他、手書きできる
      • 再帰下降+バックトラック……Parsec*1他(たぶんREBOLもあとNFA正規表現もここ)、手書きできる
        • Packrat parsing……バックトラックしてると遅いのでメモ化を併用、Pappy他、PEG(Parsing Expression Grammar)を取るパーサジェネレータはたぶんこれ吐いてくれる
  • LR……ボトムアップ
    • LR(0)……lookahead-setもfollow-setも使わない。ひたすら積んでいってパターン満たしたらreduce。
    • SLR……follow-setを使う。噂によると手書きできるらしい？
    • LALR……lookahead-setを使う。
      • LALR(1)……yacc, bison, caper他多数*2
    • GLR……幅優先探索(たぶんDFA正規表現もここ？), Elkhound, D Parser, bisonの派生物などが実装しているらしい
    • LR(k)……いちばんすごいらしい。
    • アーリー法 http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%BC%E3%83%AA%E3%83%BC%E6%B3%95 よくわからん……衝突とか考えずshift/reduceを全通り試しながら最後まで突き進む法（first/follow/lookahead-setの先読みを使って多少衝突減らしながら突き進むアーリー法改など色々あり）
    • CYK法 http://ja.wikipedia.org/wiki/CYK%E6%B3%95 よくわからん……ソース文字列全体見渡してとにかく作れそうな部分木を片っ端から全部作ってみて、全体の木ができちゃったらOK法

ようご

  • first-set……あるルールの先頭になるトークン
  • follow-set……あるルールの後に続くトークン
  • lookahead-set……あるルールの途中の要素の次に来れるトークン

*1:Parsecの中身は知りませんがパーサコンビネータを素直に実装すると先読みはせずにひたすらバックトラックで分岐を解決します。

*2: (2)以上はあるのか？

頭の悪いパーサジェネレータ

Parser OCaml

あんだけ進めといてアレなのですが、方針転換します。パーサジェネレータ作ります。

  • OCamlのコンパイラが吐くエラーメッセージは正気とは思えないため、最終的に使う言語自身で書いたほうがパーサジェネレータ用の間に合わせの構文よりも嬉しいというパーサコンビネータの売り文句が、逆転しそう。
  • 型推論があろうがタプルがあろうが、ASTを自作するのは面倒くさい。
  • OCamlではタプルに1要素加えたタプル作成を一般化できないため尚更面倒くさい。D言語はすばらしい。
  • Parsecにはbuildなんたらいう関数があるらしい。パーサコンビネータのふりしてても前処理してんじゃん。中身知らんけど。
  • 前処理無しの再帰下降では出せるエラーメッセージに限界がありそう。

……という思考過程を経ました。結論としてはOCamlが全部悪い。

目標。

  • AST作ってくれる。
  • 何もしなくてもそれなりのエラーを複数検出してくれる。
  • 何もしなくてもエラー時もエラー部分だけ穴抜けになった値を返してくれる。

少なくともocamlyaccでは全部できないのでどれかひとつでも達成したらocamlyaccには勝てます。というよりは、パーサジェネレーターって、汎用の方がむしろあり得なくて、用途に合ったものをその都度作るべきではないかと思えて来ました。

アルゴリズムはなんでもいいですが折角ですのでLALR(1)に挑戦しようかなあと。

あとhttp://d.hatena.ne.jp/ytqwerty/20050426#p1で作ったやつはDでしたので構文木をinterfaceで自動生成してメソッドの中身書かせるようにしたのですが、今回OCamlですので構文木の処理は仮想関数にするよりもパターンマッチ使える方が嬉しいでしょうからふつーにバリアントにすることにします。単にパターンにobjectって書いたらsyntax error出たからってだけです。

続きを読む

caperが吐いたコードを読む

Parser D

LALR(1)はどうやって動作しているのでしょうか？
理解を完全にするために、caperの吐いたコードを追いかけてみたいと思います。
caperは、jonigataさんの作られたパーサジェネレーターです。パーサジェネレータの中では群を抜いてきれいなコードを吐いてくれます。最近のバージョンアップでジェネレータが追加されていろんな言語を吐いてくれますので私みたいなC/C++は一応読むことはできても直感的な理解には言語障害があるやつにはもってこいです。感謝感謝。
とりあえずcaper付属のcalc0.cpgを相手にします。

%token Number<int> Add Sub Mul Div;
%namespace calc;
%dont_use_stl;

Expr<int> : [Identity] Term(0)
	  | [MakeAdd] Expr(0) Add Term(1)
	  | [MakeSub] Expr(0) Sub Term(1)
	  ;

Term<int> : [Identity] Number(0)
	  | [MakeMul] Term(0) Mul Number(1)
	  | [MakeDiv] Term(0) Div Number(1)
	  ;

トークンはNumber, Add, Sub, Mul, Divの5種類。値はint。[]の中はセマンティックアクションの関数名です。左再帰もありますので手頃でしょう。

続きを読む