Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 201:b8bc24abaf8a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add TODO and fix CharClassWalker
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 26 Dec 2015 18:13:32 +0900
parents 35608dc85e83
children 39ca25ed0607
comparison
equal deleted inserted replaced
198:35608dc85e83 201:b8bc24abaf8a
115 115
116 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) { 116 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) {
117 while (next->left) { 117 while (next->left) {
118 CharClassStackPtr ccs = NEW(CharClassStack); 118 CharClassStackPtr ccs = NEW(CharClassStack);
119 ccs->next = walk->stack; 119 ccs->next = walk->stack;
120 ccs->turn = LEFT; 120 ccs->turn = walk->turn;
121 walk->turn = LEFT;
121 ccs->cc = next; 122 ccs->cc = next;
122 walk->stack = ccs; 123 walk->stack = ccs;
123 next = next->left; 124 next = next->left;
124 } 125 }
126 walk->turn = SELF;
125 walk->next = next; 127 walk->next = next;
126 } 128 }
127 129
128 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) { 130 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) {
129 CharClassWalkerPtr walk = NEW(CharClassWalker); 131 CharClassWalkerPtr walk = NEW(CharClassWalker);
130 walk->next = NULL; 132 walk->next = NULL;
131 walk->stack = NULL; 133 walk->stack = NULL;
132 if (!next) return walk; 134 if (!next) return walk;
133 if (!next->left) {
134 walk->next = next;
135 return walk;
136 }
137 findLeftMost(next,walk); 135 findLeftMost(next,walk);
138 return walk; 136 return walk;
139 } 137 }
140 138
141 bool hasNext(CharClassWalkerPtr walk) { 139 bool hasNext(CharClassWalkerPtr walk) {
142 return walk->next != NULL; 140 return walk->next != NULL;
143 } 141 }
144 142
145 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) { 143 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) {
146 if (!walk->stack) {
147 return NULL;
148 }
149 CharClassStackPtr prev = walk->stack->next; 144 CharClassStackPtr prev = walk->stack->next;
150 free(walk->stack); 145 free(walk->stack);
151 walk->stack = prev; 146 walk->stack = prev;
147 walk->turn = prev->turn;
152 return prev; 148 return prev;
153 } 149 }
154 150
155 CharClassPtr getNext(CharClassWalkerPtr walk) { 151 CharClassPtr getNext(CharClassWalkerPtr walk) {
156 CharClassPtr current = walk->next; 152 CharClassPtr current = walk->next;
157 walk->next = NULL; 153 walk->next = NULL;
158 while (walk->stack) { 154 if (walk->turn == SELF) {
159 while (walk->stack->turn == RIGHT) {
160 if (charClassStackPop(walk) == NULL) {
161 return current;
162 }
163 }
164 if (walk->stack->turn == LEFT) {
165 walk->next = walk->stack->cc;
166 walk->stack->turn = SELF;
167 return current;
168 }
169 if (current->right) { 155 if (current->right) {
170 walk->stack->turn = RIGHT; 156 walk->turn = RIGHT;
171 findLeftMost(current->right,walk); 157 findLeftMost(current->right,walk);
172 return current; 158 return current;
173 } 159 }
160 }
161 while (walk->stack) {
162 walk->next = walk->stack->cc;
174 charClassStackPop(walk); 163 charClassStackPop(walk);
175 } 164 if (walk->turn == LEFT) {
165 walk->turn = SELF;
166 return current;
167 }
168 }
169 walk->next = NULL;
176 return current; 170 return current;
177 } 171 }
178 172
179 void setState(CharClassPtr cc, BitVector bi) { 173 void setState(CharClassPtr cc, BitVector bi) {
180 cc->nextState = bi; 174 cc->nextState = bi;
227 * があったら、次の状態はその時の先頭の状態になる 221 * があったら、次の状態はその時の先頭の状態になる
228 */ 222 */
229 TGValue stateAllocate(NodePtr n,TGValue tgv) { 223 TGValue stateAllocate(NodePtr n,TGValue tgv) {
230 if (n->tokenType == '+') { 224 if (n->tokenType == '+') {
231 TGValue tgvLeft = stateAllocate(n->left,tgv); 225 TGValue tgvLeft = stateAllocate(n->left,tgv);
232 n->left->state = createState(tgvLeft,n->left);
233 if (tgvLeft.asterisk) { 226 if (tgvLeft.asterisk) {
234 TGValue tgvRight = tgvLeft; 227 TGValue tgvRight = tgvLeft;
235 tgvRight.asterisk = false; 228 tgvRight.asterisk = false;
236 tgvRight = stateAllocate(n->right,tgvRight); 229 tgvRight = stateAllocate(n->right,tgvRight);
237 tgvRight.asterisk = true; 230 tgvRight.asterisk = true;
338 331
339 void printState(StatePtr state) { 332 void printState(StatePtr state) {
340 printf("state : %lx\n",state->bitState.bitContainer); 333 printf("state : %lx\n",state->bitState.bitContainer);
341 long nodeNumber = 0; 334 long nodeNumber = 0;
342 if (state->node) { 335 if (state->node) {
343 if (state->node->nextState) { 336 printf("node : %c %lx -> %d\n",state->node->tokenType,state->bitState.bitContainer,state->node->nextStateNum);
344 printf("node : %c %lx -> %lx\n",state->node->tokenType,
345 state->bitState.bitContainer,state->node->nextState->bitState.bitContainer);
346 if (state->node->state) 337 if (state->node->state)
347 nodeNumber = state->node->state->bitState.bitContainer; 338 nodeNumber = state->node->state->bitState.bitContainer;
348 }
349 } 339 }
350 if (state->cc) { 340 if (state->cc) {
351 printCharacterClass(state->cc,nodeNumber,4); 341 printCharacterClass(state->cc,nodeNumber,4);
352 } 342 }
353 } 343 }