The road to C# master trapemiya

C#を中心に、.NETの話題を取り上げます。

ホーム 連絡をする 同期する ( RSS 2.0 ) Login
投稿数  256  : 記事  1  : コメント  10703  : トラックバック  30

ニュース

Since 2005年10月26日

わんくま同盟

わんくま同盟

Microsoft MVP


Visual Developer - Visual C#

記事カテゴリ

書庫

日記カテゴリ

正規表現において、空文字はどうやら特別扱いされています。
例によって調査結果を元に動作を推測していますので、誤りがあればご指摘下さい。m(_ _)m

abc
に対して
.*
とすると何がマッチするだろうか?

答えはabcと空文字です。なぜ空文字がマッチするのだろうか?
実験すると、
^.*
だとabcにしかマッチしない。
.*$
だとabcと空文字にマッチする。ということは空文字が$の直前にあるようだ。

調査・・・調査・・・調査・・・

どうやら正規表現上、abcというのは以下のように考えられるとのことだ。

行頭 空文字 a 空文字 b 空文字 c 空文字 行末

要するに間に全部空文字が入っているわけだ。

.*はできるだけ長い文字列にマッチするから、
空文字 a 空文字 b 空文字 c 空文字
にマッチしている。つまり、abcだ。次に残ったのは行末だ。この検査対象の行末の前にも空文字があると考え、実際には、空文字+行末に対してマッチングを行うことになる。この結果、.*は.の0回繰り返しとなり、空文字がマッチする。マッチを2回にわけて考えれば、

行頭 空文字 a 空文字 b 空文字 c 空文字

でマッチ、

空文字 行末

でマッチとなったわけだ。上記だと

行頭 空文字 a 空文字 b 空文字 c 空文字 空文字 行末

と行末に空文字が2つ続くイメージになるが、空文字は元々存在せず、検査する際には常に存在すると考えるのであろう。それに空文字なのでいくつあっても空文字一つと同じである。というより何個という概念がない。(虚数のような感じか?)

以上のように考えると、^.*が空文字にマッチしなくて、.*$がマッチするのも説明が付く。

では、
abc
に対して
b*
とすると何がマッチするだろうか?

答えは、空文字、b、空文字、空文字である。
動作的にはたぶんこうだ。
行頭の次の空文字はbの0回の繰り返してでマッチ。・・・(1)
次のaはマッチしようがないのでスキップ。
次の「空文字 b 空文字」はbと考えられるのでbの1回の繰り返しでマッチ。・・・(2)
残りは「空文字 c 空文字 行末」。
よってcの前の空文字がマッチ。・・・(3)
cはマッチしないのでスキップ。
残りの「空文字 行末」で空文字がマッチ・・・(4)

以上より、空文字、b、空文字、空文字がマッチすることになる。


#以上のこと合ってる? >みなさん。

投稿日時 : 2009年4月24日 16:39

コメント

