Mercurial > hg > Applications > Grep

comparison c/regexParser/createBitVectorList.cc @ 104:3eb3cb5d581f bitVec-Kaito

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implemented 'or' node translator
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Tue, 17 Nov 2015 22:20:42 +0900
parents 4ad2a75dec4a
children 766fc2476f01
comparison
equal deleted inserted replaced
103:4ad2a75dec4a 104:3eb3cb5d581f
5 #include "regexParser.h" 5 #include "regexParser.h"
6 6
7 extern BitVectorPtr bitSet(int); 7 extern BitVectorPtr bitSet(int);
8 extern void bitPrint(BitVectorPtr); 8 extern void bitPrint(BitVectorPtr);
9 BitVectorListPtr createBitVector(NodePtr); 9 BitVectorListPtr createBitVector(NodePtr);
10 BitVectorListPtr descendTreeNode(NodePtr,BitVectorListPtr); 10 BitVectorListPtr descendTreeNode(NodePtr, BitVectorListPtr, BitVectorListPtr, bool&);
11 BitVectorListPtr setNextBitVectorList(BitVectorListPtr bvl, BitVectorListPtr next, NodePtr n); 11 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next);
12 12
13 BitVectorListPtr initBvl; 13 BitVectorListPtr initBvl;
14 14
15 BitVectorListPtr allocateBitVectorList() { 15 BitVectorListPtr allocateBitVectorList() {
16 BitVectorListPtr bvl = (BitVectorListPtr)malloc(sizeof(BitVectorList)); 16 BitVectorListPtr bvl = (BitVectorListPtr)malloc(sizeof(BitVectorList));
17 bvl->self = bvl; 17 bvl->self = bvl;
18 bvl->bi = (BitVectorPtr)malloc(sizeof(BitVector)); 18 bvl->bi = (BitVectorPtr)malloc(sizeof(BitVector));
19 19
20 return bvl; 20 return bvl;
21 } 21 }
22 22
23 BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) { 23 BitVectorListPtr createBitVector(NodePtr n,BitVectorListPtr bvl) {
24 BitVectorListPtr nextBvl = bvl->next[(int)n->Value.character] = allocateBitVectorList(); 24 BitVectorListPtr nextBvl = allocateBitVectorList();
25 nextBvl->self = bvl->next[(int)n->Value.character]; 25 nextBvl->bi = bitSet(n->nodeNumber);
26 nextBvl->bi = bitSet(n->nodeNumber); 26 nextBvl->initBvl = initBvl;
27 nextBvl->initBvl = initBvl; 27 return nextBvl;
28
29 return nextBvl;
30 } 28 }
31 29
32 30
33 BitVectorListPtr initBitVector() { 31 BitVectorListPtr initBitVector() {
32
33 BitVectorListPtr bvl = allocateBitVectorList();
34 bvl->initBvl = initBvl = bvl;
35 bvl->bi = bitSet(0);
34 36
35 BitVectorListPtr bvl = allocateBitVectorList(); 37 for (int i = 0; i < 256; i++) {
36 bvl->initBvl = initBvl = bvl; 38 bvl->next[i] = NULL;
37 bvl->bi = bitSet(0); 39 }
38 40
39 for (int i = 0; i < 256; i++) { 41 return bvl;
40 bvl->next[i] = NULL;
41 }
42
43 return bvl;
44 } 42 }
45 43
46 void printBitVectorList (BitVectorListPtr bvl) { 44 void printBitVectorList (BitVectorListPtr bvl) {
47 bool initPrintFlag = true; 45 bool isFirstPrint = true;
48 for (int i = 0; i < 256; i++) { 46 for (int i = 0; i < 256; i++) {
49 if (bvl->next[i] != NULL) { 47 if (bvl->next[i] != NULL) {
50 if (initPrintFlag) { 48 if (isFirstPrint){
51 puts("----"); 49 puts("----");
52 printf(" state : "); bitPrint(bvl->bi); 50 printf(" state : "); bitPrint(bvl->bi);
53 initPrintFlag = false; 51 isFirstPrint = false;
54 } 52 }
55 printf("input char : %c\n",i); 53 printf("input char : %c\n",i);
56 printf("next state : "); bitPrint(bvl->next[i]->bi); 54 printf("next state : ");bitPrint(bvl->next[i]->bi);
57 } 55 }
56 }
57
58 for (int i = 0; i < 256; i++) {
59 if (bvl->next[i] != NULL) {
60 printBitVectorList(bvl->next[i]);
61 }
62 }
63 }
64
65 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr) {
66 bool leftIsOr, rightIsOr;
67 if (n->tokenType == '*') {
68
69 } else if (n->Value.character == '|') {
70 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
71 setNextBitVectorList(n->left, prev, bvl);
72 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
73 setNextBitVectorList(n->right, prev, bvl);
74 fromOr = true;
75 return prev;
76 } else if (n->Value.character == '+') {
77 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr);
78 setNextBitVectorList(n->left, prev, bvl);
79 prev = bvl;
80 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr);
81
82 if (leftIsOr){
83 for (int i = 0; i < 256; i++)
84 if (prev->next[i] != NULL)
85 setNextBitVectorList(n->right, prev->next[i], bvl);
86 }
87 else {
88 setNextBitVectorList(n->right, prev, bvl);
58 } 89 }
59 90
60 for (int i = 0; i < 256; i++) { 91 fromOr = false;
61 if (bvl->next[i] != NULL) { 92 } else if (n->tokenType == 'a') {
62 printBitVectorList(bvl->next[i]); 93 bvl = createBitVector(n,bvl);
63 } 94 fromOr = false;
64 } 95 }
96 return bvl;
65 } 97 }
66 98
67 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl) { 99 BitVectorListPtr setNextBitVectorList(NodePtr n, BitVectorListPtr bvl, BitVectorListPtr next){
68 100 if (isalnum((int)n->Value.character)){
69 if (n->Value.character == '*') { 101 bvl->next[(int)n->Value.character] = next;
70 bvl = descendTreeNode(n->left,bvl); 102 }
71 } else if (n->Value.character == '|') { 103 return next;
72 bvl = descendTreeNode(n->left,bvl);
73 bvl = descendTreeNode(n->parent->right,bvl);
74 } else if (n->Value.character == '+') {
75 bvl = descendTreeNode(n->left,bvl);
76 bvl = descendTreeNode(n->right,bvl);
77 } else if (n->tokenType == 'a') {
78 bvl = createBitVector(n,bvl);
79 }
80 return bvl;
81 } 104 }
82 105
83 BitVectorListPtr createBitVectorList(NodePtr n) { 106 BitVectorListPtr createBitVectorList(NodePtr n) {
84 BitVectorListPtr bvl = initBitVector(); 107 BitVectorListPtr bvl = initBitVector();
85 descendTreeNode(n,bvl); 108 bool fromOr = false;
86 printBitVectorList(bvl); 109 descendTreeNode(n, bvl, bvl, fromOr);
87 return bvl; 110 printBitVectorList(bvl);
111 return bvl;
88 } 112 }