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