☰

交互に最短一致を選択する方法はありますか?

tag-icon • tag-icon awk grep regular-expression
交互に最短一致を選択する方法はありますか?

grepとawkはNFA（非決定性）正規表現マシンを使用しているという印象を受けました。
このページの真ん中あたりにある画像では正規表現マッチングはシンプルかつ高速にそれが事実であることを確認します。

NFAの実装は、最初の交替が一致したときに停止する可能性があることが知られています。たとえば、リンクされた記事のこのNFAマシン例えば、abab|abbbのNFAを考えてみましょう。:

ここに画像の説明を入力してください

正規表現に対応するものは、最初の一致時にabab|abbb文字列の右側の一致状態に到達します。その時点で、最後に到達して一致状態 (S10) になったため停止します。別の一致が可能である場合でも、それ以上の入力をテストする必要はありません。ababbbbabababbb

つまり、このコードでは次のようになります。

echo 'catfish' | grep -Eo 'cat|catfish'

結果は になるcatはずですが、 になっていますcatfish。 交代が入れ替わっても、結果は同じです。

grep 正規表現エンジンが常に最長一致を見つけるのはなぜですか?

そして、そのデフォルトを変更することは可能ですか?

答え1

実際、標準では最長一致が要求されるため、 POSIX 準拠のgrepまたはでこれを行う方法はないと思います(たとえば、 man ページを参照してください)。awkregex(7)

プログラムと正規表現を変更することで、例えば、希望awkする出力を得ることができます。awk

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

pcregrepこのような状況では、 (pcre perl 互換正規表現ライブラリの一部)を使用します。これにより、次のように番号付きサブグループを指定できます-o。

echo SetValue | pcregrep -o1 '(Set)(Value)?'

または、pcreには非貪欲なマッチングの構文があるため、

echo SetValue | pcregrep -o0 'Set(Value)??'

答え2

私が理解できた限りでは、実際には、2台のNFAマシン:

  • 従来のNFAエンジン
    バックトラックを行うNFAマシン最長左端の一致が常に尊重されるわけではない。

  • POSIX NFA エンジン
    すべての状態を並列に処理し、入力文字列内の任意の一致を選択できる非バックトラック NFA エンジン。最も左にある最長の一致を選択することは、POSIX の要件です。

しかし、DFAバックトラッキングマシン（Perl）は指数関数的に増加する（2^n）正規表現ではなくテキストによって駆動され、選択肢の最初のものを選択することができます (または選択しないこともできます)。

また、DFAはすべての可能な一致を並行して認識します。

そして、質問にリンクされている記事の著者によると、re2 実装では、交替を次のように定義します: x|y ==> x または y (x を優先)つまり、交代のうち最初のものを優先します。

したがって、結論として、NFA または DFA を、代替のどの部分が選択されるかに実際に関連付ける方法はなく、それは特定の実装に依存します。

そして、いいえ、特定の実装にデフォルトを変更するように指示する方法は見つかりませんでした。

関連している：

関連情報