Mercurial > hg > Applications > Grep

comparison c/regexParser/subsetConstraction.cc @ 137:c292c67b3100 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add generateTransitionList function
author masa
date Fri, 04 Dec 2015 20:32:09 +0900
parents 166136236891
children 6c258910cacb
comparison
equal deleted inserted replaced
136:15815fcb6c2f 137:c292c67b3100
1 #include <stdio.h> 1 #include <stdio.h>
2 #include <stdlib.h> 2 #include <stdlib.h>
3 #include <ctype.h> 3 #include <ctype.h>
4 #include "subsetConstraction.h" 4 #include "subsetConstraction.h"
5 5
6 void printBitVectorList (BitVectorListPtr bvl) { 6 typedef struct transitionGenerator {
7 bool isFirstPrint = true; 7 TransitionListPtr tl;
8 for (int i = 0; i < 256; i++) { 8 StatePtr state;
9 if (bvl->next[i] != NULL) { 9 long stateMax;
10 if (isFirstPrint){ 10 } TransitionGenerator, *TransitionGeneratorPtr;
11 puts("----"); 11
12 printf(" state : "); bitPrint(bvl->bi); 12 typedef struct tgValue {
13 isFirstPrint = false; 13 TransitionListPtr tl;
14 } 14 bool asterisk;
15 printf("input char : %c\n",i); 15 } TGValue, *TGValuePtr;
16 printf("next state : ");bitPrint(bvl->next[i]->bi); 16
17 bvl->isLoop = bvl->isLoopAnker; 17 TGValue generateTransitionList(NodePtr n,TransitionGeneretorPtr tg) {
18
19 if (n->left != NULL) {
20 TGValue tl = generateTransitionList(n->left, tg);
21 }
22 if (n->tokenType == 'a') {
23 printf("%*c",d*4, ' ');
24 for (int i = 0; i < n->cc->cond->w->length; i++) {
25 putchar(n->cc->cond->w->word[i]);
18 } 26 }
27 printf("(%lu)\n",n->nodeNumber);
28 } else if (n->tokenType == 'c') {
29 TGValue tl = generateTransitionList(n->cc,tg);
30 } else {
31 printf("%*c%c(%lu)\n",d*4, ' ',n->tokenType,n->nodeNumber);
19 } 32 }
20 33
21 for (int i = 0; i < 256; i++) { 34 if (n->right != NULL) {
22 if ((bvl->next[i] != NULL) && !(bvl->isLoop && bvl->isLoopAnker)) { 35 TGValue tl = generateTransitionList(n->right, tg);
23 // if ((bvl->next[i] != NULL) ) {
24 printBitVectorList(bvl->next[i]);
25 }
26 } 36 }
27 } 37 }
28
29 const
30 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr, bool &fromAsterisk) {
31 bool leftIsOr, rightIsOr;
32 if (n->cc->cond->character == '*') {
33 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
34 unsigned char repertChar = 0;
35 for (int i = 0; i < 256; i++) {
36 if (prev->next[i] != NULL) repertChar = i;
37 }
38 setNextBitVectorList(repertChar, bvl, prev->next[repertChar]); // here
39 bvl->isLoopAnker = true;
40 fromAsterisk = true;
41
42 return prev;
43 } else if (n->cc->cond->character == '|') {
44 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
45 setNextBitVectorList(n->left->cc->cond->character, prev, bvl);
46 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
47 setNextBitVectorList(n->right->cc->cond->character, prev, bvl);
48 fromOr = true;
49 return prev;
50 } else if (n->cc->cond->character == '+') {
51 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
52 setNextBitVectorList(n->left->cc->cond->character, prev, bvl);
53 prev = bvl;
54 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
55
56 if (leftIsOr){
57 for (int i = 0; i < 256; i++)
58 if (prev->next[i] != NULL)
59 setNextBitVectorList(n->right->cc->cond->character, prev->next[i], bvl);
60 }
61 else {
62 setNextBitVectorList(n->right->cc->cond->character, prev, bvl);
63 }
64
65 fromOr = false;
66 } else if (n->tokenType == 'a') {
67 bvl = createBitVector(n,bvl);
68 fromOr = false;
69 }
70 return bvl;
71 }
72
73 const
74 BitVectorListPtr setNextBitVectorList(unsigned char inputChar, BitVectorListPtr bvl, BitVectorListPtr next){
75 if (isalnum((int)inputChar)){
76 bvl->next[(int)inputChar] = next;
77 }
78 return next;
79 }
80
81 BitVectorListPtr createBitVectorList(NodePtr n) {
82 BitVectorListPtr bvl = initBitVector();
83 bool fromOr = false;
84 bool fromAsterisk = false;
85 descendTreeNode(n, bvl, bvl, fromOr, fromAsterisk);
86 printBitVectorList(bvl);
87 return bvl;
88 }