Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstruction.cc @ 250:e60dd2fa3409

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove SCValue
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 23 Jan 2016 13:51:33 +0900
parents 2b1fbfb92d54
children 21b9ba76f91b
comparison
equal deleted inserted replaced
249:9493800265a8 250:e60dd2fa3409
196 /** 196 /**
197 作成する state を linked list 197 作成する state を linked list
198 bitvector を index とした配列に BitVectorPtr を格納 198 bitvector を index とした配列に BitVectorPtr を格納
199 state に対応する NodePtr を 199 state に対応する NodePtr を
200 */ 200 */
201 StatePtr createState(TransitionGeneratorPtr tg,BitVector bi) {
202 StatePtr s = NEW(State);
203 s->stateNum = tg->totalStateCount++;
204 s->next = NULL;
205 tg->stateEnd->next = s;
206 tg->stateEnd = s;
207 s->bitState = bi;
208 s->cc = NULL;
209 s->node = NULL;
210 return s;
211 }
212
201 StatePtr createState(TGValue tgv,NodePtr n) { 213 StatePtr createState(TGValue tgv,NodePtr n) {
202 BitVector bi = createBitVector(tgv.tg->totalStateCount); 214 BitVector bi = createBitVector(tgv.tg->totalStateCount);
203 StatePtr s = createState(tgv.tg,bi); 215 StatePtr s = createState(tgv.tg,bi);
204 n->stateNum = s->stateNum; 216 n->stateNum = s->stateNum;
205 s->next = tgv.tg->stateList; 217 s->next = tgv.tg->stateList;
207 s->node = n; 219 s->node = n;
208 s->bitState = bi; 220 s->bitState = bi;
209 s->accept = false; 221 s->accept = false;
210 s->cc = n->cc; 222 s->cc = n->cc;
211 return s; 223 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;
224 } 224 }
225 225
226 /** 226 /**
227 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る 227 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る
228 前が * でない + は新しく状態を作る 228 前が * でない + は新しく状態を作る
350 printState(state); 350 printState(state);
351 putchar('\n'); 351 putchar('\n');
352 } 352 }
353 } 353 }
354 354
355 SCValue createSCValue(TGValue tgv) {
356 SCValue scv;
357 scv.tg = tgv.tg;
358 scv.stateTop = tgv.tg->stateList;
359 scv.stateEnd = scv.stateTop;
360 while (scv.stateEnd->next) {
361 scv.stateEnd = scv.stateEnd->next;
362 }
363 return scv;
364 }
365
366 /** 355 /**
367 現在のステートに含まれる組み合わせ状態をとってくる 356 現在のステートに含まれる組み合わせ状態をとってくる
368 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する 357 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
369 生成した状態は stateArray に格納するA 358 生成した状態は stateArray に格納するA
370 新しい状態ができなくなったら終了 359 新しい状態ができなくなったら終了
389 } 378 }
390 } 379 }
391 380
392 void subsetConstruction(TransitionGeneratorPtr tg) { 381 void subsetConstruction(TransitionGeneratorPtr tg) {
393 for (;tg->stateTop;tg->stateTop = tg->stateTop->next) { 382 for (;tg->stateTop;tg->stateTop = tg->stateTop->next) {
394 CharClassWalkerPtr cw = createCharClassWalker(state->cc); 383 CharClassWalkerPtr cw = createCharClassWalker(tg->stateTop->cc);
395 while (hasNext(cw)) { 384 while (hasNext(cw)) {
396 CharClassPtr cc = getNext(cw); 385 CharClassPtr cc = getNext(cw);
397 BitVector bi = cc->nextState; 386 BitVector bi = cc->nextState;
398 if (tg->stateArray[bi.bitContainer]) continue; // already done 387 if (tg->stateArray[bi.bitContainer]) continue; // already done
399 StatePtr s = createState(tg,bi); 388 StatePtr s = createState(tg,bi);