comparison regexParser/subsetConstraction.cc @ 182:dbe004d03ef0 pairPro

implement stateAllocate()
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 24 Dec 2015 19:14:49 +0900
parents 3c4db09b8581
children 7ae0a3070647
comparison
equal deleted inserted replaced
181:3c4db09b8581 182:dbe004d03ef0
173 charClassStackPop(walk); 173 charClassStackPop(walk);
174 } 174 }
175 return current; 175 return current;
176 } 176 }
177 177
178 void setState(CharClassPtr cc, BitVector bi) {
179 setState(cc,bi);
180 if (cc->left) {
181 setState(cc->left,bi);
182 }
183 cc->nextState = bi;
184 if (cc->right) {
185 setState(cc->right,bi);
186 }
187 }
188
178 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) { 189 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) {
179 if (x->cc == NULL) { 190 if (x->cc == NULL) {
180 return y; 191 return y;
181 } 192 }
182 CharClassWalkerPtr walk = createCharClassWalker(x->cc); 193 CharClassWalkerPtr walk = createCharClassWalker(x->cc);
190 } 201 }
191 free(walk); 202 free(walk);
192 return ccy; 203 return ccy;
193 } 204 }
194 205
206 TGValue stateAllocate(NodePtr n,TGValue tg) {
207 TGValue tgv2 = tg;
208 if (n->tokenType == '+') {
209 TGValue tgLeft = stateAllocate(n->left,tg);
210 if (tgLeft.asterisk) {
211 TGValue tgRight = tgLeft;
212 tgRight.asterisk = false;
213 tgRight = stateAllocate(n->right,tgRight);
214 tgRight.asterisk = true;
215 return tgRight;
216 }
217 TGValue tgRight = tgLeft;
218 tgRight.stateBegin = ++tgRight.stateNum;
219 tgRight.state = NEW(State);
220 TGValue tgv1 = stateAllocate(n->right,tgLeft);
221 return tgLeft;
222 } else if (n->tokenType == '|') {
223 TGValue tgv = stateAllocate(n->left,tg);
224 TGValue tgv1 = stateAllocate(n->right,tgv);
225 return tgv1;
226 } else if (n->tokenType == '*') {
227 TGValue tgAstah = tg;
228 tgAstah.stateEnd = tgAstah.stateBegin;
229 tgAstah = stateAllocate(n->left,tgAstah);
230 tgAstah.asterisk = true;
231 return tgAstah;
232 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
233 TGValue tgv = tg;
234 tgv.asterisk = false;
235 BitVector bi = createBitVector(tgv.stateEnd);
236 setState(n->cc,bi);
237 tgv.state->cc = mergeTransition(tgv.state,n->cc);
238 return tgv;
239 } else {
240 // error
241 }
242 return tgv2;
243 }
244
195 TGValue generateTransition(NodePtr n,TGValue tg) { 245 TGValue generateTransition(NodePtr n,TGValue tg) {
196 TGValue tgv2; 246 TGValue tgv2 = tg;
197 if (n->tokenType == '+') { 247 if (n->tokenType == '+') {
198 TGValue tgv = generateTransition(n->right,tg); 248 tgv2.stateBegin = ++tgv.stateNum;
199 if (tgv.asterisk) { 249 TGValue tgLeft = generateTransition(n->right,tgv2);
200 TGValue tgv1 = generateTransition(n->left,tgv); 250 tgLeft.stateEnd = tgv2.stateBegin;
201 return tgv1;
202 }
203 TGValue tgLeft = createTransitionGenerator(tgv);
204 TGValue tgv1 = generateTransition(n->left,tgLeft); 251 TGValue tgv1 = generateTransition(n->left,tgLeft);
205 return tgv; 252 if (tgv1.asterisk) {
253 }
254 return tgv1;
206 } else if (n->tokenType == '|') { 255 } else if (n->tokenType == '|') {
207 TGValue tgv = generateTransition(n->left,tg); 256 TGValue tgv = generateTransition(n->left,tg);
208 TGValue tgv1 = generateTransition(n->right,tgv); 257 TGValue tgv1 = generateTransition(n->right,tgv);
209 tgv.tg = tgv1.tg; 258 tgv.tg = tgv1.tg;
210 tgv.asterisk |= tgv1.asterisk; 259 tgv.asterisk |= tgv1.asterisk;