Mercurial > hg > Applications > Grep

annotate regexParser/subsetConstruction.cc @ 300:3e78631a6222

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