Mercurial > hg > Applications > Grep

comparison c/regexParser/subsetConstraction.cc @ 153:e2e717fbeb2f pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Fri, 18 Dec 2015 14:02:41 +0900
parents 1c9e8ba64f6a
children 1fad21fd6028
comparison
equal deleted inserted replaced
152:1c9e8ba64f6a 153:e2e717fbeb2f
12 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { 12 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
13 // 重なっているccの領域を分割する 13 // 重なっているccの領域を分割する
14 // 必要ならばnextStateを重ねあわせる 14 // 必要ならばnextStateを重ねあわせる
15 // 変更があった場合は新しくリストを作って返す 15 // 変更があった場合は新しくリストを作って返す
16 if (end < cc->cond.range.begin ) { // 1 16 if (end < cc->cond.range.begin ) { // 1
17 CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,cc->right); 17 CharClassPtr cc1 = charClassMerge(cc,cc->cond.range.begin,cc->cond.range.end,nextState);
18 if (cc->left) { 18 if (cc->left) {
19 cc1->left = charClassMerge(cc->left,begin,end,nextState); 19 cc1->left = charClassMerge(cc->left,begin,end,nextState);
20 return cc1; 20 return cc1;
21 } else { 21 } else {
22 CharClassPtr cc2 = createCharClassRange(begin,end,0,0); 22 CharClassPtr cc2 = charClassMerge(begin,end,0,0);
23 cc2->nextState = nextState; 23 cc2->nextState = nextState;
24 cc1->left = cc2; 24 cc1->left = cc2;
25 return cc1; 25 return cc1;
26 } 26 }
27 } else if (end == cc->cond.range.begin ) { // 2 27 } else if (end == cc->cond.range.begin ) { // 2
34 return cc; 34 return cc;
35 } else if (begin > cc->cond.range.end ) { // 13 35 } else if (begin > cc->cond.range.end ) { // 13
36 if (cc->right) { 36 if (cc->right) {
37 cc->right = charClassMerge(cc->right,begin,end); 37 cc->right = charClassMerge(cc->right,begin,end);
38 } else { 38 } else {
39 cc->right = createCharClassRange(begin,end,0,0); 39 cc->right = charClassMerge(begin,end,0,0);
40 } 40 }
41 return cc; 41 return cc;
42 } 42 }
43 if (cc->right) { 43 if (cc->right) {
44 CharClassPtr right = cc->right; 44 CharClassPtr right = cc->right;
46 free(cc); 46 free(cc);
47 return charClassMerge(right,begin,end); 47 return charClassMerge(right,begin,end);
48 } 48 }
49 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12 49 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12
50 if (end > cc->cond.range.end) cc->cond.range.end = end; // 11,8 50 if (end > cc->cond.range.end) cc->cond.range.end = end; // 11,8
51 } else if (begin < cc->cond.range.begin) { // 6 51 } else if (begin < cc->cond.range.begin) { // 5
52 cc->cond.range.begin = begin; 52 cc->cond.range.begin = begin;
53 cc->cond.range.end = end; 53 cc->cond.range.end = end;
54 } else { 54 } else {
55 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); 55 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
56 } 56 }
57 return cc; 57 return cc;
58 } 58 }
59 59
60 void printTransition(TransitionPtr ts) {
61
62 }
63
64 TGValue generateTransition(NodePtr n,TransitionGenerator tg) { 60 TGValue generateTransition(NodePtr n,TransitionGenerator tg) {
65 if (n->tokenType == '+') { 61 if (n->tokenType == '+') {
66 TGValue tgv = generateTransition(n->left,tg); 62 TGValue tgv = generateTransition(n->left,tg);
67 if (tgv.asterisk) { 63 if (tgv.asterisk) {
68 TGValue tgv1 = generateTransition(n->right,tg); 64 TGValue tgv1 = generateTransition(n->right,tg);
69 tgv.ts->state->bitContainer |= tgv1.ts->state->bitContainer; 65 tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer;
70 return tgv; 66 return tgv;
71 } 67 }
72 bitSet(tgv.ts->state,n->right->nodeNumber); 68 TGValue tgv1 = generateTransition(n->right,tg);
69 tgv.ts->nextState = tgv1.ts->nextState;
73 return tgv; 70 return tgv;
74 } else if (n->tokenType == '|') { 71 } else if (n->tokenType == '|') {
75 72 TGValue tgv = generateTransition(n->left,tg);
73 TGValue tgv1 = generateTransition(n->right,tg);
74 tgv.ts = appendTransition(tgv.ts,tgv1.ts);
75 return tgv;
76 } else if (n->tokenType == '*') { 76 } else if (n->tokenType == '*') {
77 77 TGValue tgv = generateTransition(n->left,tg);
78 tgv.asterisk = true;
79 return tgv;
78 } else if (n->tokenType == 'c'){ 80 } else if (n->tokenType == 'c'){
79 81
80 } else if (n->tokenType == 'a'){ 82 } else if (n->tokenType == 'a'){
81 83 TGValue tgv;
84 tgv.ts = (TransitionPtr)malloc(sizeof(Transition));
85 tgv.ts->condition = n->cc;
86 tgv.ts->nextState = (BitVectorPtr)malloc(sizeof(BitVector));
87 bitSet(tgv.ts->nextState,n->nodeNumber);
88 tg.ts = appendTransition(tg.ts,tgv.ts);
89 return tgv;
82 } else { 90 } else {
83 // error 91 // error
84 } 92 }
85 } 93 }
86 94
95 void printTransitionList(TransitionPtr ts) {
96 for (;ts;ts = ts->next) {
97 printf("\n");
98 }
99 }
100
87 TransitionGenerator generateTransitionList(NodePtr n) { 101 TransitionGenerator generateTransitionList(NodePtr n) {
88 TransitionGenerator tg; 102 TransitionGenerator tg;
103 tg.ts = (TransitionPtr)malloc(sizeof(Transition));
89 generateTransition(n,tg); 104 generateTransition(n,tg);
105 printTransitionList(tg.ts);
90 return tg; 106 return tg;
91 } 107 }