# [正規表現] 「 0 文字以上の任意の文字」は何にマッチする? 2009/04/24 19:10 雑記 - otherwise
久々に正規表現の話が出来る♪ 正規表現における空文字は特別扱いだ。 (The road to C# master trapemiya) とても面白い考察ですが、残念ながら違います。 実のところ、この辺の処理仕様は、詳説 正規表現を読むと判る話なんですが、さすがに NFA エンジンの細かい処理の話

# re: 正規表現における空文字は特別扱いだ。 2009/04/24 19:35 こくぶん
「空文字が入っている」と云う記述に反応して「違う」とかトラックバック送っちゃいましたが、
基本的には間違っていなそうです。スミマセン。。。

「0文字マッチング」(所謂「『何もない』にマッチする」)を表現するのは難しいですね。(日本人だからでしょうか)

# re: 正規表現における空文字は特別扱いだ。 2009/04/24 23:50 trapemiya
コメントありがとうございます。
私も自信がないのでこれ以上話ができないのがつらい・・・w
ひょっとして.NETのRegexクラスが特殊なんだろうかと思ったり。そうではないのかな?私はRegexクラスのMatchesでマッチを確認してるんですが・・・。
それにしても私も一番しっくりきてないのは、なぜ.*がabcに加えて空文字にマッチするのかなんです。行末に最初に当たっているはずなんで、そこで終わってabcだけでいいじゃんって思うんですけどね・・・。Regexクラスが特殊なのかなぁ? 来週にでも会社でvi使って試してみようかな? いや、Knoppix落としたほうが早いか。
「詳説 正規表現」読んでみようかな・・・

# re: 正規表現における空文字は特別扱いだ。 2009/04/25 12:05 気狂い帽子屋
どういうプログラムで確認されたのかがわかりませんけど、
Matchesは入力に対してマッチしたものをすべて列挙します。
"Searches the specified input string for all occurrences of a regular expression."
http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex.matches.aspx
だからabc以外にも、空文字が引っかかるのです。

ところで正規表現云々書こうというのなら、たったひとつの実装を
ブラックボックス調べるようにあーでもないこうでもないと
つつくんじゃなく、文献調べるべきじゃないですか?
個々の処理系やライブラリに固有の拡張部分はともかく、正規表現
それ自体は大昔からある技術ですよ。


# re: 正規表現における空文字は特別扱いだ。 2009/04/26 1:54 trapemiya
コメントありがとうございます。

>だからabc以外にも、空文字が引っかかるのです。

申し訳ありませんが、この「だから」をもう少し詳しく説明していただけませんでしょうか?そもそもabcだけにマッチすれば良いと思うのですが、なぜ空文字にマッチしてしまうのでしょうか? そして、 なぜ^.*は空文字がマッチせず、.*$では空文字がマッチするのでしょうか? 

>ブラックボックス調べるようにあーでもないこうでもないと
つつくんじゃなく、文献調べるべきじゃないですか?

おっしゃる通りです。ネットではかなり調べたつもりです。しかし、空文字に関して詳しく記述しているところはありませんでした。空文字に関しては私が持っている「正規表現の達人」という本に一番詳しく載っていました。
よろしければ空文字に関して、この本を読めばわかるよというお薦めがあれば教えていただけませんでしょうか?
決して正規表現に関して偉そうに書こうと思っているのではなく、自分でも行き詰まり、自分で調査した結果をブログの力を借りて詳しい方に添削してもらえたらと思っているのが真実です。ブログの書き方が悪かったかもしれません。すみません。
ただ真実が知りたいだけなのです。

# re: 正規表現における空文字は特別扱いだ。 2009/04/26 2:35 trapemiya
ちなみに確認したプログラムは単純です。

Regex regex = new Regex(".*");

MatchCollection mc = regex.Matches("abc");

for (int i = 0; i < mc.Count; i++)
{
this.listBox1.Items.Add(mc[i].ToString() + " " + mc[i].Index);
}

# re: 正規表現における空文字は特別扱いだ。 2009/04/26 3:22 trapemiya
空一致後の次の検索
http://msdn.microsoft.com/ja-jp/library/wf1sxc1z(VS.80).aspx

をもう一度読んだら何となく見えてきたような・・・

# Illikebuisse avxsa 2021/07/03 23:57 pharmacepticacom
hydroxcloroquine https://pharmaceptica.com/

# re: ?????????????????? 2021/07/06 11:08 plaquenil sulfate 200 mg
chrloroquine https://chloroquineorigin.com/# what is hydroxychlor 200 mg

# re: ?????????????????? 2021/07/23 15:41 methotrexate side effects usmle
chloroquinne https://chloroquineorigin.com/# side effects hydroxychloroquine

# fusipdqxilse 2021/12/02 4:47 dwedayhgsm
chloroquine stock https://hydrochloroquinebtc.com/

# buy ivermectin canada http://stromectolabc.com/
ivermectin 4 tablets price 2022/02/07 17:30 Busjdhj
buy ivermectin canada http://stromectolabc.com/
ivermectin 4 tablets price

# stromectol canada http://stromectolabc.com/
ivermectin buy australia 2022/02/08 3:30 Busjdhj
stromectol canada http://stromectolabc.com/
ivermectin buy australia

# ivermectin for sale http://stromectolabc.com/
ivermectin new zealand 2022/02/08 10:16 Busjdhj
ivermectin for sale http://stromectolabc.com/
ivermectin new zealand

# buy doxycycline online 270 tabs https://doxycyline1st.com/
how to order doxycycline 2022/02/25 22:13 Doxycycline
buy doxycycline online 270 tabs https://doxycyline1st.com/
how to order doxycycline

# doxycycline 100mg dogs https://doxycyline1st.com/
buy cheap doxycycline online 2022/02/26 9:27 Doxycycline
doxycycline 100mg dogs https://doxycyline1st.com/
buy cheap doxycycline online

# best ed pills https://ed-pills.site/
ed medication online 2022/11/17 15:59 EdPills
best ed pills https://ed-pills.site/
ed medication online

# international singles https://datingsiteonline.site/
dating sites online 2022/12/05 17:11 Tading
international singles https://datingsiteonline.site/
dating sites online

# recommended canadian pharmacies https://noprescriptioncanada.com/
canadian prescriptions 2022/12/13 13:23 CanadaPh
recommended canadian pharmacies https://noprescriptioncanada.com/
canadian prescriptions

# doors2.txt;1 2023/03/14 16:30 HjAdERgvCADjwYlWH
doors2.txt;1

# buy cytotec pills online cheap - https://cytotecsale.pro/# 2023/04/28 13:03 Cytotec
buy cytotec pills online cheap - https://cytotecsale.pro/#

# canadian pharmacies recommended by aarp https://pillswithoutprescription.pro/# 2023/05/15 22:05 PillsPro
canadian pharmacies recommended by aarp https://pillswithoutprescription.pro/#

# mens erection pills https://edpill.pro/# - buy ed pills online 2023/06/27 5:21 EdPills
mens erection pills https://edpill.pro/# - buy ed pills online

# ed meds online without doctor prescription https://edpillsotc.store/# - treatments for ed 2023/10/07 16:00 EdPills
ed meds online without doctor prescription https://edpillsotc.store/# - treatments for ed

# doxycycline online https://doxycycline.forum/ doxycycline hyclate 100 mg cap 2023/11/25 3:47 Doxycycline
doxycycline online https://doxycycline.forum/ doxycycline hyclate 100 mg cap

# acquisto farmaci con ricetta https://farmaciait.pro/ farmacia online 2023/12/04 3:41 Farmacia
acquisto farmaci con ricetta https://farmaciait.pro/ farmacia online

# ed meds https://edpills.tech/# best male ed pills 2023/12/22 23:45 EdPills
ed meds https://edpills.tech/# best male ed pills

Post Feedback

タイトル
名前
Url:
コメント