本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、正規表現を解析し、構文木（Syntax Tree）を作成する方法について学んでいきます。
はじめに
正規表現によるパターンマッチを行うプログラムを作成するにあたり、以下の段階分けを行います。
今回は上記1の正規表現を解析し、構文木（Syntax Tree）を作成する方法について学びます。
正規表現とは
前回までで学んだ文字列探索では、対象の文字列とパターンが完全に一致した際に成功したとするものでした。
しかし、ファイルの拡張子が".txt"のファイル名を探索するなどの場合には、正規表現（Regular Expression）と呼ばれる記述方法を使うと便利です。
正規表現の歴史を遡ると、人間の神経系の仕組みに関する研究から始まり、1956 年に数学者のStephen Kleeneが正則集合と呼ばれる概念としてモデル化しました。
そして、UNIXの開発者であるKen ThompsonがテキストエディタのQEDに正規表現によるパターンマッチを実装し、その後のgrep、sed、awk等に受け継がれていきます。
- 連結（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()
動作確認
それでは上記で作成したスクリプトを実行してみます。
![fig1. [tex:a(a|b)*a] の構文木](https://cdn-ak.f.st-hatena.com/images/fotolife/s/s3cr3t/20190216/20190216231738.png)
> python syntax_tree.py ------ Syntax Tree ------ (concat (concat 'a' (closure )(or 'a' 'b'))) 'a')
ダンプしてみると、問題なく構文木を作成することができました。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
