--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/regexParser/transition.h	Sat Dec 19 15:38:45 2015 +0900
@@ -0,0 +1,35 @@
+#include "bitVector.h"
+
+typedef struct transition {
+    CharClassPtr condition;
+    BitVectorPtr nextState;
+    struct transition *next;
+} Transition, *TransitionPtr;
+
+typedef struct state {
+    BitVectorPtr bitState;
+    TransitionPtr transition;
+    struct state *next;
+} State, *StatePtr;
+
+StatePtr createState(BitVectorPtr bi, TransitionPtr ts, StatePtr next);
+StatePtr appendState(StatePtr x, StatePtr y);
+TransitionPtr createTransition(CharClassPtr cc ,BitVectorPtr state);
+TransitionPtr appendTransition0(TransitionPtr curr,TransitionPtr next);
+TransitionPtr appendTransition(TransitionPtr curr,TransitionPtr next);
+
+/*
+  正規表現木を辿って transition のList をつくる
+  CharClass のかさなりを判定して重なりのない新しいCharClassをつくる
+  重なっている状態はbitvectorのorをとる
+  重なっている状態はそれぞれの状態について木をたどる
+
+  nextState == 0 は正規表現の末端を表す
+  nextState == 1 は受理状態を表す
+  正規表現のノードの番号 n に対応する 2^n のbitをセットした状態
+
+  | の場合は両方のListを結合する
+  + の場合は左のノードに * がある場合は右のリストも結合する
+  左のノードに*がない場合は、右のほうだけみる
+  * は直下のリストを使って、次の状態を自分自身にする
+ */