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