From: MORI Koichiro <kmori lsi-j.co.jp>
Subject: [langsmith:185] Re: 自作言語とパーサー 
Date: Tue, 12 Apr 2005 18:34:36 +0900

> というか、ソースコードの長さの自乗に比例するパーシングアルゴリズムって
> 思いつきませんが。文法定義のサイズの自乗というのならわかりますが。

ナイーブな非決定性オートマトンで、バックトラックしまくるような文法を与えられると、
入力の自乗ってありそうな気もします。どうでしょう。

(「プログラミング言語の」パーザにはそんなものは使わないでしょうが)。

ANTLRはだいぶ昔に使った時はそんなに重く感じませんでしたが、確か
あれはトークンの無限先読みが出来たと思うので、文法の作り方によっては
えらく重くなることはあるかもしれません。

--shiro

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