正規表現（構文木の作成）（Pythonによるアルゴリズムとデータ構造）

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

今回は、正規表現を解析し、構文木（Syntax Tree）を作成する方法について学んでいきます。

はじめに
正規表現とは
連結とは
選択とは
繰り返しとは
Pythonで構文木を作成する
動作確認
参考書籍

はじめに

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

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

今回は上記1の正規表現を解析し、構文木（Syntax Tree）を作成する方法について学びます。

正規表現とは

前回までで学んだ文字列探索では、対象の文字列とパターンが完全に一致した際に成功したとするものでした。

しかし、ファイルの拡張子が".txt"のファイル名を探索するなどの場合には、正規表現（Regular Expression）と呼ばれる記述方法を使うと便利です。

正規表現の歴史を遡ると、人間の神経系の仕組みに関する研究から始まり、1956 年に数学者のStephen Kleeneが正則集合と呼ばれる概念としてモデル化しました。

そして、UNIXの開発者であるKen ThompsonがテキストエディタのQEDに正規表現によるパターンマッチを実装し、その後のgrep、sed、awk等に受け継がれていきます。

正規表現は、主に以下の3つを再帰的に操作していきます。

連結（Concatenation）
選択（Union）
繰り返し（Closure（閉包））

また、正規表現の中でも特別な意味を持つ文字としてメタキャラクタ（Metacharacter）と呼ばれるものがあります。

基本的なメタキャラクタとして、以下の4つがあります。

' * '：繰り返し
' | '：選択
' ( '：優先順位を変える
' ) '：同上

連結とは

連結とは、正規表現が出現する順番を表すものです。

例えば、"ab"という正規表現は、文字a→文字bの順番で出現することを表します。

選択とは

選択とは、上記のメタ文字である" | "を使って表した正規表現です。

例えば、"a|b"という正規表現は、文字aもしくは文字bが一つ出現することを表します。

繰り返しとは

繰り返しとは、上記のメタ文字である" * "を表した正規表現です。

例えば、"a*"という正規表現は、文字aが0回以上連続して出現することを表します。

Pythonで構文木を作成する

それでは、Pythonで正規表現を解析し、構文木（Syntax Tree）を作成します。

なお、今回は上述の基本的な正規表現に加え、'+'の拡張表現のみを解析するものとします。

# syntax_tree.py
import sys

class Node:
    def __init__(self, op, left=None, right=None, char=None):
        self.op = op
        self.char = char
        self.left = left
        self.right = right

class SyntaxTree:
    def __init__(self, regex, debug=False):
        self.regex = list(regex)
        self.current_token = None
        self.current_token = None
        self.tree = None
        self.debug = debug

    def get_token(self):
        if len(self.regex) == 0:
            self.current_token = 'end'
            return
        c = self.regex.pop(0)
        if c == '|':
            self.current_token = 'union'
        elif c == '(':
            self.current_token = 'lpar'
        elif c == ')':
            self.current_token = 'rpar'
        elif c == '*':
            self.current_token = 'star'
        elif c == '+':
            self.current_token = 'plus'
        else:
            self.current_token = 'char'
            self.token_char = c

    def make_node(self, op, left, right):
        node = Node(op, left, right)
        return node

    def make_atom(self, c):
        atom = Node('char', char=c)
        return atom

    def primary(self):
        if self.current_token == 'char':
            x = self.make_atom(self.token_char)
            self.get_token()
        elif self.current_token == 'lpar':
            self.get_token()
            x = self.parse_regex()
            if self.current_token != 'rpar':
                self.syntax_error("Close paren is expected.")
            self.get_token()
        else:
            self.syntax_error("Normal character or open paren is expected.")
        return x

    def factor(self):
        x = self.primary()
        if self.current_token == 'star':
            x = self.make_node('closure', x, None)
            self.get_token()
        elif self.current_token == 'plus':
            x = self.make_node('concat', x, self.make_node('closure', x, None))
            self.get_token()
        return x

    def term(self):
        if self.current_token in ['union', 'rpar', 'end']:
            x = self.make_node('empty')
        else:
            x = self.factor()
            while self.current_token not in ['union', 'rpar', 'end']:
                x = self.make_node('concat', x, self.factor())
        return x

    def parse_regex(self):
        x = self.term()
        while self.current_token == 'union':
            self.get_token()
            x = self.make_node('union', x, self.term())
        return x

    def make_tree(self):
        self.get_token()
        self.tree = self.parse_regex()
        if self.current_token != 'end':
            print("Extra character at end of pattern.")
            sys.exit(1)
        if self.debug:
            print("------ Syntax Tree ------")
            self.dump_tree(self.tree)
            print()
        return self.tree

    def dump_tree(self, tree):
        op = tree.op
        if op == 'char':
            print("'{}'".format(tree.char), end="")
        elif op == 'concat':
            print("(concat ", end="")
            self.dump_tree(tree.left)
            print(" ", end="")
            self.dump_tree(tree.right)
            print(")", end="")
        elif op == 'union':
            print("(or ", end="")
            self.dump_tree(tree.left)
            print(" ", end="")
            self.dump_tree(tree.right)
            print(")", end="")
        elif op == 'closure':
            print("(closure )", end="")
            self.dump_tree(tree.left)
            print(")", end="")
        elif op == 'empty':
            print("Empty")
        else:
            print("This cannot happen in ")
            sys.exit(1)

r = SyntaxTree("a(a|b)*a", debug=True)
r.make_tree()

動作確認

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

今回は $a(a|b)*a$ という正規表現から構文木を作成してみます。

fig1. [tex:a(a|b)*a] の構文木 — fig1. $a(a|b)*a$ の構文木

 > python syntax_tree.py
 ------ Syntax Tree ------
 (concat (concat 'a' (closure )(or 'a' 'b'))) 'a')

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

参考書籍

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

Engineering Note

プログラミングなどの技術的なメモ