annotate slides/2018/08/07/memo.txt @ 50:ccfc78c23c66

auto-Update generated slides by script
author Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Tue, 18 Sep 2018 20:20:07 +0900
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
50
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 - Perl6
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 - とりあえず言語部分から始めるのが良さそう
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 - 正規表現部分はRakudoを呼び出す
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 - ベンチマークのコードでどんなものを吐き出しているかを調べる
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 - CbC事態はアセンブラなのでアセンブラ的に使って問題ない
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 - ベンチマークに沿ってとりあえず作っていく
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 - 正規表現の差が出る--> Linearに終わってない
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 - ボーアムーア検索
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 - アスタリスクが直前にあると配列があるので厳しい
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 - Cで実装するとほとんど大丈夫
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 - 正規表現に突入すると組み合わせ爆発が発生する可能性
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 - 高速に実現できるパターンマッチング言語の開発?
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 - 長い部分を正規表現で探してそこ以外をボーアムーア検索で探す
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 - 1Mbのマッチングは? 画像ファイルに入れる可能性がありそう… !?
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 - 実際に正規表現は非決定的オートマトンに変換されてから処理される
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 - NFAはバックトラックしながら探すので結構大変そう
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 - マッチングする行が短ければ文字列の前後に分けて処理をする
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 - ボトムアップに数字とのパターンを作るという説もありそう
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 - 行の最長を指定する
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 - ボトムアップアプローチ
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 (CbCのgrep)
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 - 文字列を見つけるまでボーアムーアサーチを行い,見つかったら前後にregular expression searchを行う
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 - 逆方向サーチを実装するという手
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 - CbCは再帰下降が使えない(再起できない)のでDFAに乗せる方針でいけば最適化できそう
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 - 最終的にCbCで文法解析をするか...!?
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
ccfc78c23c66 auto-Update generated slides by script
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 - 文法をCbCでどうやって書くかを開発したい