Mercurial > hg > Applications > Grep
annotate regexParser/subsetConstruction.cc @ 255:61d4d466e64c
fix Makefile
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 Jan 2016 18:20:37 +0900 |
parents | 21b9ba76f91b |
children | 72f3673dd7a5 |
rev | line source |
---|---|
96
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 #include <stdio.h> |
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 #include <stdlib.h> |
101 | 3 #include <ctype.h> |
191
02031fb73af8
remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
190
diff
changeset
|
4 |
02031fb73af8
remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
190
diff
changeset
|
5 #include "regexParser.h" |
216 | 6 #include "subsetConstruction.h" |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
7 #include "node.h" |
191
02031fb73af8
remove somefiles and fix header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
190
diff
changeset
|
8 #include "BitVector.h" |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
9 #include "error.h" |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
10 |
222
c38a7b2dd996
implement exportState function (not correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
220
diff
changeset
|
11 #define SIZE 256 |
c38a7b2dd996
implement exportState function (not correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
220
diff
changeset
|
12 |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
13 CharClassPtr createCharClassRange(unsigned long begin, unsigned long end,unsigned long state, CharClassPtr left, CharClassPtr right) { |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
14 CharClassPtr cc = NEW(CharClass); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
15 cc->type = 'r'; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
16 cc->cond.range.begin = begin; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
17 cc->cond.range.end = end; |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
18 cc->cond.range.next = NULL; |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
19 cc->left = left; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
20 cc->right = right; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
21 cc->nextState.bitContainer = state; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
22 return cc; |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
23 } |
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
24 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
25 CharClassPtr mergeCCTree(CharClassPtr cc,unsigned char mBegin,unsigned char mEnd,BitVector nextState) { |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
26 CharClassPtr cc1; |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
27 if (cc) { |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
28 cc1 = charClassMerge(cc,mBegin,mEnd,nextState); |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
29 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
30 cc1 = createCharClassRange(mBegin,mEnd,nextState.bitContainer,NULL,NULL); |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
31 } |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
32 return cc1; |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
33 } |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
34 |
152 | 35 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { |
143 | 36 // 重なっているccの領域を分割する |
37 // 必要ならばnextStateを重ねあわせる | |
38 // 変更があった場合は新しくリストを作って返す | |
152 | 39 if (end < cc->cond.range.begin ) { // 1 |
40 if (cc->left) { | |
188
109d22faf7b5
remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
187
diff
changeset
|
41 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,nextState.bitContainer,charClassMerge(cc->left,begin,end,nextState),cc->right); |
152 | 42 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
43 return createCharClassRange(begin,end,nextState.bitContainer,NULL,cc); |
152 | 44 } |
163 | 45 } else if (end == cc->cond.range.begin && begin != end ) { // 2 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
46 CharClassPtr cc1 = mergeCCTree(cc->left,begin,end-1,nextState); |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
47 if (cc->cond.range.begin == cc->cond.range.end) { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
48 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end, |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
49 cc->nextState.bitContainer | nextState.bitContainer, cc1,cc->right); |
155 | 50 } |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
51 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
52 return createCharClassRange(cc->cond.range.begin,cc->cond.range.begin, |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
53 cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
163 | 54 } else if (end < cc->cond.range.end) { // range.begin < end |
155 | 55 if (begin < cc->cond.range.begin) { // 3 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
56 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
57 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,cc->left,cc->right); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
58 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
152 | 59 } |
155 | 60 if (begin == cc->cond.range.begin) { // 6 |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
61 CharClassPtr cc2 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
62 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc2); |
155 | 63 } |
64 // 9 | |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
65 CharClassPtr cc2 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
66 CharClassPtr cc3 = createCharClassRange(end+1,cc->cond.range.end,cc->nextState.bitContainer,NULL,cc->right); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
67 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc2,cc3); |
155 | 68 } else if (end == cc->cond.range.end) { |
69 if (begin == cc->cond.range.begin) { // 7 | |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
70 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc->right); |
155 | 71 } else if (begin < cc->cond.range.begin) { // 4 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
72 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
73 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right); |
155 | 74 } |
163 | 75 // 10 cond.range.begin < begin |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
76 CharClassPtr cc2 = createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,NULL,cc->right); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
77 return createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,cc2); |
143 | 78 } |
155 | 79 if (begin > cc->cond.range.end ) { // 13 |
80 if (cc->right) { | |
188
109d22faf7b5
remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
187
diff
changeset
|
81 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,nextState.bitContainer,cc->left,charClassMerge(cc->right,begin,end,nextState)); |
155 | 82 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
83 return createCharClassRange(begin,end,nextState.bitContainer,cc,NULL); |
155 | 84 } |
152 | 85 } |
155 | 86 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { |
163 | 87 if (end > cc->cond.range.end) { // cond.range.end < end |
155 | 88 if (begin == cc->cond.range.begin) { // 8 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
89 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
90 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end, |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
91 cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc1); |
155 | 92 } |
211
bc596e357a52
delete conditional branch in charClassMerge() (pattern 12)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
209
diff
changeset
|
93 if (begin > cc->cond.range.begin) { // 11,12 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
94 CharClassPtr cc1 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
95 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,NULL); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
96 return createCharClassRange(begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc3,cc1); |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
97 } |
155 | 98 } |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
99 } else if (begin < cc->cond.range.begin) { // 5 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
100 CharClassPtr cc1 = mergeCCTree(cc->left,begin,cc->cond.range.begin-1,nextState); |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
101 CharClassPtr cc3 = mergeCCTree(cc->right,cc->cond.range.end+1,end,nextState); |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
102 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
152 | 103 } else { |
104 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); | |
105 } | |
106 return cc; | |
143 | 107 } |
108 | |
181
3c4db09b8581
change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
180
diff
changeset
|
109 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) { |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
110 while (next->left) { |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
111 CharClassStackPtr ccs = NEW(CharClassStack); |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
112 ccs->next = walk->stack; |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
113 ccs->turn = walk->turn; |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
114 walk->turn = LEFT; |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
115 ccs->cc = next; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
116 walk->stack = ccs; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
117 next = next->left; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
118 } |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
119 walk->turn = SELF; |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
120 walk->next = next; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
121 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
122 |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
123 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
124 CharClassWalkerPtr walk = NEW(CharClassWalker); |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
125 walk->next = NULL; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
126 walk->stack = NULL; |
241
87ad91af8a15
turn initialization in charclasswalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
239
diff
changeset
|
127 walk->turn = LEFT; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
128 if (!next) return walk; |
181
3c4db09b8581
change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
180
diff
changeset
|
129 findLeftMost(next,walk); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
130 return walk; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
131 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
132 |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
133 bool hasNext(CharClassWalkerPtr walk) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
134 return walk->next != NULL; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
135 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
136 |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
137 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
138 CharClassStackPtr prev = walk->stack->next; |
209
959f8c00da17
fix charClassStackPop()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
208
diff
changeset
|
139 walk->turn = walk->stack->turn; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
140 free(walk->stack); |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
141 walk->stack = prev; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
142 return prev; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
143 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
144 |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
145 CharClassPtr getNext(CharClassWalkerPtr walk) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
146 CharClassPtr current = walk->next; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
147 walk->next = NULL; |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
148 if (walk->turn == SELF) { |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
149 if (current->right) { |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
150 walk->turn = RIGHT; |
181
3c4db09b8581
change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
180
diff
changeset
|
151 findLeftMost(current->right,walk); |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
152 return current; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
153 } |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
154 } |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
155 while (walk->stack) { |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
156 walk->next = walk->stack->cc; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
157 charClassStackPop(walk); |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
158 if (walk->turn == LEFT) { |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
159 walk->turn = SELF; |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
160 return current; |
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
161 } |
254
21b9ba76f91b
remove warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
250
diff
changeset
|
162 } |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
163 return current; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
164 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
165 |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
166 void setState(CharClassPtr cc, BitVector bi) { |
248
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
167 // if (word case) setNext(bitVector to the word list) |
189 | 168 cc->nextState = bi; |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
169 if (cc->left) { |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
170 setState(cc->left,bi); |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
171 } |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
172 cc->nextState = bi; |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
173 if (cc->right) { |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
174 setState(cc->right,bi); |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
175 } |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
176 } |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
177 |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
178 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) { |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
179 if (x->cc == NULL) { |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
180 return y; |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
181 } |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
182 CharClassWalkerPtr walk = createCharClassWalker(x->cc); |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
183 CharClassPtr ccy = y; |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
184 BitVector bi; |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
185 while (hasNext(walk)) { |
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
186 CharClassPtr cc = getNext(walk); |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
187 unsigned long begin = cc->cond.range.begin; |
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
188 unsigned long end = cc->cond.range.end; |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
189 bi = cc->nextState; |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
190 ccy = charClassMerge(ccy,begin,end,bi); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
191 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
192 free(walk); |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
193 return ccy; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
194 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
195 |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
196 /** |
186
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
197 作成する state を linked list |
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
198 bitvector を index とした配列に BitVectorPtr を格納 |
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
199 state に対応する NodePtr を |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
200 */ |
250
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
201 StatePtr createState(TransitionGeneratorPtr tg,BitVector bi) { |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
202 StatePtr s = NEW(State); |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
203 s->stateNum = tg->totalStateCount++; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
204 s->next = NULL; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
205 tg->stateEnd->next = s; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
206 tg->stateEnd = s; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
207 s->bitState = bi; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
208 s->cc = NULL; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
209 s->node = NULL; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
210 return s; |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
211 } |
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
212 |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
213 StatePtr createState(TGValue tgv,NodePtr n) { |
248
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
214 BitVector bi = createBitVector(tgv.tg->totalStateCount); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
215 StatePtr s = createState(tgv.tg,bi); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
216 n->stateNum = s->stateNum; |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
217 s->node = n; |
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
218 s->bitState = bi; |
239
f5931151d70c
add accept flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
238
diff
changeset
|
219 s->accept = false; |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
220 s->cc = n->cc; |
187
ef798db705e9
remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
186
diff
changeset
|
221 return s; |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
222 } |
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
223 |
185
d25f4f3b4c34
add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
184
diff
changeset
|
224 /** |
215 | 225 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る |
226 前が * でない + は新しく状態を作る | |
228
399380ad95b7
fix generateTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
227
diff
changeset
|
227 * があったら、次の状態はその時の先頭の状態か次の状態が終了状態ならば終了状態との組み合わせになる |
215 | 228 常に先頭の状態を返す |
229 最後が*ならば、それを持ち歩く | |
230 pass 2: | |
231 割り当てられた状態に沿って charclass の行き先を書き換える | |
232 書き換えた charclass を merge する | |
233 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する | |
185
d25f4f3b4c34
add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
184
diff
changeset
|
234 */ |
215 | 235 TGValue generateTransition(NodePtr n,TGValue tgv, int pass) { |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
236 if (n->tokenType == '+') { |
215 | 237 TGValue tgvLeft = tgv; |
238 tgvLeft.endState = n->right->state; | |
241
87ad91af8a15
turn initialization in charclasswalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
239
diff
changeset
|
239 if (pass==2) n->right->state->accept = tgv.endState->accept; |
215 | 240 tgvLeft.asterisk = NULL; |
217 | 241 tgvLeft = generateTransition(n->left,tgvLeft,pass); |
242 TGValue tgvRight = tgv; | |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
243 if (tgvLeft.asterisk) { |
215 | 244 n->right->state = tgv.endState; |
218
d10fa72d8f31
looks like working ...
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
217
diff
changeset
|
245 tgvRight.startState = tgvLeft.asterisk; |
215 | 246 tgvRight = generateTransition(n->right,tgvRight,pass); |
247 tgvLeft.asterisk = tgvRight.asterisk; | |
248 return tgvLeft; | |
142 | 249 } |
215 | 250 tgvRight.asterisk = NULL; |
251 if (pass==1) { | |
252 n->right->state = tgvRight.startState = createState(tgvRight,n->right); | |
253 } else { | |
217 | 254 tgvRight.startState = n->right->state; |
255 tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ; | |
215 | 256 } |
257 tgvRight = generateTransition(n->right,tgvRight,pass); | |
258 tgvLeft.asterisk = tgvRight.asterisk; | |
259 return tgvLeft; | |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
260 } else if (n->tokenType == '|') { |
215 | 261 TGValue tgv1 = generateTransition(n->left,tgv,pass); |
262 TGValue tgv2 = generateTransition(n->right,tgv1,pass); | |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
263 return tgv2; |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
264 } else if (n->tokenType == '*') { |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
265 TGValue tgvAstah = tgv; |
238
5d66672e5029
recover to previous version
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
228
diff
changeset
|
266 tgvAstah.endState = tgvAstah.startState; |
239
f5931151d70c
add accept flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
238
diff
changeset
|
267 if (pass==2) tgvAstah.endState->accept = tgv.endState->accept; |
215 | 268 tgvAstah = generateTransition(n->left,tgvAstah,pass); |
238
5d66672e5029
recover to previous version
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
228
diff
changeset
|
269 tgvAstah.asterisk = tgvAstah.startState; |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
270 return tgvAstah; |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
271 } else if (n->tokenType == 'c' || n->tokenType == 'a'){ |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
272 TGValue tgv1 = tgv; |
215 | 273 if (pass==1) { |
274 n->stateNum = tgv.startState->stateNum; | |
217 | 275 n->state = tgv.startState; |
276 } else { | |
277 int nextState = tgv.endState->stateNum; | |
278 n->nextStateNum = nextState; | |
215 | 279 n->nextState = tgv.endState; |
217 | 280 BitVector bi = createBitVector(nextState); |
244
a3cddb32b87f
change condition in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
243
diff
changeset
|
281 if (n->nextState->accept && n->nextState->node->tokenType == '*') bi = bitSet(bi,1); |
215 | 282 setState(n->cc,bi); |
283 tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc); | |
185
d25f4f3b4c34
add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
184
diff
changeset
|
284 } |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
285 return tgv1; |
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
286 } else { |
182
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
287 return tgv; |
dbe004d03ef0
implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
181
diff
changeset
|
288 } |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
289 } |
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
290 |
186
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
291 TransitionGeneratorPtr createTransitionGenerator() { |
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
292 TransitionGeneratorPtr tg = NEW(TransitionGenerator); |
213
11b6332f0a42
fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
212
diff
changeset
|
293 tg->totalStateCount = 0; |
186
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
294 tg->stack = NULL; |
3e8aae8beba9
fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
185
diff
changeset
|
295 tg->stateArray = NULL; |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
296 tg->stateList = NULL; |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
297 return tg; |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
298 } |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
299 |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
300 TGValue createTGValue() { |
183
7ae0a3070647
implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
182
diff
changeset
|
301 TGValue tgv; |
213
11b6332f0a42
fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
212
diff
changeset
|
302 tgv.startState = NULL; |
11b6332f0a42
fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
212
diff
changeset
|
303 tgv.endState = NULL; |
215 | 304 tgv.asterisk = NULL; |
213
11b6332f0a42
fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
212
diff
changeset
|
305 tgv.tg = createTransitionGenerator(); |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
306 return tgv; |
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
307 } |
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
308 |
216 | 309 TGValue generateTransitionList(NodePtr n) { |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
310 TGValue tgv = createTGValue(); |
255
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
254
diff
changeset
|
311 State dummy; |
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
254
diff
changeset
|
312 tgv.tg->stateEnd = &dummy; |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
313 StatePtr startState = tgv.startState = createState(tgv,n); |
255
61d4d466e64c
fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
254
diff
changeset
|
314 tgv.tg->stateList = startState; |
184
1da1b2eacb84
gather struct
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
183
diff
changeset
|
315 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL); |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
316 StatePtr endState = tgv.endState = createState(tgv,eof); |
239
f5931151d70c
add accept flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
238
diff
changeset
|
317 endState->accept = true; |
217 | 318 tgv.startState = startState; |
319 tgv.endState = endState; | |
215 | 320 tgv = generateTransition(n,tgv,1); |
216 | 321 printTree(n); |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
322 if (tgv.tg->totalStateCount > BITBLOCK) { |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
323 errorMassege("StateMax > BITBLOCK",__LINE__,__FILE__); |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
324 } |
208
2ec95755238e
fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
325 BitVector bi = createBitVector(tgv.tg->totalStateCount); |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
326 tgv.tg->stateArray = (StatePtr*)calloc(bi.bitContainer*2,sizeof(StatePtr*)); |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
327 tgv.tg->stateArray[startState->bitState.bitContainer] = startState; |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
328 tgv.tg->stateArray[endState->bitState.bitContainer] = endState; |
217 | 329 tgv.startState = startState; |
330 tgv.endState = endState; | |
215 | 331 tgv = generateTransition(n,tgv,2); |
216 | 332 return tgv; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
333 } |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
334 |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
335 void printState(StatePtr state) { |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
336 printf("state : %lx\n",state->bitState.bitContainer); |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
337 long nodeNumber = 0; |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
338 if (state->node) { |
201
b8bc24abaf8a
add TODO and fix CharClassWalker
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
198
diff
changeset
|
339 printf("node : %c %lx -> %d\n",state->node->tokenType,state->bitState.bitContainer,state->node->nextStateNum); |
195
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
340 if (state->node->state) |
4fefd80c05f2
change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
192
diff
changeset
|
341 nodeNumber = state->node->state->bitState.bitContainer; |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
342 } |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
343 if (state->cc) { |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
344 printCharacterClass(state->cc,nodeNumber,4); |
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
345 } |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
346 } |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
347 |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
348 void printState(TransitionGeneratorPtr tg) { |
192
ecf70fb215a5
print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
191
diff
changeset
|
349 StatePtr state = tg->stateList; |
190
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
350 for (;state;state = state->next) { |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
351 printState(state); |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
352 putchar('\n'); |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
353 } |
3e8e5780ad4a
change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
189
diff
changeset
|
354 } |
202
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
355 |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
356 /** |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
357 現在のステートに含まれる組み合わせ状態をとってくる |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
358 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
359 生成した状態は stateArray に格納するA |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
360 新しい状態ができなくなったら終了 |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
361 |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
362 charClassMerge の段階で新しい状態をリストに登録したら、charclasswalk をする必要がなくなる |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
363 */ |
248
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
364 void determinize(StatePtr s, TransitionGeneratorPtr tg) { |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
365 BitVector bi = s->bitState; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
366 for (;;) { |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
367 int bitPosition = searchBit(bi); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
368 if (!bitPosition) break; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
369 unsigned long baseNum = 1 << (bitPosition-1); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
370 // printf("bit %lx pos %d baseNum %lx\n",bi.bitContainer,bitPosition,baseNum); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
371 bi.bitContainer ^= baseNum; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
372 if (baseNum==2) continue; // EOF case |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
373 StatePtr base = tg->stateArray[baseNum]; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
374 if (base == NULL) { |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
375 errorMassege("No base state",__LINE__,__FILE__); break; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
376 } |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
377 CharClassPtr merge = mergeTransition(s,base->cc); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
378 s->cc = merge; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
379 } |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
380 } |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
381 |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
382 void subsetConstruction(TransitionGeneratorPtr tg) { |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
383 for (;tg->stateTop;tg->stateTop = tg->stateTop->next) { |
250
e60dd2fa3409
remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
248
diff
changeset
|
384 CharClassWalkerPtr cw = createCharClassWalker(tg->stateTop->cc); |
202
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
385 while (hasNext(cw)) { |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
386 CharClassPtr cc = getNext(cw); |
204
e6e862e92fdc
remove warning and error
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
203
diff
changeset
|
387 BitVector bi = cc->nextState; |
248
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
388 if (tg->stateArray[bi.bitContainer]) continue; // already done |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
389 StatePtr s = createState(tg,bi); |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
390 tg->stateArray[bi.bitContainer] = s; |
2b1fbfb92d54
implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
244
diff
changeset
|
391 determinize(s,tg); |
202
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
392 } |
241
87ad91af8a15
turn initialization in charclasswalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
239
diff
changeset
|
393 free(cw); |
202
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
394 } |
39ca25ed0607
add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
201
diff
changeset
|
395 } |