まあ人間が弱いと、構文解析は再帰を書き下すしかできないんですが、ナイーブな実装だと左再帰問題に出会います( A->A+B
みたいなルールをコードに落とし込むと、 parseA
の呼び出しで無限再帰になる)。右結合性の演算子のパースならぽいっとできるんですが、左結合の演算子だと苦戦しました。いろいろグーグルしてみるんだけど気持ちが上がらないとちゃんと読まないし、私が読めるコードが欲しい気持ちになったので書き残しておきます。n回ここに来るんだろうなぁ。
ちなみに a + b + c
が (+ (+ a b) c)
になるのが左結合性、 (+ a (+ b c))
になるのが右結合性です。
なんということは無くて、ただのループです。こんなのは知ってるかどうかという気持ちになってきた。
ちなみに明らかに parseAdd
と parseMul
が同じ形をしているのでテンプレートとかmixinに落とし込みたいところですよね。 任意の左結合性二項演算子を parseする関数を返す高階関数とか。
これをOCamlで書けるようになりたい。