Mercurial > hg > Applications > Grep

comparison regexParser/subsetConstraction.cc @ 167:3bf2c6d6d53e pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
move regexparser dir
author masa
date Sat, 19 Dec 2015 15:38:45 +0900
parents c/regexParser/subsetConstraction.cc@96854eba17e5
children 6b31d6ef9ba4
comparison
equal deleted inserted replaced
166:96854eba17e5 167:3bf2c6d6d53e
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <ctype.h>
4 #include "subsetConstraction.h"
5
6 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) {
7 CharClassPtr cc = NEW(CharClass);
8 return cc;
9 }
10
11 CharClassPtr mergeCCTree(CharClassPtr cc,unsigned char mBegin,unsigned char mEnd,BitVector nextState) {
12 CharClassPtr cc1;
13 if (cc) {
14 cc1 = charClassMerge(cc,mBegin,mEnd,nextState);
15 } else {
16 cc1 = createCharClassRange(mBegin,mEnd,NULL,NULL);
17 cc1->nextState = nextState;
18 }
19 return cc1;
20 }
21
22 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
23 // 重なっているccの領域を分割する
24 // 必要ならばnextStateを重ねあわせる
25 // 変更があった場合は新しくリストを作って返す
26 if (end < cc->cond.range.begin ) { // 1
27 if (cc->left) {
28 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,charClassMerge(cc->left,begin,end,nextState),cc->right);
29 } else {
30 CharClassPtr cc1 = createCharClassRange(begin,end,NULL,cc);
31 cc1->nextState = nextState;
32 return cc1;
33 }
34 } else if (end == cc->cond.range.begin && begin != end ) { // 2
35 CharClassPtr cc1 = mergeCCTree(cc->left,begin,end-1,nextState);
36 if (cc->cond.range.begin == cc->cond.range.end) {
37 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right);
38 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
39 return cc2;
40 }
41 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->left,cc->right);
42 cc3->nextState = cc->nextState;
43 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.begin,cc1,cc3);
44 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
45 return cc2;
46 } else if (end < cc->cond.range.end) { // range.begin < end
47 if (begin < cc->cond.range.begin) { // 3
48 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
49 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->left,cc->right);
50 cc3->nextState = cc->nextState;
51 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,end,cc1,cc3);
52 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
53 return cc2;
54 }
55 if (begin == cc->cond.range.begin) { // 6
56 CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right);
57 cc2->nextState = cc->nextState;
58 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc2);
59 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
60 return cc1;
61 }
62 // 9
63 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL);
64 cc2->nextState = cc->nextState;
65 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,NULL,cc->right);
66 cc3->nextState = cc->nextState;
67 CharClassPtr cc1 = createCharClassRange(begin,end,cc2,cc3);
68 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
69 return cc1;
70 } else if (end == cc->cond.range.end) {
71 if (begin == cc->cond.range.begin) { // 7
72 CharClassPtr cc1 = createCharClassRange(begin,end,cc->left,cc->right);
73 cc1->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
74 return cc1;
75 } else if (begin < cc->cond.range.begin) { // 4
76 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
77 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,end,cc1,cc->right);
78 cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
79 return cc3;
80 }
81 // 10 cond.range.begin < begin
82 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,NULL,cc->right);
83 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
84 CharClassPtr cc1 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,cc2);
85 cc1->nextState = cc->nextState;
86 return cc1;
87 }
88 if (begin > cc->cond.range.end ) { // 13
89 if (cc->right) {
90 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,charClassMerge(cc->right,begin,end,nextState));
91 } else {
92 CharClassPtr cc1 = createCharClassRange(begin,end,cc,NULL);
93 cc1->nextState = nextState;
94 return cc1;
95 }
96 }
97 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
98 if (end > cc->cond.range.end) { // cond.range.end < end
99 if (begin == cc->cond.range.begin) { // 8
100 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
101 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,cc1);
102 cc3->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
103 return cc3;
104 }
105 if (begin > cc->cond.range.begin) { // 11
106 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
107 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->left,NULL);
108 cc3->nextState = cc->nextState;
109 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc3,cc1);
110 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
111 return cc2;
112 }
113 }
114 // begin != end && end != cc->cond.range.end
115 if (begin == cc->cond.range.end) { // 12
116 CharClassPtr cc1 = mergeCCTree(cc->right,begin+1,end,nextState);
117 if (cc->cond.range.begin == cc->cond.range.end) {
118 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc->right);
119 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
120 return cc2;
121 }
122 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end-1,cc->left,NULL);
123 cc3->nextState = cc->nextState;
124 CharClassPtr cc2 = createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc1,cc3);
125 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
126 return cc2;
127 }
128 } else if (begin < cc->cond.range.begin) { // 5
129 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState);
130 CharClassPtr cc3 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState);
131 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc1,cc3);
132 cc2->nextState.bitContainer = cc->nextState.bitContainer | nextState.bitContainer;
133 return cc2;
134 } else {
135 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
136 }
137 return cc;
138 }
139
140 TGValue generateTransition(NodePtr n,TransitionGenerator tg) {
141 TGValue tgv2;
142 if (n->tokenType == '+') {
143 TGValue tgv = generateTransition(n->left,tg);
144 if (tgv.asterisk) {
145 TGValue tgv1 = generateTransition(n->right,tg);
146 tgv.ts->nextState->bitContainer |= tgv1.ts->nextState->bitContainer;
147 return tgv;
148 }
149 TGValue tgv1 = generateTransition(n->right,tg);
150 tgv.ts->nextState = tgv1.ts->nextState;
151 return tgv;
152 } else if (n->tokenType == '|') {
153 TGValue tgv = generateTransition(n->left,tg);
154 TGValue tgv1 = generateTransition(n->right,tg);
155 tgv.ts = appendTransition(tgv.ts,tgv1.ts);
156 return tgv;
157 } else if (n->tokenType == '*') {
158 TGValue tgv = generateTransition(n->left,tg);
159 tgv.asterisk = true;
160 return tgv;
161 } else if (n->tokenType == 'c'){
162 return tgv2;
163 } else if (n->tokenType == 'a'){
164 TGValue tgv;
165 tgv.ts = (TransitionPtr)malloc(sizeof(Transition));
166 tgv.ts->condition = n->cc;
167 tgv.ts->nextState = (BitVectorPtr)malloc(sizeof(BitVector));
168 bitSet(tgv.ts->nextState,n->nodeNumber);
169 tg.ts = appendTransition(tg.ts,tgv.ts);
170 return tgv;
171 } else {
172 // error
173 }
174 return tgv2;
175 }
176
177 void printTransitionList(TransitionPtr ts) {
178 for (;ts;ts = ts->next) {
179 printf("\n");
180 }
181 }
182
183 TransitionGenerator generateTransitionList(NodePtr n) {
184 TransitionGenerator tg;
185 tg.ts = (TransitionPtr)malloc(sizeof(Transition));
186 generateTransition(n,tg);
187 printTransitionList(tg.ts);
188 return tg;
189 }