正規表現（決定性有限オートマトンによるパターンマッチ）（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、前回作成した決定性有限オートマトン（Deterministic Finite Automaton）を使ったパターンマッチについて学んでいきます。

はじめに
メインプログラムの作成
動作確認
参考書籍

はじめに

正規表現によるパターンマッチを行うプログラムを作成するにあたり、以下の段階分けを行います。

正規表現を解析し、構文木を作成する
構文木から非決定性有限オートマトンを作成する
非決定性有限オートマトンから決定性有限オートマトンを作成する
決定性有限オートマトンを使いパターンマッチをする

今回は上記4の決定性有限オートマトンを使いパターンマッチをする方法について学びます。

メインプログラムの作成

前回までに作成した構文木、NFAおよびDFAを用いてパターンマッチを処理するメインプログラムを作成します。

今回では引数として正規表現を渡したら、ユーザからの文字列の入力を待つプロンプトを表示させ、パターンマッチができた箇所に下線を表示させます。

以下が作成したメインプログラムになります。

# regex.py
from dfa import *
import sys

class Regex:
    def __init__(self, regex, debug=False):
        self.regex = regex
        self.dfa = None
        self.start = None
        self.end = None
        self.debug = debug

    def init(self):
        self.dfa = Dfa(self.regex, self.debug)
        self.dfa.convert_nfa_to_dfa()

    def next_dfa_state(self, state, char):
        p = state.next
        while p:
            if char == p.char:
                return p.dst
            p = p.next
        return None

    def do_match(self, string):
        for i in range(len(string)):
            state = self.dfa.initial_dfa_state
            max_match = None
            j = i
            while state:
                if state.accepted:
                    max_match = j
                if len(string)-1 < j:
                    break
                state = self.next_dfa_state(state, string[j])
                j += 1
            if max_match and max_match != string[i]:
                self.start = i
                self.end = max_match
                return
        self.start = None
        return

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print("Usage: {} ".format(sys.argv[0]))
        sys.exit(1)

    regex = Regex(sys.argv[1], debug=True)
    regex.init()
    buf = ""
    while True:
        buf = input("> ")
        if buf == "q":
            break
        regex.do_match(buf)
        if regex.start != None:
            print(buf)
            for i in range(0, regex.start):
                print(" ", end="")
            for j in range(regex.start, regex.end):
                print("-",end="")
            print()

動作確認

それでは上記で作成したスクリプトを実行してみます。

 > python regex.py "te+st"
 ------ Syntax Tree ------
 (concat (concat (concat 't' (concat 'e' (closure )'e'))) 's') 't')
 ------ NFA ------
 state   0:(t . 4)
 state   2:(t . 1)
 state   3:(s . 2)
 state   4:(e . 5)
 state   5:(? . 6)
 state   6:(? . 3) (e . 7)
 state   7:(? . 6)
 ------ DFA ------
  0 : t=>1
  1 : e=>2
  2 : s=>4 e=>3
  3 : s=>4 e=>3
  4 : t=>5
  5A:
 state  0  = {0 }
 state  1  = {4 }
 state  2  = {3 5 6 }
 state  3  = {3 6 7 }
 state  4  = {2 }
 state  5A = {1 }
 > this is a test.
 this is a test.
           ----
 > this is a teeeeeeeest.
 this is a teeeeeeeest.
           -----------

正規表現 $te+st$ に対してパターンマッチができていることが確認できました。