森ともうします。

At Tue, 12 Apr 2005 17:45:54 +0900,
machida,tatsuhiko <t.machida.unicom jcom.home.ne.jp> wrote:
> 
> > 普通の文法であればジェネレータを使うほうがよいと思います。ハ
> > ンドメイドのパーサーはメンテナンスが大変です。ただ、文法がS
> 
> 　パーサージェネレーターって一般的なんですね。
> 　なんとなくアカデミックなツールというイメージがありました。

ツール自体はそんなにむずかしいものではありません。
私は、コンパイラ本体の実装の前にまずパーサージェネレータを作ったという
経験もあります(笑)。

ただし、正しい(曖昧でない)文法を書き下せるようになるには少し時間がかか
ります。最初のころはshift/reduce, reduce/reduce conflictの山と格闘する、
という経験が必要でしょう。

> 　ただ、パーサジェネレーターは遅いというイメージがあります。
> 　ANTLRのC#パーサーを使ってみたのですが...ちょっと重かった覚えがあります。
> 　なんというか、 O(n^2)の臭いがしました。

少なくともyaccはそんなに遅いことはありません。
gccも、yacc族の中では遅いといわれているbisonを使っていますが、十分高速
ですね。

> 　ソースコードが長くなると、使い物にならなくなるのでは....?
LRパーサにせよLLパーサにせよ、ソースコード全体の長さをnとすれば計算量
はおおむねO(n)といっていいでしょう。

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

-- 
森 公一郎 (MORI Koichiro)


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