研究目的

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

今日までにしたこと

• とりあえず動くところまではプログラムを直した(若干バグが)

• 正規表現木のノード内に一文字のアルファベットだけしか入らなかったが、word をいれれるようにした(一文字のアルファベットも word と見なしている)

• word が含まれているノードだけにノード番号をつけていたが、syntax が含まれているノードにもノード番号をつけた

実装すること

正規表現の parser tree から subset constraction に変換するプログラムを書く

• Parser Tree のノードに word や CharClass を挿れる(今は一文字のみ)

CharClass を Binary Tree で表現する

• 正規表現に Character Class (例 : [a-z])が含まれている場合、Character Class を二分木で表現する

Character Class が正規表現内に複数含まれる場合

複数の Character Class の範囲が重複する場合

• Character Class Tree を Merge し再構築する

直しているところ

• '|' が複数含まれていると正しく正規表現木が構築されない
• ab*c の正規表現の場合、ab という Node になる
• '()'や'*'直後の単語の先頭文字が Node に含まれない

    
(現状)%  ./regexParser -regex "(ac|b|aa)*ac" 
regex : (ac|b|aa)*ac
---Print Node----
        c(6)
    +(7)
        *(5)
                aa(3)
            |(4)
                b(2)
 |(8)
    ac(1)
-----------------
    
    

    
(理想)%  ./regexParser -regex "(ac|b|aa)*ac" 
regex : (ac|b|aa)*ac
---Print Node----
    ac(7)
+(8)
    *(6)
                aa(3)
            |(4)
                b(2)
         |(5)
            ac(1)
-----------------
    
    

どのようなリスト構造か

    
typedef struct bitVector {
    int arrayNum;
    unsigned long *bitContainer;
}BitVector,*BitVectorPtr;

typedef struct bitVectorList {
    bitVectorList *self;
    BitVectorPtr bi;
    bitVectorList* initBvl;
    bitVectorList* next[256];
}BitVectorList, *BitVectorListPtr;
    
    

• BitVectorPtr->bitContainer に状態を格納する。
• BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している