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