Mercurial > hg > Applications > Grep

annotate regexParser/subsetConstruction.cc @ 324:879dc5d1cb6a default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author mir3636
date Fri, 27 May 2016 21:21:09 +0900
parents 1188debbef10
children
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"
308
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
8 #include "bitVector.h"
1188debbef10 separate CharClass
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 300
diff changeset
9 #include "CharClass.h"
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
10 #include "error.h"
168
6b31d6ef9ba4 impl createCharClassRange()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 167
diff changeset
11
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
12 /**
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
13 作成する state を linked list
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
14 bitvector を index とした配列に BitVectorPtr を格納
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
15 state に対応する NodePtr を
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
16 */
250
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
17 StatePtr createState(TransitionGeneratorPtr tg,BitVector bi) {
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
18 StatePtr s = NEW(State);
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
19 s->stateNum = tg->totalStateCount++;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
20 s->next = NULL;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
21 tg->stateEnd->next = s;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
22 tg->stateEnd = s;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
23 s->bitState = bi;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
24 s->cc = NULL;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
25 s->node = NULL;
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 271
diff changeset
26 s->tState = NULL;
250
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
27 return s;
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
28 }
e60dd2fa3409 remove SCValue
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
29
195
4fefd80c05f2 change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 192
diff changeset
30 StatePtr createState(TGValue tgv,NodePtr n) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
31 BitVector bi = createBitVector(tgv.tg->totalStateCount);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
32 StatePtr s = createState(tgv.tg,bi);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
33 n->stateNum = s->stateNum;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
34 s->node = n;
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
35 s->bitState = bi;
239
f5931151d70c add accept flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 238
diff changeset
36 s->accept = false;
208
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
37 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
38 return s;
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
39 }
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
40
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
41 /**
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
42 pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
43 前が * でない + は新しく状態を作る
228
399380ad95b7 fix generateTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 227
diff changeset
44 * があったら、次の状態はその時の先頭の状態か次の状態が終了状態ならば終了状態との組み合わせになる
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
45 常に先頭の状態を返す
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
46 最後が*ならば、それを持ち歩く
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
47 pass 2:
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
48 割り当てられた状態に沿って charclass の行き先を書き換える
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
49 書き換えた charclass を merge する
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
50 前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
185
d25f4f3b4c34 add comment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 184
diff changeset
51 */
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
52 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
53 if (n->tokenType == '+') {
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
54 TGValue tgvLeft = tgv;
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
55 tgvLeft.endState = n->right->state;
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
56 tgvLeft.asterisk = NULL;
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
57 tgvLeft = generateTransition(n->left,tgvLeft,pass);
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
58 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
59 if (tgvLeft.asterisk) {
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
60 n->right->state = tgv.endState;
218
d10fa72d8f31 looks like working ...
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 217
diff changeset
61 tgvRight.startState = tgvLeft.asterisk;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
62 tgvRight = generateTransition(n->right,tgvRight,pass);
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
63 tgvLeft.asterisk = tgvRight.asterisk;
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
64 return tgvLeft;
142
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
65 }
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
66 tgvRight.asterisk = NULL;
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
67 if (pass==1) {
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
68 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
69 } else {
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
70 tgvRight.startState = n->right->state;
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
71 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
72 }
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
73 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
74 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
75 tgvLeft.asterisk = tgvRight.asterisk;
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
76 return tgvLeft;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
77 } else if (n->tokenType == '|') {
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
78 TGValue tgv1 = generateTransition(n->left,tgv,pass);
287
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 277
diff changeset
79 tgv1.endState = tgv.endState;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
80 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
81 return tgv2;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
82 } 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
83 TGValue tgvAstah = tgv;
238
5d66672e5029 recover to previous version
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 228
diff changeset
84 tgvAstah.endState = tgvAstah.startState;
239
f5931151d70c add accept flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 238
diff changeset
85 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
86 tgvAstah = generateTransition(n->left,tgvAstah,pass);
238
5d66672e5029 recover to previous version
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 228
diff changeset
87 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
88 return tgvAstah;
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
89 } 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
90 TGValue tgv1 = tgv;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
91 if (pass==1) {
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
92 n->stateNum = tgv.startState->stateNum;
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
93 n->state = tgv.startState;
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
94 } else {
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
95 int nextState = tgv.endState->stateNum;
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
96 n->nextStateNum = nextState;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
97 n->nextState = tgv.endState;
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
98 BitVector bi = createBitVector(nextState);
257
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 256
diff changeset
99 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
100 setState(n->cc,bi);
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
101 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
102 }
195
4fefd80c05f2 change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 192
diff changeset
103 return tgv1;
4fefd80c05f2 change variable name (TGValue tg -> TGValue tgv)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 192
diff changeset
104 } else {
182
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
105 return tgv;
dbe004d03ef0 implement stateAllocate()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 181
diff changeset
106 }
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
107 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
108
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
109 TransitionGeneratorPtr createTransitionGenerator() {
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
110 TransitionGeneratorPtr tg = NEW(TransitionGenerator);
213
11b6332f0a42 fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 212
diff changeset
111 tg->totalStateCount = 0;
186
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
112 tg->stack = NULL;
3e8aae8beba9 fix createTransitionGenerator()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 185
diff changeset
113 tg->stateArray = NULL;
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
114 tg->stateList = NULL;
175
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
115 return tg;
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
116 }
3be0fbcd4b52 implement createTransitionGenerator
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 173
diff changeset
117
208
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
118 TGValue createTGValue() {
183
7ae0a3070647 implement generateTransitionList
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 182
diff changeset
119 TGValue tgv;
213
11b6332f0a42 fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 212
diff changeset
120 tgv.startState = NULL;
11b6332f0a42 fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 212
diff changeset
121 tgv.endState = NULL;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
122 tgv.asterisk = NULL;
213
11b6332f0a42 fix tgv.tg->totalStateCount increment
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 212
diff changeset
123 tgv.tg = createTransitionGenerator();
208
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
124 return tgv;
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
125 }
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
126
216
4852bfa85db4 spell fix
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 215
diff changeset
127 TGValue generateTransitionList(NodePtr n) {
208
2ec95755238e fix mergetest
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 204
diff changeset
128 TGValue tgv = createTGValue();
271
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
129 TransitionGeneratorPtr tg = tgv.tg;
255
61d4d466e64c fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
130 State dummy;
271
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
131 tg->stateEnd = &dummy;
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
132 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
133 tg->stateList = startState;
184
1da1b2eacb84 gather struct
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 183
diff changeset
134 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
135 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
136 endState->accept = true;
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
137 tgv.startState = startState;
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
138 tgv.endState = endState;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
139 tgv = generateTransition(n,tgv,1);
216
4852bfa85db4 spell fix
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 215
diff changeset
140 printTree(n);
271
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
141 if (tg->totalStateCount > BITBLOCK) {
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
142 errorMassege("StateMax > BITBLOCK",__LINE__,__FILE__);
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
143 }
271
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
144 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
145 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
146 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
147 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
148 tg->totalBasicState = tg->totalStateCount;
217
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
149 tgv.startState = startState;
a9e3512120e2 NFA generation end
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 216
diff changeset
150 tgv.endState = endState;
215
63e9224c7b2b try to fix asterisk
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 214
diff changeset
151 tgv = generateTransition(n,tgv,2);
216
4852bfa85db4 spell fix
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 215
diff changeset
152 return tgv;
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
153 }
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
154
271
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
155 void createAnyState(TransitionGeneratorPtr tg) {
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
156 BitVector anyBi = createBitVector(tg->totalBasicState);
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 271
diff changeset
157 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
158 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
159 tg->anyState = createState(tg,anyBi);
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 271
diff changeset
160 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
161 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
162 }
6640b0d5bf13 remove anystate processing in sequential seqrch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
163
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
164 void printState(StatePtr state) {
289
20ed7536784f add test file
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 287
diff changeset
165 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
166 long nodeNumber = 0;
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
167 if (state->node) {
289
20ed7536784f add test file
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 287
diff changeset
168 BitVector bi = createBitVector(state->node->nextStateNum);
20ed7536784f add test file
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 287
diff changeset
169 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
170 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
171 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
172 }
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
173 if (state->cc) {
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
174 printCharacterClass(state->cc,nodeNumber,4);
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
175 }
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
176 }
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
177
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
178 void printState(TransitionGeneratorPtr tg) {
192
ecf70fb215a5 print charclass
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 191
diff changeset
179 StatePtr state = tg->stateList;
190
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
180 for (;state;state = state->next) {
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
181 printState(state);
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
182 putchar('\n');
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
183 }
3e8e5780ad4a change node::State to State
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 189
diff changeset
184 }
202
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
185
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
186 /**
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
187 現在のステートに含まれる組み合わせ状態をとってくる
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
188 組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
189 生成した状態は stateArray に格納するA
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
190 新しい状態ができなくなったら終了
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
191
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
192 charClassMerge の段階で新しい状態をリストに登録したら、charclasswalk をする必要がなくなる
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
193 */
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
194 void determinize(StatePtr s, TransitionGeneratorPtr tg) {
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
195 BitVector bi = s->bitState;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
196 for (;;) {
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
197 int bitPosition = searchBit(bi);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
198 if (!bitPosition) break;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
199 unsigned long baseNum = 1 << (bitPosition-1);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
200 // 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
201 bi.bitContainer ^= baseNum;
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
202 if (baseNum==2) {
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
203 s->accept = true;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
204 continue; // EOF case
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
205 }
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
206 StatePtr base = tg->stateArray[baseNum];
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
207 if (base == NULL) {
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 271
diff changeset
208 fprintf(stderr,"baseNum=%lx ",baseNum);
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
209 errorMassege("No base state",__LINE__,__FILE__); break;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
210 }
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
211 CharClassPtr merge = mergeTransition(s,base->cc);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
212 s->cc = merge;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
213 }
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
214 }
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
215
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
216 void subsetConstruction(TransitionGeneratorPtr tg) {
256
72f3673dd7a5 remove tg->stateTop
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 255
diff changeset
217 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
218 CharClassWalkerPtr cw = createCharClassWalker(st->cc);
202
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
219 while (hasNext(cw)) {
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
220 CharClassPtr cc = getNext(cw);
204
e6e862e92fdc remove warning and error
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 203
diff changeset
221 BitVector bi = cc->nextState;
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
222 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
223 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
224 determinize(s,tg);
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 244
diff changeset
225 tg->stateArray[bi.bitContainer] = s;
202
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
226 }
241
87ad91af8a15 turn initialization in charclasswalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 239
diff changeset
227 free(cw);
202
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
228 }
39ca25ed0607 add searchBit test
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 201
diff changeset
229 }