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