[Rust] 再帰下降パーサの落とし穴

CRANK

Rusty-parser 最適化Rust で作るプログラミング言語シリーズです。rusty-parser プロジェクトで、パーサが異様に遅い現象がありました。しかも、次のようなシンプルなコードでです。var a = array([[[1]]]); print(a, type(a)); こんな素朴なコードのパースに、 Rust のリリースビルドでも 2 秒もかかりました。real 0m2.447s user 0m2.446s sys 0m0.001s この遅さは配列のネストの深さを増すと急速に増大します。もう一段ネストしただけで......非合理的なほど遅くなりました。real 0m28.689s user 0m28.689s sys 0m0.000s 原因知っている人は良く知っていると思いますが、再帰下降パーサ(あるいは一般に LL(k) パーサ)は複数の構文の候補があった場合、バックトラックによって候補を決定します。それにしてもこんな簡単な構文でここまで遅くなるとは予想していませんでした。Rusty-parser は配列を操作することを目的とした言語なので、 3 段か 4 段のネストした配列はよく出てきます。これのパースにここまで時間がかかっては実用的ではありません。ここでパーサのコードを見直すと、次のようなパターンが頻出することに気づきました。fn array_rows(…