まだまだバグバグ

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

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

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

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

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

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

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

+ +

+ + + + + + + + +

Cerium 上での正規表現の実装

+ Masataka Kohagura 4th, August , 2015 +

+ +

研究目的

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

+ +

現在していること

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

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

+ +

したこと

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

+ +

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

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

+ +

まだまだバグバグ

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

+    
+% ./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
+
+    
+

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

+ + + +

+    
+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 に持っていない。

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

+ + + + + + + + +

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

したこと

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

まだまだバグバグ

Cerium 上での正規表現の実装

研究目的

現在していること

したこと

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

まだまだバグバグ