Cerium での正規表現の実装
Masataka Kohagura 12th, May , 2015
研究目的
当研究室では並列プログラミングフレームワーク Cerium Task Manager でプログラミングを行っている。
正規表現について
文字列の一部をパターン化して表現する手法
文章からあるパターン文字列を検索したいときに使用する
(e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)
. (ピリオド) : 改行コード以外の任意の1文字
* : 直前の文字の 0 回以上の繰返し
オートマトンについて
入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念
正規表現はオートマトンで表現することができる。
非決定性有限オートマトン NFA(Non-deterministic Finite Automaton)と、非決定性有限オートマトンDFA(Deterministic Finite Automaton)が存在する。
非決定性有限オートマトン : 1つの入力に対して複数の遷移先が存在する
決定性有限オートマトン : 1つの入力に対して遷移先が1つだけ
正規表現の基本三演算
正規表現は「連接」「選択」「繰返し」の演算が備えられている
R,S という 2 つの正規表現が存在すると仮定する。
連接 「RS」
: R の直後に S が続くパターン
(e.g.) RS, RRS, RSS, RRSS, ...
選択 「R|S」
: R もしくは S が出現するパターン
(e.g.) R, S, RS, ...
繰返し 「R*S」
: 「*」の直前(R)が 0 回以上出現するパターン
(e.g.) S, RS, RRS, RRRS, ...
基本三演算は結合順位が存在する
繰返し > 連接 > 選択
正規表現の他の演算
「R+S」
: 「+」の直前のパターンが 1 回以上出現するパターン
(e.g.) RS, RRS, RRRS, ...
R+S ≡ R(R*)S
「R?S」
: 「?」の直前のパターンが 0 or 1 回出現するパターン
(e.g.) S, RS
「R{1,3}」
: 「{}」の直前のパターンが 1 〜 3 回出現するパターン
(e.g.) R, RR, RRR
「R{1,}」
: 「{}」の直前のパターンが 1 回以上出現するパターン
(e.g.) R, RR, RRR, ...
R+S ≡ R(R*)S ≡ R{1,}S
実装について
まずは基本三演算を実装していく。
R*(T|S)U をオートマトンで表現してみる
状態と入力に対する遷移先、遷移したかどうかフラグで管理する。
typedef struct Automaton { int state; unsigned char input_char; int next_state; bool next_state; };