Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 186:3e8aae8beba9 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix createTransitionGenerator()
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 24 Dec 2015 20:37:29 +0900
parents d25f4f3b4c34
children ef798db705e9
comparison
equal deleted inserted replaced
185:d25f4f3b4c34 186:3e8aae8beba9
202 free(walk); 202 free(walk);
203 return ccy; 203 return ccy;
204 } 204 }
205 205
206 /** 206 /**
207 作成する state を linked list 207 作成する state を linked list
208 bitvector を index とした配列に BitVectorPtr を格納 208 bitvector を index とした配列に BitVectorPtr を格納
209 state に対応する NodePtr を 209 state に対応する NodePtr を
210 */ 210 */
211 TGValue createState(TGValue tg,NodePtr n) { 211 TGValue createState(TGValue tg,NodePtr n) {
212 StatePtr s = NEW(State); 212 StatePtr s = NEW(State);
213 s->next = tg.tg->currentState; 213 s->next = tg.tg->currentState;
214 tg.tg->currentState = s; 214 tg.tg->currentState = s;
217 s->bitState = bi; 217 s->bitState = bi;
218 s->cc = NULL; 218 s->cc = NULL;
219 } 219 }
220 220
221 /** 221 /**
222 正規表現に必要な状態を探して、それぞれに番号を割り振る 222 正規表現に必要な状態を探して、それぞれに番号を割り振る
223 前が * でない + は新しく状態を作る 223 前が * でない + は新しく状態を作る
224 * があったら、次の状態はその時の先頭の状態になる 224 * があったら、次の状態はその時の先頭の状態になる
225 */ 225 */
226 TGValue stateAllocate(NodePtr n,TGValue tg) { 226 TGValue stateAllocate(NodePtr n,TGValue tg) {
227 if (n->tokenType == '+') { 227 if (n->tokenType == '+') {
228 TGValue tgLeft = stateAllocate(n->left,tg); 228 TGValue tgLeft = stateAllocate(n->left,tg);
229 if (tgLeft.asterisk) { 229 if (tgLeft.asterisk) {
258 return tg; 258 return tg;
259 } 259 }
260 } 260 }
261 261
262 /** 262 /**
263 割り当てられた状態に沿って charclass の行き先を書き換える 263 割り当てられた状態に沿って charclass の行き先を書き換える
264 書き換えた charclass を merge する 264 書き換えた charclass を merge する
265 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する 265 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
266 */ 266 */
267 TGValue generateTransition(NodePtr n,TGValue tg) { 267 TGValue generateTransition(NodePtr n,TGValue tg) {
268 if (n->tokenType == '+') { 268 if (n->tokenType == '+') {
269 if (tg.asterisk) { 269 if (tg.asterisk) {
270 TGValue tgRight = tg; 270 TGValue tgRight = tg;
304 for (;ts;ts = ts->next) { 304 for (;ts;ts = ts->next) {
305 printf("\n"); 305 printf("\n");
306 } 306 }
307 } 307 }
308 308
309 TransitionGenerator createTransitionGenerator() { 309 TransitionGeneratorPtr createTransitionGenerator() {
310 TransitionGenerator tg; 310 TransitionGeneratorPtr tg = NEW(TransitionGenerator);
311 tg.ts = NEW(Transition); 311 tg->stateMax = 0;
312 tg.state = NEW(State); 312 tg->stack = NULL;
313 tg.transitionList = NEW(Transition); 313 tg->state = NEW(State);
314 // Init State : 00...00(64bit) 314 tg->stateArray = NULL;
315 BitVectorPtr initStateBi = NEW(BitVector); 315 tg->currentState = NULL;
316 bitSet(initStateBi,INIT_STATE_BIT);
317 StatePtr initState = createState(*initStateBi);
318 // Last State : 10...00(64bit)
319 BitVectorPtr lastStateBi = NEW(BitVector);
320 bitSet(lastStateBi,END_STATE_BIT);
321 StatePtr lastState = createState(*lastStateBi);
322 tg.stateArray = appendState(initState,lastState);
323 tg.stateArrayLast = lastState;
324 tg.currentState = initState;
325 tg.nextState = NEW(State);
326 return tg; 316 return tg;
327 } 317 }
328 318
329 TransitionGenerator generateTransitionList(NodePtr n) { 319 TransitionGenerator generateTransitionList(NodePtr n) {
330 TransitionGenerator tg = createTransitionGenerator(); 320 TransitionGeneratorPtr tg = createTransitionGenerator();
331 TGValue tgv; 321 TGValue tgv;
332 tgv.asterisk = false; 322 tgv.asterisk = false;
333 tgv.tg = tg; 323 tgv.tg = tg;
334 StatePtr start = createState(tgv,n); 324 StatePtr start = createState(tgv,n);
335 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL); 325 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL);
336 StatePtr end = createState(tgv,eof); 326 StatePtr end = createState(tgv,eof);
337 tgv.stateBegin = 0; 327 tgv.stateBegin = 0;
338 tgv.stateEnd = 1; 328 tgv.stateEnd = 1;
339 stateAllocate(n,tgv); 329 stateAllocate(n,tgv);
330 tgv.tg->stateMax = tg.stateNum;
340 tgv.tg.stateArray = (StatePtr)calloc(tg.stateNum,sizeof(StatePtr)); 331 tgv.tg.stateArray = (StatePtr)calloc(tg.stateNum,sizeof(StatePtr));
341 generateTransition(n,tgv); 332 generateTransition(n,tgv);
342 printTransitionList(tg.ts); 333 printTransitionList(tg.ts);
343 return tg; 334 return tg;
344 } 335 }