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

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

今回は、前回作成した構文木から非決定性有限オートマトン（Non-Deterministic Finite Automaton）の作成方法について学んでいきます。

はじめに

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

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

今回は上記2の構文木から非決定性有限オートマトンを作成する方法について学びます。

オートマトンとは

正規表現でパターンマッチを行うには、有限オートマトン（Finite Automaton）というものを利用します（以降オートマトンと呼びます）。

オートマトンとは、内部に固有の状態を持った機械装置のようなもので、外部からの入力に応じて、その内部の状態を変化させます（どうやら自動羊肉ではなさそうです）。

オートマトンは以下のような状態遷移図（State Transition Diagram）というグラフ構造を使うと視覚的にも解りやすくなります。

fig1. 正規表現 の状態遷移図

上記fig1は、正規表現 の状態遷移図を表したものです。

上記の0を初期状態（Inite State）といい、入力値によって、1、2、そして3へと内部状態を変化させます。

3は二重線となっていますが、これは終了状態（Final State）を表します。

今回は、オートマトンを用いて正規表現によるパターンマッチを行うために2つの段階を用意します。

一つ目は、前回で作成した構文木から機械的に非決定性有限性オートマトンに変換します。

二つ目は、非決定性有限性オートマトンを決定性有限オートマトンに変換します。

なお、バックトラック法という手法を用いれば、非決定有限オートマトンのみでパターンマッチもできるようですが、決定性有限オートマトンに変換したほうが、トータルの処理時間が短縮できるようです。

非決定性有限オートマトンとは

上記のfig1のオートマトンでは、入力値による状態遷移先が明確に決まっています。

しかし、オートマトンの中には同じ入力値でも状態遷移先が複数存在することを許容しているものもあり、これを非決定性有限オートマトン（Non-Deterministic Finite Automaton：以下NFA）と言います。

またNFAでは外部入力がない場合でも状態遷移を許可する 遷移（ - Transition）というものがあります。

なお、NFAを用いれば正規表現を機械的にオートマトンへ変換することができるようになります。

PythonでNFAを作成する

それでは、PythonでNFAを作成します。

# nfa.py
from syntax_tree import Node, SyntaxTree
import sys

EMPTY = -1
NFA_STATE_MAX = 128
NFA_VECTOR_SIZE = int(NFA_STATE_MAX / 8)
DFA_STATE_MAX = 100

class NfaList:
    def __init__(self, next=None, to=None, c=None):
        self.char = c
        self.to = to
        self.next = next

class Nfa:
    def __init__(self, regex, debug=False):
        self.nfa = [None for _ in range(NFA_STATE_MAX)]
        self.state = 0
        self.exit = None
        self.entry = None
        self.regex = regex
        self.debug = debug

    def gen_node(self):
        if self.state > NFA_STATE_MAX:
            printf("Too many NFA state.")
            sys.exit(1)
        state = self.state
        self.state += 1
        return state

    def add_transition(self, src, dst, c):
        p = NfaList(self.nfa[src], dst, c)
        self.nfa[src] = p

    def gen_nfa(self, tree, entry, way_out):
        op = tree.op
        if op == 'char':
            self.add_transition(entry, way_out, tree.char)
        elif op == 'empty':
            self.add_transition(entry, way_out, EMPTY)
        elif op == 'union':
            self.gen_nfa(tree.left, entry, way_out)
            self.gen_nfa(tree.right, entry, way_out)
        elif op == 'closure':
            a1 = self.gen_node()
            a2 = self.gen_node()
            self.add_transition(entry, a1, EMPTY)
            self.gen_nfa(tree.left, a1, a2)
            self.add_transition(a2, a1, EMPTY)
            self.add_transition(a1, way_out, EMPTY)
        elif op == 'concat':
            a1 = self.gen_node()
            self.gen_nfa(tree.left, entry, a1)
            self.gen_nfa(tree.right, a1, way_out)
        else:
            print("This cannot happen in ")
            sys.exit(1)

    def init_tree(self):
        tree = SyntaxTree(self.regex, self.debug)
        return tree.make_tree()

    def build_nfa(self):
        tree = self.init_tree()
        self.entry = self.gen_node()
        self.exit = self.gen_node()
        self.gen_nfa(tree, self.entry, self.exit)
        if self.debug:
            print("------ NFA ------")
            self.dump_nfa()
        return self.nfa

    def dump_nfa(self):
        for i in range(self.state):
            if self.nfa[i]:
                print("state {:3}:".format(i),end="")
                p = self.nfa[i]
                while p:
                    c = '?' if p.char == EMPTY else p.char
                    print("({} . {}) ".format(c, p.to), end="")
                    p = p.next
                print()

nfa = Nfa("a(a|b)*a", debug=True)
nfa.build_nfa()

動作確認 

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

なお、前回作成した構文木（正規表現 ）からNFAを生成します。

fig2. のNFA

 > python nfa.py
 ------ Syntax Tree ------
 (concat (concat 'a' (closure )(or 'a' 'b'))) 'a')
 ------ NFA ------
 state   0:(a . 3)
 state   2:(a . 1)
 state   3:(? . 4)
 state   4:(? . 2) (b . 5) (a . 5)
 state   5:(? . 4)

ダンプしてみると、問題なくNFAを作成することができました。

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)