Mercurial > hg > Applications > Grep

annotate regexParser/subsetConstraction.cc @ 190:3e8e5780ad4a pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change node::State to State
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Fri, 25 Dec 2015 15:30:52 +0900
parents fccf7941ecc2
children 02031fb73af8
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>
117
166136236891 add header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
4 #include "subsetConstraction.h"
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
5 #include "node.h"
96
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
144
d8a4922eceae remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 143
diff changeset
7 CharClassPtr createCharClassWord(unsigned char *w, CharClassPtr cc1, CharClassPtr cc2) {
146
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 144
diff changeset
8 CharClassPtr cc = NEW(CharClass);
154
1fad21fd6028 remove errors and warnings
masa
parents: 153
diff changeset
9 return cc;
171
684363c44d6f remove some warning and error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 170
diff changeset
10 }
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
11
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
12 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
13 CharClassPtr cc = NEW(CharClass);
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
14 cc->type = 'r';
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
15 cc->cond.range.begin = begin;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
16 cc->cond.range.end = end;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
17 cc->left = left;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
18 cc->right = right;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
19 cc->nextState.bitContainer = state;
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
20 return cc;
144
d8a4922eceae remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 143
diff changeset
21 }
d8a4922eceae remove some errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 143
diff changeset
22
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
23 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
24 CharClassPtr cc1;
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
25 if (cc) {
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
26 cc1 = charClassMerge(cc,mBegin,mEnd,nextState);
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
27 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
28 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
29 }
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
30 return cc1;
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
31 }
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
32
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
33 CharClassPtr charClassMerge(CharClassPtr cc,unsigned long begin, unsigned long end, BitVector nextState) {
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
34 // 重なっているccの領域を分割する
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
35 // 必要ならばnextStateを重ねあわせる
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
36 // 変更があった場合は新しくリストを作って返す
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
37 if (end < cc->cond.range.begin ) { // 1
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
38 if (cc->left) {
188
109d22faf7b5 remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 187
diff changeset
39 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
40 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
41 return createCharClassRange(begin,end,nextState.bitContainer,NULL,cc);
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
42 }
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
43 } 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
44 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
45 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
46 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
47 cc->nextState.bitContainer | nextState.bitContainer, cc1,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
48 }
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
49 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
50 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
51 cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
52 } else if (end < cc->cond.range.end) { // range.begin < end
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
53 if (begin < cc->cond.range.begin) { // 3
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
54 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
55 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
56 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
57 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
58 if (begin == cc->cond.range.begin) { // 6
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
59 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
60 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc2);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
61 }
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
62 // 9
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
63 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
64 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
65 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc2,cc3);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
66 } else if (end == cc->cond.range.end) {
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
67 if (begin == cc->cond.range.begin) { // 7
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
68 return createCharClassRange(begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
69 } 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
70 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
71 return createCharClassRange(cc->cond.range.begin,end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc->right);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
72 }
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
73 // 10 cond.range.begin < begin
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
74 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
75 return createCharClassRange(cc->cond.range.begin,begin-1,cc->nextState.bitContainer,cc->left,cc2);
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
76 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
77 if (begin > cc->cond.range.end ) { // 13
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
78 if (cc->right) {
188
109d22faf7b5 remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 187
diff changeset
79 return createCharClassRange(cc->cond.range.begin,cc->cond.range.end,nextState.bitContainer,cc->left,charClassMerge(cc->right,begin,end,nextState));
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
80 } else {
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
81 return createCharClassRange(begin,end,nextState.bitContainer,cc,NULL);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
82 }
152
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
83 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
84 if (begin >= cc->cond.range.begin && begin <= cc->cond.range.end) {
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
85 if (end > cc->cond.range.end) { // cond.range.end < end
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
86 if (begin == cc->cond.range.begin) { // 8
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
87 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
88 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
89 cc->nextState.bitContainer | nextState.bitContainer,cc->left,cc1);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
90 }
156
b5ecfc008bcf impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 155
diff changeset
91 if (begin > cc->cond.range.begin) { // 11
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
92 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
93 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
94 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
95 }
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
96 }
163
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
97 // begin != end && end != cc->cond.range.end
f0a347cd9c6a fix subsetconstraction.cc
masa
parents: 157
diff changeset
98 if (begin == cc->cond.range.end) { // 12
166
96854eba17e5 implement mergeCCTree()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 163
diff changeset
99 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
100 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
101 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
102 }
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
103 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
104 return createCharClassRange(cc->cond.range.end,cc->cond.range.end,cc->nextState.bitContainer | nextState.bitContainer,cc1,cc3);
155
6cd0141bed6c impl charClassMerge
masa
parents: 154
diff changeset
105 }
156
b5ecfc008bcf impl charClassMerge(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 155
diff changeset
106 } 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
107 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
108 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
109 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
110 } else {
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
111 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
112 }
1c9e8ba64f6a add implement charclassMerge (not working)
masa
parents: 148
diff changeset
113 return cc;
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
114 }
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
115
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
116 void findLeftMost(CharClassPtr next,CharClassWalkerPtr walk) {
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
117 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
118 CharClassStackPtr ccs = NEW(CharClassStack);
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
119 ccs->next = walk->stack;
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
120 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
121 ccs->cc = next;
180
d97bcab546e8 implement getNext
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 178
diff changeset
122 walk->stack = ccs;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
123 next = next->left;
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
124 }
172
540fc12871d9 remove some warnings and errors (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 171
diff changeset
125 walk->next = next;
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 }
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
137 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;
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
166 walk->stack->turn = SELF;
180
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;
181
3c4db09b8581 change return value findLeftMost()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 180
diff changeset
171 findLeftMost(current->right,walk);
180
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
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
179 void setState(CharClassPtr cc, BitVector bi) {
189
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 188
diff changeset
180 cc->nextState = bi;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
181 if (cc->left) {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
182 setState(cc->left,bi);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
183 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
184 cc->nextState = bi;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
185 if (cc->right) {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
186 setState(cc->right,bi);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
187 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
188 }
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
189
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
190 CharClassPtr mergeTransition(StatePtr x,CharClassPtr y) {
178
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
191 if (x->cc == NULL) {
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
192 return y;
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
193 }
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
194 CharClassWalkerPtr walk = createCharClassWalker(x->cc);
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
195 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
196 BitVector bi;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
197 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
198 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
199 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
200 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
201 ccy = charClassMerge(ccy,begin,end,bi);
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
202 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
203 free(walk);
178
5e8c6857934c implement charClassMerge
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 177
diff changeset
204 return ccy;
169
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
205 }
313f1c176328 implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 168
diff changeset
206
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
207 /**
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
208 作成する state を linked list
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
209 bitvector を index とした配列に BitVectorPtr を格納
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
210 state に対応する NodePtr を
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
211 */
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
212 StatePtr createState(TGValue tg,NodePtr n) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
213 StatePtr s = NEW(State);
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
214 s->next = tg.tg->currentState;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
215 tg.tg->currentState = s;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
216 s->node = n;
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
217 BitVector bi = createBitVector(n->stateNum);
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
218 s->bitState = bi;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
219 s->cc = NULL;
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
220 return s;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
221 }
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
222
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
223 /**
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
224 正規表現に必要な状態を探して、それぞれに番号を割り振る
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
225 前が * でない + は新しく状態を作る
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
226 * があったら、次の状態はその時の先頭の状態になる
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
227 */
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
228 TGValue stateAllocate(NodePtr n,TGValue tg) {
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
229 if (n->tokenType == '+') {
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
230 TGValue tgLeft = stateAllocate(n->left,tg);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
231 if (tgLeft.asterisk) {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
232 TGValue tgRight = tgLeft;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
233 tgRight.asterisk = false;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
234 tgRight = stateAllocate(n->right,tgRight);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
235 tgRight.asterisk = true;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
236 return tgRight;
142
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
237 }
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
238 TGValue tgRight = tgLeft;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
239 tgRight.stateBegin = ++tgRight.stateNum;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
240 n->right->state = createState(tgRight,n->right);
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
241 return tgLeft;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
242 } else if (n->tokenType == '|') {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
243 TGValue tgv = stateAllocate(n->left,tg);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
244 TGValue tgv1 = stateAllocate(n->right,tgv);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
245 return tgv1;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
246 } else if (n->tokenType == '*') {
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
247 TGValue tgAstah = tg;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
248 tgAstah.stateEnd = tgAstah.stateBegin;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
249 tgAstah = stateAllocate(n->left,tgAstah);
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
250 tgAstah.asterisk = true;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
251 return tgAstah;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
252 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
253 TGValue tgv = tg;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
254 tgv.asterisk = false;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
255 n->stateNum = tg.stateBegin;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
256 n->nextStateNum = tg.stateEnd;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
257 return tgv;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
258 } else {
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
259 return tg;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
260 }
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
261 }
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
262
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
263 /**
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
264 割り当てられた状態に沿って charclass の行き先を書き換える
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
265 書き換えた charclass を merge する
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
266 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
267 */
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
268 TGValue generateTransition(NodePtr n,TGValue tg) {
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
269 if (n->tokenType == '+') {
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
270 if (tg.asterisk) {
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
271 TGValue tgRight = tg;
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
272 tgRight.asterisk = false;
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
273 tgRight = generateTransition(n->right,tgRight);
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
274 tgRight.asterisk = true;
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
275 return tgRight;
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
276 }
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
277 StatePtr left = tg.tgState;
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
278 tg.tgState = n->left->state;
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
279 // tg.tg->stateArray[tg.tgState->bitState.bitContainer] = tg.tgState;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
280 TGValue tgLeft = generateTransition(n->left,tg);
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
281 tg.tgState = left;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
282 TGValue tgv1 = generateTransition(n->right,tgLeft);
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
283 return tgv1;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
284 } else if (n->tokenType == '|') {
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
285 TGValue tgv = generateTransition(n->left,tg);
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
286 TGValue tgv1 = generateTransition(n->right,tgv);
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
287 return tgv1;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
288 } else if (n->tokenType == '*') {
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
289 TGValue tgAstah = generateTransition(n->left,tg);
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
290 tgAstah.asterisk = true;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
291 return tgAstah;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
292 } else if (n->tokenType == 'c' || n->tokenType == 'a'){
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
293 TGValue tgv = tg;
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
294 tgv.asterisk = false;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
295 BitVector bi = createBitVector(n->nextStateNum);
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
296 setState(n->cc,bi);
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
297 tgv.tgState->cc = mergeTransition(tgv.tgState,n->cc);
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
298 return tgv;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
299 } else {
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
300 return tg;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
301 }
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
302 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
303
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
304 TransitionGeneratorPtr createTransitionGenerator() {
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
305 TransitionGeneratorPtr tg = NEW(TransitionGenerator);
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
306 tg->stateMax = 0;
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
307 tg->stack = NULL;
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
308 tg->state = NEW(State);
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
309 tg->stateArray = NULL;
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
310 tg->currentState = NULL;
175
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
311 return tg;
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
312 }
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
313
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
314 TransitionGeneratorPtr generateTransitionList(NodePtr n) {
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
315 TransitionGeneratorPtr tg = createTransitionGenerator();
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
316 TGValue tgv;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
317 tgv.asterisk = false;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
318 tgv.tg = tg;
188
109d22faf7b5 remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 187
diff changeset
319 tgv.tg->startState = createState(tgv,n);
184
1da1b2eacb84 gather struct
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 183
diff changeset
320 NodePtr eof = createNode(NULL,'e',NULL,NULL,NULL);
188
109d22faf7b5 remove errors and warnings
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 187
diff changeset
321 tgv.tg->endState = createState(tgv,eof);
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
322 tgv.stateBegin = 0;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
323 tgv.stateEnd = 1;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
324 stateAllocate(n,tgv);
187
ef798db705e9 remove some warnings and errors(not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 186
diff changeset
325 tgv.tg->stateMax = tg->stateMax;
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
326 BitVector bi = createBitVector(tg->stateMax);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
327 tgv.tg->stateArray = (StatePtr)calloc(bi.bitContainer*2,sizeof(StatePtr));
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
328 generateTransition(n,tgv);
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
329 return tg;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
330 }
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
331
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
332 void printState(StatePtr state) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
333 printf("state : %lx\n",state->bitState.bitContainer);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
334 long nodeNumber = 0;
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
335 if (state->node) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
336 printf("node : %c %d -> %d\n",state->node->tokenType,state->node->stateNum,state->node->nextStateNum);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
337 nodeNumber = state->node->stateNum;
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
338 }
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
339 printCharacterClass(state->cc,nodeNumber,4);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
340 }
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
341
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
342 void printState(TransitionGeneratorPtr tg) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
343 StatePtr state = tg->currentState;
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
344 for (;state;state = state->next) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
345 printState(state);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
346 putchar('\n');
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
347 }
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
348 }