Path: katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 23 Aug 1994 05:41:04 GMT Organization: Software Research Associates, Inc.,Japan In-reply-to: nitta@sra.co.jp's message of Mon, 22 Aug 1994 05:27:07 GMT Newsgroups: sra.tools Subject: Re: egrep Distribution: sra References: 記事 で nitta@sra.co.jp (Minoru Nitta) さんいはく > % egrep '^...... A' > egrep: regular expression too long > > となってしまいます。(SUN JLE4.1またはNEWS$.2C) > #awkでも同じです(JLEだとcoreを吐く)。 > #grep,gnu/bin/egrepでは問題ありません。 > > (1)なぜこれが、regular expression too longなのでしょうか? > (バグならパッチはありますか) JLE で awk が core を吐くのはバグでしょう。でも、grep を通る パターンが、egrep では "regular expression too long" といって 断わられることがあるのは、バグではなく grep/egrep に本質的な ことのようです。 grep ファミリに与えるパターンは正規表現(それで表現可能な言語=文字列 の集合は正規言語です)で記述されます。特定の正規表現が表す言語の 中に文字列 X が入っているかどうかは、その正規表現に対応する有限 オートマトンが X を受理するかどうかで判定できるので、一般に grep ファミリは有限オートマトンをシミュレートするものとして実装される と思います。 さて、grep は非決定性オートマトンをシミュレートする実装になって いるから、遅いけど記憶域の使用効率はよく、一方 egrep は決定性 オートマトンをシミュレートするから、速いけど決定性オートマトン を作るときに状態数の爆発などを起こすことがある(NEWS-OS 4.X の マニュアルの記述を参照)という違いがあります。ので、egrep で ... too long と言われることがあるのは決定性オートマトンを シミュレートする以上、しかたないものでしょう。 もし新田さんの質問の「なぜこれが」の意図が、 '^...... A' という表現に対応する決定性オートマトンはどういう グラフの形をしてるのか？どうして記憶域からあふれてしまうのか？ という点ならば、これは私もわかりません。「.」が内部で一体どういう 表現なのか、うまく説明がつかないんです。 '^(0|1)(0|1)(0|1)(0|1)(0|1)(0|1) A' は通る(これはせいぜい数十の 状態数だと思う)のだし。 GNU の egrep は、決定性オートマトンを生成するのに失敗したら、 次善の策として非決定性オートマトンをシミュレートする戦略を 試みるようになっているので expression too long といわれることが ないという噂です。よって GNU egrep だけを使っていればすむ時代に なりましたね。一方 GNU の egrep がない環境(や、なかった時代)では (1) 入力の大文字小文字の別を無視したければ grep を使う (2) 'A........A' のような正規表現で egrep がメゲたら grep を使う (3) 上にあてはまらなければ egrep を使う という形で egrep/grep の使い分けをするとよいようです。ただ、grep と egrep とのパターンの記法の違いは人間が吸収するんですが。 普通の egrep が GNU egrep のように２つの戦略を順次試すようになって いないのは egrep の不備だとおっしゃる hacker もいます。 > (2)「行頭から6文字何でもよくその後ブランク二つと'A'」を > egrepで調べるときのREはありませんか? 標準の egrep を使う必要があるのは、速度のためですか？ -- 渡邊克宏＠四谷 思い出話ですが、数年前の新人研修で、grep (の subset)を作れという 問題が出たことがあります。研修スタッフは、もちろんオートマトン理論の 件は新人には一切隠していました。できあがってくるプログラムはひどい 「偶然動く」ようなものが多かったのですが、スタッフの方々は苦心して 「偶然動く」入力だけ与えて判定をしていたようです。 ＳＲＡではない会社の話ですが、オートマトン理論を知っていた後輩が よい仕事をしてしまったのが契機になって、たまたまオートマトン理論の 知識がなかった先輩が会社を去ることになったということもあるそうです。