changeset 106:8e47f1618608 impl-bitvector

merge
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 18 Nov 2015 19:36:12 +0900
parents 4ad2a75dec4a (current diff) 766fc2476f01 (diff)
children c9f5ee891b5e
files
diffstat 2 files changed, 41 insertions(+), 22 deletions(-) [+]
line wrap: on
line diff
--- a/c/regexParser/createBitVectorList.cc	Tue Nov 17 19:37:29 2015 +0900
+++ b/c/regexParser/createBitVectorList.cc	Wed Nov 18 19:36:12 2015 +0900
@@ -7,8 +7,8 @@
 extern BitVectorPtr bitSet(int);
 extern void bitPrint(BitVectorPtr);
 BitVectorListPtr createBitVector(NodePtr);
-BitVectorListPtr descendTreeNode(NodePtr,BitVectorListPtr);
-BitVectorListPtr setNextBitVectorList(BitVectorListPtr bvl, BitVectorListPtr next, NodePtr n);
+BitVectorListPtr descendTreeNode(NodePtr, BitVectorListPtr, BitVectorListPtr, bool&);
+BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next);
 
 BitVectorListPtr initBvl;
 
@@ -21,11 +21,9 @@
 }
 
 BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) {
-    BitVectorListPtr nextBvl = bvl->next[(int)n->Value.character] = allocateBitVectorList();
-    nextBvl->self = bvl->next[(int)n->Value.character];
+    BitVectorListPtr nextBvl = allocateBitVectorList();
     nextBvl->bi = bitSet(n->nodeNumber);
     nextBvl->initBvl = initBvl;
-
     return nextBvl;
 }
 
@@ -44,16 +42,16 @@
 }
 
 void printBitVectorList (BitVectorListPtr bvl) {
-    bool initPrintFlag = true;
+    bool isFirstPrint = true;
     for (int i = 0; i < 256; i++) {
         if (bvl->next[i] != NULL) {
-            if (initPrintFlag) {
+            if (isFirstPrint){
                 puts("----");
                 printf("     state : "); bitPrint(bvl->bi);
-                initPrintFlag = false;
+                isFirstPrint = false;
             }
             printf("input char : %c\n",i);
-            printf("next state : "); bitPrint(bvl->next[i]->bi);
+            printf("next state : ");bitPrint(bvl->next[i]->bi);
         }
     }
 
@@ -64,25 +62,51 @@
     }
 }
 
-BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl) {
+BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr) {
+    bool leftIsOr, rightIsOr;
+    if (n->tokenType == '*') {
 
-    if (n->Value.character == '*') {
-        bvl = descendTreeNode(n->left,bvl);
     } else if (n->Value.character == '|') {
-        bvl = descendTreeNode(n->left,bvl);
-        bvl = descendTreeNode(n->parent->right,bvl);
+        bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
+        setNextBitVectorList(n->left, prev, bvl);
+        bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
+        setNextBitVectorList(n->right, prev, bvl);
+        fromOr = true;
+        return prev;
     } else if (n->Value.character == '+') {
-        bvl = descendTreeNode(n->left,bvl);
-        bvl = descendTreeNode(n->right,bvl);
+        bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
+        setNextBitVectorList(n->left, prev, bvl);
+        prev = bvl;
+        bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
+
+        if (leftIsOr){
+            for (int i = 0; i < 256; i++)
+                if (prev->next[i] != NULL)
+                    setNextBitVectorList(n->right, prev->next[i], bvl);
+        }
+        else {
+            setNextBitVectorList(n->right, prev, bvl);
+        }
+
+        fromOr = false;
     } else if (n->tokenType == 'a') {
         bvl = createBitVector(n,bvl);
+        fromOr = false;
     }
     return bvl;
 }
 
+BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next){
+    if (isalnum((int)n->Value.character)){
+        bvl->next[(int)n->Value.character] = next;
+    }
+    return next;
+}
+
 BitVectorListPtr createBitVectorList(NodePtr n) {
     BitVectorListPtr bvl = initBitVector();
-    descendTreeNode(n,bvl);
+    bool fromOr = false;
+    descendTreeNode(n, bvl, bvl, fromOr);
     printBitVectorList(bvl);
     return bvl;
 }
--- a/c/regexParser/createRegexParser.cc	Tue Nov 17 19:37:29 2015 +0900
+++ b/c/regexParser/createRegexParser.cc	Wed Nov 18 19:36:12 2015 +0900
@@ -41,19 +41,14 @@
 // <charClass> ::= '['<literal>'-'<literal>']'
 NodePtr charClass(RegexInfoPtr ri) {
     NodePtr n = (NodePtr)malloc(sizeof(Node));
-    unsigned char startChar = ri->ptr[0];
     while (ri->ptr[0] == '-') {
         ri->ptr++;
     }
-    unsigned char endChar = ri->ptr[0];
-    unsigned char *charTable = (unsigned char*)malloc(sizeof(char)*256);
-
     return n;
 }
 
 // <literal> ::= [a-z][A-Z][0-9]
 NodePtr literal(RegexInfoPtr ri) {
-    unsigned char *top = ri->ptr;
     NodePtr n = createNode(ri,ri->ptr[0],0,0);
     ri->ptr++;
     return n;