正規表現の仕様について

質問

"abcdefg"という文字列に対して、/a(bc|bcd)/ という正規表現で検索すると

秀丸エディタの正規表現検索では、"abcd"がマッチし、
スクリプト言語のrubyでは"abc"がマッチします。

これは使用している正規表現ライブラリで演算子'|'の評価の仕方が異なるのだと思うのですが、統一された仕様のようなものは存在しないのでしょうか？
他の正規表現ライブラリ間でもこのような細かな動作の違いというのは存在するのでしょうか？

回答No.3

kumoz · ベストアンサー

GNU Awk v3.1.8 (DFA 型)
awk 'BEGIN { str = "abcdefg"; sub(/a(bc|bcd)/, "xxx", str); print str; }
xxxefg

Perl v5.12.3 (NFA 型)
perl -e '$str = "abcdefg"; $str =~ s/a(bc|bcd)/xxx/; print "$str\n";'
xxxdefg

私もあまり詳しくはありませんが、DFA 型では選択を同時並行的に進めて、最長のものがマッチするようです。AWK は DFA 型を採用している少ない例で、Perl, Python, Ruby 等は NFA 型になっています。

お礼

ご回答ありがとうございました。

ご回答を拝見しまして、以前勉強の為にDFA型の正規表現エンジンを作成したこと思い出し試してみましたところ、確かにAWKと同じ結果になりました。

---
regexp : a(bc|bcd)
string : abcdefg
match : ^ ^ # aとdを指しています。

---NFA状態遷移表
no.: chr goto
0 : "a" [1]
1 : "b" [2, 4]
2 : "c" [3]
3A :
4 : "c" [5]
5 : "d" [6]
6A :

---DFA
NFAをDFAに変換
no.: NFA状態no.
0 : [0]
1 : [1]
2 : [2, 4]
3A : [3, 5]
4A : [6]

---DFA状態遷移表
no.: chr goto
0 : "a" 1
1 : "b" 2
2 : "c" 3
3A : "d" 4
4A :
---

仰るとおり、同時並行的に進めて最長のものがマッチするDFA状態遷移表が作成されました。
なるほど、DFA型とNFA型で動作が異なるのですね、参考になる情報ありがとうございました。

ただ秀丸エディタの正規表現ライブラリがDFA型かというとそうでは無いように思えますが、NFA型でも作り方によって動作というか結果が異なるのでしょうか。

回答No.6

kumoz

GNU sed v4.2.1 (or v1.18)
echo 'abcdefg' | sed 's/a\(bc\|bcd\)/xxx/'
xxxefg

sed は NFA 型に分類されていると思いますが、私の手元にある２つのバージョンの実行結果は DFN 型と同じになります。GNU 版は DFA 型を採用しているのか、あるいは NFA 型だが細かいところの違いがあるのか、どちらなんでしょうか。後者だとすれば秀丸と同じ状況？

お礼

再びのご回答ありがとうございました。

正規表現エンジン種類について検索しましたところ「詳細正規表現」という書籍のサンプルページを見つけました。
http://books.google.co.jp/books?id=RJFJ2I-thlsC&pg=PA141

そこには正規表現エンジンの種類として、DFA型、従来型NFA、POSIX NFA等があり、従来型NFAか否かを見分ける方法として正にこの質問で書いた正規表現の例が書かれておりました。
'abcd'がマッチするものはDFA型か、POSIX NFAというタイプであるとのことです。

正規表現エンジンの型というヒントをいただいたおかげで回答にたどり着くことができました、本当にありがとうございました。

回答No.5

notnot

＞私は演算子'|'の動作としては、rubyやpythonの動作が普通で秀丸エディタの動作が特異だと考えたのですが、その理解で良いのでしょうか？

「普通」「特異」とはなんぞやと言うことで変わってきます。

そもそも、正規表現は、ed エディタや grep コマンドなどが発祥なので、そういう観点からするとabcdにマッチするのが「普通」です(edやgrepだと /a\(bc\|bcd\)/ ですが)。

現在では正規表現が使われるのはプログラム中のことが多いと思う（個人的な推測）ので、そういう観点からするとabcにマッチするのが「普通」じゃないかなと思います。

お礼

ご回答ありがとうございました。
私の当該文章の中で書いた「普通」「特異」という表現は適切ではありませんでした、あの文章は個人的な感覚として書いてしまいました。
何らかの統一された仕様があり、それに則っているか、否かと書いた方が適切だったと思います。

あと、申し訳ありません、頂いたご回答の中で判らない部分があります。

> 正規表現は、ed エディタや grep コマンドなどが発祥なので、そういう観点からするとabcdにマッチするのが「普通」

これはDFA型のエンジンを搭載しているものは、abcdにマッチするのが普通という意味と理解しました。

> 正規表現が使われるのはプログラム中のことが多いと思う（個人的な推測）ので、そういう観点からするとabcにマッチするのが「普通」

この意味合いがよくわかりません？（一応、私の個人的な感覚とも一致はしているのですが……）
プログラムの式で使用される四則演算子の様に左結合していく（左の要素から評価する）のが普通と考えられるという理解で良いでしょうか？

回答No.4

yambejp

べつに興味本位ならとめませんが、
/a(bc|bcd)/なんて解釈がわかれる構文書いてたらいつまでたっても上達しないですよ

お礼

ご忠告ありがとうございます。

回答No.2

yambejp

どうなっているかが重要なのではなくどうしたいかです

条件が競合しているのであれば「どちらかがヒットする」で
どちらがヒットしても文句はいえないでしょう。

たとえばabcdを優先して、dがなくてもヒットするなら
/abcd*/
で十分ですね。（abcの後ろに0個以上のdがある）

今回の命題だと逆の条件はつけられないです
abcから始まってabcがヒットしたらそれでおしまいなら
abcdにはどうやってもヒットしません。

考えて書けばさほど問題になるケースではありません

お礼

ご回答ありがとうございました

> どうなっているかが重要なのではなくどうしたいかです

発端は望んだ検索ができなかったことによるのですが、この質問をさせていただいたのはあくまで興味というか素朴な疑問によるものです。
従いまして、この質問においては「どうなっているか」に重点がありますことお汲み取りいただけますと幸いです。

回答No.1

kmee

http://www.kt.rim.or.jp/~kbk/regex/regex.html
まったく統一されていません。

お礼

ご回答ありがとうございました

補足

申し訳ありません、質問の仕方が悪かった様ですので補足させていただきます。
ツールにより使用できる演算子が違うというのは存じ上げております。
質問の意図は同じ演算子でも動作が異なることがあるのは普通のことなのかということになります。

ご紹介いただいたリンク先を拝見しますと、演算子'|'は左右のどちらかにマッチしますと書かれております。
http://www.kt.rim.or.jp/~kbk/regex/regex.html#VBAR

質問に書いた正規表現で'|'の左右の文字を逆にすると、秀丸エディタでは結果が変わらず、rubyでは結果が変わります。
これは秀丸エディタの正規表現ライブラリでは、'|'の両側を評価してマッチする文字列の長い方を返す仕様だと理解しました。
一方rubyは'|'の左側を評価してマッチすれば右側は評価しないような仕様に見えます。
試しにpythonでも試しましたがrubyと同じ結果になりました。

私は演算子'|'の動作としては、rubyやpythonの動作が普通で秀丸エディタの動作が特異だと考えたのですが、その理解で良いのでしょうか？
それともこのような細かい動作の違いまで各ツール毎に異なっているのでしょか？