2

このページ(およびその他のページ)によると、DFA 正規表現エンジンはグループのキャプチャをかなりうまく処理できます。アトミック グループ (または所有量指定子) に興味があります。最近よく使用していて、これがどのように行われるのか想像もつかないからです。

私は答えの最初の部分に同意しません：

DFA は、アトミック グループ化のような構造を処理する必要はありません.... アトミック グループ化は、エンジンが一致を完了するのを支援する方法です。

アトミック グループは、NFA エンジンの速度にとって重要であるだけでなく、より単純でエラーが発生しにくい正規表現を作成することもできます。プログラム内のすべての C スタイルの複数行コメントを見つける必要があるとしましょう。正確な正規表現は次のようになります。

  • 文字通りから始める/*
  • 以下のものを何でも食べる
    • を除く任意の文字*
    • a の*後に何かが続く/
  • これをできるだけ繰り返す
  • 文字で終わる*/

これは少し複雑に聞こえますが、正規表現は

/\* ( [^*] | \*[^/] )+ \*/

複雑で間違っています (正しく処理されません/* foo **/)。気が進まない (怠惰な) 量指定子を使用する方が良い

/\* .*? \*/

しかし、それはライン全体を食べることができるので間違っています

/* foo */ @#$!!**@#$ /* bar */

ガベージで失敗した後の部分式によるバックトラックが発生した場合。上記を原子グループに入れると、問題がうまく解決されます。

(?> /\* .*? \*/ )

これは常に機能し (願っています)、可能な限り高速です (NFA の場合)。だから、DFAエンジンでどうにか扱えるのだろうか。

4

1 に答える 1

1

DFA は、アトミック グループ化のような構造を扱う必要はありません。DFA は「テキスト指向」であり、「正規表現指向」の NFA とは異なります。つまり、アトミック グループ化は、(NFA) エンジンが試行する際に、エンジンが一致を終了するのを支援する方法です。ある位置で一致を見つけるために可能なすべての順列、一致することさえありません。

簡単に言えば、アトミック グループ化は、バックトラッキング位置を破棄します。DFA はバックトラックしないため (NFA のようなテキストに対する正規表現ではなく、一致するテキストが正規表現に対してチェックされます。DFA は決定ごとにブランチを開きます)、存在しないものを破棄しても意味がありません。

JFFriedl の Mastering Regular Expressions (Google Books)をお勧めします。彼は DFA の一般的な考え方を説明しています。

DFA エンジン: テキスト指向

正規表現指向の NFA エンジンを、文字列をスキャンしながら「現在作業中」のすべての一致を追跡するエンジンと比較してください。今夜の例では、エンジンが t に到達した瞬間に、現在進行中のリストに潜在的な一致を追加します。

[...]

後続の各文字がスキャンされるたびに、可能な一致のリストが更新されます。さらにいくつかの文字が一致すると、状況は次のようになります

[...]

作品には2つの可能な一致があります（そして、1つの選択肢であるナイトが除外されました）. 続く g では、3 番目の選択肢のみが実行可能です。h と t もスキャンされると、エンジンは完全に一致していることを認識し、成功を返すことができます。

テキストからスキャンされた各文字がエンジンを制御するため、私はこれを「テキスト指向」マッチングと呼んでいます。例のように、部分一致は、さまざまな可能性のある一致の開始点になる可能性があります。有効でなくなった一致は、後続の文字がスキャンされるときに削除されます。「部分試合中」でも完全試合になる場合もある。たとえば、正規表現が ⌈to(…)?⌋ の場合、括弧で囲まれた式はオプションになりますが、それでも貪欲であるため、常に試行されます。これらの括弧内で部分一致が進行中の場合は常に、(「to」の) 完全一致が既に確認されており、より長い一致がうまくいかない場合に備えて予約されています。

(出典: http://my.safaribooksonline.com/book/programming/regular-expressions/0596528124/regex-directed-versus-text-directed/i87 )

グループと DFA のキャプチャについて: あなたのリンクから理解できる限り、これらのアプローチは純粋な DFA エンジンではなく、DFA と NFA のハイブリッドです。

于 2013-11-13T07:53:38.997 に答える