研究目的

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

今週のしたこと

• 正規表現の parser を再帰下降法で実装(まだ途中)

BNF記法で正規表現の文法規則を表記してみる

• <literal> ::= [a-z][A-Z][0-9]
• <characterClass> ::= '['<literal>'-'<literal>']'
• <string> :: = <literal> | <literal>*
• <or> ::= '('<regex>'|'<regex>')'
• <*> ::= <regex>'*'
• <regex> ::= <literal>|<string>|<or>

BNF 記法での表現どおりにプログラムを落とし込めば、再帰下降法でうまく実装できそう?