二つのマッチングアルゴリズムがあり、その一つは本当の正規表現(DFAに変換 することのできるもの)のためのもので、もう一つはそうではない正規表現 (non-regular regexps)のためのものである。
DFAのアルゴリズムはAho, Sethi, UllmanによるCompilersに あったアイデアを実装している(1)。
[One] approach [to pattern matching regular expressions] is to use a DFA, but avoid constructing all of the transition table by using a technique called "lazy transition evaluation". Here, transitions are computed at run time [when] actually needed. [T]ransitions are stored in a cache. [....] If the cache becomes full, we can erase some previously computed transition to make room for the new transition.
以上の2つの方法のほかに、DFAは使用するけれども、遷移の計算に“不精な 遷移評価”(遅延評価)とよばれる技法を導入して、遷移表全体を前もって 作成しておくのは避ける。というアプローチがある。このアプローチでは、 いままでのDFAとは違って、実行時にDFAの遷移を計算する。ただし、 その計算は、遷移のたびに行なうのではなく、ある入力文字による ある状態からの遷移がはじめて起きたときにだけ行なう。計算の結果は キャッシュに保存しておき、遷移はキャッシュへの問い合わせによって 決める。キャッシュの中に、該当する遷移がなければ、はじめてDFAでの 遷移を計算して、結果をキャッシュに書き込む。もし、キャッシュが一杯に なっていたら、以前に計算した遷移のどれかを消去して、新しい遷移の ための場所を確保する。
RXにおける実装は一般的には上記のものに基づいたものであるが、 上記の説明はPOSIXパターンに対して使われるものをカバーしている。
非DFAアルゴリズムは Henry Spencerがemailで説明してくれた "recursive decomposition" 技法を実装している。与えられたパターンに対し、 このアルゴリズムはまず最初にそれが(スーパーセット言語である)DFAパター ンにマッチするような単純なものであるかどうかを検査して、もしそうであ れば非DFAパターンがマッチしなければ detail-workを検査のために実行する。
rx_make_solutions, rx_next_solution and
detail workは通常、部分式に対する recursingを必要とする。たとえば、二
つの部分式を連結したものは、ある文字列が正しい順序でそれぞれの部分が
一つの部分式にマッチする二つの部分に分けられるのなら、その文字列にマ
ッチする。与えられたある一つのパターンに対して、複数の解決策がほとん
どの場合に使用可能である。この曖昧性は 仕様にある“最左最長”規則に
従うためであり、バックトラッキング
rx_make_solutions, rx_next_solution,
rx_free_solutions といった stream-of-solution 関数
を指向するためである。
rxspencer.[ch] -- 非DFAアルゴリズム rxanal.[ch] rxsuper.[ch] rxnfa.[ch] -- DFAアルゴリズム