# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1455812197 -32400
# Node ID df2df954cd01f996a5b1d0509ade580be8f4d73d
# Parent  cf5564c13205d20b10da89c5801f4f15df25cef8
add generate

diff -r cf5564c13205 -r df2df954cd01 paper/c4.tex
--- a/paper/c4.tex	Thu Feb 18 22:22:58 2016 +0900
+++ b/paper/c4.tex	Fri Feb 19 01:16:37 2016 +0900
@@ -557,9 +557,74 @@
 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
 \end{itemize}
 
+\begin{lstlisting}[frame=lrbt,label=src:generateTransition,caption=正規表現木の状態割当,numbers=left]
+typedef struct tgValue {
+    StatePtr asterisk;   // last * state of the expression
+    StatePtr startState; // startState of the expression
+    StatePtr endState;
+    TransitionGeneratorPtr tg;
+} TGValue, *TGValuePtr;
+
+TGValue generateTransition(NodePtr n,TGValue tgv, int pass) {
+    if (n->tokenType == '+') {
+        TGValue tgvLeft = tgv;
+        tgvLeft.endState = n->right->state;
+        tgvLeft.asterisk = NULL;
+        tgvLeft = generateTransition(n->left,tgvLeft,pass);
+        TGValue tgvRight = tgv;
+        if (tgvLeft.asterisk) {
+            n->right->state = tgv.endState;
+            tgvRight.startState = tgvLeft.asterisk;
+            tgvRight = generateTransition(n->right,tgvRight,pass);
+            tgvLeft.asterisk = tgvRight.asterisk;
+            return tgvLeft;
+        }
+        tgvRight.asterisk = NULL;
+        if (pass==1) {
+            n->right->state = tgvRight.startState = createState(tgvRight,n->right);
+        } else {
+            tgvRight.startState = n->right->state;
+            tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ;
+        }
+        tgvRight = generateTransition(n->right,tgvRight,pass);
+        if (tgv.endState && tgvRight.asterisk) tgvRight.startState->accept = tgv.endState->accept;
+        tgvLeft.asterisk = tgvRight.asterisk;
+        return tgvLeft;
+    } else if (n->tokenType == '|') {
+        TGValue tgv1  = generateTransition(n->left,tgv,pass);
+        tgv1.endState = tgv.endState;
+        TGValue tgv2 = generateTransition(n->right,tgv1,pass);
+        return tgv2;
+    } else if (n->tokenType == '*') {
+        TGValue tgvAstah = tgv;
+        tgvAstah.endState = tgvAstah.startState;
+        if (pass==2) tgvAstah.endState->accept = tgv.endState->accept;
+        tgvAstah = generateTransition(n->left,tgvAstah,pass);
+        tgvAstah.asterisk = tgvAstah.startState;
+        return tgvAstah;
+    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
+        TGValue tgv1 = tgv;
+        if (pass==1) {
+            n->stateNum = tgv.startState->stateNum;
+            n->state = tgv.startState;
+        } else {
+            int nextState = tgv.endState->stateNum;
+            n->nextStateNum = nextState;
+            n->nextState = tgv.endState;
+            BitVector bi = createBitVector(nextState);
+            if (n->nextState->accept) bi = bitSet(bi,1);
+            setState(n->cc,bi);
+            tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
+        }
+        return tgv1;
+    } else {
+        return tgv;
+    }
+}
+\end{lstlisting}
 ノードに状態を割り振りながら次の状態の遷移先を設定することによって、オートマトンによる状態遷移を表現することができる。
 
-([a-zA-Z]|ab*)*aa
+([a-zA-Z]\textbar ab*)*aa
 
 \begin{figure}[htpb]
   \begin{center}
@@ -747,8 +812,6 @@
 }
 \end{lstlisting}
 
-\newpage
-
 \begin{lstlisting}[frame=lrbt,label=src:task,caption=ceriumGrep のマッチング部分,numbers=left]
 TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
     tsv.current = tsv.tg->stateStart->tState;
diff -r cf5564c13205 -r df2df954cd01 paper/master_paper.pdf
Binary file paper/master_paper.pdf has changed