Mercurial > hg > Applications > Grep
annotate c/regexParser/subsetConstraction.cc @ 155:6cd0141bed6c pairPro
impl charClassMerge
| author | masa |
|---|---|
| date | Fri, 18 Dec 2015 15:40:55 +0900 |
| parents | 1fad21fd6028 |
| children | b5ecfc008bcf |
| rev | line source |
|---|---|
|
96
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 #include <stdio.h> |
|
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 #include <stdlib.h> |
| 101 | 3 #include <ctype.h> |
|
117
166136236891
add header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
4 #include "subsetConstraction.h" |
|
96
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
6 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) { |
| 146 | 7 CharClassPtr cc = NEW(CharClass); |
| 154 | 8 return cc; |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
9 } |
|
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
10 |
| 152 | 11 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { |
| 143 | 12 // 重なっているccの領域を分割する |
| 13 // 必要ならばnextStateを重ねあわせる | |
| 14 // 変更があった場合は新しくリストを作って返す | |
| 152 | 15 if (end < cc->cond.range.begin ) { // 1 |
| 16 if (cc->left) { | |
| 155 | 17 return createCharClassRange(cc->begin,cc->end,charClassMerge(cc->left,begin,end,nextState),cc->right); |
| 152 | 18 } else { |
| 155 | 19 CharClassPtr cc1 = createCharClassRange(begin,end,NULL,cc); |
| 20 cc1->nextState = nextState; | |
| 152 | 21 return cc1; |
| 22 } | |
| 23 } else if (end == cc->cond.range.begin ) { // 2 | |
| 155 | 24 CharClassPtr cc1; |
| 25 if (cc->left) { | |
| 26 cc1 = charClassMerge(cc->left,begin,end-1,nextState); | |
| 152 | 27 } else { |
| 155 | 28 cc1 = createCharClassRange(begin,end-1,NULL,NULL); |
| 29 cc1->nextState = nextState; | |
| 30 } | |
| 31 if (cc->begin == cc->end) { | |
| 32 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc1,cc->right); | |
| 33 cc2->nextState = cc->nextState | nextState; | |
| 34 return cc2; | |
| 35 } | |
| 36 CharClassPtr cc3; | |
| 37 createCharClassRange(cc->begin+1,cc->end,cc->left,cc->end); | |
| 38 cc3->nextState = cc->nextState; | |
| 39 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->begin,cc1,cc3); | |
| 40 cc2->nextState = cc->nextState | nextState; | |
| 41 return cc2; | |
| 42 } else if (end < cc->cond.range.end) { | |
| 43 if (begin < cc->cond.range.begin) { // 3 | |
| 44 CharClassPtr cc1; | |
| 45 if (cc->left) { | |
| 46 cc1 = charClassMerge(cc->left,begin,cc->begin-1,nextState); | |
| 47 } else { | |
| 48 cc1 = createCharClassRange(begin,cc->begin-1,NULL,NULL); | |
| 49 cc1->nextState = nextState; | |
| 50 } | |
| 51 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc->left,cc->right); | |
| 52 cc3->nextState = cc->nextState; | |
| 53 CharClassPtr cc2 = createCharClassRange(cc->begin,end,cc1,cc3); | |
| 54 cc2->nextState = cc->nextState | nextState; | |
| 55 return cc2; | |
| 152 | 56 } |
| 155 | 57 if (begin == cc->cond.range.begin) { // 6 |
| 58 CharClassPtr cc2 = createCharClassRange(end,cc->end,NULL,cc->right); | |
| 59 cc2->nextState = cc->nextState; | |
| 60 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2); | |
| 61 cc1->nextState = cc->nextState | nextState; | |
| 62 return cc1; | |
| 63 } | |
| 64 // 9 | |
| 65 CharClassPtr cc2 = createCharClassRange(cc->begin,begin-1,cc->left,NULL); | |
| 66 cc2->nextState = cc1->nextState; | |
| 67 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,NULL,cc->right); | |
| 68 cc3->nextState = cc->nextState; | |
| 69 CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3); | |
| 70 cc1->nextState = cc->nextState | nextState; | |
| 71 return cc1; | |
| 72 } else if (end == cc->cond.range.end) { | |
| 73 if (begin == cc->cond.range.begin) { // 7 | |
| 74 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right); | |
| 75 cc1->nextState = cc->nextState | nextState; | |
| 76 return cc1; | |
| 77 } else if (begin < cc->cond.range.begin) { // 4 | |
| 78 CharClassPtr cc1; | |
| 79 if (cc->left) { | |
| 80 cc1 = charClassMerge(cc->left,begin,end-1,nextState); | |
| 81 } else { | |
| 82 cc1 = createCharClassRange(begin,end-1,NULL,NULL); | |
| 83 cc1->nextState = nextState; | |
| 84 } | |
| 85 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right); | |
| 86 cc3->nextState = cc->nextState | nextState; | |
| 87 return cc3; | |
| 88 } | |
| 89 // 10 | |
| 90 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right); | |
| 91 cc2->nextState = cc->nextState | nextState; | |
| 92 CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,NULL,NULL); | |
| 93 cc1->nextState = cc->nextState; | |
| 94 return cc1; | |
| 95 | |
| 143 | 96 } |
| 155 | 97 if (begin > cc->cond.range.end ) { // 13 |
| 98 if (cc->right) { | |
| 99 return createCharClassRange(cc->begin,cc->end,cc->left,charClassMerge(cc->right,begin,end,nextState)); | |
| 100 } else { | |
| 101 CharClassPtr cc1 = createCharClassRange(begin,end,cc,NULL); | |
| 102 cc1->nextState = nextState; | |
| 103 return cc1; | |
| 104 } | |
| 152 | 105 } |
| 155 | 106 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { |
| 107 if (end > cc->cond.range.end) { | |
| 108 if (begin == cc->cond.range.begin) { // 8 | |
| 109 CharClassPtr cc1; | |
| 110 if (cc->left) { | |
| 111 cc1 = charClassMerge(cc->left,begin,end-1,nextState); | |
| 112 } else { | |
| 113 cc1 = createCharClassRange(begin,end-1,NULL,NULL); | |
| 114 cc1->nextState = nextState; | |
| 115 } | |
| 116 CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right); | |
| 117 cc3->nextState = cc->nextState | nextState; | |
| 118 return cc3; | |
| 119 } | |
| 120 // 11 | |
| 121 cc->cond.range.end = end; // 11,8 | |
| 122 return cc; | |
| 123 } | |
| 124 // 12 | |
| 125 CharClassPtr cc1; | |
| 126 if (cc->right) { | |
| 127 cc1 = charClassMerge(cc->right,begin+1,end,nextState); | |
| 128 } else { | |
| 129 cc1 = createCharClassRange(begin+1,end,NULL,NULL); | |
| 130 cc1->nextState = nextState; | |
| 131 } | |
| 132 if (cc->begin == cc->end) { | |
| 133 CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc->left,cc1); | |
| 134 cc2->nextState = cc->nextState | nextState; | |
| 135 return cc2; | |
| 136 } | |
| 137 CharClassPtr cc3 = createCharClassRange(cc->begin,cc->end-1,NULL,cc->right); | |
| 138 cc3->nextState = cc->nextState; | |
| 139 CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3); | |
| 140 cc2->nextState = cc->nextState | nextState; | |
| 141 return cc2; | |
| 153 | 142 } else if (begin < cc->cond.range.begin) { // 5 |
| 152 | 143 cc->cond.range.begin = begin; |
| 144 cc->cond.range.end = end; | |
| 145 } else { | |
| 146 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); | |
| 147 } | |
| 148 return cc; | |
| 143 | 149 } |
| 150 | |
| 142 | 151 TGValue generateTransition(NodePtr n,TransitionGenerator tg) { |
| 154 | 152 TGValue tgv2; |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
153 if (n->tokenType == '+') { |
| 142 | 154 TGValue tgv = generateTransition(n->left,tg); |
| 155 if (tgv.asterisk) { | |
| 156 TGValue tgv1 = generateTransition(n->right,tg); | |
| 153 | 157 tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer; |
| 142 | 158 return tgv; |
| 159 } | |
| 153 | 160 TGValue tgv1 = generateTransition(n->right,tg); |
| 161 tgv.ts->nextState = tgv1.ts->nextState; | |
| 142 | 162 return tgv; |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
163 } else if (n->tokenType == '|') { |
| 153 | 164 TGValue tgv = generateTransition(n->left,tg); |
| 165 TGValue tgv1 = generateTransition(n->right,tg); | |
| 166 tgv.ts = appendTransition(tgv.ts,tgv1.ts); | |
| 167 return tgv; | |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
168 } else if (n->tokenType == '*') { |
| 153 | 169 TGValue tgv = generateTransition(n->left,tg); |
| 170 tgv.asterisk = true; | |
| 171 return tgv; | |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
172 } else if (n->tokenType == 'c'){ |
| 154 | 173 return tgv2; |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
174 } else if (n->tokenType == 'a'){ |
| 153 | 175 TGValue tgv; |
| 176 tgv.ts = (TransitionPtr)malloc(sizeof(Transition)); | |
| 177 tgv.ts->condition = n->cc; | |
| 178 tgv.ts->nextState = (BitVectorPtr)malloc(sizeof(BitVector)); | |
| 179 bitSet(tgv.ts->nextState,n->nodeNumber); | |
| 180 tg.ts = appendTransition(tg.ts,tgv.ts); | |
| 181 return tgv; | |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
182 } else { |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
183 // error |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
184 } |
| 154 | 185 return tgv2; |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
186 } |
|
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
187 |
| 153 | 188 void printTransitionList(TransitionPtr ts) { |
| 189 for (;ts;ts = ts->next) { | |
| 190 printf("\n"); | |
| 191 } | |
| 192 } | |
| 193 | |
|
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
194 TransitionGenerator generateTransitionList(NodePtr n) { |
|
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
195 TransitionGenerator tg; |
| 153 | 196 tg.ts = (TransitionPtr)malloc(sizeof(Transition)); |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
197 generateTransition(n,tg); |
| 153 | 198 printTransitionList(tg.ts); |
|
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
199 return tg; |
|
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
200 } |