Cerium 上での正規表現の実装
|
Masataka Kohagura 2nd, June , 2015
|
研究目的
-
当研究室では並列プログラミングフレームワーク Cerium Task Manager でプログラミングを行っている。
-
-
-
正規表現を有限オートマトンで書いてみる
例題 : (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 を記述する