Regular Expressions
正規表現エンジンの種類

NFA

そのパターンによって NFA（Nondeterministic Finite Automaton）エンジンが駆動される 。

原理

正規表現パターンはツリーに解析されます。

現在位置ポインタは入力文字列の先頭に設定され、この位置で一致が試行されます。マッチすると、その位置は文字列の次の文字に増分され、別のマッチがこの位置から試行されます。このプロセスは、一致が見つかるまで、または入力ストリングの終わりに達するまで繰り返されます。

試合ごとに

このアルゴリズムは、与えられた開始位置に対してパターンツリーを走査することによって機能する。ツリー内を進むにつれて、一致する文字を消費して現在の入力位置を更新します。

アルゴリズムが、現在の位置で入力文字列と一致しないツリーノードに遭遇すると、それはバックトラックする必要があります。これは、ツリー内の親ノードに戻り、現在の入力位置を親ノードに入力したときの値にリセットし、次の代替分岐を試行することによって実行されます。

アルゴリズムがツリーを終了することを管理する場合、成功した一致を報告する。それ以外の場合は、すべての可能性が試されたときに一致が失敗します。

最適化

正規表現エンジンは通常、より良いパフォーマンスのためにいくつかの最適化を適用します。たとえば、ある文字で始まる必要があると判断した場合、入力文字列内のその文字が表示されている位置でのみ一致を試みます。

例

a(b|c)aと入力文字列abeacabます。

パターンツリーは次のようになります。

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

マッチは次のように処理されます。

a(b|c)a      abeacab
^            ^

aが入力文字列内で見つかっaはそれを消費し、パターンツリーの次の項目に進みます。最初の可能性を試してください：正確なb 。

a(b|c)a      abeacab
  ^           ^

bが見つかったので、交替が成功し、それを消費し、連結の次の項目に進む：正確なa ：

a(b|c)a      abeacab
      ^        ^

aは期待された位置に見つからない 。交互にバックトラックして、交互に最初に入力したときの値に入力位置をリセットし、 2番目の方法を試してください。

a(b|c)a      abeacab
    ^         ^

cはこの位置には見つかりません 。連結へのバックトラック。この時点で試す他の方法はないので、文字列の先頭には一致するものはありません。

次の入力位置で2番目の一致を試してください：

a(b|c)a      abeacab
^             ^

aはそこに一致しません 。次の位置で別の試合を試してください：

a(b|c)a      abeacab
^              ^

運もない。次のポジションに進んでください。

a(b|c)a      abeacab
^               ^

マッチ、それを消費し、交代を入力します。

a(b|c)a      abeacab
  ^              ^

bが一致しません。 2番目の選択肢を試してください：

a(b|c)a      abeacab
    ^            ^

c一致するので、それを消費し、連結内の次の項目に進みます。

a(b|c)a      abeacab
      ^           ^

マッチ、そして木の終わりに達しました。一致するものを報告してください：

a(b|c)a      abeacab
                \_/

DFA

入力によって DFA（決定論的有限オートマトン）エンジンが駆動される 。

原理

アルゴリズムは入力文字列を1回スキャンし、正規表現内で一致する可能性のあるすべてのパスを覚えています。例えば、パターンに交替がある場合、2つの新しいパスが作成され、独立して試行されます。指定されたパスが一致しない場合、設定されているパスからドロップされます。

含意

マッチング時間は、入力文字列サイズによって制限されます。バックトラックはなく、エンジンは複数のマッチを同時に見つけることができます。

この方法の主な欠点は、NFAエンジンタイプと比較して、エンジンによってサポートされ得る低減された特徴セットである。

例

a(b|c)a一致a(b|c)aとabadaca ：

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL