35.3.5 正規表現にまつわるトラブル

Emacsのregexp実装は他の多くの類似する実装と同じように概ね堅牢ですが、2つの問題のいずれかを引き起こすことがあります。それはマッチングが内部スタックスペースを使い果たしてエラーをシグナルしたり、完了まで長時間を要するかもしれないという問題です。以下のアドバイスはこれらの症状を軽減して、発生する問題を緩和する助けとなるでしょう。

• ゼロ幅アサーション(‘^’および\`)の使用による行、文字列、あるいはバッファー先頭のアンカーregexp。これは実装内部の高速パスを利用して、無駄なマッチングの試行を回避できる。これら以外のゼロ幅アサーションでも、早期にマッチを失敗させることによる利益が得られるかもしれない。
• orパターンを避けて文字候補を使う(‘a\|b’のかわりに‘[ab]’と記述する)。‘\s-’および‘\sw’はそれぞれ‘[[:space:]]’および‘[[:word:]]’と等価であることを思い出してほしい。
• orパターン最後の分岐はバックトラックポイントをスタックに追加しないので、もっともマッチしそうなパターンを最後に配置するよう検討する。たとえば‘^\(?:a\|.b\)*c’は‘a’からなる非常に長い文字列へのマッチを試みるとスタックを使い果たすだろうが、これと等価な‘^\(?:.b\|a\)*c’ならそのようなことはない。

  (これはトレードオフである。マッチに成功するorパターンは、もっとも頻繁にマッチするパターンを最初にすると実行が高速になる。)

• テキストの任意の部分がただ1つの方法でのみマッチするよう試みる。たとえば‘a*a*’は同じ文字列セット‘a*’にマッチするだろうが、前者は多くの方法でマッチを行うので、そのマッチが後で失敗すると低速なバックトラッキングを引き起こすだろう。可能ならorパターンの分岐を互いに排他にすることによって、そのマッチが失敗する前に2つ以上先の分岐には進まなくなる。

  ネストした繰り返しには特に注意。曖昧さが存在すると、それらのマッチングが非常に低速になるのは容易である。たとえば‘\(?:a*b*\)+c’は‘a’からなる適切な長さの文字列にたいするマッチ試行でも、失敗までに長時間を要するだろう。これと等価な‘\(?:a\|b\)*c’はより高速であり、‘[ab]*c’は更に良い。

• 本当に必要でないならキャプチャリングを使用しない。つまりカッコで括るのが目的なら‘\(…\)’のかわりに‘\(?:…\)’を使用する。
• rxの使用を検討する(Rx Notationを参照)。これはいくつかのorパターンを自動的に最適化するとともに、明示的に要求されなければキャプチャリンググループを決して導入しない。

上記アドバイスにしたがってなおregexpがスタックオーバーフローするようなら、ためらうことなくマッチングを複数の関数呼び出しで行い、それぞれの関数呼び出しではバックトラッキングが容易に含まれるように単純なregexpを使ってください。