# HG changeset patch # User Masataka Kohagura # Date 1445940029 -32400 # Node ID e8fd8c7d22c2d9d0ee1c0ca761f709d91f1e0ea2 # Parent 18bbb4a5db60cd239ebbbdab91dcab56bf4e5452 add 1027.html diff -r 18bbb4a5db60 -r e8fd8c7d22c2 2015/0929.html --- a/2015/0929.html Tue Sep 29 19:47:31 2015 +0900 +++ b/2015/0929.html Tue Oct 27 19:00:29 2015 +0900 @@ -120,8 +120,8 @@

現在していること

-

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

-

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

+

ソース分割

+

subset constraction と bitVector

@@ -155,55 +155,6 @@
-
-

まだまだバグバグ

-

同じ正規表現でも生成される木が違う(正しくもない)

- 
-    
-% ./regexParser -regex "(a*b)"
-    +
-        b
- +
-    *
-        a
-
-% ./regexParser -regex "a*b"
-    b
- +
-    *
-        a
-
-    理想
-
-    b
- *
-    a
-    
-
- -

'|'の挙動が正しくない

- 
-    
-% ./regexParser -regex "(a|b)c"
-
-        c
-    +
-        b
- |
-    a
-
-
-    理想
-    c
- +
-        b
-    |
-        a
-
-    
-
-

'(' ')'まわりと '|' まわりの処理が正しくない

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

Cerium 上での正規表現の実装

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

研究目的

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

現在していること

+

ソース分割

+

subset constraction と bitVector

+
+ +
+

したこと

+

二分木を表示するための関数を作成

+
+ +
+

正規表現で生成された二分木を表示

+ 
+    
+% ./regexParser -regex "test"
+
+            t
+        +
+            s
+    +
+        e
+ +
+    t
+
+% ./regexParser -regex "a*bc"
+
+        c
+    +
+        b
+ +
+    *
+        a
+    
+
+
+ + + + + + + + + + + + + +
+ +