Yukihiro Matsumoto <matz ruby-lang.org> writes:

> |　ただ、パーサジェネレーターは遅いというイメージがあります。
> |　ANTLRのC#パーサーを使ってみたのですが...ちょっと重かった覚えがあります。
> |　なんというか、 O(n^2)の臭いがしました。
> |　ソースコードが長くなると、使い物にならなくなるのでは....?
> |　もしかしたら、パーサというよりレクサ(?)の問題だったのかもしれません。
> 
> ANTLRは使ったことがないので分からないのですが、一般にyaccが
> 使っているLALRなどの構文解析でO(n^2)になるような要素はないと
> 思います。個人的な経験でもソースコードの量によって使い物にな
> らなかったことはないです。

yaccやbisonが生成するパーサの使うLALR(1)構文解析法は、人が手で書く時に
良く使うLL(1)より少し効率が良いと中田育男先生の「コンパイラ」(産業図書,
1981)にありました。

いずれも、オーダーはO(n)です。

実際、yaccやbisonが生成するパーザは、人が手で書くのと比べて劣らないく
らい速いと思います。

Shiro Kawai <shiro lava.net> writes:

> From: MORI Koichiro <kmori lsi-j.co.jp>
> Subject: [langsmith:185] Re: 自作言語とパーサー 
> Date: Tue, 12 Apr 2005 18:34:36 +0900
> 
> > というか、ソースコードの長さの自乗に比例するパーシングアルゴリズムって
> > 思いつきませんが。文法定義のサイズの自乗というのならわかりますが。
> 
> ナイーブな非決定性オートマトンで、バックトラックしまくるような文法を与えられると、
> 入力の自乗ってありそうな気もします。どうでしょう。
> 
> (「プログラミング言語の」パーザにはそんなものは使わないでしょうが)。
> 
> ANTLRはだいぶ昔に使った時はそんなに重く感じませんでしたが、確か
> あれはトークンの無限先読みが出来たと思うので、文法の作り方によっては
> えらく重くなることはあるかもしれません。

ANTLRが生成するのはLL(k)パーザですね(n >= 1)。

祖先のPCCTSはLL(k), k > 1の場合、バックトラックするO(n^k) のパーザを生
成することがあったそうですが、ANTLR は LL(k)の中でも O(nk) で近似でき
るサブセットだけを扱うそうです。

http://www.antlr.org/doc/glossary.html#Linear_approximate_lookahead

なので、オーダとしては線形のはずです。

また、ANTLRが生成する再帰下降lexerが遅いというのも本当のようです。
http://www.jguru.com/faq/view.jsp?EID=458474

				前田敦司

--
ML: langsmith quickml.atdot.net
使い方: http://www.atdot.net/~ko1/quickml