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

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

ただいまの
回答率

88.83%

内包されているときのバックトラックの動きが分からない

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 1,085

aaaaaaaa

score 481

詳説正規表現第四章157pにて*+のバックトラックの仕組みについて解説している箇所の一節に分からないとこがありました。

x*」が「x?x?x?x?x?x?…」(より正確には「(x(x(x(x…?)?)?)?)?」のようなものだと考えれば、これまでに見てきたものと大きな違いはない。
エンジンは、スターの対象となっている要素をチェックする前に、チェックが不成功になったら(あるいは最終的に不成功だとわかったら)、スターの後ろの物をチェックするためのステートを保存する。このステートの保存は、スターによるくりかえしマッチが不成功になるまで続く。

上記の(x(x(x(x…?)?)?)?)?の動作についての疑問です。xの部分に対し任意の文字を意味する.に変更したうえで、文字列「123456789」を置換したとすると

(.(.(.(.?)?)?)?)?
↓
「$1」と「$2」と「$3」と「$4」と「$5」(←のように置換したとすると…)
↓
「1234」と「234」と「34」と「4


となります。$1の場合は、最も外側のカッコが1234をキャプチャし、最も外側のカッコに内包されている子カッコが234、その子括弧に内包されているカッコが34、最深部のカッコが「4」です。

文字列123456789に(.(.(.(.?)?)?)?)?をマッチさせるとき、マッチが開始した現在の状態(カレントステート▲)は、下記になります。

▲123456789 ▲(.(.(.(.?)?)?)?)?…「1」が任意の文字にマッチするか調べるが、マッチに失敗したときのために、「▲123456789」は、「(.▲(.(.(.?)?)?)?)?」にマッチするか?を保存。数字の「1」は、ドットにマッチ。

1▲23456789 (.▲(.(.(.?)?)?)?)?…「2」が任意の文字にマッチするか調べるが、マッチに失敗したときのために、「1▲23456789」は、「(.(.▲(.(.?)?)?)?)?」にマッチするか?を保存。数字の「2」は、ドットにマッチ。

...以下同じような動作。

マトリョーシカのようにカッコがカッコを内包しているときの正規表現の動きは、上記の形であっているのでしょうか。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • ikedas

    2017/03/08 21:50

    すみませんが、もう少し引用の範囲を広げてもらえませんか。節の最初から3段落くらいを引用しないと、読んだ人にはなぜそういう正規表現を持ち出してきたのかがわからないです。

    キャンセル

回答 2

checkベストアンサー

+2

正規表現の括弧はキャプチャの働きも持ちますが、それ以前に、部分表現をまとめる働きがあります。ご質問の引用箇所では、後者の働きが重要です。

状態の保存がされる場所が複数ある場合のバックトラックの動作について考えます。正規表現でのそのような場所を、以下では₁、₂、₃、…で示します。

たとえば「₁A?₂B?C」では、次のように動作します。

  • A?B?C」によるマッチは次のように動作する。
    ₁で状態を保存し、A?」によるマッチを試行。次にB?C」によるマッチを試行して、失敗したらバックトラックして₁の状態に戻り再試行。
    最終的に「A?」によるマッチですべての再試行が失敗した場合は、「A?B?C」によるマッチは失敗。

  • B?C」によるマッチは次のように動作する。
    ₂で状態を保存し、B?」によるマッチを試行。次にC」によるマッチを試行して、失敗したらバックトラックして₂の状態に戻り再試行。
    最終的に「B?」によるマッチですべての再試行が失敗した場合は、「B?C」によるマッチは失敗。

  • C」によるマッチは次のように動作する。
    状態保存はしない。マッチが失敗したら失敗。

A?」がマッチした後でバックトラックが起きる (状態₁に戻って再試行する) のは、後続する表現によるマッチが失敗したときです。バックトラックの条件は、後続する表現が失敗することだけで、後続する表現がどんなものなのかは考慮されません。つまりこの正規表現は「A?によるマッチが成功した後に、残りのマッチが成功する。失敗したらバックトラックする」という意味です。

よって、「A?B?C」は、バックトラックを考慮すると「A?(B?C)」と書けます。両者は同じものを表しています。

同様に、「₁x?₂x?₃x?₄x?…」は、次のように書きかえることができます。

  • x?(x?x?x?…)
  • x?(x?(x?x?…))
  • x?(x?(x?(x?…)))
  • x?(x?(x?(x?(…))))

下のものほど、バックトラックを考慮した「より正確」な表現だという言いかたもできるでしょう。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

仕様としては 0 回以上の繰り返しであり、実装としてはその処理系の自由です。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/03/12 15:44

    原著の該当箇所を見ると3つの正規表現の直後に脚注がついており、「DFAではこの3つは区別されない」という趣旨の断り書きがあります (訳書は持っていないのですが、同じ脚注があるはずです)。
    つまり、修正前の質問文のように断わりなく3つの正規表現を並べただけだと、Zuishinさんのように「実装によってはどれも同じである場合もある」という趣旨のご回答があっても不思議でないです。つまり、質問のほうに不備があったので、回答のほうにマイナス評価がつくのは不当です。

    質問者さんへ。ご自分がわかっていることなら他人にもわかっているとは限りません。質問を読む人の気持ちになって質問して下さい。「質問する」ボタンを押す前に、書いた質問文を読み返して、他人にわかってもらえる文章になっているか確認して下さい。

    キャンセル

  • 2017/03/12 20:27

    ikedas さんフォローありがとうございます。DFA については以前言及したのですが、なしのつぶてでした。

    キャンセル

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

  • ただいまの回答率 88.83%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

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