質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.34%

  • 正規表現

    830questions

    正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。

グループ化した要素のバックトラック

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 337

aaaaaaaa

score 471

▲…マッチのカレントステート(現在の状態)
△…最初にマッチをしたところ

ABC  AB?C
という文字列「ABC」と正規表現AB?Cがあったとします。
Aがマッチし、▲を一つずらして下記のようになる。

△A▲BC  A▲B?C

「B」がB?にマッチするか調べるが、失敗してもよいように、文字列「B」が正規表現AB?▲Cにマッチするか?という保存ステートを保存。

<あとは質問と関係がないので省略>

ここまでの動作は、理解できます。ここで疑問が一つあります。別の正規表現になりますが、下記のようにバックトラックが発生する要素、つまり()*内にある否定先読みと*がグループ化されている場合、

<p>のマッチ後、あめんぼのの前まで進める…
△<p>▲あめんぼ </p>あおいな</p> あいうえお <p>▲((?!</?p>).)*</p>

最初の例の場合は、

「B」がB?にマッチするか調べるが、失敗してもよいように、文字列Bが正規表現AB?▲Cにマッチするか?という保存ステートを保存。

ですが、2番目の例の処理の場合は、
文字列「あ」が((?!</?p>).)にマッチするか調べるが、失敗しても良いように、「あ」が<p>((?!</?p>)▲.)*</p>にまっちするか?という保存ステートを保存。
あるいは、
文字列「あ」が((?!</?p>).)にマッチするか調べるが、失敗しても良いように、「あ」が<p>((?!</?p>).)*▲</p>にまっちするか?という保存ステートを保存。
なのか、いったいどちらなのでしょうか。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

ご質問の例は複雑で見づらいので、<p>P</p>Qに置き換えたもので説明します。次のようになります。

  • 文字列:
    Pあめんぼ QあおいなQ あいうえお
  • 正規表現:
    P((?!P|Q).)*Q

次のことに注意して下さい。
(1) 量指定子は、自身が量化している部分表現がどんなものかは知らない。ただ、その部分表現によるマッチを指定の回数だけ成功させようとするだけである。
(2) 正規表現エンジンは、連接する部分表現がマッチするかどうかを順番に試していくが、次にどんな部分表現が後続するかは知らないし、マッチさせている文字列に次にどんな文字が出現するかも知らない。
(次の部分表現が先読み表現だった場合も、その部分表現によるマッチを実際に試行するときにはじめて、次に出現する文字を調べます。)

ご質問の「2番目の例の処理の場合」は、前者がおおむね正しいです。以下、説明します。

まず注意の (1) により、量指定子は自身が量化している部分表現の詳細を知りませんから、(?!P|Q).という部分表現を仮にRで表せば
P₁R*Q
と表すことができます (「₁」は状態の保存がされ得る場所を示します)。

ですから、次のように動作するはずです (先日の回答も参照)。

  1. PR*Q」によるマッチは次のように動作する。
    P」によるマッチを試行。成功すれば「R*Q」によるマッチを試行して、失敗したら失敗。
  2. R*Q」によるマッチは次のように動作する。
    ₁で状態を保存し、「R*」によるマッチを試行。次に「Q」によるマッチを試行して、失敗したらバックトラックして₁の状態に戻り再試行。 
  3. Q」によるマッチは次のように動作する。
    マッチが失敗したら失敗。

ここで注意の (2) を確認していただきたいのですが、状態の保存はマッチさせられる文字列の中に次にどんな文字が現れるかに依存していません。


結果として、この正規表現はPあめんぼ Qにマッチします。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

「文字列」と「正規表現」の境界が分かりづらいので、区別できるように書く配慮があると助かります。
次の場合と仮定します。

var string = '<p>▲あめんぼ </p>あおいな</p>';
/<p>((?!</?p>).)*<\/p>/.exec(string);

((?!</?p>).) では </p> を消費できないので、後続の あおいな はテストする事すらしません。

Re: aaaaaaaa さん

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • 正規表現

    830questions

    正規表現とは特定の文字列によるパターンマッチングを行う際に用いられる宣言型プログラミングです。