Mercurial > hg > Applications > Grep
comparison regexParser/subsetConstraction.cc @ 202:39ca25ed0607
add searchBit test
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 26 Dec 2015 19:49:34 +0900 |
parents | b8bc24abaf8a |
children | e809a2dd0731 |
comparison
equal
deleted
inserted
replaced
201:b8bc24abaf8a | 202:39ca25ed0607 |
---|---|
347 for (;state;state = state->next) { | 347 for (;state;state = state->next) { |
348 printState(state); | 348 printState(state); |
349 putchar('\n'); | 349 putchar('\n'); |
350 } | 350 } |
351 } | 351 } |
352 | |
353 SCValue createSCValue(TGValue tgv) { | |
354 SCValue scv; | |
355 scv.stateTop = tgv.tg->stateList; | |
356 scv.stateEnd = scv.stateTop; | |
357 while (scv.stateEnd->next) { | |
358 scv.stateEnd = scv.stateEnd->next; | |
359 } | |
360 return; | |
361 } | |
362 | |
363 SCValue createState(SCValue scv,BitVector bi) { | |
364 StatePtr s = NEW(State); | |
365 s->stateNum = ++scv.tg->totalStateCount; | |
366 s->next = NULL; | |
367 scv.stateEnd->next = s; | |
368 scv.stateEnd = s; | |
369 s->bitState = bi; | |
370 s->cc = NULL; | |
371 return scv; | |
372 } | |
373 | |
374 /** | |
375 現在のステートに含まれる組み合わせ状態をとってくる | |
376 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する | |
377 生成した状態は stateArray に格納するA | |
378 新しい状態ができなくなったら終了 | |
379 | |
380 charClassMerge の段階で新しい状態をリストに登録したら、charclasswalk をする必要がなくなる | |
381 */ | |
382 SCValue subsetConstraction(SCValue scv) { | |
383 for (;scv.stateTop;scv.stateTop = scv.stateTop->next) { | |
384 CharClassWalker cw = createCharClassWalker(scv.stateTop->cc); | |
385 while (hasNext(cw)) { | |
386 CharClassPtr cc = getNext(cw); | |
387 unsigned long bi = cc->nextState.bitContainer; | |
388 if (scv.stateArray[bi]) continue; | |
389 scv = createState(scv,bi); | |
390 StatePtr s = scv.stateEnd; | |
391 for (;bi.bitContainer;) { | |
392 int bitPosition = searchBit(bi); | |
393 unsigned long baseNum = 1 << bitPosition; | |
394 bi.bitContainer ^= baseNum; | |
395 StatePtr base = scv.stateArray[baseNum]; | |
396 if (base == NULL) {// error | |
397 continue; | |
398 } | |
399 CharClassPtr merge = mergeTransition(s,base->cc); | |
400 s->cc = merge; | |
401 } | |
402 scv.stateArray[bi] = s; | |
403 } | |
404 } | |
405 return; | |
406 } |