PEGと構文解析に関するアレコレの勉強会 Vol.1 まとめ

erukiti @erukiti

無限先読みがあるPEGの処理速度の問題を救うのが、 packrat parsing #peg_study

コツメカワウソ @_nnioo_

Packrat Parsing(Ford02) - PEGベース - 線形時間 - 単純　#peg_study

erukiti @erukiti

へー > memois が正しく memorize じゃない #peg_study

やぬすさん / TAKAGI Kensuke @janus_wel

memoize は r がない #peg_study

phenan @phenan

メモ化とキャッシュの違いってなんだろう #peg_study

ドッグ @Linda_pp

バックトラックする可能性のあるパーサなら何でもメモ化は有効そう #peg_study

Agata Naomichi @agatan_

D言語では memoize!fib でメモ化実装した関数を生成できます！！！！！！ #peg_study

やぬすさん / TAKAGI Kensuke @janus_wel

計算結果をキャッシュしておくのが memoize #peg_study

Agata Naomichi @agatan_

このへんはLL(*)かなんかでも使ってるお話だった気がする #peg_study

erukiti @erukiti

あらま。グラフが壊れてる #peg_study

コツメカワウソ @_nnioo_

PEGがBacktrackというか再評価する場面多いのでメモ化を用いるだけで性能が爆上げになるのか #peg_study

わかめ@毎日猫がいる @vvakame

わかる。処理速度がネックになるパティーンあった。強いPC買えばいいだろ💢って逆ギレしていく構えした。 #peg_study

コツメカワウソ @_nnioo_

メモ化故にメモリ食ってしまう・大規模なものには向かないかも？ 実行効率がイマイチ #peg_study

チェシャ猫 @y_taka_23

ちなみに Packrat Parsing についての元論文 (Ford, 2002) はこちら。pdos.csail.mit.edu/~baford/packra… #peg_study

κeen @blackenedgold

#peg_study 性能が上がるというかアルゴリズムのオーダーが変わるので。

コツメカワウソ @_nnioo_

O(k^n)がO(n)になるというのが本当ならすごくよさ気に思える #peg_study

わかめ@毎日猫がいる @vvakame

PEG.js使うマンしてます #peg_study

κeen @blackenedgold

#peg_study clangのメモリ消費量が爆発するのはだいたい C++の機能のせいじゃないかなぁ。

コツメカワウソ @_nnioo_

色んなPEG実装：Rats!, Parboiled2, Treetop, Lpeg, PEG.js #peg_study

しょしー @syocy

HaskellだとPeggyというのがありますね、Packrat Parser Generator。 #peg_study

iWA @vmi_jp

#peg_study 「gem list -r treetop」なんかいっぱい出てきた(白目

Takuto Wada @t_wada

無限長の先読みに伴う PEG の処理速度問題に対する解として出てきたのが Packrat Parsing(Ford02)。 PEG ベースだがバックトラックをメモ化して処理を線形時間にする( O(k^n) から O(n) へ)。その代わりメモリ消費量が多い。 #peg_study

ELD-R-ESH-2 @eldesh

上手くキャッシュが効くような構文を普段我々が扱って無いというｗ (^^;; #peg_study

がくぞ @gakuzzzz

くらん って何かと思ったら clang の事なのか #peg_study

秋津早苗 @akitsu_sanae

C++用のは無いんですか！？ #peg_study