Q&A
ATOM とは結果が異なりますね。
私は ATOM の正規表現エンジンのバグではないかと疑っています。
否定先読みについて困っております。実行環境はatomです。
#聞きたい事
・私の考えのどこが間違っているのか？
・プログラムは正規表現をどう理解してマッチ部分を判断しているのか、流れがしりたい。
（まず括弧内をひと固まりにする⇒左の塊から見ていく⇒マッチしたものが見つかった場合は正規表現の欄の左右に記号が無いかを見る⇒あった場合はその記号の意味を適用し先ほどのマッチした文字の条件をもう一度見る、のような）
汚くて申し訳ないのですが私の解釈はこうです。（私の考えの部分が間違っているはずです）
#現在の私の考え
###画像左
前方に「値段」という文字を含まない「値」という文字を検索する。
・２４行目２文字目の「値」はマッチすると思っていたがしていない
・２４行目４文字目の「値」は前方に「値段」という文字があるのでマッチしないと思っていたがしている
・「(?<!)値」という表記も試してみたが、atomでは使えないようだった
###画像右
後方に「値段」という文字を含まない「値」という文字を検索する。
・２４行目二文字目は、後方に「値段」という文字が来ている為マッチしないと思っていたらマッチしている
#参考にしたサイト
https://msdn.microsoft.com/ja-jp/library/cc392020.aspx
https://abicky.net/2010/05/30/135112/
http://uxmilk.jp/50674
http://d.hatena.ne.jp/satosystems/20100519/1274237784
他多数
##所感
サイトによって表現がバラバラだったり、実際試してみると思い通りいくときといかない時がある。
根本的に理解が足りてないと思うが上手くいかない度合いがすごいので、基本の所で単純な勘違いをしているかも・・・
正規表現は理解が足りていないと、バグを簡単に入れ込んでしまうと思うので使用が怖い・・・
##追記２（混乱再び）（画像を載せる為）
・(?=hoge)はhogeの左側の位置とマッチングする
・(?<=hoge)はhogeの右側の位置とマッチングする
なるほど！位置とマッチングという考え方が抜けていたのか
という事は(?!=hoge)はhogeの左側以外の位置とマッチングするのかな？
orz...
ーーーーーーーーーーーーーー訂正ーーーーーーーーーー
私の書き方が間違えておりました。(?!e)と否定先読みのアンカーだけで検索することで、e前の空白文字列以外が検索されました。
ーーーーーーーーーーーーーーーーーーーーーーーーーー
という流れを辿っています。位置とマッチングだと正規表現の書き方としてすごく分かりやすかったのでうれしかったのです残念です。
またこれでは、先読みと後読みという言葉の意味理解ができていないです。
###追記３
コメントでは表現が見えづらいのでこちらを使用させていただきます。
KSwordOfHaste様のコメントに対してです。
(?![a-e])[b-f] と f とのマッチングの様子を先読み後読みの表現が加わるように書いてみます。
１、検索文字列(?![a-e])と本文ｆの左の位置が比較される
２、検索文字列(?![a-e])は次に本文[a-e]が来る可能性があるため、本文ｆの左の位置をとりあえずキープしつつも次の本文の文字を読んでみる（これが先読みと言われる所以）
３、本文fが来た事により、検索文字列(?![a-e])と本文ｆの左の位置がマッチング
４、検索文字列(?![a-e])[b-f]のうち(?![a-e])がマッチングしたので、検索文字列[b-f]の検索に入る
５、本文ｆの左の位置はマッチングされたので次の検索比較される本文はf
６、検索文字列[b-f]は本文fと比較されマッチング
７、検索文字列(?![a-e])[b-f]がすべてマッチングする箇所が見つかったので、本文f（正確には{ｆの左の位置+f}）はマッチングした文字列となる。
８、次の比較対象を求め検索文字列(?![a-e])と本文ｆの右の位置が比較される
９、検索文字列(?![a-e])は次に本文[a-e]が来る可能性があるため、本文ｆの右の位置をとりあえずキープしつつも次の本文の文字を読んでみるが文字は無い
１０、検索文字列(?![a-e])はアンマッチングなので、本文を本文ｆの右の位置から一文字進めようとするが無い
１１、最後まで検索したので検索終了
この流れであってますかね？
###お礼
否定先読み正規表現のマッチングがよく分からなかったので質問したのですが、Atomの使用や入力ミスそのほか様々な要素がアンマッチとなってしまった為、コメント含め複雑化してしまったようです。
しかし、テスト用に正規化されているとはまったく言えない入力文字列の画像で始まる質問にも、親切に答えてくださる皆様とマッチングできた事をとても嬉しく思っております。
お後がよろしいかは置いておいて、また色々な事を考えるきっかけとなりました。
ありがとうございました。
（僕はこの時間お腹が減る事を先読みしキープしておいたお菓子を食べながら作業を進めたいと思います）
回答6件
4
ベストアンサー
理解のポイントは，先読みがアンカーである，という事実です。
^ や $ といったアンカーは分かりますよね。先読みはアレの仲間です。
^ は，行頭という位置に存在する空文字列（長さ 0 の文字列）を意味します。
だから，^foo は行頭にある foo だけにマッチするわけです。
^foo は ^ と foo の連接です。
（連接というのは \d+ と 年 をくっつけた \d+年 のように，二つのパターンをつなげたもの）
先読みもアンカーである以上，〈特定の条件を満たす位置に存在する空文字列〉を表します。
R が何らかの正規表現であるとして，肯定先読み (?=R) を考えましょう。
このアンカーは，〈R にマッチする文字列が直後に存在する，そんな位置にある空文字列〉です。
否定先読み (?!R) は，〈R にマッチする文字列が直後に存在しない，そんな位置にある空文字列〉です。
だから，u32 という文字列に対し，
(?=\d)で検索して*に置換すれば，u*3*2になるし，(?!\d)で検索して*に置換すれば，*u32*になります。
肯定版と否定版で位置が完全に相補的であることに注目してください。
残念なことに Atom 上でこの実験はうまくいかないので，ブラウザーのコンソールなどを使って，JavaScript で
js
1"u32".replace(/(?=\d)/g, "*") 2"u32".replace(/(?!\d)/g, "*")
を試してみてください。
Atom でうまくいかないのは，正規表現エンジン自体の問題ではなく，空文字列にマッチする正規表現での検索・置換の動作がおかしいだけだと思います。
Atom でも，先読みを他のパターンと組み合わせて，長さ 1 以上の文字列を検索させるようにすれば期待どおりの動作となります。なので，先読み自体の理解は上記のとおりで大丈夫です。
上に挙げた，u32 を置換する例が完全に理解できるなら，答えは出たも同然です。
値値段値 というテキスト中で，(?!値段) にマッチする位置を * で示すと，*値値*段*値* となります。
そしてこの * の位置（にある空文字列）に続けて 値 が存在する，となると，第 1 字，第 4 字の「値」が該当します。
というわけで，正規表現エンジンの実装方法など考えなくてもよいのでした。
「追記２」で混乱されていますが，実は非常に正しい理解をなさっています。
追記２の最後の実験が期待どおりでないのは，書き方が間違っているからです。
(?!e) と書こうとして (?!=e) と書いてしまっているので，〈直後に =e が存在しない位置〉を検索しています。
投稿2018/01/10 06:05
総合スコア2108
3
正規表現は得意ではないのですが、よく使っているツールがあるので。
https://regex101.com/
こちらのサイトで、左上のメニューから「Regex Debugger」を選択すると、挙動が追えます。
便利です。
投稿2018/01/10 01:47
退会済みユーザー
総合スコア0
ん？この結果だと3番目の値はマッチしてますよ？
すみません。見間違えたようです。
とっても役に立ちそうなサイトなのですが、デバッガーの表示を見ても各ステップで何が比較されているのかさっぱりわかりません・・・
記載画像の各行では何をどのように判断し左右の選択位置が動いているのでしょうか？
私の理解では、文字間にある細い縦棒の箇所がポインタ、左の色付き箇所が現在の走査パターン、右の色付き箇所が走査箇所の認識です。
左のパターンの走査が最後まで行くと、マッチ。マッチしなければ、（見切れていますが）赤い矢印がついて、最初から。
残念ながら、取説があるわけではないので、いろいろ試してみて理解するしかナイっぽいです。
濃い色とうすい色の違いとか分かっていません＾＾；
英語が判ると情報の収集能力が格段にあがりそうでね・・・。
ありがとうございます。
3
(?!値段)値
24行目4文字目の「値」は前方に「値段」という文字があるのでマッチしないと思っていたがしている
否定先読みの意味を少し勘違いしておられます。
text
1値値段値 2 ^ここを調べているとき 3<----> <=この範囲に「値段」が存在しないという意味(A)ではない 4 ____ <=この位置が「値段」でないことをチェックするという意味である 5 6 7(A)の意味にするなら次のように書きます 8 9(!?値段.+)値 10 11もう少し分かり易くするなら 12 13(!?値段.*.)値 14 ^ ここが否定先読みの次のパターンである「値」の位置にあたる部分 15 ______ この範囲が今チェックしようとしている位置の直前までの部分
追加３について
比較の様子を「処理になぞらえて」理解するのもよいのですが、どちらかといえば宣言的に理解した方がよいというのが自分の考えです。
何度も例を変更して申し訳ないですが・・・
正規表現に含まれる連続したパターン..., A , B, ...がありBが先読みでも後読みでもないとして...
text
1Aが先読みパターン: 2 ...|x|x|x|x|x|... ＜＝照合対象の文字列 3 ^ Aを照合するまでの照合対象位置がここだとすると 4 ^_ _ ... Aは^の位置から始まる部分文字列と照合する。 5 ^_ _ ... BはAと同じ位置から照合される 6 (要するにAの照合によりBの照合位置は変わらない) 7 8Aが後読みパターン: 9 ...|x|x|x|x|x|x|... ＜＝照合対象の文字列 10 ^ Aを照合するまでの照合対象位置がここだとすると 11 ... _ _$ Aは$の位置で終わる部分文字列と照合する。 12 ^_ _ ... BはAの照合位置の次の位置から照合される 13 (要するにAの照合によりBの照合位置は変わらない) 14 15Aが先読みでも後読みでもないパターン: 16 ...|x|x|x|x|x|x|... ＜＝照合対象の文字列 17 ^ Aを照合するまでの照合対象位置がここだとすると 18 ^_ ... _$ Aは^の位置から始まる部分文字列と照合する。 19 ^_ _ ... BはAの照合位置の末尾の位置から照合される 20
投稿2018/01/10 00:45
編集2018/01/10 06:50
総合スコア18404
質問者さんの疑問はマッチのメカニズムではなく「正規表現の意味」だと思ったのでNFA,DFAによるマッチングアルゴリズムの違いについては言及していません。どのアルゴリズムであろうと「正規表現の仕様」に従った結果が得られます。つまりNFA,DFAの違いは同じ結果を得るための実装の違いに過ぎません。とはいえ「正規表現の意味するところを正確に知る」ために実装であるNFA,DFAの詳細について触れることも役立つこともあるかも知れません。何が手がかりとなって「正しい意味を知るきっかけになる」かは人それぞれのところもあり、一概には言えないかも知れませんね・・・
回答ありがとうございます。
空白やインデントで、位置情報まで記していただき非常にわかりやすかったです。他の例もありがとうございます。
調べていて再び疑問がわいたのですが、
`(?!hoge)`と`(?=hoge)`は左側の文字を修飾する
`(?<!hoge)`と`(?<=hoge)`は右側の文字を修飾する
と思いました。（正確にはそう思うと理解ができたような気がした）
これでコンピューターの正規表現解釈アルゴリズムの理解まではいかなくても、狙った正規表現をかけるようになったかと思ったのですが、追記に記したような`(?=hoge)`であっても右側を修飾しているものを発見しました。これはどういう解釈をすればよいでしょうか・・・？何度もすみません
個人的意見としては右・左という理解よりも「先読み」「後読み」と言う理解の方が正確な捉え方だと思います。?=, ?!は「先読み」?<=,?<!は「後読み」と呼ばれたりします。
abcd
'(?=b)[a-z]{2}' => bcにマッチ(A)
'[a-z]{2}(?<=c)' => bcにマッチ(B)
(A)が先読みと呼ばれる所以は[a-z]{2}のマッチングに先だって「比較対象文字列を(?=b)のマッチングのために読み込むが、読み込んだ文字列はマッチ済みとして消費されず、[a-z]{2}のマッチングの際には再びマッチ対象として評価される」ということで、構文解析の分野ではこのような意味合いを先読みといいます。
(B)が後読みと呼ばれる所以は[a-z]{2}のマッチングの後から「既にマッチ済みの部分の最後の部分をもう一度(?<=c)のマッチング対象として評価する＝＞後からもう一度読み込む」という意味合いとして理解するとよいのではないでしょうか？
つまりどちらかといえば
?=,?!はあるパターンの右側（直後）を修飾するときに使う
?<=,?<!はあるパターンの左側（直前）を修飾するときに使う
と考えた方がわかりやすいと思います。
>(?=b)のマッチング
というのはbの左側の`位置`の事ですよね？これをマッチしてもマッチ済みとして消費せずに再び評価されるの意味がわからないです・・・
位置にマッチングという考え方も間違っているのでしょうか？（本投稿追記２を参照願います）
> これをマッチしてもマッチ済みとして消費せずに再び評価されるの意味がわからないです・・・
んー、意味を伝えるのは難しいものですね・・・
正規表現[a-e][b-f]を考えてみてください。この正規表現は[a-e]と[b-f]の二つのパターンが連続しているということを意味します。比較対象文字列abが与えられたとき[a-e]がマッチしたあと次のパターン[b-f]はどこからマッチが試みられるかと言えば直前の[a-e]がマッチした部分の直後からですよね？つまり[a-e]のマッチングで比較対象の文字列のaの文字は「マッチ対象として消費されてしまった」と見做すといった意味合いです。マッチングはまだマッチ対象として消費されていない部分が対象になるのが原則です。（このような表現は実装を踏まえた表現なのであまりよい表現とは言えないかも知れませんね）
さて
(?![a-e])[b-f]
をfとマッチを試みるとしましょう。(?!a-e])のマッチングがfと行われたとき条件は成立します。普通のパターンと先読みパターンが違うのはfが消費されず次のパターンの照合でそのまま対象になり続ける点です。fの次ではなくfが[b-f]のマッチング対象になるわけです。これが「消費せず」の意味です。
質問本文追記３を確認お願いします。
流れと２の先読みの所以の理解は正しいでしょうか？
本文に追記してみました。
詳しい追記ありがとうございます。
現在の理解で正しいようでした。何度もありがとうございます。
3
下記内容には間違いがあります。間違った経緯はコメント欄を参照下さい。
正規表現エンジンにより実装が異なります。実際には DFA(決定性有限オートマトン) と NFA(非決定性オートマトン) の違いにより結果が異なります。
DFA の場合、今見ている入力に対して次にやってくる遷移が確定されます。逆に NFA の場合、各々の入力に対して遷移は複数存在しています。
今回のケースであれば24行目の2文字目の「値」は、DFA の場合は24行目1文字目の「値」のマッチにより遷移を失ってしまった為、2文字目はマッチしなくなったという結果です。(文字がない、つまり先行しない)
逆に NFA の場合 (?!値段)値 は先行する事が必須となる為、24文字目1文字目は先行するものがありませんのでマッチしません。ちなみに20行目の違いもそれです。しかし24行目2文字目にはパターンにマッチする事になります。
DFA や NFA をキーワードに検索されると見つかると思います。
投稿2018/01/10 00:32
編集2018/01/10 05:03
総合スコア5030
内部実装の違いでメタ文字の意味まで変わってしまうことがあるんですか？
どちらで実装されているか公開されてない場合もあると思うんですが、それを忖度しなければいけないんでしょうか？
DFA と NFA で否定先読みの仕様が異なるとする何か公的な資料はありますか？
１．`(?!値段)`は左側の文字を修飾する為、`（無）のものの右側が「値段」でないもの`という意味となり、画像左側２０行目１－２文字目「値段」を見つけるが、（無）を検索しようがないので飛ばす。
２．画像左側２０行目１文字目「値」は１で飛ばされたので`値`の判定も特にされずにマッチしなかった。
【DFA、NFAについて】
２が起きているという事はDFAで検索されている可能性が高い。又は、NFAであっても内部で決まっているであろう優先順位的に`（無）のものの右側が「値段」でないもの`が優先されて２が起きている
という解釈はあっていますか？
既に domidomi さんが書かれていますが、実装次第だと思いますがありえるとおもいます。特にバックトラックに関する物だと「入力がない事」を否定のマッチとするか、「入力はあるがマッチしない」を否定のマッチとするかなど。DFA の場合、既に先行してしまっているので後者にしかなり得ません。NFA の場合は前者です。
資料……
重ねてしまい申し訳ないのですが、`全ての NFA は必ず等価な DFA に書き換えることができる`との記述をみました。（http://basicwerk.com/blog/archives/1511）
Zuishin様と似たような思いとして、正規表現の意味が一意に決まらない事を防ぐためにも、NFA処理もDFAと等価になるような優先順位付けがされているのではないでしょうか？
http://www.geocities.jp/oraclesqlpuzzle/regex/regex-mame-08.html こちらによると正規表現エンジン oniguruma は NFA で実装されている可能性が高いということです。
ATOM は oniguruma ではありませんでしたでしょうか？
正規表現は実装に名づけられた名前なので方言でしかないので[公的]な資料は出て来ないと思います。出てきてもそれは特定言語やエンジンの挙動の話になるかと。(肯定|否定)(先読み|後読み)は実装によりパターン識別や結果も異なるのが現状という認識です。また NFA の場合は最短でマッチする文字が使われるので結果が異なる事も普通にあり得ると思います。
では NFA DFA の話は今回関係ないということにはなりませんか？
atom は node-oniguruma のはずなので NFA ですね。
DFA で否定先読みができるものはありますか？
> では NFA DFA の話は今回関係ないということにはなりませんか？
僕はこの質問を「なぜマッチしないのか」という物よりは「私の考えのどこが間違っているのか」あるとフォーカスしました。domidomi さんの考えはおそらく DFA だったと思ったので DFA/NFA により異なる事を示させて貰いました。
> DFA で否定先読みができるものはありますか？
バックトラックの実装次第だと思います。Vim も DFA でバックトラックできる実装の一つです。
私の知見が足りず、飛び交う様々なコメントのやり取りでは判断できなかったので明示的にお聞きしたいです。
私の記述したこの回答に対する二つ目のコメントの内容の解釈は正しいでしょうか？
http://d.hatena.ne.jp/osyo-manga/20131009/1381330204
古くは DFA だったようですが、2013 年には NFA になっているようです。
古いエンジンを使って否定先読みができるということでしょうか？
domidomi さん
> 私の記述したこの回答に対する二つ目のコメントの内容の解釈は正しいでしょうか？
はい。その認識です。
Zuishin さん
Vim は正規表現エンジンを2つ持っていて、DFA/NFA 両方使えます。regexpengine というオプションで切替えられます。デフォルトでは DFA → NFA という順で試す様になっています。
大変ありがとうございます、皆様の知識の深さには驚きを隠せません。
追記の「`(?=hoge)`であっても右側を修飾しているもの」、「`(?<=hoge)`であっても左側を修飾しているもの」の謎についてもう少し調べてみます。
言葉の使い方が悪かったようです。
DFA の使用を強制して否定先読みをすることができるでしょうか？
それならば今回の結果とは違う結果になるということでしょうか？
ちなみに NFA である .NET Framework では異なる結果が出ています。
私の質問意図は、各エンジンの仕様の違いではなく本当に DFA と NFA の違いなのかということです。
DFA と NFA の違いであるならば、DFA エンジンでは DFA エンジンの結果が出るし、NFA エンジンでは NFA エンジンの結果が出るということになります。
資料が無いのであれば、これを知りたければそれぞれのエンジンでの結果を集計するしかないと思います。
今のところ NFA エンジンで否定先読みできるものは多くありますが、DFA ではみつかっていません。
vim も本当に否定先読みに DFA を使っているのか微妙では検証になりません。
むしろ、DFA NFA ではなく Oniguruma の結果がほかのエンジンと違うということではないかと思っています。
Oniguruma と同じ結果のでるエンジンはありますでしょうか？
> Oniguruma と同じ結果のでるエンジンはありますでしょうか？
これは各々の実装を見てみないと分かりません。
> vim も本当に否定先読みに DFA を使っているのか微妙では検証になりません。
Vim は regexpengine=1 にすると DFA だけで、regexpengine=2 にすると NFA だけで処理を行います。Vim の DFA 実装では実際に先読みの識別を見つけた時点でレジスタにブランチ位置を保持しながら読み取りを進め、バックトラックが必要になった時点で前のブランチに戻る処理が書いてあります。
gvim80-586 でやってみました。
E486: パターンはみつかりませんでした: (?!値段)値
否定先読みに対応していないようです。
Vim の否定先読みはパターンの指定方法が一般的な物とは異なります。
/\%(値段)\@!値
参考 :help \@!
ありがとうございます。
使わないもので知りませんでした。
でも NFA と同じ結果が出たようです。
そちらでは NFA と DFA とで違う結果になりますか？
うっ。すいません！
こちらの間違いだったようです。
/\%(値段)\@!値
を
/\%(\値段)\@!値
と書くと DFA エンジンと NFA エンジンで差が出た様です。vim のバグですね。。。本文、修正しておきました。
domidomi さん、他の方のを参考にして下さい。。。すいません。
Atom の検索・置換の正規表現エンジンが Oniguruma というのは確かでしょうか？
以下の特徴からして，とても Oniguruma とは思えません。
①Unicode プロパティーの文字クラス `\p{Latin}` が使えない。
②`\u3000` は使えるけどカーリーブラケットを使った `\u{3000}` が書けない（したがって，コードポイントが 5 桁以上が指定できない？）。
③戻り読み（look behind）が使えない。
④BMP（基本多言語面）外の文字が二文字として認識される。
JavaScript くさいですが・・・
確かめてはいませんが
https://en.wikipedia.org/wiki/Oniguruma
It is also used in products such as Atom とあります。
その Wikipedia の記事の参照先ブログでは，
> TextMate の文法サポートのために Oniguruma まわりのラッパーを書いた
と述べているだけで，Atom エディターの検索機能のエンジンが Oniguruma だとは読めませんね。
Atom のリポジトリーで「もっとマシな正規表現エンジンを使って欲しい」という issue を見つけました。
Use a better regular expression engine · Issue #571 · atom/find-and-replace
https://github.com/atom/find-and-replace/issues/571
どうも V8 ぽいですね。
で，V8 の最新版に戻り読みが入ったので，いずれ Atom で使えるようになるだろうみたいなことが書いてあります。
なるほど node-oniguruma は text mate 用だったんですね。
1
正規表現には「文字」にマッチする表現と「位置」にマッチする表現があります。
先読みとか後読みとか言われているのは後者に当たります。文字マッチする表現を「修飾」するというのはちょっとずれているのではないかなと感じます。
これまでいろいろ見てきて私にとって一番すんなり理解できた解説webページのURLを貼っておきます。
https://abicky.net/2010/05/30/135112/
投稿2018/01/10 05:23
総合スコア13727
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/01/10 07:13