演算子の先読みが少し必要だが、素直に実装すればよい。括弧を用いた方法https://en.wikipedia.org/wiki/Operator-precedence_parser#Alternative_methods中置記法の数式を対象とした、英wikipediaに載ってた名前の分からない暴力的な方法。演算子の周りにその優先順位に対応した数の括弧を足すことで、木構造を作る。優先順位の大きい演算子から順に小さい数の括弧を割り当てている。括弧が付いてしまえば木構造ができているので、優先順位のことを忘れてしまえる。結合順のあたりは未処理なので適当にする。雑にごまかしたいときに使えばよいっぽい。y/()/[]/とかして適当にevalに投げつけたりするとよさげ。みの数が高々$k$なら$\rm{LL}(k)$で上限なしなら$\rm{LL}(\ast)$。LL(0)http://stackoverflow.com/questions/5253816/are-there-such-a-thing-as-ll0-parsershttp://stackoverflow.com/questions/21328816/from-article-on-wikipedia-is-this-a-ll0-grammar先読みができない。不安になるぐらい貧弱。先読みができないというのは、現在の状態(非終端記号)のみから(入力によらず)使用する規則を決めないといけないということ。starとかそういうのは禁止なので全部inlineに展開できて、単一の規則で表せるはず。何も知らずに書こうとしたらたぶん自然とこれに近いものになる。$1$文字だけ先読み、つまり現在の状態と未処理の$1$文字から使用する規則を決める。構成し、これに従い決定的に遷移しながら入力をなめる。表から手で書くと、非終端記号の数だけ関数を用意して相互再帰になることが多い。\Sigma)$になる。統一的に求める方法がある。入力は入力末尾記号$\$$を持つものとする4。以下を再帰なりで適当に作る。非終端記号$A$の後ろに続きうる終端記号これらより、$\operatorname{director}$集合を定める。\gamma)$とすれば、遷移表ができる。この表に衝突がある、つまり$f$が(部分)関数にならなかったとき、対象とした言語は$\rm{LL}(1)$の範囲外の言語だったということになる。表の衝突を最低限の部分で防ぐため、事前に以下が行われる。\epsilon$に。b$にLR法https://www.amazon.co.jp/dp/4798114685左からなめて最右導出。bottomupな構文解析、区間DPぽいやつ。$\rm{LL}(k)$だと左から$k$文字まで見た時点で使用する規則決定を迫られ、これが困難なので、決定を延期する。決定対象の右端とさらに$k$文字まで見てから決定するようにする。2$はほぼ使われないらしい。このcanonicalは正準。LR(0)https://www.amazon.co.jp/dp/4798114685先読みはないが、右端導出そのものがある種の先読みなのでそこまで弱くはない。文法は開始記号$S$を持つものとし4、入力は終端記号$\$$を持つものとする。各規則の右辺に区切り記号$\cdot$を付けたものを$\rm{LR}(0)$項(termではなくitem)と呼ぶ。F$に対しては以下の$4$個が項。\cdot$解析器の状態は項の集合で、次に適用されうるものを集めたものとなる。$\cdot$はどこまで見たかを表す。\gamma)$に閉じた閉包を考え、これが状態になる。\gamma$が適用されうるからである。状態間の遷移を考える。状態$X$のとき終端記号$a$が来たときを考えると、$\cdot$が$a$を越えてひとつ右に移動した項の集まりが次の状態である。非終端記号に関しても同様にして、それが来たときの次の状態を定める。状態を頂点とし終端記号/非終端記号を辺とする有効グラフが作れる。\$$を開始状態として、特にその連結成分だけを作る。collection(正準$\rm{LR}(0)$集成)と呼ばれる5。構文解析の実行は、このグラフの上をスタック(と入力)と共に走ることで行われる。スタックには状態(項の集合あるいはその番号)とその状態に遷移するために使った終端/非終端記号の対が積まれる。開始状態と適当な記号のみをスタックに積んだところから始め、以下を繰り返す。その実行で、実行に複数の選択肢が発生する可能性があるなら言語のエラー。$\rm{LR}(0)$では対応していなかったこととなる。\$$ならacceptと呼ぶつまり辺を逆に辿っている無事に入力末尾$\$$を読んで遷移できたら解析成功。このグラフの上を走る操作は、事前に$\rm{LR}$構文解析表という形にまとめられるのが普通。言語のエラーは表の同じマスに複数の規則が書かれているかという形で判断される。$\rm{LR}(0)$よりちょっとましなやつ。ほとんど全ては$\rm{LR}(0)$と同じ。差異は、shift/reduce衝突やreduce/reduce衝突が起こったとき。そのとき$1$文字先読みして、reduce先の非終端記号の$\operatorname{follow}$集合に先読みした文字が入っていないとき、そのようなreduceをしない。これは明らかに失敗を導く遷移を刈る操作である。必然的に先読みを伴うので、$\rm{SLR}(0)$というのは存在しない2。このため項の形が$\rm{LR}(0)$のそれと異なり、表がけっこう大きくなる。$\rm{LR}(1)$項は、$\rm{LR}(0)$項のそれに加え先読み記号を持つ。a)$の形をしている。遷移の方法は単に$\cdot$をずらすだけであるなど、その他諸々に変化はないが、先読み部分により要素が区別されるため結果は違うものとなる。yaccで使われているもの。$\rm{LR}(1)$の表を作って、これから先読み部分だけが違う頂点を併合してしまう。これは表の大きさを減らすためであり、表現力のためではない。衝突は発生しうるが、あまり問題にならないらしい。表の修正https://www.amazon.co.jp/dp/4798114685衝突が起こるなら表を手で修正しちゃえばいいじゃない、というやばげな解決方法がある。これは言語の曖昧性を決め打ちにより解決することに対応する。GLRhttps://en.wikipedia.org/wiki/GLR_parserhttp://qiita.com/jonigata/items/69381937b2d5b0af410c衝突が起こるなら全部試せばいいじゃない、という安直な方法。扱えるのはさすがに文脈自由言語の全体で、最悪$O(N^3)$ではあるが、決定的な文法なら分岐が発生せず$O(N)$なのでそれなり。曖昧な文法を扱えるので結果となる構文木も複数となり、全て求めると森になる。このため永続木のようなものが必要になるらしい。基にする表はどの$\rm{LR}$のものでもよさそうだが2、$\rm{LALR}(1)$のものが効率的らしい。($S$は開始記号)空になる非終端記号が基本的にない、構文木が二分木になる、というのが嬉しい。左再帰や右再帰は存在しうる。要求から外れる規則を、規則中にinlineに展開することで吸収させれば作れる。適切にやれば元の$O(k^2)$の規則数に収まる。以下を順にやればよくてそれぞれそう難しくないが、適用順序は重要。B$の形の規則を$B$をinline展開して除去CYK法https://en.wikipedia.org/wiki/CYK_algorithmCocke-Younger-Kasami法。Chomsky標準形にして$O(N^3)$の区間DP。($K$は規則の数)でやる。parserだがtopdownで、$\rm{LR}(0)$項を使う。$O(N^3)$ではあるが文法に曖昧性がなければ$O(N^2)$になる。LR法をDPにした感じ。N)$を以下による漸化式で作成する。漸化式とはいっても再帰的なので、各$k$に関して左から右へ、それぞれで可能な限り繰り返すことになるだろう。\}$閉包を取るのに相当する2。\}$shiftに相当する2。S(j)\}$reduceに相当する2。($S$は開始記号)どんな文脈自由文法でもこの形に直せるのだが、規則は最悪で元の$O(k^4)$に膨れる。解析は$O(N)$になる2。予言的に構文解析できるので、stack系のesolangで継続を積みながらやる感じだとこれを使うのが楽。toolsyacchttps://en.wikipedia.org/wiki/Yacchttps://www.gnu.org/software/bison/manual/bison.html伝統的な$\rm{LALR}(1)$の構文解析器。preprocessor的に動いてCを吐く。同様な字句解析器であるlexと併せて使われる。抽象構文木を作るのが重たい処理だった時代からあるようで、そのあたりは自分でしないといけない。手元ではbisonへのwrapperとして存在していた。軽い用途に使うにはCだとつらいのでpythonのplyあたりがよさげ。文脈依存言語まで対応してるけど$\rm{LL}(1)$文法のときが最も効率的だそうな。字句解析まで適当にできるしmonadicに書けるしでとても便利。他にも似たものはあるので、使うときはそれらも検討すべき。https://hackage.haskell.org/package/trifectahttp://hackage.haskell.org/package/attoparsecANTLRhttp://www.antlr.org/https://ja.wikipedia.org/wiki/LL%E6%B3%95#LL.28k.29_.E6.A7.8B.E6.96.87.E8.A7.A3.E6.9E.90.E5.99.A8.E7.94.9F.E6.88.90.E3.83.84.E3.83.BC.E3.83.AB$\rm{LL}(\ast)$を使うつよいやつ。字句解析や抽象構文木まで組み立ててくれる。2$な$\rm{LL}(k)$に関する状況を変えるものだったらしい。使ったことはないです。参考実装$\rm{LL}(1)$や$\rm{LR}(0)$の実装までするつもりでしたが、やればできそうだったこともあり途中で飽きました。頭から始めて肝心なところの直前で力尽きるのほんとだめですね。9)変なところがあったらぜひ教えてください。↩いまいちどうLook-Aheadなのか分からない。