私の C は少し不安定ですが、python のソース コードを調べたところ、ほとんどの python のreモジュールはステート マシンによって実装されているようです。正規表現は決定論的な有限状態マシンに還元できるため、これは当然のことです。
他の正規表現の実装も似ていると思います。しかし、現代の正規表現の実装が、教科書の定義に従って規則的であるものは、あるとしてもほとんどありません。では、後方参照などの不規則性をどのように説明するのでしょうか?
(.*)\1 // this is not regular
彼らは、修正された (有限状態を超えた) オートマトン クラスを使用してこれを説明し、バニラのトムソン アルゴリズムよりも複雑なマッチング アルゴリズムを使用します。特定の "RE" エンジンがサポートするオートマトン クラスの正式な特性を見つけた場合は、非常に幸運です。
Python ソース コードから作成できるものからre、グループをバッファーに格納し (これを一致オブジェクトの一部として返さなければならないため、いずれにせよ必要です)、一致アルゴリズムで単純な文字列一致を実行し、次のように消費します。グループマッチバッファにある文字数と同じです。
[任意の暴言: 残念ながら、実際の RE エンジンは、その数学的特性を破壊する NFA 上のハックの集まりです。多くの実装者は、正規言語の洗練された代数と正規関係への強力な拡張を無視しており、 FSTによって効率的に捉えることができます。]