Mercurial > hg > Applications > Grep
annotate regexParser/TODO @ 296:28c695dac305
Todo
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 02 Feb 2016 11:50:33 +0900 |
parents | 0c663f46954d |
children | 63213964502a |
rev | line source |
---|---|
295 | 1 Tue Feb 2 11:21:14 JST 2016 |
2 | |
3 あとは word の処理だけだ | |
4 charClassMergeをなおさないといけない | |
5 merge で文字列のlistにする | |
6 長いものは分割 | |
7 部分文字列は分解する? | |
8 | |
296 | 9 Cerirum 側で、最初のmatchが表示されてない |
10 | |
293
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
11 Tue Feb 2 09:55:40 JST 2016 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
12 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
13 % ./regexParser -subst -regex '(a|b)*a(a|b)(a|b)' |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
14 ---Print Node---- |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
15 a(1)->(1) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
16 | |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
17 b(1)->(1) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
18 * |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
19 + |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
20 a(4)->(4) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
21 + |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
22 a(4)->(8) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
23 | |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
24 b(4)->(8) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
25 + |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
26 a(8)->(2) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
27 | |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
28 b(8)->(2) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
29 ----------------- |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
30 state : 1 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
31 node : + 1 -> 1 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
32 [a-a] (5) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
33 [b-b] (1) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
34 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
35 state : 2* |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
36 node : e 2 -> 1 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
37 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
38 state : 4 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
39 node : | 4 -> 1 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
40 [a-a] (8) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
41 [b-b] (8) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
42 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
43 state : 8 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
44 node : | 8 -> 1 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
45 [a-a] (2) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
46 [b-b] (2) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
47 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
48 state : 5 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
49 [a-a] (1) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
50 [b-b] (9) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
51 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
52 state : 9 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
53 [a-a] (1) <---- 間違い 2 とmergeしているはずだが... |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
54 [b-b] (3) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
55 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
56 state : 3* |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
57 [a-a] (5) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
58 [b-b] (1) |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
59 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
60 やはり charClassMerge のbugだった。 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
61 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
62 createCharClassRangeで、同じものだったら新しく作らないってのがあると良い |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
63 charClassMerg が同じものを返す場合があるってことね |
295 | 64 同じレンジで同じ状態のものだけなので、それほどあるとは思えないが。 |
293
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
65 |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
291
diff
changeset
|
66 |
289 | 67 Mon Feb 1 01:51:10 JST 2016 kono |
68 | |
69 非決定性がある時の maxmum match がよろしくない | |
70 これ以上拡張できないという終了条件の実現は? | |
71 | |
72 ./regexParser -ts -subset -regex '(a|b)*a' -file ahoaho.txt | |
73 | |
74 で、bの後にaが来なくなると、bの手前までをacceptする | |
75 | |
291 | 76 subset construction はいじらない方針で。 |
77 | |
78 | |
79 state : 1 | |
80 node : + 1 -> 1 | |
81 [a-a] (3) | |
82 [b-b] (1) | |
83 | |
84 state : 2* | |
85 node : e 2 -> 1 | |
86 | |
87 state : 3* | |
88 [a-a] (3) | |
89 [b-b] (1) | |
90 | |
91 * はaccept state。 | |
92 | |
93 [a-a] (3) で stateMatch で良いが、maxmum だと match している間は stateMatch はしない。 | |
94 現状は、*の付いているstateで、条件にmatchしない時に stateMatch してる。 | |
95 これだと state 3 で b で satete 1 に行ってしまい、b 以降に a がない時に失敗する。b に行く前の state 3 で stateMatchするべき。 | |
96 | |
97 matchする可能性がなくなったところで、前の部分でmatchさせる必要がある。 | |
98 * match してなければ、match top をupdate | |
99 * match している間は直前matchをupdate | |
100 * match fail したところで、直前のmatch があれば、それを返す | |
101 という感じか? | |
102 | |
103 minimum match は | |
104 * match してなければ、match top をupdate | |
105 * match したところで、直前のmatch があれば、それを返す | |
106 か? | |
107 | |
108 ソース生成を CbC に対応させる。(でないと動かないらしい) | |
289 | 109 |
110 | |
284 | 111 Sun Jan 31 20:37:49 JST 2016 masa |
289 | 112 並列処理時のバグ Ok |
113 (mili|have) のsubset construction のミス Ok | |
114 tSearch の segv Ok | |
284 | 115 |
289 | 116 '(main|int) ' .. Ok |
117 '(main|int)\(' .. Ok | |
287 | 118 |
119 とかが動かない。 | |
120 | |
291 | 121 start state に accept flag が立っていると''にmatchしてしまう。それは別に生成する。 |
122 | |
221 | 123 Sat Jan 2 15:29:16 JST 2016 kono |
124 | |
125 stateよりもstate transitionの方が大きいので、subset contructionで CharClassWalkするのは良くない。 | |
126 mergeTransition した時に、state listに新しいものを接続してやれば、CharClassWalkの必要はない。 | |
127 その時に、stateArray には入れないでおく。sateArrayは処理済みなので。 | |
128 | |
129 EOF stateには cc がないので特別扱いする必要がある。 | |
130 | |
131 Tue Dec 29 17:55:17 JST 2015 kono | |
215 | 132 |
133 Todo は上に付け加えていく。 | |
134 | |
135 abc*d + | |
136 / \ | |
137 + d | |
138 / \ | |
139 + * | |
140 / \ | | |
141 a b c | |
142 | |
143 Parserを書き換えて、 | |
144 | |
145 abc*d + | |
146 / \ | |
147 a + | |
148 / \ | |
149 b + | |
150 / \ | |
151 * d | |
152 | | |
153 c | |
154 | |
155 とすることもできる。たぶん、こっちの方が良い。でも、 | |
156 ((ab)(c*))d | |
157 と書いても良いはずで、しかも、これは abc*d とおなじになるので解決になってない。 | |
158 | |
159 sub treeは、最初の状態を返す必要がある。そうでないと、 | |
160 (ab*|bc*) | |
161 とかがうまく動かない。 | |
162 | |
163 最後が*で終わっている時には、次の式と重ねる必要がある。なので、 | |
164 最後の*があれば、それを持ち歩く | |
165 方式が良いと思います。 | |
166 | |
167 stateAllocateをgenerateTransitionは1 passにすると stateArrayの大きさを徐々に増やす必要がある。 | |
168 少なくともループは一つにした方が間違いが少ないだろう。 | |
169 | |
210
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
170 |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
171 2015年 12月27日 日曜日 19時31分03秒 JST |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
172 例題 特定の IP のアクセス数をカウントする |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
173 concordance |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
174 regex をつかった条件付き concordance |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
175 regex をつかった条件付き wordcount |
e8aa8a1ea749
add benchmark TODO
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
204
diff
changeset
|
176 これを行う perl スクリプトと比較 |
215 | 177 |
178 2015年 12月26日 土曜日 18時07分00秒 JST | |
179 TODO CharClassWalker の routine test を作成する | |
180 TODO CharClassMerge の routine test を作成する | |
181 TODO searchBit の routine test を作成する | |
182 TODO subsetConstraction の routine test を作成する | |
183 |