☰

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

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

私の考えでは、grepとawkはNFA（非決定的）正規表現マシンを使用しているということです。
このページの中央にある画像は次のとおりです。正規表現の一致は簡単で高速です。これが実際に真であることを確認してください。

最初のシフトが一致すると、NFAの実装が中断される可能性があることが知られています。たとえば、リンクされた記事のNFAマシンは次のとおりです。たとえば、abab | abbbのNFAを考えてみましょう。:

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

正規表現は、abab|abbb最初の正規表現と一致すると、文字列の右側と一致する状態に達します。このとき、終了点に達してマッチング状態に達すると停止する（Ｓ１０）。別の一致があっても追加の入力をテストする必要はありません。ababbbbabababbb

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

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

結果はでなけれcatばなりませんがcatfish。交換の有無にかかわらず、結果は同じです。

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

そして、デフォルト値を変更できますか？

答え1

標準では最長のマッチングが要求されるため、POSIX準拠のORでgrepこれを行う方法はないと思います（例えば、マンページを参照）。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

私が知る限り、実際にはNFAマシン2台:

  • 従来のNFAエンジン
    追跡可能なNFAマシン最も長い左の一致が常に尊重されるわけではありません。。

  • POSIX NFAエンジン
    すべての状態を並列に処理し、入力文字列から一致するものを選択できる非逆追跡NFAエンジン。一番左から最も長い一致を選択するのはPOSIXの要件です。

しかし、DFAバックトラッカー（Perl）は指数爆発(2^n)正規表現ではなくテキストで駆動され、最初の代替項目を選択または選択しないことがあります。

またあります。DFA は、すべての可能な一致を同時に識別します。。

そして、質問にリンクされた記事の作成者と判断すると、re2 の実装では、シフトを次のように定義します。 x|y ==> x または y (x が好ましい)つまり、交互に最初の項目を好みます。

したがって、要約すると、代替部分が選択されるNFAまたはDFAを実際に関連付ける方法はなく、実装によって異なります。

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

関連:

関連情報