RE2-新しい正規表現ライブラリ

Googleは昨日、新しい正規表現ライブラリRE2をリリースしました。 ライブラリはC ++で書かれています。



正規表現の実装には、非決定性有限状態マシン （NFA）と決定性有限状態マシン（DFA）の2つのアプローチがあります。 最初の正規表現エンジンは、たとえば、Perl、Python、Ruby、および.NETで使用されます。 残念ながら、この場合、プログラムの実行時間は指数関数的に増加する可能性があり、スタックの使用も無限に増加する可能性があります。 この動作は、コード検索、Sawzall、BigtableなどのGoogleプロジェクトでは受け入れられなかったため、同社のプログラマーは決定論的な有限状態マシンに基づいたライブラリを作成しました。 RE2は、線形検索パフォーマンスと限られたスタック使用率を保証します。 DFAは、たとえばlexおよびegrepでも使用されます。 これらの実装のほとんどとは異なり、RE2はPCREのほぼすべての基本機能をサポートしています。



ライブラリはBSDライセンスの下で配布されています。



UPD ：NFAの例からTclが削除され、DFAが使用されるようになりました。