1

私は、現在の組み込み C++ プロジェクトで Xpressive を広範囲に使用しています。

私が知っているように、Xpressive はスタックの優れたユーザーです。しかし、より効率的なスタック効率の Xpressive 正規表現アプローチはありますか?

たとえば、32 ビット整数を表す文字列に一致する正規表現は、数字 6 が 6 以下かどうかをテストする必要がある場合があります。

Xpressive (および他の正規表現エンジンも、私が知っている) では、次のような多数のアプローチが可能です。

range('0','6')

また

('0'|'1'|'2'|'3'|'4'|'5'|'6')

また

set['0'|'1'|'2'|'3'|'4'|'5'|'6']

正規表現は、次の 3 つの数字を許可する場合があります。

repeat<3>(_d) >> _b

また

_d >> _d >> _d >> _b

しかし、選択肢があり、ソース コードのレイアウトをあまり気にしない場合、次の場合に最適なアプローチは次のとおりです。

a) スタック;

b) 速度;

c) ?

4

1 に答える 1

2

バックトラッキングが必要なため、シーケンシングと繰り返しはスタックを使い果たします。あなたの例を見てみましょう。

range('0','6')

これは、文字が文字範囲内にあるかどうかを確認するためのクイック チェックとして実装されています。シーケンスや繰り返しを使用しないため、スタック スペースを消費しません。

('0'|'1'|'2'|'3'|'4'|'5'|'6')

一般に、セットまたは範囲に入れることができるものを別のものに入れないでください。この種のことには、はるかに効率的です。明らかに、これは有効な xpressive 正規表現ではないことに注意してください。次のように記述します。

(as_xpr('0')|'1'|'2'|'3'|'4'|'5'|'6')

私はあなたがそれを知っていると確信しています。これに対して同様の編集を行います。

set[as_xpr('0')|'1'|'2'|'3'|'4'|'5'|'6']

セットは速いです。これらは、ASCII 範囲のルックアップ テーブルと (Unicode の場合) 256 を超える文字コードのスパース ベクトルとして実装されます。一部のセットはスパースであるため、このスキームは単純な範囲よりも多くのヒープ スペースを占有する可能性があります。ただし、それは、一致するときに使用されるスタック スペースの量には影響しません。次のように書くこともできます。

(set= '1','2','3','4','5','6')

繰り返しのために：

repeat<3>(_d) >> _b

前に述べたように、繰り返しは通常、バックトラッキングを正しく行うために再帰を使用して実装されます。しかし、この場合、xpressive は_dが 1 文字しか食べられず、それがちょうど 3 回繰り返されていることを認識します。したがって、この限られたケースでは、スタック スペースを節約するためにループを使用して実装されています。これは、次のケースとは対照的です。

_d >> _d >> _d >> _b

_d >> _d >> _dXpressive はと同じように扱うほどスマートではありませんrepeat<3>(_d)。その結果、これは ごとに個別のスタック フレームを消費します_d。

短いバージョン: より一般的な同等のものよりも、可能な場合は特殊な構造を優先します。これにより、最適化のためのより多くのコンテキストが xpressive に提供されます。

さらに、独立したサブ式について理解します。に何かを入れることができる場合は、それを選択keep()してください。なんで？keep()部分式に一致し、その部分一致によって使用されたスタック スペースを再利用します。そのため、そのサブ式に戻って別のことを試すことはできませんが、それが必要ない場合もあります。

それが役立つことを願っています。

于 2012-10-05T23:43:21.930 に答える