[#16732] sharing sub-regexp — Tanaka Akira <akr@...17n.org>

Oniguruma についてひとつ要望があります。

51 messages 2002/04/03
[#16744] Re: sharing sub-regexp — "K.Kosako" <kosako@...> 2002/04/04

Tanaka Akiraさんの<hvopu1hxfyd.fsf@coulee.a02.aist.go.jp>から

[#16746] Re: sharing sub-regexp — matz@... (Yukihiro Matsumoto) 2002/04/04

まつもと ゆきひろです

[#16753] Re: sharing sub-regexp — Tanaka Akira <akr@...17n.org> 2002/04/04

In article <1017890618.302241.17865.nullmailer@ev.netlab.jp>,

[#16755] Re: sharing sub-regexp — "K.Kosako" <kosako@...> 2002/04/05

Tanaka Akiraさんの<hvo7knn93ug.fsf@coulee.a02.aist.go.jp>から

[#16756] Re: sharing sub-regexp — Tanaka Akira <akr@...17n.org> 2002/04/05

In article <20020405044506.D4784349@helium.ruby-lang.org>,

[#16822] Re: sharing sub-regexp — "K.Kosako" <kosako@...> 2002/04/10

Tanaka Akiraさんの<hvopu1e4omy.fsf@coulee.a02.aist.go.jp>から

[#16831] Re: sharing sub-regexp — Tanaka Akira <akr@...17n.org> 2002/04/10

In article <20020410025054.C8DF0915@helium.ruby-lang.org>,

[#16863] Re: sharing sub-regexp — Tanaka Akira <akr@...17n.org> 2002/04/11

In article <hvor8lnchak.fsf@coulee.a02.aist.go.jp>,

[#16877] Re: sharing sub-regexp — Shugo Maeda <shugo@...> 2002/04/12

前田です。

[#16887] Re: sharing sub-regexp — Tanaka Akira <akr@...17n.org> 2002/04/12

In article <87pu15z80q.wl@studly.priv.netlab.jp>,

[#16909] Regexp#to_s — Shugo Maeda <shugo@...> 2002/04/15

前田です。

[#16912] Re: Regexp#to_s — Tanaka Akira <akr@...17n.org> 2002/04/15

In article <87g01x1e6m.wl@studly.priv.netlab.jp>,

[#16931] Re: Regexp#to_s — Kazuhiro NISHIYAMA <zn@...> 2002/04/16

西山和広です。

[#16934] Re: Regexp#to_s — Tanaka Akira <akr@...17n.org> 2002/04/16

In article <20020416180631.988E.ZN@mbf.nifty.com>,

[#16938] Re: Regexp#to_s — Shugo Maeda <shugo@...> 2002/04/17

前田です。

[#16939] Re: Regexp#to_s — Tanaka Akira <akr@...17n.org> 2002/04/17

In article <87u1qaj0xe.wl@studly.priv.netlab.jp>,

[#16947] Re: Regexp#to_s — Shugo Maeda <shugo@...> 2002/04/18

前田です。

[#16950] Re: Regexp#to_s — matz@... (Yukihiro Matsumoto) 2002/04/18

まつもと ゆきひろです

[#16951] Re: Regexp#to_s — Tanaka Akira <akr@...17n.org> 2002/04/18

In article <1019116103.420173.12691.nullmailer@picachu.netlab.jp>,

[#16960] Re: Regexp#to_s — nobu.nakada@... 2002/04/18

なかだです。

[#16761] StringIO — tadf@...

ふなばです。

43 messages 2002/04/05
[#16786] Re: StringIO — nobu.nakada@... 2002/04/08

なかだです。

[#16802] Re: StringIO — tadf@... 2002/04/09

ふなばです。

[#16803] Re: StringIO — nobu.nakada@... 2002/04/09

なかだです。

[#16804] Re: StringIO — tadf@... 2002/04/09

ふなばです。

[#17221] Re: StringIO — Wakou Aoyama <wakou@...> 2002/05/30

青山です。

[#17230] Re: StringIO — matz@... (Yukihiro Matsumoto) 2002/05/30

まつもと ゆきひろです

[#17231] Re: StringIO — Tanaka Akira <akr@...17n.org> 2002/05/30

In article <1022740594.117106.6073.nullmailer@picachu.netlab.jp>,

[#17233] IO#size — Shugo Maeda <shugo@...> 2002/05/30

前田です。

[#17239] Re: IO#size — Tanaka Akira <akr@...17n.org> 2002/05/31

In article <874rgqdt3x.wl@studly.priv.netlab.jp>,

[#17253] Re: IO#size — Wakou Aoyama <wakou@...> 2002/05/31

青山です。

[#16790] Ruby Shim — "Akinori MUSHA" <knu@...>

 1.7 early access kit という仮称で提案した構想ですが、先ほど

27 messages 2002/04/08
[#16796] Re: Ruby Shim — Koji Arai <JCA02266@...> 2002/04/08

新井です。

[#16833] math.c 1.10 — "U.Nakamura" <usa@...>

こんにちは、なかむら(う)です。

23 messages 2002/04/11
[#16834] Re: math.c 1.10 — matz@... (Yukihiro Matsumoto) 2002/04/11

まつもと ゆきひろです

[#16869] Makefiles dependency — nobu.nakada@...

なかだです。

17 messages 2002/04/12

[ruby-dev:16732] sharing sub-regexp

From: Tanaka Akira <akr@...17n.org>
Date: 2002-04-03 09:57:16 UTC
List: ruby-dev #16732
Oniguruma についてひとつ要望があります。

パターン中で、同じ部分パターンを複数記述しなければならない時に、最初の
ひとつだけを記述して、後の部分は最初のを参照するような機能を入れられな
いでしょうか?

仮に参照を行なう構文を (?*n) とし、n 番目の group (shy group を含む)を
参照するとすると、/(?:a+)(?*1)/ が /(?:a+)(?:a+)/ と等価になるというよ
うなものです。
# 後方参照とは異なり、マッチした文字列ではなく、パターンそのものが入り
# ます。

# なお、番号ではなく、group に名前が付けられて、名前で参照できるという
# ほうが望ましいです。

ただし、内部的に複製は行なわないで部分パターンを共有するというのが前提
です。

なぜこんな機能が欲しいかというと、DFA から正規表現に変換したいからです。
正規表現は等価な DFA に比較的簡単に変換でき、DFA はマッチの条件を逆に
したり、複数の DFA の共通部分にしかマッチしないような DFA を求めたりと
いった操作が比較的簡単に行なえます。こういう操作ができると、いろいろと
面白い DFA が簡単に生成できます。そこで、DFA から正規表現に変換してパ
ターンマッチングに使えるといろいろと楽しいわけです。

ところが、残念ながら、DFA から正規表現への変換は今のところ困難です。
この変換は理論的には可能なのですが、DFA の大きさに対して正規表現の大き
さが指数関数的になってしまうので非現実的な結果になってしまうことが多々
あります。

例えば、http://www.din.or.jp/~ohzaki/regex.htm によれば、ISBN にマッチ
する正規表現は 105488889066bytes になるそうです。当然ですが、こんなパ
ターンは動作させることはおろか、生成することもままなりません。

ここで、なぜこんな非現実的な大きさになるかというと、正規表現の複製が大
量に行なわれるからです。そこで、パターンの複製を行なわずに共有できれば
問題は解決します。というわけで冒頭の提案のように部分パターンを共有でき
る機能があるといいなぁ、ということになるんですが、これは困難でしょうか?

なお、目的は DFA からの変換だけなので、共有部分で後方参照やや zero
width assertion など、理論的な正規表現以外のものが使えなくてもまったく
問題ありません。むろん、自分自身を含むような部分パターンを参照すること
も必要ありません。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)

In This Thread

Prev Next