Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 183:7ae0a3070647 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement generateTransitionList
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 24 Dec 2015 20:02:09 +0900
parents dbe004d03ef0
children 1da1b2eacb84
comparison
equal deleted inserted replaced
182:dbe004d03ef0 183:7ae0a3070647
201 } 201 }
202 free(walk); 202 free(walk);
203 return ccy; 203 return ccy;
204 } 204 }
205 205
206 /**
207 作成する state を linked list
208 bitvector を index とした配列に BitVectorPtr を格納
209 state に対応する NodePtr を
210 */
211 TGValue createState(TGValue tg,NodePtr n) {
212 StatePtr s = NEW(State);
213 s->next = tg.tg->currentState;
214 tg.tg->currentState = s;
215 s->node = n;
216 BitVector bi = createBitVector(tg.stateBegin);
217 s->bitState = bi;
218 s->cc = NULL;
219 }
220
206 TGValue stateAllocate(NodePtr n,TGValue tg) { 221 TGValue stateAllocate(NodePtr n,TGValue tg) {
207 TGValue tgv2 = tg;
208 if (n->tokenType == '+') { 222 if (n->tokenType == '+') {
209 TGValue tgLeft = stateAllocate(n->left,tg); 223 TGValue tgLeft = stateAllocate(n->left,tg);
210 if (tgLeft.asterisk) { 224 if (tgLeft.asterisk) {
211 TGValue tgRight = tgLeft; 225 TGValue tgRight = tgLeft;
212 tgRight.asterisk = false; 226 tgRight.asterisk = false;
214 tgRight.asterisk = true; 228 tgRight.asterisk = true;
215 return tgRight; 229 return tgRight;
216 } 230 }
217 TGValue tgRight = tgLeft; 231 TGValue tgRight = tgLeft;
218 tgRight.stateBegin = ++tgRight.stateNum; 232 tgRight.stateBegin = ++tgRight.stateNum;
219 tgRight.state = NEW(State); 233 n->right->state = createState(tgRight,n->right);
220 TGValue tgv1 = stateAllocate(n->right,tgLeft); 234 TGValue tgv1 = stateAllocate(n->right,tgLeft);
221 return tgLeft; 235 return tgLeft;
222 } else if (n->tokenType == '|') { 236 } else if (n->tokenType == '|') {
223 TGValue tgv = stateAllocate(n->left,tg); 237 TGValue tgv = stateAllocate(n->left,tg);
224 TGValue tgv1 = stateAllocate(n->right,tgv); 238 TGValue tgv1 = stateAllocate(n->right,tgv);
230 tgAstah.asterisk = true; 244 tgAstah.asterisk = true;
231 return tgAstah; 245 return tgAstah;
232 } else if (n->tokenType == 'c' || n->tokenType == 'a'){ 246 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
233 TGValue tgv = tg; 247 TGValue tgv = tg;
234 tgv.asterisk = false; 248 tgv.asterisk = false;
235 BitVector bi = createBitVector(tgv.stateEnd); 249 n->stateNum = tg.stateBegin;
250 n->nextStateNum = tg.stateEnd;
251 return tgv;
252 } else {
253 return tg;
254 }
255 }
256
257 TGValue generateTransition(NodePtr n,TGValue tg) {
258 if (n->tokenType == '+') {
259 StatePtr left = tg.state;
260 tg.state = n->left->state;
261 tg.tg.stateArray[tg.state->bitState.bitContainer] = tg.state;
262 TGValue tgLeft = generateTransition(n->left,tg);
263 tg.state = left;
264 TGValue tgv1 = generateTransition(n->right,tgLeft);
265 return tgv1;
266 } else if (n->tokenType == '|') {
267 TGValue tgv = generateTransition(n->left,tg);
268 TGValue tgv1 = generateTransition(n->right,tgv);
269 return tgv1;
270 } else if (n->tokenType == '*') {
271 tgAstah = generateTransition(n->left,tgAstah);
272 return tgAstah;
273 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
274 TGValue tgv = tg;
275 BitVector bi = createBitVector(n->nextStateNum);
236 setState(n->cc,bi); 276 setState(n->cc,bi);
237 tgv.state->cc = mergeTransition(tgv.state,n->cc); 277 tgv.state->cc = mergeTransition(tgv.state,n->cc);
238 return tgv; 278 return tgv;
239 } else { 279 } else {
240 // error 280 return tg;
241 } 281 }
242 return tgv2;
243 }
244
245 TGValue generateTransition(NodePtr n,TGValue tg) {
246 TGValue tgv2 = tg;
247 if (n->tokenType == '+') {
248 tgv2.stateBegin = ++tgv.stateNum;
249 TGValue tgLeft = generateTransition(n->right,tgv2);
250 tgLeft.stateEnd = tgv2.stateBegin;
251 TGValue tgv1 = generateTransition(n->left,tgLeft);
252 if (tgv1.asterisk) {
253 }
254 return tgv1;
255 } else if (n->tokenType == '|') {
256 TGValue tgv = generateTransition(n->left,tg);
257 TGValue tgv1 = generateTransition(n->right,tgv);
258 tgv.tg = tgv1.tg;
259 tgv.asterisk |= tgv1.asterisk;
260 return tgv;
261 } else if (n->tokenType == '*') {
262 TGValue tgv = generateTransition(n->left,tg);
263 tgv.asterisk = true;
264 return tgv;
265 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
266 TGValue tgv = tg;
267 tgv.ts = mergeTransition(tgv.ts,n->cc);
268 return tgv;
269 } else {
270 // error
271 }
272 return tgv2;
273 } 282 }
274 283
275 void printTransitionList(TransitionPtr ts) { 284 void printTransitionList(TransitionPtr ts) {
276 for (;ts;ts = ts->next) { 285 for (;ts;ts = ts->next) {
277 printf("\n"); 286 printf("\n");
298 return tg; 307 return tg;
299 } 308 }
300 309
301 TransitionGenerator generateTransitionList(NodePtr n) { 310 TransitionGenerator generateTransitionList(NodePtr n) {
302 TransitionGenerator tg = createTransitionGenerator(); 311 TransitionGenerator tg = createTransitionGenerator();
303 generateTransition(n,tg); 312 TGValue tgv;
313 tgv.asterisk = false;
314 tgv.tg = tg;
315 StatePtr start = createState(tgv,n);
316 NodePtr eof = createNode();
317 StatePtr end = createState(tgv,eof);
318 tgv.stateBegin = 0;
319 tgv.stateEnd = 1;
320 stateAllocate(n,tgv);
321 tgv.tg.stateArray = (StatePtr)calloc(tg.stateNum,sizeof(StatePtr));
322 generateTransition(n,tgv);
304 printTransitionList(tg.ts); 323 printTransitionList(tg.ts);
305 return tg; 324 return tg;
306 } 325 }