15

これがどこかに公開されている場合は申し訳ありませんが、私の大まかな検索では何も見つかりませんでした.

Python プログラミングを行っているときに、次のコマンドに気付きました。

re.sub("a*((ab)*)b", r"\1", "aabb")

空文字列を返します。しかし、sed の同等のコマンド:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/"

戻りますab。

aPython 正規表現の先頭にある "a*" ディレクティブが両方の に一致し、"(ab)*" が 0 回一致することは理にかなっていますが、 sed がどのようにab. これを引き起こす2つの正規表現エンジンの違いを知っている人はいますか? どちらもデフォルトで貪欲に星に一致すると思いますが、sed は左ではなく右から一致する可能性があることに気づきました。どんな洞察も大歓迎です。

4

2 に答える 2

4

Python と sed はどちらもデフォルトで貪欲ですが... Python 正規表現は、試行されているブランチが一致して続行できない場合、最終的に前の状態に戻る必要があるにもかかわらず、すべての状況で左から右に評価しようとします。反対に、Sed 正規表現は、正規表現をより決定論的な形式に書き換えることにより、不要なバックトレースを防ぐために評価前に最適化されます。したがって、結合されたオプションのパターン "aab" は、最も具体的な可能な文字列が最初に試行されるため、通常の "a" よりも前にテストされる可能性があります。

Python パターンは、文字列 "aabb" を "aab" + "b" ("<>" で囲まれている) として 2 回一致させます。

>>> re.sub("a*((ab)*)b", r"<\1>", "aabb")
'<><>'

一方、sed は「aabb」全体を 1 つの置換で一致させます。

$ echo "aabb" | sed "s/a*\(\(ab\)*\)b/<\1>/"
<ab>

Python 正規表現バックトレース アルゴリズムは、正規表現のハウツーで説明されています。「ステップバイステップの例...」という言葉で紹介されている 2 つの段落で物事を繰り返します。正規表現ドキュメントで説明されているとおりに IMO を実行します。「ターゲット文字列がスキャンされると、'|' で区切られた RE は左から右に試行されます。」

デモンストレーション

「(|a|aa)」の順番です。"(aa|a|)" は Python によって尊重されます

>>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb")
'<ab>'
>>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb")
'<><>'

ただし、sed は正規表現を最適化するため、この順序はsed によって無視されます。「aab」+「b」のマッチングは、パターンから「a」オプションを削除して再現できます。

$ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g"
<><>

編集：現在のテキストから証明できないため、DFA/NFA に関するすべてを削除しました。

于 2012-08-25T18:34:26.767 に答える
2

あなたが作った面白いパズル。私が読んだことによると、python と sed の両方の正規表現エンジンは、Henry Spencer の正規表現ライブラリ (perl のものと同様) に基づいており、バックトラッキングに依存しています。（残念ながら、私がこれに基づいている記事を見つけることができません）。

とにかく、これは実装の詳細であると想定されているものではありません: Python の動作は POSIX 標準に反しており、RE は (a) 可能な限り早い時点で一致し、(b) その時点で始まる可能な限り長い文字列と一致する必要があります。 . (これについてはman 7 regex(Linux の場合) を参照してください。)

最長の一致を見つけるために、バックトラッキング (「NFA タイプ」) 正規表現エンジンは、1 つの一致を見つけた後も代替案を調べ続ける必要があります。したがって、実装者が手抜きをしたことは驚くべきことではありません。明らかに、Python の動作は、最長の一致を見つけることができないため、準拠していません。sed マニュアルページによると、sed は「パフォーマンス上の理由から」常に準拠しているわけではありません。しかし、明らかに、このケースは正しくなります。

ちなみに、あなたのコマンドは完全に同等ではありません.sedは1回しか実行しませんがre.sub、可能な限り何度も置換をs/a/b/実行します.sedバージョンは次のようになるはずです:

echo "aabb" | sed "s/a*\(\(ab\)*\)b/\1/g"

これは、Python で空の文字列を取得する理由を説明しています。REaabは最初に一致し、残りbは 2 回目に一致し、各部分を削除します (すべてが正規表現a*の最後に一致するため)。bこれは、次のバリアントで確認できます。

>>> re.sub("a*((ab)*)b", r"X\1Y", "aabb")
'XYXY'
于 2012-08-25T19:12:09.267 に答える