Cerium 上での正規表現の実装

Masataka Kohagura 2nd, June , 2015

研究目的

正規表現を有限オートマトンで書いてみる

例題 : (a|aa|aaa)*b 非決定性オートマトンから subset Constraction

正規表現を有限オートマトンで書いてみる

例題 : ab(ab)+ テキストが abab の途中で分割される場合を考える 分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする)

状態を bit列で表現

状態をビットで表現するため、bitSet を実装した。
    

typedef struct bitInfo {
    int arrayNum;
    unsigned long *bitContainer;
}BitInfo,*BitInfoPtr;

void bitSet(BitInfoPtr bi, int bitSetPosition) {

    unsigned long tmp = 1;
    int arrayPosition = 0;

    arrayPosition = bitSetPosition / 64;
    bitSetPosition = bitSetPosition % 64;

    tmp = tmp << (63 - bitSetPosition);
    bi->bitContainer[arrayPosition] = bi->bitContainer[arrayPosition] | tmp;
}

    
    

次にやること

bitVector を生成するため、正規表現の parser を記述する