Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 195:4fefd80c05f2 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change variable name (TGValue tg -> TGValue tgv)
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 26 Dec 2015 13:48:12 +0900
parents ecf70fb215a5
children 35608dc85e83 98ff9d94566a
comparison
equal deleted inserted replaced
194:b9db09ff630f 195:4fefd80c05f2
207 /** 207 /**
208 作成する state を linked list 208 作成する state を linked list
209 bitvector を index とした配列に BitVectorPtr を格納 209 bitvector を index とした配列に BitVectorPtr を格納
210 state に対応する NodePtr を 210 state に対応する NodePtr を
211 */ 211 */
212 StatePtr createState(TGValue tg,NodePtr n) { 212 StatePtr createState(TGValue tgv,NodePtr n) {
213 StatePtr s = NEW(State); 213 StatePtr s = NEW(State);
214 s->stateNum = n->stateNum = ++tg.tg->stateMax; 214 s->stateNum = n->stateNum = ++tgv.tg->stateMax;
215 s->next = tg.tg->stateList; 215 s->next = tgv.tg->stateList;
216 tg.tg->stateList = s; 216 tgv.tg->stateList = s;
217 s->node = n; 217 s->node = n;
218 BitVector bi = createBitVector(n->stateNum); 218 BitVector bi = createBitVector(n->stateNum);
219 s->bitState = bi; 219 s->bitState = bi;
220 s->cc = NULL; 220 s->cc = NULL;
221 return s; 221 return s;
224 /** 224 /**
225 正規表現に必要な状態を探して、それぞれに番号を割り振る 225 正規表現に必要な状態を探して、それぞれに番号を割り振る
226 前が * でない + は新しく状態を作る 226 前が * でない + は新しく状態を作る
227 * があったら、次の状態はその時の先頭の状態になる 227 * があったら、次の状態はその時の先頭の状態になる
228 */ 228 */
229 TGValue stateAllocate(NodePtr n,TGValue tg) { 229 TGValue stateAllocate(NodePtr n,TGValue tgv) {
230 if (n->tokenType == '+') { 230 if (n->tokenType == '+') {
231 TGValue tgLeft = stateAllocate(n->left,tg); 231 TGValue tgvLeft = stateAllocate(n->left,tgv);
232 if (tgLeft.asterisk) { 232 if (tgvLeft.asterisk) {
233 TGValue tgRight = tgLeft; 233 TGValue tgvRight = tgvLeft;
234 tgRight.asterisk = false; 234 tgvRight.asterisk = false;
235 tgRight = stateAllocate(n->right,tgRight); 235 tgvRight = stateAllocate(n->right,tgvRight);
236 tgRight.asterisk = true; 236 tgvRight.asterisk = true;
237 return tgRight; 237 return tgvRight;
238 } 238 }
239 TGValue tgRight = tgLeft; 239 TGValue tgvRight = tgvLeft;
240 n->right->state = createState(tgRight,n->right); 240 n->right->state = createState(tgvRight,n->right);
241 tgRight.startState = n->right->state; 241 tgvRight.startState = n->right->state;
242 stateAllocate(n->right,tgRight); 242 stateAllocate(n->right,tgvRight);
243 return tgLeft; 243 return tgvLeft;
244 } else if (n->tokenType == '|') { 244 } else if (n->tokenType == '|') {
245 TGValue tgv = stateAllocate(n->left,tg); 245 TGValue tgv1 = stateAllocate(n->left,tgv);
246 TGValue tgv1 = stateAllocate(n->right,tgv); 246 TGValue tgv2 = stateAllocate(n->right,tgv1);
247 return tgv2;
248 } else if (n->tokenType == '*') {
249 TGValue tgvAstah = tgv;
250 tgvAstah.endState = tgvAstah.startState;
251 tgvAstah = stateAllocate(n->left,tgvAstah);
252 tgvAstah.asterisk = true;
253 return tgvAstah;
254 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
255 TGValue tgv1 = tgv;
256 tgv1.asterisk = false;
257 n->stateNum = tgv.startState->stateNum;
258 n->nextStateNum = tgv.endState->stateNum;
259 n->state = tgv.startState;
260 n->nextState = tgv.endState;
247 return tgv1; 261 return tgv1;
248 } else if (n->tokenType == '*') { 262 } else {
249 TGValue tgAstah = tg;
250 tgAstah.endState = tgAstah.startState;
251 tgAstah = stateAllocate(n->left,tgAstah);
252 tgAstah.asterisk = true;
253 return tgAstah;
254 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
255 TGValue tgv = tg;
256 tgv.asterisk = false;
257 n->stateNum = tg.startState->stateNum;
258 n->nextStateNum = tg.endState->stateNum;
259 n->state = tg.startState;
260 return tgv; 263 return tgv;
261 } else {
262 return tg;
263 } 264 }
264 } 265 }
265 266
266 /** 267 /**
267 割り当てられた状態に沿って charclass の行き先を書き換える 268 割り当てられた状態に沿って charclass の行き先を書き換える
268 書き換えた charclass を merge する 269 書き換えた charclass を merge する
269 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する 270 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
270 */ 271 */
271 TGValue generateTransition(NodePtr n,TGValue tg) { 272 TGValue generateTransition(NodePtr n,TGValue tgv) {
272 if (n->tokenType == '+') { 273 if (n->tokenType == '+') {
273 TGValue tgLeft = generateTransition(n->left,tg); 274 TGValue tgvLeft = generateTransition(n->left,tgv);
274 if (tgLeft.asterisk) { 275 if (tgvLeft.asterisk) {
275 TGValue tgRight = tgLeft; 276 TGValue tgvRight = tgvLeft;
276 tgRight.asterisk = false; 277 tgvRight.asterisk = false;
277 tgRight = generateTransition(n->right,tgRight); 278 tgvRight = generateTransition(n->right,tgvRight);
278 tgRight.asterisk = true; 279 tgvRight.asterisk = true;
279 return tgRight; 280 return tgvRight;
280 } 281 }
281 StatePtr left = tgLeft.startState; 282 StatePtr left = tgvLeft.startState;
282 tgLeft.startState = n->right->state; 283 tgvLeft.startState = n->right->state;
283 tgLeft.tg->stateArray[tgLeft.startState->bitState.bitContainer] = left; 284 tgvLeft.tg->stateArray[tgvLeft.startState->bitState.bitContainer] = left;
284 TGValue tgv1 = generateTransition(n->right,tgLeft); 285 TGValue tgv1 = generateTransition(n->right,tgvLeft);
285 tgv1.startState = left; 286 tgv1.startState = left;
286 return tgv1; 287 return tgv1;
287 } else if (n->tokenType == '|') { 288 } else if (n->tokenType == '|') {
288 TGValue tgv = generateTransition(n->left,tg); 289 TGValue tgv1 = generateTransition(n->left,tgv);
289 TGValue tgv1 = generateTransition(n->right,tgv); 290 TGValue tgv2 = generateTransition(n->right,tgv1);
290 return tgv1; 291 return tgv2;
291 } else if (n->tokenType == '*') { 292 } else if (n->tokenType == '*') {
292 TGValue tgAstah = generateTransition(n->left,tg); 293 TGValue tgvAstah = generateTransition(n->left,tgv);
293 tgAstah.asterisk = true; 294 tgvAstah.asterisk = true;
294 return tgAstah; 295 return tgvAstah;
295 } else if (n->tokenType == 'c' || n->tokenType == 'a'){ 296 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
296 TGValue tgv = tg; 297 TGValue tgv1 = tgv;
297 tgv.asterisk = false; 298 tgv1.asterisk = false;
298 BitVector bi = createBitVector(n->nextStateNum); 299 BitVector bi = createBitVector(n->nextStateNum);
299 setState(n->cc,bi); 300 setState(n->cc,bi);
300 tgv.startState->cc = mergeTransition(tgv.startState,n->cc); 301 tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
302 return tgv1;
303 } else {
301 return tgv; 304 return tgv;
302 } else {
303 return tg;
304 } 305 }
305 } 306 }
306 307
307 TransitionGeneratorPtr createTransitionGenerator() { 308 TransitionGeneratorPtr createTransitionGenerator() {
308 TransitionGeneratorPtr tg = NEW(TransitionGenerator); 309 TransitionGeneratorPtr tg = NEW(TransitionGenerator);
336 337
337 void printState(StatePtr state) { 338 void printState(StatePtr state) {
338 printf("state : %lx\n",state->bitState.bitContainer); 339 printf("state : %lx\n",state->bitState.bitContainer);
339 long nodeNumber = 0; 340 long nodeNumber = 0;
340 if (state->node) { 341 if (state->node) {
341 printf("node : %c %d -> %d\n",state->node->tokenType,state->node->stateNum,state->node->nextStateNum); 342 printf("node : %c %lx -> %d\n",state->node->tokenType,state->bitState.bitContainer,state->node->nextStateNum);
342 nodeNumber = state->node->stateNum; 343 if (state->node->state)
344 nodeNumber = state->node->state->bitState.bitContainer;
343 } 345 }
344 if (state->cc) { 346 if (state->cc) {
345 printCharacterClass(state->cc,nodeNumber,4); 347 printCharacterClass(state->cc,nodeNumber,4);
346 } 348 }
347 } 349 }