Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 169:313f1c176328 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement mergeTransition
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Dec 2015 19:06:35 +0900
parents 6b31d6ef9ba4
children de2438d4146a
comparison
equal deleted inserted replaced
168:6b31d6ef9ba4 169:313f1c176328
110 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); 110 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
111 } 111 }
112 return cc; 112 return cc;
113 } 113 }
114 114
115 CharClassWalkerPtr findLeftMost(CharClassPtr next,CharClassWalker walk) {
116 while (next->left) {
117 CharClassStackPtr ts = NEW(CharClassStack);
118 ts->next = walk->stack;
119 ts->left = false;
120 ts->cc = next;
121 walk->stack = ts;
122 next = next->left;
123 }
124 walk->next = next;
125 return walk;
126 }
127
128 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) {
129 CharClassWalkerPtr walk = NEW(CharClassWalker);
130 walk->next = NULL;
131 if (!next) return walk;
132 if (!next->left) {
133 walk->next = next;
134 return walk;
135 }
136 walk->next = findLeftMost(next,walk);
137 return walk;
138 }
139
140 bool hasNext(CharClassWalkerPtr walk) {
141 return walk->next != NULL;
142 }
143
144 CharClassPtr getNext(CharClassWalkerPtr walk) {
145 CharClassPtr current = walk->next;
146 if (ts->left && current->right) {
147 ts->left = true;
148 CharClassPtr next = findLeftMost(current->right,walk);
149 walk->next = next;
150 } else {
151 TransitionPtr tsOld = ts;
152 ts = ts->next;
153 free(tsOld);
154 CharClassPtr ret;
155 if (ts) ret = ts->cc;
156 else ret = NULL;
157 walk->next = ret;
158 }
159 return current;
160 }
161
162 TransitionPtr mergeTransition(TransitionPtr x,TransitionPtr y) {
163 CharClassWalkerPtr walk = createCharClassWalker(x);
164 CharClassPtr ccy = y->condition;
165 for (CharClassPtr cc = getNext(walk); hasNext(walk); cc=getNext(walk)) {
166 unsigned long begin = cc->range.cond.begin;
167 unsigned long end = cc->range.cond.end;
168 BitVectorPtr bi = cc->nextState;
169 ccy = charClassMerge(ccy,begin,end,*bi);
170 }
171 TransitionPtr z = createTransition(ccy);
172 free(walk);
173 return z;
174 }
175
115 TGValue generateTransition(NodePtr n,TransitionGenerator tg) { 176 TGValue generateTransition(NodePtr n,TransitionGenerator tg) {
116 TGValue tgv2; 177 TGValue tgv2;
117 if (n->tokenType == '+') { 178 if (n->tokenType == '+') {
118 TGValue tgv = generateTransition(n->left,tg); 179 TGValue tgv = generateTransition(n->left,tg);
119 if (tgv.asterisk) { 180 if (tgv.asterisk) {
120 TGValue tgv1 = generateTransition(n->right,tg); 181 TGValue tgv1 = generateTransition(n->right,tg);
121 tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer; 182 tgv1.ts = mergeTransition(tgv.ts,tgv1.ts);
122 return tgv; 183 return tgv1;
123 } 184 }
124 TGValue tgv1 = generateTransition(n->right,tg);
125 tgv.ts->nextState = tgv1.ts->nextState;
126 return tgv; 185 return tgv;
127 } else if (n->tokenType == '|') { 186 } else if (n->tokenType == '|') {
128 TGValue tgv = generateTransition(n->left,tg); 187 TGValue tgv = generateTransition(n->left,tg);
129 TGValue tgv1 = generateTransition(n->right,tg); 188 TGValue tgv1 = generateTransition(n->right,tg);
130 tgv.ts = appendTransition(tgv.ts,tgv1.ts); 189 tgv.ts = mergeTransition(tgv.ts,tgv1.ts);
190 tgv.asterisk |= tgv1.asterisk;
131 return tgv; 191 return tgv;
132 } else if (n->tokenType == '*') { 192 } else if (n->tokenType == '*') {
133 TGValue tgv = generateTransition(n->left,tg); 193 TGValue tgv = generateTransition(n->left,tg);
134 tgv.asterisk = true; 194 tgv.asterisk = true;
135 return tgv; 195 return tgv;
136 } else if (n->tokenType == 'c'){ 196 } else if (n->tokenType == 'c'){
197 tgv2.ts = createTransition(n->cc);
137 return tgv2; 198 return tgv2;
138 } else if (n->tokenType == 'a'){ 199 } else if (n->tokenType == 'a'){
139 TGValue tgv; 200 TGValue tgv;
140 tgv.ts = (TransitionPtr)malloc(sizeof(Transition)); 201 tgv.ts = (TransitionPtr)malloc(sizeof(Transition));
141 tgv.ts->condition = n->cc; 202 tgv.ts->condition = n->cc;