Mercurial > hg > Applications > Grep
annotate regexParser/subsetConstraction.cc @ 180:d97bcab546e8 pairPro
implement getNext
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 24 Dec 2015 17:56:28 +0900 |
parents | 5e8c6857934c |
children | 3c4db09b8581 |
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> |
117
166136236891
add header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
4 #include "subsetConstraction.h" |
96
b807383bcc43
add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
6 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) { |
146 | 7 CharClassPtr cc = NEW(CharClass); |
154 | 8 return cc; |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
9 } |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
10 |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
11 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
|
12 CharClassPtr cc = NEW(CharClass); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
13 cc->type = 'r'; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
14 cc->cond.range.begin = begin; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
15 cc->cond.range.end = end; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
16 cc->left = left; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
17 cc->right = right; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
18 cc->nextState.bitContainer = state; |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
19 return cc; |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
20 } |
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
21 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
22 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
|
23 CharClassPtr cc1; |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
24 if (cc) { |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
25 cc1 = charClassMerge(cc,mBegin,mEnd,nextState); |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
26 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
27 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
|
28 } |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
29 return cc1; |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
30 } |
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
31 |
152 | 32 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) { |
143 | 33 // 重なっているccの領域を分割する |
34 // 必要ならばnextStateを重ねあわせる | |
35 // 変更があった場合は新しくリストを作って返す | |
152 | 36 if (end < cc->cond.range.begin ) { // 1 |
37 if (cc->left) { | |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
38 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,charClassMerge(cc->left,begin,end,nextState),cc->right); |
152 | 39 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
40 return createCharClassRange(begin,end,nextState.bitContainer,NULL,cc); |
152 | 41 } |
163 | 42 } 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
|
43 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
|
44 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
|
45 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
|
46 cc->nextState.bitContainer | nextState.bitContainer, cc1,cc->right); |
155 | 47 } |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
48 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
|
49 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
|
50 cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
163 | 51 } else if (end < cc->cond.range.end) { // range.begin < end |
155 | 52 if (begin < cc->cond.range.begin) { // 3 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
53 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
|
54 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
|
55 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
152 | 56 } |
155 | 57 if (begin == cc->cond.range.begin) { // 6 |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
58 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
|
59 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc2); |
155 | 60 } |
61 // 9 | |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
62 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
|
63 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
|
64 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc2,cc3); |
155 | 65 } else if (end == cc->cond.range.end) { |
66 if (begin == cc->cond.range.begin) { // 7 | |
168
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,cc->left,cc->right); |
155 | 68 } 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
|
69 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
|
70 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right); |
155 | 71 } |
163 | 72 // 10 cond.range.begin < begin |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
73 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
|
74 return createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,cc2); |
143 | 75 } |
155 | 76 if (begin > cc->cond.range.end ) { // 13 |
77 if (cc->right) { | |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
78 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->left,charClassMerge(cc->right,begin,end,nextState)); |
155 | 79 } else { |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
80 return createCharClassRange(begin,end,nextState.bitContainer,cc,NULL); |
155 | 81 } |
152 | 82 } |
155 | 83 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) { |
163 | 84 if (end > cc->cond.range.end) { // cond.range.end < end |
155 | 85 if (begin == cc->cond.range.begin) { // 8 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
86 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
|
87 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
|
88 cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc1); |
155 | 89 } |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
90 if (begin > cc->cond.range.begin) { // 11 |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
91 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
|
92 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
|
93 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
|
94 } |
155 | 95 } |
163 | 96 // begin != end && end != cc->cond.range.end |
97 if (begin == cc->cond.range.end) { // 12 | |
166
96854eba17e5
implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
163
diff
changeset
|
98 CharClassPtr cc1 = mergeCCTree(cc->right,begin+1,end,nextState); |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
99 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
|
100 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right); |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
101 } |
168
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
102 CharClassPtr cc3 = createCharClassRange(cc->cond.range.begin,cc->cond.range.end-1,cc->nextState.bitContainer,cc->left,NULL); |
6b31d6ef9ba4
impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
103 return createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
155 | 104 } |
156
b5ecfc008bcf
impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
155
diff
changeset
|
105 } 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
|
106 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
|
107 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
|
108 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3); |
152 | 109 } else { |
110 printf("charClassMerge Error : begin %lu end %lu cc->begin %lu cc->end %lu\n", begin,end,cc->cond.range.begin,cc->cond.range.end); | |
111 } | |
112 return cc; | |
143 | 113 } |
114 | |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
115 CharClassWalkerPtr findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) { |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
116 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
|
117 CharClassStackPtr ccs = NEW(CharClassStack); |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
118 ccs->next = walk->stack; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
119 ccs->turn = LEFT; |
171
684363c44d6f
remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
170
diff
changeset
|
120 ccs->cc = next; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
121 walk->stack = ccs; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
122 next = next->left; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
123 } |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
124 walk->next = next; |
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
125 return walk; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
126 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
127 |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
128 CharClassWalkerPtr createCharClassWalker (CharClassPtr next) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
129 CharClassWalkerPtr walk = NEW(CharClassWalker); |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
130 walk->next = NULL; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
131 walk->stack = NULL; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
132 if (!next) return walk; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
133 if (!next->left) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
134 walk->next = next; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
135 return walk; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
136 } |
172
540fc12871d9
remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
171
diff
changeset
|
137 walk = findLeftMost(next,walk); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
138 return walk; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
139 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
140 |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
141 bool hasNext(CharClassWalkerPtr walk) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
142 return walk->next != NULL; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
143 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
144 |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
145 CharClassStackPtr charClassStackPop(CharClassWalkerPtr walk) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
146 if (!walk->stack) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
147 return NULL; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
148 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
149 CharClassStackPtr prev = walk->stack->next; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
150 free(walk->stack); |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
151 walk->stack = prev; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
152 return prev; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
153 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
154 |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
155 CharClassPtr getNext(CharClassWalkerPtr walk) { |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
156 CharClassPtr current = walk->next; |
180
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
157 walk->next = NULL; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
158 while (walk->stack) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
159 while (walk->stack->turn == RIGHT) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
160 if (charClassStackPop(walk) == NULL) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
161 return current; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
162 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
163 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
164 if (walk->stack->turn == LEFT) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
165 walk->next = walk->stack->cc; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
166 walk->stack->tuen == SELF; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
167 return current; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
168 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
169 if (current->right) { |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
170 walk->stack->turn = RIGHT; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
171 walk->next = findLeftMost(current->right,walk); |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
172 return current; |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
173 } |
d97bcab546e8
implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
178
diff
changeset
|
174 charClassStackPop(walk); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
175 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
176 return current; |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
177 } |
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
178 |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
179 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) { |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
180 if (x->cc == NULL) { |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
181 return y; |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
182 } |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
183 CharClassWalkerPtr walk = createCharClassWalker(x->cc); |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
184 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
|
185 BitVector bi; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
186 for (CharClassPtr cc = getNext(walk); hasNext(walk); 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 |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
196 TGValue generateTransition(NodePtr n,TGValue tg) { |
154 | 197 TGValue tgv2; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
198 if (n->tokenType == '+') { |
170 | 199 TGValue tgv = generateTransition(n->right,tg); |
142 | 200 if (tgv.asterisk) { |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
201 TGValue tgv1 = generateTransition(n->left,tgv); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
202 return tgv1; |
142 | 203 } |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
204 TGValue tgLeft = createTransitionGenerator(tgv); |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
205 TGValue tgv1 = generateTransition(n->left,tgLeft); |
142 | 206 return tgv; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
207 } else if (n->tokenType == '|') { |
153 | 208 TGValue tgv = generateTransition(n->left,tg); |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
209 TGValue tgv1 = generateTransition(n->right,tgv); |
170 | 210 tgv.tg = tgv1.tg; |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
168
diff
changeset
|
211 tgv.asterisk |= tgv1.asterisk; |
153 | 212 return tgv; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
213 } else if (n->tokenType == '*') { |
153 | 214 TGValue tgv = generateTransition(n->left,tg); |
215 tgv.asterisk = true; | |
216 return tgv; | |
178
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
217 } else if (n->tokenType == 'c' || n->tokenType == 'a'){ |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
218 TGValue tgv = tg; |
5e8c6857934c
implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
177
diff
changeset
|
219 tgv.ts = mergeTransition(tgv.ts,n->cc); |
153 | 220 return tgv; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
221 } else { |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
222 // error |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
223 } |
154 | 224 return tgv2; |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
225 } |
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
226 |
153 | 227 void printTransitionList(TransitionPtr ts) { |
228 for (;ts;ts = ts->next) { | |
229 printf("\n"); | |
230 } | |
231 } | |
232 | |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
233 TransitionGenerator createTransitionGenerator() { |
144
d8a4922eceae
remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
143
diff
changeset
|
234 TransitionGenerator tg; |
173 | 235 tg.ts = NEW(Transition); |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
236 tg.state = NEW(State); |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
237 tg.transitionList = NEW(Transition); |
176
c092dd0e1ae0
implement appendState() and serchState()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
238 // Init State : 00...00(64bit) |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
239 BitVectorPtr initStateBi = NEW(BitVector); |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
240 bitSet(initStateBi,INIT_STATE_BIT); |
177
8de9a33f6ae5
change createState aug
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
176
diff
changeset
|
241 StatePtr initState = createState(*initStateBi); |
176
c092dd0e1ae0
implement appendState() and serchState()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
242 // Last State : 10...00(64bit) |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
243 BitVectorPtr lastStateBi = NEW(BitVector); |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
244 bitSet(lastStateBi,END_STATE_BIT); |
177
8de9a33f6ae5
change createState aug
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
176
diff
changeset
|
245 StatePtr lastState = createState(*lastStateBi); |
176
c092dd0e1ae0
implement appendState() and serchState()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
246 tg.stateArray = appendState(initState,lastState); |
c092dd0e1ae0
implement appendState() and serchState()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
175
diff
changeset
|
247 tg.stateArrayLast = lastState; |
177
8de9a33f6ae5
change createState aug
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
176
diff
changeset
|
248 tg.currentState = initState; |
175
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
249 tg.nextState = NEW(State); |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
250 return tg; |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
251 } |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
252 |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
253 TransitionGenerator generateTransitionList(NodePtr n) { |
3be0fbcd4b52
implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
173
diff
changeset
|
254 TransitionGenerator tg = createTransitionGenerator(); |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
255 generateTransition(n,tg); |
153 | 256 printTransitionList(tg.ts); |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
257 return tg; |
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
139
diff
changeset
|
258 } |