研究目的

正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は 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 に持っていない。

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