# HG changeset patch # User Masataka Kohagura # Date 1436862204 -32400 # Node ID 39f9309334f916a5171eb15bfd3aeb675c738a57 # Parent 0bec56f5c23f932aef13987d502f18d4ac3c9e9b add 0714.html diff -r 0bec56f5c23f -r 39f9309334f9 2015/0609.html --- a/2015/0609.html Tue Jun 09 17:13:09 2015 +0900 +++ b/2015/0609.html Tue Jul 14 17:23:24 2015 +0900 @@ -102,7 +102,7 @@
- Masataka Kohagura 2nd, June , 2015 + Masataka Kohagura 9th, June , 2015
@@ -111,35 +111,51 @@

研究目的

- -
- - -
-

正規表現を有限オートマトンで書いてみる

- 例題 : (a|aa|aaa)*b - - 非決定性オートマトンから subset Constraction -
-

正規表現を有限オートマトンで書いてみる

+

今週のしたこと

+ +
+ +
+

BNF記法で正規表現の文法規則を表記してみる

+ + + BNF 記法での表現どおりにプログラムを落とし込めば、再帰下降法でうまく実装できそう? +
+ + + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

+
+
+ Masataka Kohagura 9th, June , 2015 +
+
+ +
+

研究目的

+ 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。
+ この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。
+ コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。
+ 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 + +
+ +
+

今週のしたこと

+
    +
  • + 正規表現の parser を再帰下降法で実装(まだ途中) +
    • +
+
+ +
+

BNF記法で正規表現の文法規則を表記してみる

+
    +
  • +<literal> ::= [a-z][A-Z][0-9] +
    • +
  • +<characterClass> ::= '['<literal>'-'<literal>']' +
    • +
  • +<string> :: = <literal> | <literal>* +
    • +
  • +<or> ::= '('<regex>'|'<regex>')' +
    • +
  • +<*> ::= <regex>'*' +
    • +
  • +<regex> ::= <literal>|<string>|<or> +
    • +
+ + BNF 記法での表現どおりにプログラムを落とし込めば、再帰下降法でうまく実装できそう? +
+ + + + + +
+ +