ruby-list

成瀬です。

(2010/08/17 22:25), dezawa@aliadne.net wrote:
> そんなものじゃないでしょうか。 って書いた出沢です
> 
> とはいえ、
> 人が見ると　
>    /<X(?:\s[^>]*)?>.*? はたくさんあるなぁ 、でも
>    <\/Y>/　はないなぁ
>    よって nil
> 
> というのが一目で判ります。
> これを(低コストで)実装するのは大変なんでしょうね。

Ruby, Perl, Python, JavaScript などが採用している NFA 型のエンジンでなく、
grep や sed などで用いている DFA 型のエンジンなら一瞬ですね。
後方参照やメモリする括弧、最左最長マッチなどを諦めれば NFA から DFA への
変換は理論上可能です。

で、参照を入れ忘れたのですが、この辺の話は
詳説正規表現の6.1.4や以下のサイトで語られています。
http://swtch.com/~rsc/regexp/regexp1.html

-- 
NARUSE, Yui  <naruse@airemix.jp>

Thread

Prev Next

In This Thread

Prev Next

[#47278] RejectKaigi 2010 開催のお知らせ [ 8月29日（日）] — "KOSHIBA Toshiaki(so-net)" <koshiba@...8.so-net.ne.jp>

[#47279] RubyKaigi2010 LTでのMacBook用モニタアダプターを貸していただける人を募集しています. — Sora Harakami <sora134@...>

[#47282] [ANN] RubyKaigi 2010 併催 キーサインパーティーのおさそい — Urabe Shyouhei <shyouhei@...>

[#47283] [ANN] RubyKaigi 2010 『MSWin32版Ruby野良ビルダー養成塾』 宣伝 — arton <artonx@...>

[#47284] Ruby committers Q&A at RubyKaigi — Shugo Maeda <shugo@...>

[#47285] make install後、config.hの置き場所について — Moru <lateau@...>

[#47288] [ANN] RubyConf 2010 の情報共有ML — Kakutani Shintaro <shintaro@...>

[#47290] 改行やタグを含むデータをmysqlでinsertするには — Yosuke Suzuki <yosuke.suzuki@...>

[#47298] スキップリストをリリースしました — "KISHIMOTO, Makoto" <ksmakoto@...4u.or.jp>

[#47299] Re: 改行やタグを含むデータをmysqlでinsertするには +追加 XMLの操作 — Yosuke Suzuki <yosuke.suzuki@...>

[#47300] [ANN] Ruby 1.9.1-p430 is out — "Yuki Sonoda (Yugui)" <yugui@...>

[#47301] [ANN][Security] Ruby 1.8.7 patchlevel 301 released (CVE-2010-0541) — Urabe Shyouhei <shyouhei@...>

[#47303] マッチしない正規表現「.*?」が遅い? — SATOH Fumiyasu <fumiyas@...>

[#47306] to_i — Mitsuyoshi Kawabata <kawabata@...>

[#47314] ruby on github and NonComitterHowto — masayoshi takahashi <maki@...>

[#47316] 拡張ライブラリ作成時のrb_gc_mark()の呼び出し方について — tueda <tueda@...>

[#47321] [ANN] Ruby 1.9.2リリース — "Yuki Sonoda (Yugui)" <yugui@...>

[#47323] 無欲マッチの使い方 — AOKI Yoshihiro <aoki@...>

[#47330] ftpファイル再配置のお願い — Tadashi Saito <shiba@...2.accsnet.ne.jp>

[#47331] 入れ子ブレースのマッチング — AOKI Yoshihiro <aoki@...>

[#47335] [ANN] rcairo 1.8.3 — Kouhei Sutou <kou@...>

[#47338] [ANN]hikidoc-0.0.5 — kimura wataru <kimuraw@...>

[#47339] [ANN] rcairo 1.8.5 — Kouhei Sutou <kou@...>

[#47340] GAEについて — "T.Soejima" <clev@...2.so-net.ne.jp>

[#47342] [ANN] rroonga 1.0.0 — Kouhei Sutou <kou@...>

[#47343] [ANN]MiyakoLauncherLite2.0.0 — cyross@...

[#47345] 「Rubyリファレンスマニュアル刷新計画」2010-08分のスナップショットリリース — okkez <okkez000@...>

[#47347] [ANN]Miyako2.1.16&MiyakoPack2.1.16リリース — cyross@...

[#47360] Ruby'sライセンスの、BSDLとのデュアルライセンスへの変更 — "NARUSE, Yui" <naruse@...>

[ruby-list:47312] Re: マッチしない正規表現「.*?」が遅い?

Thread

In This Thread

[#47282] [ANN] RubyKaigi 2010 併催キーサインパーティーのおさそい — Urabe Shyouhei <shyouhei@...>

[#47283] [ANN] RubyKaigi 2010 『MSWin32版Ruby野良ビルダー養成塾』宣伝 — arton <artonx@...>

[#47299] Re: 改行やタグを含むデータをmysqlでinsertするには　+追加 XMLの操作 — Yosuke Suzuki <yosuke.suzuki@...>