changeset 182:dbe004d03ef0 pairPro

implement stateAllocate()
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 24 Dec 2015 19:14:49 +0900
parents 3c4db09b8581
children 7ae0a3070647
files regexParser/bitVector.cc regexParser/subsetConstraction.cc regexParser/subsetConstraction.h
diffstat 3 files changed, 69 insertions(+), 24 deletions(-) [+]
line wrap: on
line diff
--- a/regexParser/bitVector.cc	Thu Dec 24 18:00:55 2015 +0900
+++ b/regexParser/bitVector.cc	Thu Dec 24 19:14:49 2015 +0900
@@ -3,26 +3,20 @@
 #include <string.h>
 #include "bitVector.h"
 
-BitVectorPtr createBitVector(NodePtr n) {
-    BitVectorPtr bi = allocateBitVector();
-    bitSet(bi,n->nodeNumber);
-    return bi;
+BitVector createBitvector(int state) {
+    unsigned long tmp = 1 << bitSetPosition;
+    BitVector bi1 = (struct BitVector){.bitContainer = tmp};
+    return bi1;
 }
 
-const BitVectorPtr allocateBitVector() {
-    BitVectorPtr bi = (BitVectorPtr)malloc(sizeof(BitVector));
-    bi->bitContainer = 0;
-    return bi;
+BitVector bitSet(BitVector bi, int bitSetPosition) {
+    unsigned long tmp = 1 << bitSetPosition;
+    BitVector bi1 = (struct BitVector){.bitContainer = bi.bitContainer | tmp};
+    return bi1;
 }
 
-void bitSet(BitVectorPtr bi, int bitSetPosition) {
-    unsigned long tmp = 1 << (bitSetPosition % BITBLOCK);
-    bi->bitContainer = bi->bitContainer | tmp;
-    return;
-}
-
-void bitPrint(BitVectorPtr bi) {
-    unsigned long vec = bi->bitContainer;
+void bitPrint(BitVector bi) {
+    unsigned long vec = bi.bitContainer;
     for (int j = 0; j < BITBLOCK; j++) {
         putchar((vec & 1) ? '1':'0');
         vec >>= 1;
--- a/regexParser/subsetConstraction.cc	Thu Dec 24 18:00:55 2015 +0900
+++ b/regexParser/subsetConstraction.cc	Thu Dec 24 19:14:49 2015 +0900
@@ -175,6 +175,17 @@
     return current;
 }
 
+void setState(CharClassPtr cc, BitVector bi) {
+    setState(cc,bi);
+    if (cc->left) {
+        setState(cc->left,bi);
+    }
+    cc->nextState = bi;
+    if (cc->right) {
+        setState(cc->right,bi);
+    }
+}
+
 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) {
     if (x->cc == NULL) {
         return y;
@@ -192,17 +203,55 @@
     return ccy;
 }
 
-TGValue generateTransition(NodePtr n,TGValue tg) {
-    TGValue tgv2;
+TGValue stateAllocate(NodePtr n,TGValue tg) {
+    TGValue tgv2 = tg;
     if (n->tokenType == '+') {
-        TGValue tgv = generateTransition(n->right,tg);
-        if (tgv.asterisk) {
-            TGValue tgv1 = generateTransition(n->left,tgv);
-            return tgv1;
+        TGValue tgLeft = stateAllocate(n->left,tg);
+        if (tgLeft.asterisk) {
+            TGValue tgRight = tgLeft;
+            tgRight.asterisk = false;
+            tgRight = stateAllocate(n->right,tgRight);
+            tgRight.asterisk = true;
+            return tgRight;
         }
-        TGValue tgLeft = createTransitionGenerator(tgv);
+        TGValue tgRight = tgLeft;
+        tgRight.stateBegin = ++tgRight.stateNum;
+        tgRight.state = NEW(State);
+        TGValue tgv1 = stateAllocate(n->right,tgLeft);
+        return tgLeft;
+    } else if (n->tokenType == '|') {
+        TGValue tgv  = stateAllocate(n->left,tg);
+        TGValue tgv1 = stateAllocate(n->right,tgv);
+        return tgv1;
+    } else if (n->tokenType == '*') {
+        TGValue tgAstah = tg;
+        tgAstah.stateEnd = tgAstah.stateBegin;
+        tgAstah = stateAllocate(n->left,tgAstah);
+        tgAstah.asterisk = true;
+        return tgAstah;
+    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
+        TGValue tgv = tg;
+        tgv.asterisk = false;
+        BitVector bi = createBitVector(tgv.stateEnd);
+        setState(n->cc,bi);
+        tgv.state->cc = mergeTransition(tgv.state,n->cc);
+        return tgv;
+    } else {
+        // error
+    }
+    return tgv2;
+}
+
+TGValue generateTransition(NodePtr n,TGValue tg) {
+    TGValue tgv2 = tg;
+    if (n->tokenType == '+') {
+        tgv2.stateBegin = ++tgv.stateNum;
+        TGValue tgLeft = generateTransition(n->right,tgv2);
+        tgLeft.stateEnd = tgv2.stateBegin;
         TGValue tgv1 = generateTransition(n->left,tgLeft);
-        return tgv;
+        if (tgv1.asterisk) {
+        }
+        return tgv1;
     } else if (n->tokenType == '|') {
         TGValue tgv  = generateTransition(n->left,tg);
         TGValue tgv1 = generateTransition(n->right,tgv);
--- a/regexParser/subsetConstraction.h	Thu Dec 24 18:00:55 2015 +0900
+++ b/regexParser/subsetConstraction.h	Thu Dec 24 19:14:49 2015 +0900
@@ -18,6 +18,8 @@
 
 typedef struct tgValue {
     bool asterisk;
+    int stateBegin;
+    int stateEnd;
     TransitionGeneratorPtr tg;
 } TGValue, *TGValuePtr;