Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstruction.cc @ 248:2b1fbfb92d54

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement tSearch
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Fri, 22 Jan 2016 20:09:42 +0900
parents a3cddb32b87f
children e60dd2fa3409
comparison
equal deleted inserted replaced
247:96c2507fd22d 248:2b1fbfb92d54
162 } 162 }
163 return current; 163 return current;
164 } 164 }
165 165
166 void setState(CharClassPtr cc, BitVector bi) { 166 void setState(CharClassPtr cc, BitVector bi) {
167 // if (word case) setNext(bitVector to the word list)
167 cc->nextState = bi; 168 cc->nextState = bi;
168 if (cc->left) { 169 if (cc->left) {
169 setState(cc->left,bi); 170 setState(cc->left,bi);
170 } 171 }
171 cc->nextState = bi; 172 cc->nextState = bi;
196 作成する state を linked list 197 作成する state を linked list
197 bitvector を index とした配列に BitVectorPtr を格納 198 bitvector を index とした配列に BitVectorPtr を格納
198 state に対応する NodePtr を 199 state に対応する NodePtr を
199 */ 200 */
200 StatePtr createState(TGValue tgv,NodePtr n) { 201 StatePtr createState(TGValue tgv,NodePtr n) {
201 StatePtr s = NEW(State); 202 BitVector bi = createBitVector(tgv.tg->totalStateCount);
202 s->stateNum = n->stateNum = tgv.tg->totalStateCount; 203 StatePtr s = createState(tgv.tg,bi);
204 n->stateNum = s->stateNum;
203 s->next = tgv.tg->stateList; 205 s->next = tgv.tg->stateList;
204 tgv.tg->stateList = s; 206 tgv.tg->stateList = s;
205 s->node = n; 207 s->node = n;
206 BitVector bi = createBitVector(n->stateNum);
207 s->bitState = bi; 208 s->bitState = bi;
208 s->accept = false; 209 s->accept = false;
209 tgv.tg->totalStateCount++;
210 s->cc = n->cc; 210 s->cc = n->cc;
211 return s; 211 return s;
212 }
213
214 SCValue createState(TransitionGeneratorPtr tg,BitVector bi) {
215 StatePtr s = NEW(State);
216 s->stateNum = tg->totalStateCount++;
217 s->next = NULL;
218 tg->stateEnd->next = s;
219 tg->stateEnd = s;
220 s->bitState = bi;
221 s->cc = NULL;
222 s->node = NULL;
223 return scv;
212 } 224 }
213 225
214 /** 226 /**
215 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る 227 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る
216 前が * でない + は新しく状態を作る 228 前が * でない + は新しく状態を作る
349 scv.stateEnd = scv.stateEnd->next; 361 scv.stateEnd = scv.stateEnd->next;
350 } 362 }
351 return scv; 363 return scv;
352 } 364 }
353 365
354 SCValue createState(SCValue scv,BitVector bi) {
355 StatePtr s = NEW(State);
356 s->stateNum = ++scv.tg->totalStateCount;
357 s->next = NULL;
358 scv.stateEnd->next = s;
359 scv.stateEnd = s;
360 s->bitState = bi;
361 s->cc = NULL;
362 s->node = NULL;
363 return scv;
364 }
365
366 /** 366 /**
367 現在のステートに含まれる組み合わせ状態をとってくる 367 現在のステートに含まれる組み合わせ状態をとってくる
368 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する 368 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
369 生成した状態は stateArray に格納するA 369 生成した状態は stateArray に格納するA
370 新しい状態ができなくなったら終了 370 新しい状態ができなくなったら終了
371 371
372 charClassMerge の段階で新しい状態をリストに登録したら、charclasswalk をする必要がなくなる 372 charClassMerge の段階で新しい状態をリストに登録したら、charclasswalk をする必要がなくなる
373 */ 373 */
374 SCValue subsetConstruction(SCValue scv) { 374 void determinize(StatePtr s, TransitionGeneratorPtr tg) {
375 for (;scv.stateTop;scv.stateTop = scv.stateTop->next) { 375 BitVector bi = s->bitState;
376 CharClassWalkerPtr cw = createCharClassWalker(scv.stateTop->cc); 376 for (;;) {
377 int bitPosition = searchBit(bi);
378 if (!bitPosition) break;
379 unsigned long baseNum = 1 << (bitPosition-1);
380 // printf("bit %lx pos %d baseNum %lx\n",bi.bitContainer,bitPosition,baseNum);
381 bi.bitContainer ^= baseNum;
382 if (baseNum==2) continue; // EOF case
383 StatePtr base = tg->stateArray[baseNum];
384 if (base == NULL) {
385 errorMassege("No base state",__LINE__,__FILE__); break;
386 }
387 CharClassPtr merge = mergeTransition(s,base->cc);
388 s->cc = merge;
389 }
390 }
391
392 void subsetConstruction(TransitionGeneratorPtr tg) {
393 for (;tg->stateTop;tg->stateTop = tg->stateTop->next) {
394 CharClassWalkerPtr cw = createCharClassWalker(state->cc);
377 while (hasNext(cw)) { 395 while (hasNext(cw)) {
378 CharClassPtr cc = getNext(cw); 396 CharClassPtr cc = getNext(cw);
379 BitVector bi = cc->nextState; 397 BitVector bi = cc->nextState;
380 if (scv.tg->stateArray[bi.bitContainer]) continue; // already done 398 if (tg->stateArray[bi.bitContainer]) continue; // already done
381 scv = createState(scv,bi); 399 StatePtr s = createState(tg,bi);
382 StatePtr s = scv.stateEnd; 400 tg->stateArray[bi.bitContainer] = s;
383 scv.tg->stateArray[bi.bitContainer] = s; 401 determinize(s,tg);
384 for (;;) {
385 int bitPosition = searchBit(bi);
386 if (!bitPosition) break;
387 unsigned long baseNum = 1 << (bitPosition-1);
388 // printf("bit %lx pos %d baseNum %lx\n",bi.bitContainer,bitPosition,baseNum);
389 bi.bitContainer ^= baseNum;
390 if (baseNum==2) continue; // EOF case
391 StatePtr base = scv.tg->stateArray[baseNum];
392 if (base == NULL) {
393 errorMassege("No base state",__LINE__,__FILE__); break;
394 }
395 CharClassPtr merge = mergeTransition(s,base->cc);
396 s->cc = merge;
397 }
398 } 402 }
399 free(cw); 403 free(cw);
400 } 404 }
401 return scv; 405 }
402 }