頭の悪いぱーさめも

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)以上はあるのか？