Mercurial > hg > Applications > Grep
view c/regexParser/subsetConstraction.cc @ 155:6cd0141bed6c pairPro
impl charClassMerge
author | masa |
---|---|
date | Fri, 18 Dec 2015 15:40:55 +0900 (2015-12-18) |
parents | 1fad21fd6028 |
children | b5ecfc008bcf |
line wrap: on
line source
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include "subsetConstraction.h" CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) { CharClassPtr cc = NEW(CharClass); return cc; } CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { // 重なっているccの領域を分割する // 必要ならばnextStateを重ねあわせる // 変更があった場合は新しくリストを作って返す if (end < cc->cond.range.begin ) { // 1 if (cc->left) { return createCharClassRange(cc->begin,cc->end,charClassMerge(cc->left,begin,end,nextState),cc->right); } else { CharClassPtr cc1 = createCharClassRange(begin,end,NULL,cc); cc1->nextState = nextState; return cc1; } } else if (end == cc->cond.range.begin ) { // 2 CharClassPtr cc1; if (cc->left) { cc1 = charClassMerge(cc->left,begin,end-1,nextState); } else { cc1 = createCharClassRange(begin,end-1,NULL,NULL); cc1->nextState = nextState; } if (cc->begin == cc->end) { CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc1,cc->right); cc2->nextState = cc->nextState | nextState; return cc2; } CharClassPtr cc3; createCharClassRange(cc->begin+1,cc->end,cc->left,cc->end); cc3->nextState = cc->nextState; CharClassPtr cc2 = createCharClassRange(cc->begin,cc->begin,cc1,cc3); cc2->nextState = cc->nextState | nextState; return cc2; } else if (end < cc->cond.range.end) { if (begin < cc->cond.range.begin) { // 3 CharClassPtr cc1; if (cc->left) { cc1 = charClassMerge(cc->left,begin,cc->begin-1,nextState); } else { cc1 = createCharClassRange(begin,cc->begin-1,NULL,NULL); cc1->nextState = nextState; } CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc->left,cc->right); cc3->nextState = cc->nextState; CharClassPtr cc2 = createCharClassRange(cc->begin,end,cc1,cc3); cc2->nextState = cc->nextState | nextState; return cc2; } if (begin == cc->cond.range.begin) { // 6 CharClassPtr cc2 = createCharClassRange(end,cc->end,NULL,cc->right); cc2->nextState = cc->nextState; CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2); cc1->nextState = cc->nextState | nextState; return cc1; } // 9 CharClassPtr cc2 = createCharClassRange(cc->begin,begin-1,cc->left,NULL); cc2->nextState = cc1->nextState; CharClassPtr cc3 = createCharClassRange(end+1,cc->end,NULL,cc->right); cc3->nextState = cc->nextState; CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3); cc1->nextState = cc->nextState | nextState; return cc1; } else if (end == cc->cond.range.end) { if (begin == cc->cond.range.begin) { // 7 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right); cc1->nextState = cc->nextState | nextState; return cc1; } else if (begin < cc->cond.range.begin) { // 4 CharClassPtr cc1; if (cc->left) { cc1 = charClassMerge(cc->left,begin,end-1,nextState); } else { cc1 = createCharClassRange(begin,end-1,NULL,NULL); cc1->nextState = nextState; } CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right); cc3->nextState = cc->nextState | nextState; return cc3; } // 10 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right); cc2->nextState = cc->nextState | nextState; CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,NULL,NULL); cc1->nextState = cc->nextState; return cc1; } if (begin > cc->cond.range.end ) { // 13 if (cc->right) { return createCharClassRange(cc->begin,cc->end,cc->left,charClassMerge(cc->right,begin,end,nextState)); } else { CharClassPtr cc1 = createCharClassRange(begin,end,cc,NULL); cc1->nextState = nextState; return cc1; } } if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { if (end > cc->cond.range.end) { if (begin == cc->cond.range.begin) { // 8 CharClassPtr cc1; if (cc->left) { cc1 = charClassMerge(cc->left,begin,end-1,nextState); } else { cc1 = createCharClassRange(begin,end-1,NULL,NULL); cc1->nextState = nextState; } CharClassPtr cc3 = createCharClassRange(end+1,cc->end,cc1,cc->right); cc3->nextState = cc->nextState | nextState; return cc3; } // 11 cc->cond.range.end = end; // 11,8 return cc; } // 12 CharClassPtr cc1; if (cc->right) { cc1 = charClassMerge(cc->right,begin+1,end,nextState); } else { cc1 = createCharClassRange(begin+1,end,NULL,NULL); cc1->nextState = nextState; } if (cc->begin == cc->end) { CharClassPtr cc2 = createCharClassRange(cc->begin,cc->end,cc->left,cc1); cc2->nextState = cc->nextState | nextState; return cc2; } CharClassPtr cc3 = createCharClassRange(cc->begin,cc->end-1,NULL,cc->right); cc3->nextState = cc->nextState; CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3); cc2->nextState = cc->nextState | nextState; return cc2; } else if (begin < cc->cond.range.begin) { // 5 cc->cond.range.begin = begin; cc->cond.range.end = end; } else { printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); } return cc; } TGValue generateTransition(NodePtr n,TransitionGenerator tg) { TGValue tgv2; if (n->tokenType == '+') { TGValue tgv = generateTransition(n->left,tg); if (tgv.asterisk) { TGValue tgv1 = generateTransition(n->right,tg); tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer; return tgv; } TGValue tgv1 = generateTransition(n->right,tg); tgv.ts->nextState = tgv1.ts->nextState; return tgv; } else if (n->tokenType == '|') { TGValue tgv = generateTransition(n->left,tg); TGValue tgv1 = generateTransition(n->right,tg); tgv.ts = appendTransition(tgv.ts,tgv1.ts); return tgv; } else if (n->tokenType == '*') { TGValue tgv = generateTransition(n->left,tg); tgv.asterisk = true; return tgv; } else if (n->tokenType == 'c'){ return tgv2; } else if (n->tokenType == 'a'){ TGValue tgv; tgv.ts = (TransitionPtr)malloc(sizeof(Transition)); tgv.ts->condition = n->cc; tgv.ts->nextState = (BitVectorPtr)malloc(sizeof(BitVector)); bitSet(tgv.ts->nextState,n->nodeNumber); tg.ts = appendTransition(tg.ts,tgv.ts); return tgv; } else { // error } return tgv2; } void printTransitionList(TransitionPtr ts) { for (;ts;ts = ts->next) { printf("\n"); } } TransitionGenerator generateTransitionList(NodePtr n) { TransitionGenerator tg; tg.ts = (TransitionPtr)malloc(sizeof(Transition)); generateTransition(n,tg); printTransitionList(tg.ts); return tg; }