Mercurial > hg > Applications > Grep

comparison regexParser/regexParser.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/regexParser.cc@1c9e8ba64f6a
children b9e913030a47
comparison
equal deleted inserted replaced
166:96854eba17e5 167:3bf2c6d6d53e
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <ctype.h>
5 #include "regexParser.h"
6
7 static NodePtr charClass(RegexInfoPtr);
8 static void token(RegexInfoPtr);
9 static NodePtr regexAtom(RegexInfoPtr);
10 NodePtr regex(RegexInfoPtr);
11
12 /**
13 * Create a node of regex parse tree.
14 * tokenType
15 * regexPosition(state)
16 * stateTransitionTable
17 */
18
19 static
20 NodePtr allocateNode() {
21 NodePtr n = NEW(Node);
22 n->cc = NULL;
23 n->left = NULL;
24 n->right = NULL;
25 return n;
26 }
27
28 static
29 NodePtr createNode(RegexInfoPtr ri,unsigned char type,CharClassPtr cc, NodePtr left, NodePtr right) {
30 NodePtr n = allocateNode();
31
32 n->tokenType = type;
33 n->cc = cc;
34 n->left = left;
35 n->right = right;
36 n->nodeNumber = ri->nodeNumber;
37 ri->nodeNumber++;
38
39 return n;
40 }
41
42 CharClassPtr createCharClassRange(unsigned long begin, unsigned long end, CharClassPtr left, CharClassPtr right) {
43 CharClassPtr cc = NEW(CharClass);
44 cc->type = 'r';
45 cc->cond.range.begin = begin;
46 cc->cond.range.end = end;
47 cc->left = left;
48 cc->right = right;
49 cc->nextState.bitContainer = 0;
50 return cc;
51 }
52
53 CharClassPtr createCharClassWord(RegexInfoPtr ri) {
54 CharClassPtr cc = NEW(CharClass);
55 cc->type = 'a';
56 cc->cond.w.word = ri->tokenValue;
57 cc->cond.w.length = ri->ptr - ri->tokenValue;
58 cc->nextState.bitContainer = 0;
59 return cc;
60 }
61
62 /*
63 cond.range.begin cond.range.end
64 |----------------|
65 1.b---e
66 2.b------e
67 3.b------------e
68 4.b-----------------------e
69 5.b----------------------------e
70
71 |----------------|
72 6. b---------e
73 7. b----------------e
74 8. b---------------------e
75
76 |----------------|
77 9. b-----e
78 10. b--------e
79 11. b-------------e
80
81 |----------------|
82 12. b-----e
83
84 |----------------|
85 13. b--e
86
87 */
88 CharClassPtr insertCharClass(CharClassPtr cc, unsigned long begin, unsigned long end) {
89
90 if (end < cc->cond.range.begin ) { // 1
91 if (cc->left) {
92 cc->left = insertCharClass(cc->left,begin,end);
93 } else {
94 cc->left = createCharClassRange(begin,end,0,0);
95 }
96 return cc;
97 } else if (end == cc->cond.range.begin ) { // 2
98 cc->cond.range.begin = begin;
99 return cc;
100 } else if (end <= cc->cond.range.end) { // 3,4,6,7,9,10
101 if (begin < cc->cond.range.begin) { // 3,4
102 cc->cond.range.begin = begin;
103 }
104 return cc;
105 } else if (begin > cc->cond.range.end ) { // 13
106 if (cc->right) {
107 cc->right = insertCharClass(cc->right,begin,end);
108 } else {
109 cc->right = createCharClassRange(begin,end,0,0);
110 }
111 return cc;
112 }
113 if (cc->right) {
114 CharClassPtr right = cc->right;
115 begin = cc->cond.range.begin;
116 free(cc);
117 return insertCharClass(right,begin,end);
118 }
119 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12
120 if (end > cc->cond.range.end) cc->cond.range.end = end; // 11,8
121 } else if (begin < cc->cond.range.begin) { // 5
122 cc->cond.range.begin = begin;
123 cc->cond.range.end = end;
124 } else {
125 printf("insertCharClass Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end);
126 }
127 return cc;
128 }
129
130 // <charClass> ::= '['<literal>'-'<literal>']'
131 static
132 NodePtr charClass(RegexInfoPtr ri) {
133 CharClassPtr cc = NEW(CharClass);
134 NodePtr n = createNode(ri,'c',cc,0,0);
135 cc->type = 'r';
136 cc->nextState.bitContainer = 0;
137 cc->left = NULL;
138 cc->right = NULL;
139 RangeListPtr rangeList = &cc->cond.range;
140 rangeList->begin = *ri->ptr;
141 rangeList->end = *ri->ptr;
142 rangeList->next = NULL;
143
144 for (ri->ptr++; *ri->ptr && *ri->ptr != ']'; ri->ptr++) {
145 if (*ri->ptr == '-') {
146 rangeList->end = *(ri->ptr + 1);
147 ri->ptr++;
148 continue;
149 }
150 if (ri->ptr[0] == 0 || ri->ptr[0] == ']') break;
151 rangeList->next = NEW(RangeList);
152 rangeList = rangeList->next;
153 rangeList->begin = *ri->ptr;
154 rangeList->end = *ri->ptr;
155 rangeList->next = NULL;
156 }
157
158 RangeListPtr r = cc->cond.range.next;
159 cc->cond.range.next = 0;
160 for (; r; r = r->next) {
161 cc = insertCharClass(cc, r->begin, r->end);
162 }
163
164 n->cc = cc;
165 // TODO literal support
166 // merge rangeList here
167 if (*ri->ptr) ri->ptr++;
168 token(ri);
169 return n;
170 }
171
172 // <literal> ::= [a-z][A-Z][0-9]
173 static
174 NodePtr literal(RegexInfoPtr ri) {
175 CharClassPtr cc = createCharClassWord(ri);
176 token(ri);
177 NodePtr n = createNode(ri,'a',cc,0,0);
178 return n;
179 }
180
181 static
182 void token(RegexInfoPtr ri) {
183 while (ri->ptr[0] != '\0') {
184 if (ri->ptr[0] == '('){
185 ri->ptr++;
186 ri->tokenType = '(';
187 ri->tokenValue = NULL;
188 return;
189 } else if (ri->ptr[0] == ')') {
190 ri->ptr++;
191 ri->tokenType = ')';
192 ri->tokenValue = ri->ptr;
193 return;
194 } else if (ri->ptr[0] == ']') {
195 ri->ptr++;
196 ri->tokenType = ']';
197 ri->tokenValue = ri->ptr;
198 return;
199 } else if (ri->ptr[0] == '|'){
200 ri->ptr++;
201 ri->tokenType = '|';
202 ri->tokenValue = NULL;
203 return;
204 } else if (ri->ptr[0] == '*'){
205 ri->ptr++;
206 ri->tokenType = '*';
207 ri->tokenValue = NULL;
208 return;
209 } else if (ri->ptr[0] == '\\'){
210 // need more proccesing
211 /*
212 \277
213 \0xa5
214 \[
215 \\
216 \utf-8 etc...
217 */
218 } else if (ri->ptr[0] == '[') {
219 ri->ptr++;
220 ri->tokenType = 'c';
221 ri->tokenValue = ri->ptr;
222 return;
223 } else {
224 ri->tokenType = 'a';
225 ri->tokenValue = ri->ptr;
226 if (isalnum(ri->ptr[0])) {
227 ri->ptr++;
228 }
229 return;
230 }
231 }
232 ri->tokenType = 0;
233 ri->tokenValue = NULL;
234 return;
235 }
236
237 // <regexAtom> ::= <literal>|<charClass>|<group>
238 static
239 NodePtr regexAtom(RegexInfoPtr ri) {
240
241 NodePtr n = NULL;
242 if (ri->tokenType == 'c') n = charClass(ri);
243 else if (ri->tokenType == 'a') n = literal(ri);
244 else if (ri->tokenType == '(') {
245 n = regex(ri);
246 if (ri->tokenType != ')') {
247 // error
248 }
249 token(ri);
250 }
251 if (ri->tokenType == '*') {
252 n = createNode(ri,'*',0,n,0);
253 token(ri);
254 }
255
256 return n;
257 }
258
259 // <regex> ::= <regexAtom> | <regexAtom>'*'<regex> | <regexAtom>'|'<regex> | <regexAtom><regexAtom>'*' | <regexAtom><regex>
260 NodePtr regex(RegexInfoPtr ri) {
261 token(ri);
262 NodePtr n = regexAtom(ri);
263 while (ri->tokenType) {
264 if (ri->tokenType == '*') {
265 n = createNode(ri,'*',0,n,0);
266 token(ri);
267 return n;
268 } else if (ri->tokenType == '|') {
269 n = createNode(ri,'|',0,n,0);
270 NodePtr n1 = regex(ri);
271 n->right = n1;
272 } else if (ri->tokenType == ')') {
273 return n;
274 } else {
275 n = createNode(ri,'+',0,n,0);
276 NodePtr n1 = regexAtom(ri);
277 n->right = n1;
278 }
279 }
280 return n;
281 }