メモ

TDP4Rの高速化に関連して、Packrat Parsingの論文を少し眺めてみた。やりたいことは、バックトラッキングの抑止で、その手段として、lazy evaluationとmemoizationという新しい道具を使ったという感じだ。関数で再帰下降式に実装する場合を考えると、各パース関数は(statelessであれば)文字を一つ入力すれば、後続するパース関数が一意に定まる。よって、その後続するパース関数をメモできるというもの。のように見えた。結局、A->B C D1 | B C D2 があれば、A -> B C (D1 | D2) にする。そして、D1 | D2 の部分は文字一つでどちらかに決まれば良いわけで、これをどうスマートに実現するかだろう。さて、packratじゃなくてもいいけど、うまいことtdp4rを速くするにはどうするのがよいだろう？余談1：packratというrubyforgeのプロジェクトがあった。