# Date 1439285742 -32400 # Node ID 8a5b151da414eef33991147742b6bb3961705fec # Parent 1b92285a767a2bc60844f259c5f4b30e6c275c9f add 0804.html diff -r 1b92285a767a -r 8a5b151da414 2015/0804.html --- a/2015/0804.html Tue Aug 04 19:45:57 2015 +0900 +++ b/2015/0804.html Tue Aug 11 18:35:42 2015 +0900 @@ -102,7 +102,7 @@

- Masataka Kohagura 14th, July , 2015 + Masataka Kohagura 4th, August , 2015

@@ -119,61 +119,39 @@

したこと

- characterClass 以外を実装 - +

現在していること

正規表現の Subset Constraction の状態の集合を生成するために正規表現の Parser を記述している

正規表現の Parser によって生成された Tree が

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

-<literal> ::= [a-z][A-Z][0-9] -
-<characterClass> ::= '['<literal>'-'<literal>']' -
-<string> :: = <literal> | <literal>* -
-<or> ::= '('<regex>'|'<regex>')' -
-<*> ::= <regex>'*' -
-<regex> ::= <literal>|<string>|<or> -

-<or> が '|' とグループ化の '('')' とまだ分解できるので、<or> を <or> と <group> に分割 -

どのように正規表現の Parser によって生成された木を表示させるか

+    
+% ./regexParser -regex abc
+
+  #-c
+#-+
+# #-b
++
+#-a
+
+% ./regexParser -regex (a*|bc)d
+
 
-  
-    BNF記法で正規表現の文法規則を表記してみる(修正後)
-    
-    
-<literal> ::= [a-z][A-Z][0-9]
-    
-    
-<characterClass> ::= '['<literal>'-'<literal>']'
-    
-    
-<string> :: = <literal> | <literal>*
-    
-    
-<group> ::= '('<regex>')' <- 追加
-    
-    
-<or> ::= <regex>'|'<regex> <- 修正
-    
-    
-<*> ::= <regex>'*'
-    
-    
-<regex> ::= <literal>|<string>|<or>
-    
-    
+#-d
++
+#   #-c
+# #-+
+# # #-b
+#-|
+  #
+  #-*
+    #-a
+
+    
+

string なのか literal なのか判断しないで createNode をしてる

@@ -185,12 +163,7 @@

問題点

正規表現 a tree 構造(現状)

原因は string()

- +

これからすること

diff -r 1b92285a767a -r 8a5b151da414 2015/0811.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2015/0811.html Tue Aug 11 18:35:42 2015 +0900 @@ -0,0 +1,250 @@ + + + + + seminar + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + + + + + + +

Cerium 上での正規表現の実装

+ Masataka Kohagura 4th, August , 2015 +

+ +

研究目的

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

+ +

現在していること

正規表現の Subset Constraction の状態の集合を生成するために正規表現の Parser を記述している

正規表現の Parser によって生成された Tree が

+ +

どのように正規表現の Parser によって生成された木を表示させるか

+    
+% ./regexParser -regex abc
+
+  #-c
+#-+
+# #-b
++
+#-a
+
+% ./regexParser -regex (a*|bc)d
+
+
+#-d
++
+#   #-c
+# #-+
+# # #-b
+#-|
+  #
+  #-*
+    #-a
+
+    
+

string なのか literal なのか判断しないで createNode をしてる

+ +

問題点

正規表現 a*b の tree 構造(本当はこうなってほしい)

+ +

正規表現 a*b の tree 構造(現状)

+ + + +

これからすること

+ tree 生成の修正 +
+ tree を見やすく表示 +

+ + + + + + +

+ +