# HG changeset patch # User Masataka Kohagura # Date 1440496451 -32400 # Node ID 60a678b8539cf55b612dd85a9a3380a2d36443f8 # Parent 8a5b151da414eef33991147742b6bb3961705fec add 0825.html diff -r 8a5b151da414 -r 60a678b8539c 2015/0811.html --- a/2015/0811.html Tue Aug 11 18:35:42 2015 +0900 +++ b/2015/0811.html Tue Aug 25 18:54:11 2015 +0900 @@ -121,7 +121,7 @@

現在していること

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

-

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

+

正規表現の二分木が正しく構築できているかどうか確認するために、Tree を表示させるためのプログラムを書いている。

@@ -129,31 +129,30 @@ 
     
 % ./regexParser -regex abc
-
-  #-c
-#-+
-# #-b
+    c
+  +
+    b
 +
-#-a
+  a
 
 % ./regexParser -regex (a*|bc)d
 
 
-#-d
+    d
+  +
+    c
 +
-#   #-c
-# #-+
-# # #-b
-#-|
-  #
-  #-*
-    #-a
+    b
+  |
+    *
+      a

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

+ + +
+ 
+    
+typedef struct node {
+    unsigned char type;
+    union value {
+        charClass *cc;
+        unsigned char character;
+    } Value, *ValuePtr;
+    struct node *self;
+    struct node *left;
+    struct node *right;
+} Node, *NodePtr;
+    
+
+

木を表示する際に、右ノード、親ノード、左ノードの順番で表示する。

+

右ノードから親ノードに移動する際、ノードを遡るための情報が node に持っていない。

+

親ノードの情報も持たせたほうが良さそう

+
-
-

これからすること

- -
- + + + + + + + + + + + + + + + + + + + + + +
+ +
+ + + + + + + + +
+

Cerium 上での正規表現の実装

+
+
+ Masataka Kohagura 4th, August , 2015 +
+
+ +
+

研究目的

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

現在していること

+

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

+

正規表現の二分木が正しく構築できているかどうか確認するために、Tree を表示させるためのプログラムを書いている。

+
+ +
+

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

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

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

+
+ + + +
+ 
+    
+typedef struct node {
+    unsigned char type;
+    union value {
+        charClass *cc;
+        unsigned char character;
+    } Value, *ValuePtr;
+    struct node *self;
+    struct node *left;
+    struct node *right;
+} Node, *NodePtr;
+    
+
+

木を表示する際に、右ノード、親ノード、左ノードの順番で表示する。

+

右ノードから親ノードに移動する際、ノードを遡るための情報が node に持っていない。

+

親ノードの情報も持たせたほうが良さそう

+
+ + + + + + + + +
+ +