5.004_04においてREGALIGNがdefineされてないときの動作を元にした、 jperlの正規表現ルーチンに関するメモです。プログラムがそのまま 残っている部分が多々ありますが、おいおいきちんとした解説文に 直すつもりです(例によって未定な予定ですが ;-p)。
perlの5.005でもさらに正規表現ルーチンに手が入ってますので、この 解説がそのままは使えません。また、5.006では入力にUTF8を許して、 さらにインタープリターがUNICODE対応になりそうです。現在5.006開発 準備の5.005_xx(xx >= 50)で作業が進行しているようです。
pregexec編は最大の難関でつまっていて、完成は未定です。
#やる気起きないし(笑)
大域変数
EXT OP * op; カレントのオペコード
EXT I32 padix; /* max used index in current "register" pad */
/* This regexp stuff is global since it always happens within 1 expr eval */
EXT char * regprecomp; コンパイル前の文字列
EXT char * regparse; 現在注目しているパターンの位置
EXT char * regxend; コンパイル対象の入力の終端
EXT I32 regnpar; () の数
EXT char * regcode; コンパイル後のコードを格納する位置。ただし、
regcode==®dumyのときは実際に格納はしない
(コンパイル後の大きさを確認するときに使用)
EXT I32 regsize; コンパイルずみイメージのサイズ
EXT I32 regnaughty; このパターンはどれくらいひどい(bad)か?
EXT I32 regsawback; 後方参照が現れたか?
EXT char * reginput; 入力文字列のポインター
EXT char * regbol; ^のチェックのための入力の先頭。
EXT char * regeol; $のチェックのための入力の末尾。
EXT char ** regstartp; startp配列へのポインター
EXT char ** regendp; endpに同じ
EXT U32 * reglastparen; lastparenに同じ
EXT char * regtill; /* How far we are required to go. */
EXT U16 regflags; 大小文字無視、複数行モードなどのフラグ。
チェックされるビット値は以下の通り
PMf_MULTILINE 0x1000 複数行であると仮定する
PMf_SINGLELINE 0x2000 単一行であると仮定する
PMf_LOCALE 0x4000 キャラクタータイプの判定にlocaleを反映させる
PMf_EXTENDED 0x8000 埋め込みの空白を取り除く
EXT char regprev; regbolの直前のキャラクター。存在しない場合には\nとなる。
IEXT PMOP * Ioldlastpm; /* for saving regexp context during debugger */
フラグ
WORST 0 /* Worst case. */
HASWIDTH 0x1 空文字列にはマッチしない
SIMPLE 0x2 STAR/PLUS のオペランドに使えるくらいSIMPLE
SPSTART 0x4 *か+で始まった
TRYAGAIN 0x8 /* Weeded out a declaration. */ 宣言を取り除く?
オペコード
名前 値 オペランド 意味
END 0 なし プログラムの終端
+-----+-----+-----+
| END | 0 |
+-----+-----+-----+
BOL 1 なし 行の先頭の空文字列にマッチ
+-----+-----+-----+
| BOL | next |
+-----+-----+-----+
MBOL 2 なし 複数行マッチを仮定したBOL
+------+-----+-----+
| MBOL | next |
+------+-----+-----+
SBOL 3 なし 単一行マッチを仮定したBOL
+------+-----+-----+
| SBOL | next |
+------+-----+-----+
EOL 4 なし 行の終端にある空文字列にマッチ
+-----+-----+-----+
| EOL | next |
+-----+-----+-----+
MEOL 5 なし 複数行マッチを仮定したEOL
+------+-----+-----+
| MEOL | next |
+------+-----+-----+
SEOL 6 なし 単一行マッチを仮定したEOL
+------+-----+-----+
| SEOL | next |
+------+-----+-----+
ANY 7 なし 改行を除く任意のキャラクターにマッチ
+-----+-----+-----+
| ANY | next |
+-----+-----+-----+
SANY 8 なし 任意のキャラクターにマッチ
+------+-----+-----+
| SANY | next |
+------+-----+-----+
ANYOF 9 sv クラスに含まれる(もしくは含まれない)キャラクターにマッチする
jperl
ANYOFのフラグ bit vectorへのポインター
↓ ↓
+-------+-----+-----+-------+------+------+------+------+
| ANYOF | next | flag | bit vectorへのポインター |
+-------+-----+-----+-------+------+------+------+------+
original
+-------+-----+-----+-------+-------+--------+
| ANYOF | next | flag | bit vector |
+-------+-----+-----+-------+-------+--------+
↑
32 bytes (256 elements)
flag は以下のビットフラグのbitwise OR で表わされる。
ANYOF_INVERT 0x40 ^による補集合指定
ANYOF_FOLD 0x20 大小文字無視
ANYOF_LOCALE 0x10 ロカールを意識
ANYOF_ISA 0x0F (regexecにおいて、下の四つのフラグ判定に使用)
ANYOF_ALNUML 0x08 ロカールを意識した alphanumeric
ANYOF_NALNUML 0x04 ロカールを意識した 非alphanumeric
ANYOF_SPACEL 0x02 ロカールを意識した whitespace
ANYOF_NSPACEL 0x01 ロカールを意識した 非whitespace
最後の四つは、クラス指定の中で\w, \W, \s, \Sが
現れたときに使われる。ロカールを意識しないalphanumeicなどは
その場でビットがセットされる。
CURLY 10 sv “単純なもの”の{n,m}の繰り返しにマッチする
+------+-------+-------+-------+-------+-------+-------+----
| CURY | next |HI(min)|LO(min)|HI(max)|LO(max)| XXXXX
+------+-------+-------+-------+-------+-------+-------+----
+----------------------------------------------------↑
(繰り返しの外へ)
CURLYX 11 sv “複雑なもの”の{n,m}の繰り返しにマッチする
(WHILEM, NOTHINGと組み合わせて使用する)
+-------+-------+-------+-------+-------+-------+-------+---
| CURYX | next |HI(min)|LO(min)|HI(max)|LO(max)| XXXXX
+-------+-------+-------+-------+-------+-------+-------+---
+----------------------------------------------------↑
(繰り返しの外へ)
XXXXX = 繰り返しの対象
BRANCH 12 ノード /* node Match this alternative, or the next... */
+--------+------+------+
| BRANCH | next |
+--------+------+------+
+----------次の選択肢へ (トップレベルの場合は終端へ) --↑
BACK 13 なし ""にマッチし、後方への“次のノード”に対するポインター
+------+-----+-----+
| BACK | next |
+------+-----+-----+
注: Henry Spencerによるオリジナルでは'*'、'+'のときに使用していたが、
現状のPerlではこのノードは使ってないようである。
EXACT 14 sv 後続の文字列(長さが先に来る)にマッチ
後続の文字列の長さを示す(max 127)
↓
+-------+-----+-----+-------+-------+-------+-----+
| EXACT | next | len | 対象文字列 | \0 |
+-------+-----+-----+-------+-------+-------+-----+
オペランドの文字列にマッチ
EXACTF 15 sv 大小文字を無視してオペランドの文字列にマッチ
後続の文字列の長さを示す(max 127)
↓
+--------+-----+-----+-------+-------+-------+-----+
| EXACTF | next | len | 対象文字列 | \0 |
+--------+-----+-----+-------+-------+-------+-----+
EXACTFL 16 sv ロカールに応じた大小文字の無視を行ってオペランドの文字列にマッチ
後続の文字列の長さを示す(max 127)
↓
+---------+-----+-----+-------+-------+-------+-----+
| EXACTFL | next | len | 対象文字列 | \0 |
+---------+-----+-----+-------+-------+-------+-----+
NOTHING 17 なし 空文字列にマッチする
+---------+-----+-----+
| NOTHING | next |
+---------+-----+-----+
STAR 18 ノード (単純なものの)0回以上の繰り返し
+------+-----+-----+-----
| STAR | next | 繰り返しの対象
+------+-----+-----+-----
PLUS 19 ノード (単純なものの)1回以上の繰り返し
+------+-----+-----+-----
| PLUS | next | 繰り返しの対象
+------+-----+-----+-----
BOUND 20 なし 任意の語境界(word baundary)にある""(空文字列)にマッチする
+-------+-----+-----+
| BOUND | next |
+-------+-----+-----+
BOUNDL 21 なし 任意の語境界(word baundary)にある""(空文字列)にマッチする
+--------+-----+-----+
| BOUNDL | next |
+--------+-----+-----+
NBOUND 22 なし 語境界(word baundary)以外にある任意の""(空文字列)にマッチする
+--------+-----+-----+
| NBOUND | next |
+--------+-----+-----+
NBOUNDL 23 なし 語境界(word baundary)以外にある任意の""にマッチする
+---------+-----+-----+
| NBOUNDL | next |
+---------+-----+-----+
REF 24 num すでにマッチしている文字列(num番目の部分式)にマッチする
+-----+-----+-----+-----+-----+
| REF | next | num |
+-----+-----+-----+-----+-----+
REFF 25 num すでにマッチしている文字列(num番目の部分式)にマッチする(大小文字の違いは無視)
+------+-----+-----+-----+-----+
| REFF | next | num |
+------+-----+-----+-----+-----+
REFFL 26 num すでにマッチしている文字列(num番目の部分式)にマッチする(カレントのロカールで大小文字の無視)
+-------+-----+-----+-----+-----+
| REFFL | next | num |
+-------+-----+-----+-----+-----+
OPEN 27 num 入力の現在の位置を #nの開始点としてマークする
+------+-----+-----+-----+-----+
| OPEN | next | num |
+------+-----+-----+-----+-----+
CLOSE 28 num OPENと対になるもの
+-------+-----+-----+-----+-----+
| CLOSE | next | num |
+-------+-----+-----+-----+-----+
MINMOD 29 なし 後続の操作はgreedyでない
+--------+-----+-----+
| MINMOD | next |
+--------+-----+-----+
GPOS 30 なし 最後にm//gがマッチした場所にマッチ
+------+-----+-----+
| GPOS | next |
+------+-----+-----+
IFMATCH 31 なし 後続がマッチすると成功
+---------+-----+-----+
| IFMATCH | next |
+---------+-----+-----+
UNLESSM 32 なし 後続がマッチすると失敗
+---------+-----+-----+
| UNLESSM | next |
+---------+-----+-----+
SUCCEED 33 なし Return from a subroutine, basically. */
サブルーチンからの復帰
+---------+-----+-----+
| SUCCEED | next |
+---------+-----+-----+
WHILEM 34 なし Do curly processing and see if rest matches. */
curly処理を行い、後続がマッチするかどうか確認する
+--------+-----+-----+
| WHILEM | next |
+--------+-----+-----+
ALNUM 35 なし alphanumericキャラクターにマッチする
+-------+-----+-----+
| ALNUM | next |
+-------+-----+-----+
ALNUML 36 なし そのlocaleにおけるalphanumericキャラクターにマッチする
+--------+-----+-----+
| ALNUML | next |
+--------+-----+-----+
NALNUM 37 なし 非alphanumericキャラクターにマッチする
+--------+-----+-----+
| NALNUM | next |
+--------+-----+-----+
NALNUML 38 なし そのlocaleにおける非alphanumericキャラクターにマッチする
+---------+-----+-----+
| NALNUML | next |
+---------+-----+-----+
SPACE 39 なし 空白キャラクターにマッチ
+-------+-----+-----+
| SPACE | next |
+-------+-----+-----+
SPACEL 40 なし そのlocaleにおける空白キャラクターにマッチ
+--------+-----+-----+
| SCAPEL | next |
+--------+-----+-----+
NSPACE 41 なし 非空白キャラクターにマッチ
+--------+-----+-----+
| NSPACE | next |
+--------+-----+-----+
NSPACEL 42 なし そのlocaleにおける非空白キャラクターにマッチ
+---------+-----+-----+
| NSPACEL | next |
+---------+-----+-----+
DIGIT 43 なし 数字のキャラクターにマッチする
+-------+-----+-----+
| DIGIT | next |
+-------+-----+-----+
NDIGIT 44 なし 数字以外のキャラクターにマッチする
+--------+-----+-----+
| NDIGIT | next |
+--------+-----+-----+
/*
* オペコードに関するメモ:
*
* BRANCH 一つの選択肢を構成する分岐の集合は個々の分岐が先行する分岐
と連結されるので、そのノードにある“next”ポインターが一緒
にフックされている。選択肢の最後のBRANCHノードにある“next”
ポインターは選択肢全体に後続しているものを指している。これ
は、個々の分岐の最後の“next”ポインターが指している場所で
もある。各分岐はBRANCHノードのオペランドノードで始まる
*
* BACK 通常の“next”ポインターはすべて暗黙のうちに前方を指してい
る。BACKはループ構造を構築するために存在する。
*
* STAR,PLUS '?'および、複雑な'*'と'+'は BACKを使った巡回 BRANCH構造とし
て実装されている。処理速度を稼ぐのと再帰動作を最小限にする
ために、単純な場合(一キャラクター毎にマッチ)に対してはSTART
やPLUSを使って実装している。
*
* OPEN,CLOSE コンパイル時に番号付けされる。
*/
構造体
typedef struct regexp {
char **startp;
char **endp;
SV *regstart; /* Internal use only. */
char *regstclass;
SV *regmust; /* Internal use only. */
I32 regback; /* Can regmust locate first try? */
I32 minlen; $&の可能な最小の長さ
I32 prelen; precompの長さ
U32 nparens; カッコの数
U32 lastparen; 最後にマッチしたカッコ
char *precomp; コンパイル前の正規表現 /* pre-compilation regular expression */
char *subbase; /* saved string so \digit works forever */
char *subbeg; /* same, but not responsible for allocation */
char *subend; /* end of subbase */ subbaseの終端
U16 naughty; /* how exponential is this pattern? */ このパターンがどのくらい複雑か
char reganch; /* Internal use only. */
char exec_tainted; /* Tainted information used by regexec? */ regexecによって使われる taint情報?
char program[1]; /* Unwarranted chumminess with compiler. */ コンパイラに合わせるためのもの
} regexp;
フラグ
#define ROPT_ANCH 3
#define ROPT_ANCH_BOL 1
#define ROPT_ANCH_GPOS 2
#define ROPT_SKIP 4
#define ROPT_IMPLICIT 8
#define ROPT_KANJI 16 regexecで漢字を意識するかしないかのビット(ONで意識する)
コンパイル
/*
- pregcomp - 正規表現を内部コードへ変換する
*
コンパイルの結果がどのくらい大きくなるかわからなければスペースの割り当ては
できない。しかし、コンパイルした結果を格納する場所がなければ(つまりはコン
パイル結果がどのくらい大きくなるか知らなければ)コンパイルすることができな
い。そこでちょっとずるをする: 二度コンパイルをすることにし、一度目は実際に
コード生成はせずにサイズの計算をする。そして二度目に“実際の”コード生成の
ためのコンパイルをする。これはまた、実際にコンパイルがきちんとできるもので
なければスペースを割り付けないということであり、コンパイル結果を移動する必
要がないので(移動先の)ポインターのチェックもしないでよいということである
(free()がすべてを解放できるようにするために全体が一塊でなければならないこ
とに注意)。[注意: perlにおいては真ではない]
*
* 一部のコンパイル済み正規表現の構造を知っているoptimization-preparation
* コードに注意。
*/
regexp *
pregcomp(exp, xend, pm)
char* exp; IN: コンパイルする正規表現の先頭アドレス
char* xend; IN: コンパイルする正規表現の終端アドレス
PMOP* pm; IN: struct pmop へのポインター
pm->pmflagsがreglfagsに反映される
全体のエントリ
大まかな手順
1. コンパイル後の正規表現の大きさを求める
2. 1.で求めた大きさに応じてメモリーを割付
3. コンパイル本体
4. オプティマイズ?
戻り値:
コンパイル結果を収めた regexp構造体へのポインター。何らかの
エラーが起きた場合にはNULL。
参考: 構成要素のBNF表記(名称は関数名に依った)
regexp : reg
reg : regbranch '|' regexp
| regbranch
regbranch : regpiece
regpiece : regatom '*'
| regatom '+'
| regatom '?'
| regatom '{N, M}'
| regatom '*?'
| regatom '+?'
| regatom '??'
| regatom '{N, M}?'
| regatom regpiece
| regatom
regatom : '^' | '$' | '.' | '?' | '+' | '*'
| '\A'| '\G'| '\Z'| '\w'| '\W'| '\b'| '\B'| '\s' | '\S'
| '\d'| '\D'| '\n'| '\r'| '\t'| '\f'| '\e'| '\cA'
| '\000' | '\0'| '\x00'
| '[' class ']'
| '(' reg ')'
| char
/*
- reg - 正規表現の解析。全体とカッコに囲まれた部分式の両方を解析する。
*
* 呼び出し側は開きカッコを取り除いていなければならない。
*
正規表現のbaseレベルでのカッコの組の取り扱いは少々強引であるが、(後続を
無視することが困難なので)分岐の末尾をtieする必要がある。
*/
static char *
reg(paren, flagp)
I32 paren; IN: カッコの中なら1、そうでなければ0が来る
I32 *flagp; OUT: 設定するフラグ
regcomp.c(438) : reg(paren, flagp)
・*flagp = HASWIDTH; /* Tentatively. */
・parenが!0なら前処理を行う
(?#...)によるコメントの読み飛ばし
(?i)、(?x)、(?g) などのフラグの処理
*flagp = TRYAGAIN;
・br = regbranch(&flags) /* 処理しつつある部分正規表現の先頭ノードを作成 */
・regtail(ret, br); /* OPEN -> first. */
・'|'で接続されている間
br = regbranch(&flags) /* '|'の後の部分に対応するノードを作成する */
regtail(ret, br); /* BRANCH -> BRANCH. */ (チェイン構造の作成)
・parenの値に応じて後処理
':' (?:...)
ender = regnode(NOTHING);
'=' (?=...)
'!' (?!...)
ender = regnode(SUCCEED);
*flagp &= ~HASWIDTH; // これら二つは長さがないので HASWIDTHビットを落とす
0 (トップレベル)
ender = regnode(END);
1 (通常のカッコ)
ender = reganode(CLOSE, parno);
・regtail(ret, ender);
・チェイン構造の解決
・後処理
paren == '=' のとき
reginsert(IFMATCH,ret);
regtail(ret, regnode(NOTHING));
paren == '!' のとき
reginsert(UNLESSM,ret);
regtail(ret, regnode(NOTHING));
戻り値:
/*
- regbranch - '|'のオペランドの処理を行う
*
* 連接演算子(concatenation operator)の実装
*/
static char *
regbranch(flagp)
I32 *flagp; OUT: 設定するフラグ
ret = regnode(BRANCH); 作成するノードのオペコードを格納
+--------+------+------+----
| BRANCH | next |regpiece()で処理された部分式
+--------+------+------+-----
↑
ret
戻り値
ret = regnode(BRANCH); のretか、NULL
/*
- regpiece - [*+?]が後続する可能性のある何か
*
?を使っていたり、*や+を使っている一般的なケースにおいては分岐のコードは最
適化が行われることに注意すること: これらにおいて、同じNOTHINGノードが分岐
リストの終端マーカーおよび最終分岐の本体として使用される。このNOTHINGノー
ドは完全に取り除くことができるように思えるが、終端マーカーの役目は余計なも
のではない。
*/
static char *
regpiece(flagp)
I32 *flagp; OUT:見つかった演算子に応じてビットフラグを立てる
動作:
*+?{}が後続するものの処理?
1. ret = regatom(&flags); アトムの取得
2. アトムに続くコメントの読み飛ばし
3.
アトムの直後が
'{'
SMIPLEなとき
+-------+-----+-----+-----+-----+-----+-----+
| CURLY | next | min | max |
+-------+-----+-----+-----+-----+-----+-----+
SIMPLEでないとき
+-------+-----+-----+-----+-----+-----+-----+--------+-----+-----+---------+-----+-----+
| CURYX | next | min | max | WHILEM | next | NOTHING | next |
+-------+-----+-----+-----+-----+-----+-----+--------+-----+-----+---------+-----+-----+
'*' (かつ、アトムがSIMPLEな場合)
'+'
+-----+-------+-------+
| op | next |
+-----+-------+-------+
'*' (かつ、アトムがSIMPLEでない場合)
'+'
→ CURYXに同じ
'?'
→ SIMPLEならCURY、SIMPLEでないならCURYXに同じ
'?'がさらに続いているなら
reginsert(MINMOD, ret);
regtail(ret, ret + 3);
+--------+-------+-------+-----+-------+-------+-------+--
| MINMOD | next | op | opに応じたオペランド
+--------+-------+-------+-----+-------+-------+-------+--
op = STAR
PLUS
CURLY
CURLYX
マッチの長さが1以上なら *flagp = (WORST|HASWIDTH);
'*'か'?'の繰り返しなら *flagp = (WORST|SPSTART);
戻り値:
作成したノードの先頭アドレス
/*
- regatom - the lowest level
*
最適化: 通常キャラクター(ordinary characters)の並び全体はそれを単一のノー
ドにまとめることができるので、そういった並びを gobble(むしゃむしゃ食べる)
する。これにより格納するための領域が小さくなり、また、実行速度が向上する。
バックスラッシュのついたキャラクターは例外で、それぞれが独立したノードとな
る。そのためのプログラムは単純な方法を使っていて、修正する価値もない。
[実は修正する価値はあって、一部のスクリプトを二倍の速度で実行できるように
なる]
*/
static char *
regatom(flagp)
I32 *flagp; OUT:見つかった演算子に応じてビットフラグを立てる
正規表現の“アトム”の処理を行う。
regatom : '^' | '$' | '.' | '?' | '+' | '*'
| '\A'| '\G'| '\Z'| '\w'| '\W'| '\b'| '\B'| '\s' | '\S'
| '\d'| '\D'| '\n'| '\r'| '\t'| '\f'| '\e'| '\cA'
| '\000' | '\0'| '\x00'
| '[' class ']'
| '(' regexp ')'
| char
・'('を見つけたら、reg(1, &flags)でカッコの中を処理する。
・'['を見つけたらキャラクタクラスの処理を開始する
→ regclass()
*flagpの HASWIDTHビットを立てる
・通常のキャラクターであれば、次に現れるメタキャラクターの直前、
文字列の終端、126バイト目のいずれかの最初に条件を満たした
ところまでポインターを進め、そこまでの部分文字列を
EXACT(もしくはEXACTFかEXACTFL)のオペランドとして
regcodeに格納する。このとき、xフラグが指定されていれば
間にある空白文字はスキップされ、regcodeには格納されない。
*OPERAND(ret)
↓
+-------+-------+-------+-------+-------+-------+------+
| op | next | len | 対象文字列 | \0 |
+-------+-------+-------+-------+-------+-------+------+
↓ ↑regc('\0');
“次”のノードへ ─────────────→
この場合のopは、正規表現全体に対するフラグに応じて以下のものの
いずれかが入る。
EXACT
EXACTF
EXACTFL
戻り値:
static char *
regwhite(p, e)
char *p; スキャンを始める位置
char *e; スキャンを終了する位置(この位置を越えることはない)
動作:
空白と#によるコメントの読み飛ばしを行う
戻り値:
最初に見つかった非空白キャラクターの位置
static void
block_on(b, x, y)
char *b; ビットベクターの先頭アドレス
int x; 範囲指定開始位置
int y; 範囲指定終了位置
動作:
xからyまでのビットフラグをオンにする
戻り値:
なし
static void
regset(opnd, c)
char *opnd; ビットベクターのアドレス
register I32 c; キャラクターの文字コード
ビットベクター opndの cで指定されるビット位置のビットをオンにす
る。ただし、cは255以下のこと(関数内でビットが切りつめられる)
static char *
regclass()
キャラクタークラス指定のコンパイルを行う。`]'に至るまで一文字ずつ
処理するが、このときマルチバイト文字を考慮して一文字取得を行う
(下のプログラム片を参照)。
class = UCHARAT(regparse++);
if (ISKANJI(class) && regparse < regxend) {
if (*opnd & ANYOF_LITERAL)
FAIL("kanji and hex/octal literal");
class = (class << 8) + UCHARAT(regparse++);
ismb = 1;
}
ある文字を取り出したときに、後続の文字が'-'であった場合には
範囲指定の処理のフラグを立てる(実際には次回のループで処理)。
クラスに文字が属しているかどうかはビットベクターを使用して判定する。
ビットベクターの構造は以下の通り
0 0x100 0x8100(通しのビット位置)
+--------+-------------------+
| ------ | --------------- |
+--------+-------------------+
↑ ↑
｜ マルチバイト文字の分(キャラクターコード - 0x7900がそ
｜ のキャラクタに対応するビット位置)
最初の256キャラ分 (32bytes)
+-------+-------+-------+-------+-------+------+------+------+
| ANYOF | next | flags | pointer to bitvec | (jperlの場合)
+-------+-------+-------+-------+-------+------+------+------+
↑ (bit vector へのポインター)
classに対するビットフラグ
参考: (originalの場合)
+-------+-------+-------+-------+-------+-------------+------+
| ANYOF | next | flags | bitvector |
+-------+-------+-------+-------+-------+-------------+------+
(32bytes = 256 elements)
flags は以下のビットフラグのbit OR で表わされる
ANYOF_LITERAL 0x80 jperlにおいて、\xhhもしくは\ooo指定が使われている
ANYOF_INVERT 0x40 ^による補集合指定
ANYOF_FOLD 0x20 大小文字無視
ANYOF_LOCALE 0x10 ロカールを意識
ANYOF_ISA 0x0F (regexecで、下の四つのフラグ判定に使用)
ANYOF_ALNUML 0x08 ロカールを意識した alphanumeric
ANYOF_NALNUML 0x04 ロカールを意識した 非alphanumeric
ANYOF_SPACEL 0x02 ロカールを意識した whitespace
ANYOF_NSPACEL 0x01 ロカールを意識した 非whitespace
static char*
nextchar()
動作:
(?#)の読み飛ばしや、xフラグ指定時の空白キャラクターの
読み飛ばしを行って、“次のキャラクター”の位置を探す。
regparseが読み飛ばされた量に応じてインクリメントされる。
戻り値:
次のキャラクターが置かれているアドレス。
/*
- regnode - ノードを埋め込む
*/
static char * /* Location. */
regnode(
char op 埋め込むオペコード
コンパイル結果格納領域の末尾にopで指定されたオペコードを格納し、
続く二バイトに0を格納する。regcodeは三バイト分進む。
関数呼び出し時点での regcode
↓
+-------+-------+-------+
| op | 0 | 0 |
+-------+-------+-------+
↑
関数から戻る時点での regcode
戻り値:
オペコード格納前のアドレス
/*
- reganode - 引数付きノードを埋め込む
*/
static char * /* Location. */
reganode(
char op, オペコード
unsigned short arg オペコードに対する引数
)
コンパイル結果格納領域の末尾に opで指定されたオペコードを格納し、
続く二バイトに0を格納する。さらに続く二バイトにargを格納する。
regcodeは五バイト分進む。
関数呼び出し時点での regcode
↓
+-------+-------+-------+-------+-------+
| op | 0 | 0 |HI(arg)|LO(arg)|
+-------+-------+-------+-------+-------+
↑
関数から戻る時点での regcode
戻り値:
オペコード格納前のアドレス
/*
- regc - 一バイトのコードを埋め込む
*/
static void
regc(
char b) 格納するバイトデータ
bで指定されたバイトデータを*regcodeに格納する。regcodeは一バイト
分インクリメントされる。
+-------+
| op |
+-------+
戻り値:
なし
/*
- reginsert - すでに格納されたオペランドの前にオペレーターを挿入する。
*
* オペランドの再配置
*/
static void
reginsert(
char op, オペコード
char *opnd) ずらしの先頭アドレス
opndで指定されたアドレスにopで指定されるオペコードを格納し、後続
の二バイトを0で埋める。opが CURLYであればさらに四バイト分を0で埋
める。このとき、opndにもとからあったノードを、挿入するノードの大
きさだけ後ろにずらす。
opnd op != CURLYのとき
↓
+-------+-------+-------+----
| op | 0 | 0 |
+-------+-------+-------+----
↑
--- ここに動かされたノードが来る --
op == CURLYのとき │
↓
+-------+-------+-------+-------+-------+-------+-------+------
| op | 0 | 0 | 0 | 0 | 0 | 0 |
+-------+-------+-------+-------+-------+-------+-------+------
/*
- regtail - ノードチェインの終端でnextポインターをセットする
*/
static void
regtail(p, val)
char *p; IN: 検索開始のノードアドレス
char *val; IN: scanと加減算してoffsetを求めるアドレス
1. コンパイル済み正規表現中でpから辿れる最後のノードを検索する
見つかったアドレス → scan
2. オフセットの計算
if (OP(scan) == BACK)
offset = scan - val; 後方へのオフセット
else
offset = val - scan; 前方へのオフセット
1.で見付かった場所にオフセットを格納する
後方← →前方
scan
↓
+--------+----------+----------+
| op |HI(offset)|LO(offset)|
+--------+----------+----------+
戻り値:
なし
/*
- regoptail - 第一引数のオペランドに対するregtail。オペランドがなければなにもしない
*/
static void
regcomp.c(1579) : regoptail(p, val)
regoptail(p, val)
char *p; チェックするノードのアドレス
char *val; regtailの第二引数に使うもの
*pにあるオペコードがBRANCHでなければ何もせずにリターン
BRANCHなら
regtail(NEXTOPER(p), val);
戻り値:
なし
/*
- regcurly - {\d+,?\d*}を受理するちょっとしたオートマトン
*/
STATIC I32
regcurly(s)
register char *s;
sで指定される部分文字列が、 {\d+,?\d*}にマッチするようなものならTRUEを、
そうでなければFALSEを返す。
/*
- regdump - regexpを(読みやすい形式で)Perl_debug_logへダンプする
*/
void
regdump(r)
regexp *r; dump対象の正規表現を格納しているregex構造体へのポインター
デバッグ用ルーチン
/*
- regprop - オペコードに対する表示可能文字列を得る
*/
void
regprop(sv, op)
SV *sv;
char *op; 注目しているオペコードへのポインター
デバッグ用ルーチン(regdump()から呼ばれて使われる)
void
pregfree(r)
struct regexp *r;
regcomp.c(1851) : pregfree(r)
pregfree(struct regexp *r)
static void
regclassfree(r)
struct regexp *r;
regcomp.c(1879) : regclassfree(r)
######
簡単なサンプルに対する perl -Drによる出力(の一部)とそれに応じた
コンパイル時の関数呼び出しの履歴
(?:)を使ったパターンの例
/a(?:bc)def/
1:BRANCH(35)
5:EXACT(11) <a>
11:BRANCH(23)
15:EXACT(23) <bc>
23:NOTHING(27)
27:EXACT(35) <def>
35:END(0)
br = regbranch(&flags); BRANCHノードを作成 & それに対応する部分の処理
ender = regnode(NOTHING); NOTHINGノードを作成
regtail(ret, ender); NOTHINGへのオフセットを格納
-----------------------
↑ ↓
+--------+-------+-------+---------+---------+-------+-------+
| BRANCH | next | ....... | NOTHING | 0 | 0 |
+--------+-------+-------+---------+---------+-------+-------+
↑
proccess in regbranch
(?=)を使ったパターンの例
/abc(?=def)/
1:BRANCH(37)
5:EXACT(13) <abc>
13:IFMATCH(33)
17:BRANCH(29)
21:EXACT(29) <def>
29:SUCCEED(0)
33:NOTHING(37)
37:END(0)
br = regbranch(&flags);
ender = regnode(SUCCEED);
-----------------------
↑ ↓
+--------+-------+-------+---------+---------+-------+-------+
| BRANCH | next | ....... | SUCCEED | 0 | 0 |
+--------+-------+-------+---------+---------+-------+-------+
*flagp &= ~HASWIDTH; HASWIDTHビットを落とす
regtail(ret, ender);
reginsert(IFMATCH,ret);
regtail(ret, regnode(NOTHING));
---------------------
↑ ↓
+---------+--------+--------+--------+-----+-----+---------+---------+-------+-------+---
| IFMATCH | next | BRANCH | next | ....... | SUCCEED | 0 | 0 | NOTHING
+---------+--------+--------+--------+-----+-----+---------+---------+-------+-------+---
↓ ↑
---------------------------------------------------------------------
(?!)を使ったパターンの例
/abc(?!def)/
1:BRANCH(37)
5:EXACT(13) <abc>
13:UNLESSM(33)
17:BRANCH(29)
21:EXACT(29) <def>
29:SUCCEED(0)
33:NOTHING(37)
37:END(0)
br = regbranch(&flags);
ender = regnode(SUCCEED);
enderにはSUCCEEDのアドレスが返る
-----------------------
↑ ↓
+--------+-------+-------+---------+---------+-------+-------+
| BRANCH | next | ....... | SUCCEED | 0 | 0 |
+--------+-------+-------+---------+---------+-------+-------+
*flagp &= ~HASWIDTH; HASWIDTHビットを落とす
regtail(ret, ender);
reginsert(UNLESSM,ret);
regtail(ret, regnode(NOTHING));
---------------------
↑ ↓
+---------+--------+--------+--------+-----+-----+---------+---------+-------+-------+---
| UNLESSM | next | BRANCH | next | ....... | SUCCEED | 0 | 0 | NOTHING
+---------+--------+--------+--------+-----+-----+---------+---------+-------+-------+---
↓ ↑
---------------------------------------------------------------------
() を使ったパターンの例
/a(bc)def/
1:BRANCH(43)
5:EXACT(11) <a>
11:OPEN1(17)
17:BRANCH(29)
21:EXACT(29) <bc>
29:CLOSE1(35)
35:EXACT(43) <def>
43:END(0)
ret = reganode(OPEN, parno); //parno = 式の番号指定
br = regbranch(&flags);
regtail(ret, br); /* OPEN -> first. */
reganode()で0にセットされているオフセットの部分に br
(regbranch()で処理した部分式の先頭アドレス)へのオフセ
ットを格納する。
ret からノードをたどるが、OPENのnext部が0なので
OPENのアドレスが返る。
ender = reganode(CLOSE, parno);
----------------------------- ---- regclose(CLOSE, parno)----
l ↓ ↓ ↓
+-------+-----+-----+---------+---------+-------+-------+----+-----+---------+---------+
| OPEN | next |HI(parno)|LO(parno)| ..... | CLOSE | next |HI(parno)|LO(parno)|
+-------+-----+-----+---------+---------+-------+-------+----+-----+---------+---------+
↑ ↑ ↑ ↓ ↑
--- reganode(OPEN, parno) ----- │ ------------------------------
regbranch() で処理したもの
regtail(ret, ender);
ノードをクローズするために分岐の末尾をフックする
for (br = ret; br != NULL; br = regnext(br))
regoptail(br, ender);
{}を使った例
/a(b){1,5}/
1:BRANCH(49)
5:EXACT(11) <a>
11:CURLYX {1,5}(45)
19:OPEN1(25)
25:BRANCH(35)
29:EXACT(35) <b>
35:CLOSE1(41)
41:WHILEM(0)
45:NOTHING(49)
49:END(0)