Mercurial > hg > Applications > Grep
annotate regexParser/regexParser.cc @ 300:3e78631a6222
remove ragne list
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 03 Feb 2016 13:56:01 +0900 |
parents | 2f3e7bba038e |
children | 1188debbef10 |
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 |
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 * Create a node of regex parse tree. |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 * tokenType |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 * regexPosition(state) |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 * stateTransitionTable |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 */ |
118 | 17 static |
116
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
115
diff
changeset
|
18 NodePtr allocateNode() { |
129
b930be74a16e
remove word.h
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
128
diff
changeset
|
19 NodePtr n = NEW(Node); |
125 | 20 n->cc = NULL; |
260
3f3c9902bb6d
initialize node in allocateNode()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
255
diff
changeset
|
21 n->stateNum = 0; |
3f3c9902bb6d
initialize node in allocateNode()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
255
diff
changeset
|
22 n->nextStateNum = 0; |
3f3c9902bb6d
initialize node in allocateNode()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
255
diff
changeset
|
23 n->state = NULL; |
3f3c9902bb6d
initialize node in allocateNode()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
255
diff
changeset
|
24 n->nextState = NULL; |
125 | 25 n->left = NULL; |
26 n->right = NULL; | |
116
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
115
diff
changeset
|
27 return n; |
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
115
diff
changeset
|
28 } |
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
115
diff
changeset
|
29 |
187
ef798db705e9
remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
30 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
|
31 NodePtr n = allocateNode(); |
125 | 32 n->tokenType = type; |
134 | 33 n->cc = cc; |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
180
diff
changeset
|
34 n->state = NULL; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 n->left = left; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 n->right = right; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 return n; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 } |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
40 CharClassPtr createCharClassWord(RegexInfoPtr ri) { |
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
41 CharClassPtr cc = NEW(CharClass); |
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
42 cc->type = 'a'; |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
190
diff
changeset
|
43 cc->left = NULL; |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
190
diff
changeset
|
44 cc->right = NULL; |
144
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) { |
300 | 78 if (begin>end) { |
79 unsigned long tmp = begin; begin = end; end = tmp; | |
80 } | |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
81 if (cc == NULL) { |
300 | 82 return createCharClassRange(begin,end,0,0,0); |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
83 } |
149
f1880f25fabf
add insertCharClass images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
148
diff
changeset
|
84 if (end < cc->cond.range.begin ) { // 1 |
147 | 85 if (cc->left) { |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
179
diff
changeset
|
86 cc->left = insertCharClass(cc->left,begin,end); |
147 | 87 } else { |
188
109d22faf7b5
remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
187
diff
changeset
|
88 cc->left = createCharClassRange(begin,end,0,0,0); |
147 | 89 } |
152 | 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.begin ) { // 2 |
147 | 92 cc->cond.range.begin = begin; |
150 | 93 return cc; |
149
f1880f25fabf
add insertCharClass images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
148
diff
changeset
|
94 } 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
|
95 if (begin < cc->cond.range.begin) { // 3,4 |
147 | 96 cc->cond.range.begin = begin; |
97 } | |
150 | 98 return cc; |
149
f1880f25fabf
add insertCharClass images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
148
diff
changeset
|
99 } else if (begin > cc->cond.range.end ) { // 13 |
147 | 100 if (cc->right) { |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
179
diff
changeset
|
101 cc->right = insertCharClass(cc->right,begin,end); |
147 | 102 } else { |
188
109d22faf7b5
remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
187
diff
changeset
|
103 cc->right = createCharClassRange(begin,end,0,0,0); |
147 | 104 } |
151 | 105 return cc; |
150 | 106 } |
107 if (cc->right) { | |
151 | 108 CharClassPtr right = cc->right; |
109 begin = cc->cond.range.begin; | |
110 free(cc); | |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
179
diff
changeset
|
111 return insertCharClass(right,begin,end); |
150 | 112 } |
113 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { // 12 | |
151 | 114 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
|
115 } else if (begin < cc->cond.range.begin) { // 5 |
147 | 116 cc->cond.range.begin = begin; |
150 | 117 cc->cond.range.end = end; |
118 } else { | |
119 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 | 120 } |
121 return cc; | |
142 | 122 } |
125 | 123 |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 // <charClass> ::= '['<literal>'-'<literal>']' |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
108
diff
changeset
|
125 static |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 NodePtr charClass(RegexInfoPtr ri) { |
300 | 127 CharClassPtr cc = NULL; |
135 | 128 NodePtr n = createNode(ri,'c',cc,0,0); |
300 | 129 unsigned char begin = *ri->ptr; |
130 unsigned char end = *ri->ptr; | |
130
7925e9abb078
add or flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
129
diff
changeset
|
131 |
135 | 132 for (ri->ptr++; *ri->ptr && *ri->ptr != ']'; ri->ptr++) { |
133 if (*ri->ptr == '-') { | |
300 | 134 end = *(ri->ptr + 1); |
135 cc = insertCharClass(cc, begin, end); | |
135 | 136 ri->ptr++; |
137 continue; | |
300 | 138 } else { |
139 cc = insertCharClass(cc, begin, end); | |
135 | 140 } |
141 if (ri->ptr[0] == 0 || ri->ptr[0] == ']') break; | |
300 | 142 begin = *ri->ptr; |
143 end = *ri->ptr; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 } |
300 | 145 n->cc = insertCharClass(cc, begin, end); |
142 | 146 // TODO literal support |
147 // merge rangeList here | |
135 | 148 if (*ri->ptr) ri->ptr++; |
149 token(ri); | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 return n; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 } |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 // <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
|
154 static |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 NodePtr literal(RegexInfoPtr ri) { |
134 | 156 CharClassPtr cc = createCharClassWord(ri); |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
157 token(ri); |
134 | 158 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
|
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 |
133
ccc673449351
Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
132
diff
changeset
|
162 static |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 void token(RegexInfoPtr ri) { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164 while (ri->ptr[0] != '\0') { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 if (ri->ptr[0] == '('){ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 ri->ptr++; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 ri->tokenType = '('; |
118 | 168 ri->tokenValue = NULL; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 return; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 } else if (ri->ptr[0] == ')') { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 ri->ptr++; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 ri->tokenType = ')'; |
118 | 173 ri->tokenValue = ri->ptr; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 return; |
135 | 175 } else if (ri->ptr[0] == ']') { |
176 ri->ptr++; | |
177 ri->tokenType = ']'; | |
178 ri->tokenValue = ri->ptr; | |
179 return; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 } else if (ri->ptr[0] == '|'){ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181 ri->ptr++; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 ri->tokenType = '|'; |
118 | 183 ri->tokenValue = NULL; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 return; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 } else if (ri->ptr[0] == '*'){ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 ri->ptr++; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187 ri->tokenType = '*'; |
118 | 188 ri->tokenValue = NULL; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
189 return; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 } else if (ri->ptr[0] == '\\'){ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 // need more proccesing |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192 /* |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193 \277 |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 \0xa5 |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 \[ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 \\ |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197 \utf-8 etc... |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 */ |
287 | 199 ri->ptr++; |
200 ri->tokenType = 'a'; | |
201 ri->tokenValue = ri->ptr; | |
202 ri->ptr++; | |
203 return; | |
142 | 204 } else if (ri->ptr[0] == '[') { |
205 ri->ptr++; | |
206 ri->tokenType = 'c'; | |
207 ri->tokenValue = ri->ptr; | |
208 return; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
209 } else { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210 ri->tokenType = 'a'; |
118 | 211 ri->tokenValue = ri->ptr; |
287 | 212 // if (isalnum(ri->ptr[0])) { |
122 | 213 ri->ptr++; |
287 | 214 // } |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 return; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216 } |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
217 } |
134 | 218 ri->tokenType = 0; |
219 ri->tokenValue = NULL; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 return; |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
221 } |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222 |
130
7925e9abb078
add or flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
129
diff
changeset
|
223 // <regexAtom> ::= <literal>|<charClass>|<group> |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
108
diff
changeset
|
224 static |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
225 NodePtr regexAtom(RegexInfoPtr ri) { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
226 |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
227 NodePtr n = NULL; |
124 | 228 if (ri->tokenType == 'c') n = charClass(ri); |
134 | 229 else if (ri->tokenType == 'a') n = literal(ri); |
230 else if (ri->tokenType == '(') { | |
231 n = regex(ri); | |
232 if (ri->tokenType != ')') { | |
233 // error | |
287 | 234 fprintf(stderr,"unclosed ')' before %s \n", ri->ptr); |
235 return createNode(ri,0,0,0,0); | |
134 | 236 } |
237 token(ri); | |
238 } | |
239 if (ri->tokenType == '*') { | |
240 n = createNode(ri,'*',0,n,0); | |
241 token(ri); | |
242 } | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
243 return n; |
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 |
133
ccc673449351
Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
132
diff
changeset
|
246 // <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
|
247 NodePtr regex(RegexInfoPtr ri) { |
134 | 248 token(ri); |
128 | 249 NodePtr n = regexAtom(ri); |
134 | 250 while (ri->tokenType) { |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
251 if (ri->tokenType == '*') { |
134 | 252 n = createNode(ri,'*',0,n,0); |
253 token(ri); | |
254 return n; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
255 } else if (ri->tokenType == '|') { |
134 | 256 n = createNode(ri,'|',0,n,0); |
133
ccc673449351
Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
132
diff
changeset
|
257 NodePtr n1 = regex(ri); |
134 | 258 n->right = n1; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
259 } else if (ri->tokenType == ')') { |
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
260 return n; |
255
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
214
diff
changeset
|
261 } else if (ri->tokenType == ']') { |
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
214
diff
changeset
|
262 // error |
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
214
diff
changeset
|
263 return n; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
264 } else { |
134 | 265 n = createNode(ri,'+',0,n,0); |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
179
diff
changeset
|
266 NodePtr n1 = regexAtom(ri); |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
179
diff
changeset
|
267 n->right = n1; |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
268 } |
134 | 269 } |
270 return n; | |
82
1d9bbf922bb6
add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
271 } |