■

NFAのデータ構造をどうするか考えてみた。
状態番号ではなく状態遷移に着目して以下のような構造を考える

struct ntrans {
  char ch;
  int from;
  int to;
};

chは文字で空文字の場合は「-1」としてセットしておく。
fromはどの遷移元の状態番号でtoは遷移先の状態番号とする。
さらにfromに着目して状態番号の構造体を考える

struct _nnode {
  char ch;
  int to;
  nnode* next;
};

この構造体は各from毎に持たせて複数のtoを持つ場合はnextで片方向リストとして連結させておく。
正規表現からnnodeへの変換は以下のような流れでとりあえずやってみる

1. OPを調べその状態により以下のような再帰的処理をする。
 ※再帰処理をさせるときの始点と終点をそれぞれSとEとしておく
 a) Union(X|Y)の場合
   S,Eは関数の引数として渡し、間に4つの状態(A,B,C,D）を作り左枝には始点と終点をA,Bとして渡し、右枝には始点と終点をC,Dとして渡し再帰処理をさせる。また、以下のntransに状態遷移を追加する
 ※ntransは配列としておき、最大番地に格納していく事とする
 S⇒A empty
 B⇒E empty
 S⇒C empty
 D⇒E empty

 b) Concat(XY)の場合
   一つ状態を作成しそれをAとし左枝には始点とAをそれぞれ始点と終点として渡し、右枝にはAと終点をそれぞれ始点と終点として渡し再帰処理をさせる。

 c) Closure(X*)の場合
   二つ状態を作成しそれをA,Bとし、左枝にA,Bをそれぞれ始点と終点として渡し再帰処理をさせる。また、以下の状態遷移を追加する
　S⇒A empty
  B⇒A empty
  A⇒E empty

 d) PClosure(X+)の場合
   二つ状態を作成しそれをA,Bとし、左枝にA,Bをそれぞれ始点と終点として渡し再帰処理をさせる。また、以下の状態遷移を追加する
　S⇒A empty
  B⇒A empty
  B⇒E empty

 e) Charcter or Emptyの場合
  以下の状態遷移を追加する
  S⇒E char(or empty)

2. ntransが完成したらそのfrom値を元にnnodeを作成する。

ntransなんて作らずにnnode作る事も可能っぽいけどそれはコーディングしながら考えてみるかな。。