「Sun、新プログラミング言語Fortressをオープンソースとして公開」記事へのコメント

Rats!ステ

[Anonymous Coward]

いくら参照実装とはいっても、アルゴリズム自体が半端なく実用的じゃない。
ヒープ消費量がO(n)なパーザRats! [nyu.edu]はいらん。

んで、FORTRANのように大規模なものが組まれるようになった時、
Fortressではどんなパージングするかっつーことが問題ですが。
まさかyaccではできないからpackrat選んだんだろうし…

Re:Rats!ステ

[Anonymous Coward]

あれ、O(N) なんですか？
だったら全然問題ないような気がするんですが…
だって、1モジュールで 10万行という気違いじみたサイズだとしても、
バイト数にしたら 2Mバイトくらいですよ。
仮にソースコードサイズの 10倍メモリを食ったって 20MB 程度ですから、
今どきの計算機なら全然余裕じゃないですか。
普通のプログラムなら、モジュール分割するので、1モジュールあたりだと
大きくてせいぜい数千行程度、ということは 10倍計算でも 2MB 未満ですよね。

どこら辺が問題なんでしょう？

Re:Rats!ステ

[Anonymous Coward]

Rats!というかPackrat Parsingをプログラミング言語の
解析に使うときに問題なのは、ヒープ使用量が入力長に対して
O(n)であることよりも、定数係数で割と性能が悪いことかと。
ヒープ使用量については、１ファイルがものすごく馬鹿でかい
ということにさえならなければ、問題ありません。

一方、実行性能についてですが、Packrat Parsingでは、LLやLALR
と違って、選択演算子(/)の動作順序が決まっており、ある選択肢が
失敗したらバックトラックして次の選択肢を試すという動作を行うため、
選択肢が多数ある文法の場合、選択肢の並び順によって性能が
かなり落ちる危険性があります。もちろん、Packrat Parsingでは
memoizationを行うため、性能は入力長に対してO(n)になりますが、
高速なLALRパーザに比べて定数係数で10倍くらい遅いということは
普通にありえます。