Mercurial > hg > Applications > Grep
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; |