Mercurial > hg > Applications > Grep

changeset 183:7ae0a3070647 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement generateTransitionList
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 24 Dec 2015 20:02:09 +0900
parents dbe004d03ef0
children 1da1b2eacb84
files regexParser/regexParser.cc regexParser/regexParser.h regexParser/subsetConstraction.cc regexParser/subsetConstraction.h
diffstat 4 files changed, 60 insertions(+), 40 deletions(-) [+]
line wrap: on
line diff
--- a/regexParser/regexParser.cc	Thu Dec 24 19:14:49 2015 +0900
+++ b/regexParser/regexParser.cc	Thu Dec 24 20:02:09 2015 +0900
@@ -28,14 +28,11 @@
 static
 NodePtr createNode(RegexInfoPtr ri,unsigned char type,CharClassPtr cc, NodePtr left, NodePtr right) {
     NodePtr n = allocateNode();
-
     n->tokenType = type;
     n->cc = cc;
+    n->state = NULL;
     n->left = left;
     n->right = right;
-    n->nodeNumber = ri->stateNumber;
-    ri->stateNumber++;
-
     return n;
 }
 
--- a/regexParser/regexParser.h	Thu Dec 24 19:14:49 2015 +0900
+++ b/regexParser/regexParser.h	Thu Dec 24 20:02:09 2015 +0900
@@ -35,6 +35,9 @@
     unsigned char tokenType;
     unsigned long nodeNumber;
     CharClassPtr cc;
+    int stateNum;
+    int nextStateNum;
+    StatePtr state;
     struct node *left;
     struct node *right;
 } Node, *NodePtr;
--- a/regexParser/subsetConstraction.cc	Thu Dec 24 19:14:49 2015 +0900
+++ b/regexParser/subsetConstraction.cc	Thu Dec 24 20:02:09 2015 +0900
@@ -203,8 +203,22 @@
     return ccy;
 }
 
+/**
+ 作成する state を linked list
+bitvector を index とした配列に BitVectorPtr を格納
+state に対応する NodePtr を
+ */
+TGValue createState(TGValue tg,NodePtr n) {
+    StatePtr s = NEW(State);
+    s->next = tg.tg->currentState;
+    tg.tg->currentState = s;
+    s->node = n;
+    BitVector bi = createBitVector(tg.stateBegin);
+    s->bitState = bi;
+    s->cc = NULL;
+}
+
 TGValue stateAllocate(NodePtr n,TGValue tg) {
-    TGValue tgv2 = tg;
     if (n->tokenType == '+') {
         TGValue tgLeft = stateAllocate(n->left,tg);
         if (tgLeft.asterisk) {
@@ -216,7 +230,7 @@
         }
         TGValue tgRight = tgLeft;
         tgRight.stateBegin = ++tgRight.stateNum;
-        tgRight.state = NEW(State);
+        n->right->state = createState(tgRight,n->right);
         TGValue tgv1 = stateAllocate(n->right,tgLeft);
         return tgLeft;
     } else if (n->tokenType == '|') {
@@ -232,44 +246,39 @@
     } else if (n->tokenType == 'c' || n->tokenType == 'a'){
         TGValue tgv = tg;
         tgv.asterisk = false;
-        BitVector bi = createBitVector(tgv.stateEnd);
+        n->stateNum = tg.stateBegin;
+        n->nextStateNum = tg.stateEnd;
+        return tgv;
+    } else {
+        return tg;
+    }
+}
+
+TGValue generateTransition(NodePtr n,TGValue tg) {
+    if (n->tokenType == '+') {
+        StatePtr left = tg.state;
+        tg.state = n->left->state;
+        tg.tg.stateArray[tg.state->bitState.bitContainer] = tg.state;
+        TGValue tgLeft = generateTransition(n->left,tg);
+        tg.state = left;
+        TGValue tgv1 = generateTransition(n->right,tgLeft);
+        return tgv1;
+    } else if (n->tokenType == '|') {
+        TGValue tgv  = generateTransition(n->left,tg);
+        TGValue tgv1 = generateTransition(n->right,tgv);
+        return tgv1;
+    } else if (n->tokenType == '*') {
+        tgAstah = generateTransition(n->left,tgAstah);
+        return tgAstah;
+    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
+        TGValue tgv = tg;
+        BitVector bi = createBitVector(n->nextStateNum);
         setState(n->cc,bi);
         tgv.state->cc = mergeTransition(tgv.state,n->cc);
         return tgv;
     } else {
-        // error
+        return tg;
     }
-    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);
-        if (tgv1.asterisk) {
-        }
-        return tgv1;
-    } else if (n->tokenType == '|') {
-        TGValue tgv  = generateTransition(n->left,tg);
-        TGValue tgv1 = generateTransition(n->right,tgv);
-        tgv.tg = tgv1.tg;
-        tgv.asterisk |= tgv1.asterisk;
-        return tgv;
-    } else if (n->tokenType == '*') {
-        TGValue tgv = generateTransition(n->left,tg);
-        tgv.asterisk = true;
-        return tgv;
-    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
-        TGValue tgv = tg;
-        tgv.ts = mergeTransition(tgv.ts,n->cc);
-        return tgv;
-    } else {
-        // error
-    }
-    return tgv2;
 }
 
 void printTransitionList(TransitionPtr ts) {
@@ -300,7 +309,17 @@
 
 TransitionGenerator generateTransitionList(NodePtr n) {
     TransitionGenerator tg = createTransitionGenerator();
-    generateTransition(n,tg);
+    TGValue tgv;
+    tgv.asterisk = false;
+    tgv.tg = tg;
+    StatePtr start = createState(tgv,n);
+    NodePtr eof = createNode();
+    StatePtr end = createState(tgv,eof);
+    tgv.stateBegin = 0;
+    tgv.stateEnd = 1;
+    stateAllocate(n,tgv);
+    tgv.tg.stateArray = (StatePtr)calloc(tg.stateNum,sizeof(StatePtr));
+    generateTransition(n,tgv);
     printTransitionList(tg.ts);
     return tg;
 }
--- a/regexParser/subsetConstraction.h	Thu Dec 24 19:14:49 2015 +0900
+++ b/regexParser/subsetConstraction.h	Thu Dec 24 20:02:09 2015 +0900
@@ -20,6 +20,7 @@
     bool asterisk;
     int stateBegin;
     int stateEnd;
+    StatePtr state;
     TransitionGeneratorPtr tg;
 } TGValue, *TGValuePtr;