部分集合構成法

昨日、コンパイラⅠを立ち読みしてきました。(た、高いですからね、つ、Ⅱは持ってるんですよっ)
忘れないうちにメモを残しておきます。
集合構成法では、位置の集合を状態とし、状態と次の文字から次の状態を引けるような表を作るようです。

例えば、次のような正規表現があったとします。

[0-9]+|0x[0-9a-fA-F]+

最初の位置を、orとか考慮した上で(ε遷移と呼ぶらしい)まとめて、最初の状態とします。

(┃[0-9]+)|(┃0x[0-9a-fA-F]+)

取りうる全ての文字に対して移動先(とそこからε遷移する先)を求めます。

0   : (┃[0-9]+)|(0┃x[0-9a-fA-F]+)┃(OK)
1〜9: (┃[0-9]+)|(0x[0-9a-fA-F]+)┃(OK)
他  : (BAD)

こうして得られた状態が、未探索のパターンであれば、そこからまた同じように繰り返します。
こうしてできた表をたどってマッチングを行うわけです。
ひとつでも末尾に到達したら打ち切ると最短一致、可能性が無くなるまで繰り返すと最長一致になります。
A*?とかみたいな部分最短一致みたいなのは多分できない…かな？

誤ってたらつっこんでいただけたら幸いです。アルゴリズム関係(入門向けのソートとかで終わっているやつを除く)の本が書店から消えてて、コンパイラⅠの2ページぐらいの説明しか無かったのですよ…。

と、ところで、は、はてなのpreタグ解析、バグってませんか…？