From: Tanaka Akira <akr@...17n.org>
Date: 2003-03-04T17:56:34+09:00
Subject: [ruby-dev:19738] Re: [Oniguruma] Version 1.8.1

In article <20030304083813.0DBD3567@helium.ruby-lang.org>,
  "K.Kosako" <kosako@sofnec.co.jp> writes:

> 以下のような左再帰はエラーにしようと思います。
>
> /\A(?<n>|(?*n)a)\z/

LL(k) を越えるものは扱わなくても構わないと思います。

> 対象文字列の長さから、必要な最大再帰回数が分かるので、
> 解くことが不可能ではないとは思いますが。

subexp call が使えると一般の CFG を記述できちゃうわけですが、一般のCFG
だって parse は可能ではあります。(古典的には CKY アルゴリズムとか。)

でも、簡単なアルゴリズムは遅い(入力の大きさに対して線形では済まない)し、
速いものは難しくて得られる利点に引き合わないように思うので、どこかで線
をひくのが妥当だと思います。その線として左再帰禁止というのは悪くないと
思います。
-- 
[田中 哲][たなか あきら][Tanaka Akira]