Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstruction.cc @ 217:a9e3512120e2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
NFA generation end
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 30 Dec 2015 18:37:01 +0900
parents 4852bfa85db4
children d10fa72d8f31
comparison
equal deleted inserted replaced
216:4852bfa85db4 217:a9e3512120e2
222 TGValue generateTransition(NodePtr n,TGValue tgv, int pass) { 222 TGValue generateTransition(NodePtr n,TGValue tgv, int pass) {
223 if (n->tokenType == '+') { 223 if (n->tokenType == '+') {
224 TGValue tgvLeft = tgv; 224 TGValue tgvLeft = tgv;
225 tgvLeft.endState = n->right->state; 225 tgvLeft.endState = n->right->state;
226 tgvLeft.asterisk = NULL; 226 tgvLeft.asterisk = NULL;
227 tgvLeft = generateTransition(n->left,tgv,pass); 227 tgvLeft = generateTransition(n->left,tgvLeft,pass);
228 TGValue tgvRight = tgvLeft; 228 TGValue tgvRight = tgv;
229 if (tgvLeft.asterisk) { 229 if (tgvLeft.asterisk) {
230 n->right->state = tgv.endState; 230 n->right->state = tgv.endState;
231 tgvRight.startState = tgvRight.asterisk; 231 tgvRight.startState = tgvRight.asterisk;
232 tgvRight = generateTransition(n->right,tgvRight,pass); 232 tgvRight = generateTransition(n->right,tgvRight,pass);
233 tgvLeft.asterisk = tgvRight.asterisk; 233 tgvLeft.asterisk = tgvRight.asterisk;
235 } 235 }
236 tgvRight.asterisk = NULL; 236 tgvRight.asterisk = NULL;
237 if (pass==1) { 237 if (pass==1) {
238 n->right->state = tgvRight.startState = createState(tgvRight,n->right); 238 n->right->state = tgvRight.startState = createState(tgvRight,n->right);
239 } else { 239 } else {
240 tgvLeft.startState = n->right->state; 240 tgvRight.startState = n->right->state;
241 tgvLeft.tg->stateArray[tgvLeft.startState->bitState.bitContainer] = tgvLeft.startState ; 241 tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ;
242 } 242 }
243 tgvRight = generateTransition(n->right,tgvRight,pass); 243 tgvRight = generateTransition(n->right,tgvRight,pass);
244 tgvLeft.asterisk = tgvRight.asterisk; 244 tgvLeft.asterisk = tgvRight.asterisk;
245 return tgvLeft; 245 return tgvLeft;
246 } else if (n->tokenType == '|') { 246 } else if (n->tokenType == '|') {
255 return tgvAstah; 255 return tgvAstah;
256 } else if (n->tokenType == 'c' || n->tokenType == 'a'){ 256 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
257 TGValue tgv1 = tgv; 257 TGValue tgv1 = tgv;
258 if (pass==1) { 258 if (pass==1) {
259 n->stateNum = tgv.startState->stateNum; 259 n->stateNum = tgv.startState->stateNum;
260 n->nextStateNum = tgv.endState->stateNum; 260 n->state = tgv.startState;
261 n->state = tgv.startState;; 261 } else {
262 int nextState = tgv.endState->stateNum;
263 n->nextStateNum = nextState;
262 n->nextState = tgv.endState; 264 n->nextState = tgv.endState;
263 } else { 265 BitVector bi = createBitVector(nextState);
264 BitVector bi = createBitVector(n->nextStateNum);
265 setState(n->cc,bi); 266 setState(n->cc,bi);
266 tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc); 267 tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
267 } 268 }
268 return tgv1; 269 return tgv1;
269 } else { 270 } else {
292 TGValue generateTransitionList(NodePtr n) { 293 TGValue generateTransitionList(NodePtr n) {
293 TGValue tgv = createTGValue(); 294 TGValue tgv = createTGValue();
294 StatePtr startState = tgv.startState = createState(tgv,n); 295 StatePtr startState = tgv.startState = createState(tgv,n);
295 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL); 296 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL);
296 StatePtr endState = tgv.endState = createState(tgv,eof); 297 StatePtr endState = tgv.endState = createState(tgv,eof);
298 tgv.startState = startState;
299 tgv.endState = endState;
297 tgv = generateTransition(n,tgv,1); 300 tgv = generateTransition(n,tgv,1);
298 printTree(n); 301 printTree(n);
299 if (tgv.tg->totalStateCount > BITBLOCK) { 302 if (tgv.tg->totalStateCount > BITBLOCK) {
300 errorMassege("StateMax > BITBLOCK",__LINE__,__FILE__); 303 errorMassege("StateMax > BITBLOCK",__LINE__,__FILE__);
301 } 304 }
302 BitVector bi = createBitVector(tgv.tg->totalStateCount); 305 BitVector bi = createBitVector(tgv.tg->totalStateCount);
303 tgv.tg->stateArray = (StatePtr*)calloc(bi.bitContainer*2,sizeof(StatePtr*)); 306 tgv.tg->stateArray = (StatePtr*)calloc(bi.bitContainer*2,sizeof(StatePtr*));
304 tgv.tg->stateArray[startState->bitState.bitContainer] = startState; 307 tgv.tg->stateArray[startState->bitState.bitContainer] = startState;
305 tgv.tg->stateArray[endState->bitState.bitContainer] = endState; 308 tgv.tg->stateArray[endState->bitState.bitContainer] = endState;
309 tgv.startState = startState;
310 tgv.endState = endState;
306 tgv = generateTransition(n,tgv,2); 311 tgv = generateTransition(n,tgv,2);
307 return tgv; 312 return tgv;
308 } 313 }
309 314
310 void printState(StatePtr state) { 315 void printState(StatePtr state) {