正規表現の勉強!　その１

■１．はじめに

セキュリティキャンプ全国大会に参加にあたり

正規表現を用いたパターンマッチングエンジンの高速化をするので、その勉強もかねて正規表現に関しての記事を書いていきます。

正規表現に触れるのは初なのでミス等あるかもですが、ご了承ください＾＾；

f:id:yottiii:20170720231501j:plain

■２．正規表現とは？？

正規表現とは式です。

プログラマにとっての式は||(or)や&&(and),!(not)などの論理式を使って

プログラムを作成しています。式は演算子や数の組み合わせで構成されています。

正規表現は文字列のパターンで表現が可能である。

あ｜い｜う｜え｜お

という正規表現はあ～おまでの1文字でというパターンで表現されている。

記号|(or)という複数の可能性を表す表現の演算子である。

　例えば

私は p(erl | ython | hp)が好きです。

といえば perl,python,phpのどれかが好きということを表現している。

この場合、c++はマッチしない。

■３．基本メタ文字

またメタ文字について少し触れておきます。

メタ文字とは正規表現において、特別な意味を持った文字のことです。

また、特別な意味を持たないものをリテラルと呼びます。

簡単に言うと、正規表現はこのメタ文字とリテラルで構成されています。

基礎的なメタ文字について以下に示しておきます。

名称	演算子
選択	｜
量指定子	* + ? {}
グループ化	() (?:)
先読み等	(?=) (?!)(?<=)(?<!)

これらのメタ文字に関してはのちのち説明します。

■４.　初歩的な正規表現プログラムを書いてみる

ではさっそくこれらを用いてパターンマッチングエンジンのプログラムを書いていきます。今回はpythonを使って書きたいと思います。pythonの正規表現のライブラリはreモジュールという名前で出てます。

f:id:yottiii:20170720231413j:plain

import re

test1="foo "
test2="foo bar"
test3="test foo bar"
regexp=re.compile(r"[fb]oo")

for str in(test1, test2,test3):
print u"[%sのマッチ結果]"% test1
if regexp.match(str):print u"matchでマッチ"
if regexp.search(str):print u"searchでマッチ"



//実行結果
[fooのマッチ結果]
matchでマッチ
searchでマッチ
[fooのマッチ結果]
matchでマッチ
searchでマッチ
[fooのマッチ結果]
serchでマッチ
//

pythonの正規表現オブジェクトにはmatch()とsearch()という2種類のマッチングメソッドがある。

match()は部分文字列によるマッチの判定、

search()は前方一致によるマッチしているの上記の結果から言える。

またpythonのreモジュール以外に、dfaregという前文一致が出来る、モジュールがあるので使ってみる。

import　dfareg

regexp = dfareg.compile(r"(p(erl | ython | php ) | ruby)")
if regexp.matches("python"): print u"pythonがマッチ"
if regexp.matches("ruby"): print u"rubyがマッチ"
if regexp.matches("c"): print u"cがマッチ"

dfareg.compileを呼ぶと、コンパイルされた正規表現が返ってきます。この正規表現に対して、matchesメソッドによって、文字列がマッチするかしないかを判別できます。

■5.NFAとDFAについて

NFAとDFAについての説明の前に、有限オートマンについての説明をします。有限オートマンとは、文字を入力すると真偽値を出力するものです。

有限の状態を持っており、入力ごとにその状態を変化させます。最後の入力で、出力が決定されます。

有限オートマンにはNFAやDFAがあり、それを示すには状態遷移図を利用します。円は状態を示し、矢印は文字の入力により変化を示します。

εは空文字('')を表します空文字とはその名の通り空っぽの文字であり、他の文字列と繋げても文字列を変化させません。例えば、'a'+''+'c'は'ac'となります。

詳しい説明はまたしたいと思います。

NFAとDFAの違いに関して簡単に説明します。

NFAは入力により状態が一意には決まりません。またε（または ''）での状態遷移を許可します。例えば "abc" と言う文字列は、 'a'、'b'、'c' と入力してもいいし、''、''、'a'、''、''、''、'b'、''、''、'c' 等にしても大丈夫です。

対する DFA は入力により遷移する先の状態は一つになることが保障されています。

先ほどのNFAのεも許可されていません。

NFAエンジンとDFAエンジン

みなさんはバックトラックという方式をご存知ですか？

私はグラフ理論系の研究室なので、嫌というほどやっています(笑)

深さ優先探索とも呼ばれます。深さ優先探索アルゴリズムに関しては、わかりやすいものがネットにあったのでこちらを参照してください。

http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/07.pdf#search=%27%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2+%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%27

NFAエンジンはこの深さ優先探索というアルゴリズムを使用しています。

簡単にいうと、選択肢を適当に選んで失敗するまで進み、失敗したら戻り、別の選択肢をやるというアルゴリズムです。

一方DFAエンジンは幅優先探索というアルゴリズムを使っており、これは全ての可能性をマッチするまで広げていくというアルゴリズムです。

■6．最後に

今後としては、セキュリティキャンプまでにDFAとNFAをPythonで実装まで行いたいです。まずはDFAエンジンの作成を行いたいです。

またこの勉強をした上で、参考にした資料等を以下に示します。

正規表現技術入門　最新エンジン実装と理論的背景

著者：新屋良磨、鈴木勇介、高田鎌

http://yara.readthedocs.io/en/v3.6.0/writingrules.html

Regular Expression Matching: the Virtual Machine Approach