11

正規表現の原子グループは分配的ですか？

つまり、(?>A?B?)常に(?>A?)(?>B?)？

そうでない場合は、反例を提供してください。

4

2 に答える 2

2

一般的な原子グループ

  1. アトミックグループ(?>regex1|regex2|regex3)は、その中で最初に成功した一致のみを取得します。つまり、バックトラックは許可されません。

  2. 正規表現は左から右に評価されるため、一致させる予定の順序を表現します。エンジンは最初の位置から始動し、一致を成功させようとし、必要に応じてバックトラックします。式を通るパスが一致に成功する場合は、その位置で一致します。

  3. 原子グループは分配的ではありません。ABC:( (?>(AB?))(?>(BC))一致なし）および(?>(AB?)(BC))（一致）で評価されたこれらのパターンを検討してくださいABC。

すべてのオプションコンポーネントを含む原子グループ

ただし、両方の部分がオプションであるシナリオは異なる場合があります。

2つの貪欲なオプション部分AとB（(A)?および(B)?）を持つ原子グループを考えます。任意の位置で、A一致する場合は、オプションのを評価するために移動できますB。それ以外の場合、A一致しない場合は、オプションであるため、これも問題ありません。したがって、(A)?どの位置でも一致します。同じロジックがオプションのに適用されますB。残っている問題は、バックトラックに違いがあるかどうかです。

すべてのオプションパーツ（(?>A?B?)）の場合、各パーツは常に一致するため、アトミックグループ内でバックトラックする理由はなく、常に一致します。そして、それは原子グループに属しているので、バックトラックすることは禁止されています。

別々の原子グループ（(?>A?)(?>B?)）の場合、各部分は常に一致し、どちらの場合もエンジンはバックトラックできません。これは、結果が同じになることを意味します。

繰り返しになりますが、エンジンはで最初に可能な一致のみを使用できます(?>A?)(?>B?)。これは、で最初に可能な一致と常に同じになり(?>A?B?)ます。したがって、私の推論が正しければ、この特殊なケースでは、複数のオプションのアトミックグループの一致は、両方のオプションのコンポーネントを持つ単一のアトミックグループと同じになります。

于 2012-05-31T02:47:49.830 に答える
1

指定しなかったので、(?>)他の言語でのグループ化演算子を見たことがないので、Perl正規表現を参照していると仮定します。

次のことを考慮してください。

ra = 'A?'
rb = 'B?'

/(?>${ra} ${rb})/xと同じ/(?>${ra})(?>${rb})/xです。

この場合、はい、どちらの方法でも機能します。ただし、バックトラッキングを無効にするため、および(?>)のその他の値には当てはまりません。rarb

たとえば、次のようになります。

ra = 'A*'
rb = 'AB*'

/(?>${ra} ${rb})/x！= /(?>${ra})(?>${rb})/x。

後者の場合、raはAのシーケンス全体を消費し、バックトラックを許可しないため、rbは一致しません。これは(?:)、グループ化演算子として使用した場合に機能することに注意してください。また、キャプチャグループを使用した場合()、一致は同じになりますが、副作用\1（ 、、 ...への割り当て\2）が異なることに注意してください。

于 2012-05-31T02:56:34.033 に答える