Mercurial > hg > Applications > Grep

comparison c/regexParser/subsetConstraction.cc @ 110:a3adc5c24e19 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
start branch
author masa
date Fri, 20 Nov 2015 21:02:00 +0900
parents c/regexParser/createBitVectorList.cc@6401c708f5dd
children 66c633575b53
comparison
equal deleted inserted replaced
109:6401c708f5dd 110:a3adc5c24e19
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <ctype.h>
4 #include "bitVector.h"
5 #include "regexParser.h"
6
7
8 void printBitVectorList (BitVectorListPtr bvl) {
9 bool isFirstPrint = true;
10 for (int i = 0; i < 256; i++) {
11 if (bvl->next[i] != NULL) {
12 if (isFirstPrint){
13 puts("----");
14 printf(" state : "); bitPrint(bvl->bi);
15 isFirstPrint = false;
16 }
17 printf("input char : %c\n",i);
18 printf("next state : ");bitPrint(bvl->next[i]->bi);
19 bvl->isLoop = bvl->isLoopAnker;
20 }
21 }
22
23 for (int i = 0; i < 256; i++) {
24 if ((bvl->next[i] != NULL) && !(bvl->isLoop && bvl->isLoopAnker)) {
25 // if ((bvl->next[i] != NULL) ) {
26 printBitVectorList(bvl->next[i]);
27 }
28 }
29 }
30
31 BitVectorListPtr descendTreeNode(NodePtr n,BitVectorListPtr bvl, BitVectorListPtr prev, bool &fromOr, bool &fromAsterisk) {
32 bool leftIsOr, rightIsOr;
33 if (n->Value.character == '*') {
34 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
35 unsigned char repertChar = 0;
36 for (int i = 0; i < 256; i++) {
37 if (prev->next[i] != NULL) repertChar = i;
38 }
39 setNextBitVectorList(repertChar, bvl, prev->next[repertChar]); // here
40 bvl->isLoopAnker = true;
41 fromAsterisk = true;
42
43 return prev;
44 } else if (n->Value.character == '|') {
45 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
46 setNextBitVectorList(n->left->Value.character, prev, bvl);
47 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
48 setNextBitVectorList(n->right->Value.character, prev, bvl);
49 fromOr = true;
50 return prev;
51 } else if (n->Value.character == '+') {
52 bvl = descendTreeNode(n->left, bvl, prev, leftIsOr, fromAsterisk);
53 setNextBitVectorList(n->left->Value.character, prev, bvl);
54 prev = bvl;
55 bvl = descendTreeNode(n->right, bvl, prev, rightIsOr, fromAsterisk);
56
57 if (leftIsOr){
58 for (int i = 0; i < 256; i++)
59 if (prev->next[i] != NULL)
60 setNextBitVectorList(n->right->Value.character, prev->next[i], bvl);
61 }
62 else {
63 setNextBitVectorList(n->right->Value.character, prev, bvl);
64 }
65
66 fromOr = false;
67 } else if (n->tokenType == 'a') {
68 bvl = createBitVector(n,bvl);
69 fromOr = false;
70 }
71 return bvl;
72 }
73
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 }