Cerium 上での正規表現の実装
Masataka Kohagura 4th, August , 2015

研究目的

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

現在していること

正規表現の Subset Constraction の状態の集合を生成するために正規表現の Parser を記述している

正規表現の Parser によって生成された Tree が

どのように正規表現の Parser によって生成された木を表示させるか

    
% ./regexParser -regex abc

  #-c
#-+
# #-b
+
#-a

% ./regexParser -regex (a*|bc)d


#-d
+
#   #-c
# #-+
# # #-b
#-|
  #
  #-*
    #-a

string なのか literal なのか判断しないで createNode をしてる

問題点

正規表現 a*b の tree 構造(本当はこうなってほしい)


正規表現 a*b の tree 構造(現状)


これからすること