Cerium 上での正規表現の実装

Masataka Kohagura

研究目的

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

今日までにしたこと

実装すること

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

CharClass を Binary Tree で表現する


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

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



直しているところ

どのようなリスト構造か

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

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