最近のキーワード

2006年07月20日

TDP4R: Packrat Parsing

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のプロジェクトがあった。
ラベル:tdp4r ruby packrat
posted by ttate at 10:17| ☔| Comment(0) | TrackBack(0) | Ruby | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。