Cerium 上での正規表現の実装
|
Masataka Kohagura 14th, July , 2015
|
研究目的
正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。
この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。
コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。
本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。
したこと
characterClass 以外を実装
BNF記法で正規表現の文法規則を表記してみる
-
<literal> ::= [a-z][A-Z][0-9]
-
<characterClass> ::= '['<literal>'-'<literal>']'
-
<string> :: = <literal> | <literal>*
-
<or> ::= '('<regex>'|'<regex>')'
-
<*> ::= <regex>'*'
-
<regex> ::= <literal>|<string>|<or>
<or> が '|' とグループ化の '('')' とまだ分解できるので、<or> を <or> と <group> に分割
BNF記法で正規表現の文法規則を表記してみる(修正後)
-
<literal> ::= [a-z][A-Z][0-9]
-
<characterClass> ::= '['<literal>'-'<literal>']'
-
<string> :: = <literal> | <literal>*
-
<group> ::= '('<regex>')' <- 追加
-
<or> ::= <regex>'|'<regex> <- 修正
-
<*> ::= <regex>'*'
-
<regex> ::= <literal>|<string>|<or>
問題点
正規表現 a*b の tree 構造(本当はこうなってほしい)
正規表現 a*b の tree 構造(現状)
問題点
正規表現 a tree 構造(現状)
原因は string()
NodePtr string() {
char c = *ptr;
NodePtr n = NULL;
if (isLiteral(c)) {
n = createNode(0,literal(),string());
} else {
n = createNode(0,0,0);
}
return n;
}
string なのか literal なのか判断しないで createNode をしてる