正規表現エンジンを作ろう （3）

はじめに

　こんにちは。hirataraです。

　前回はDFAエンジンの仕様を明らかにし、DFAとNFAをPythonで実装しました。今回は、実装するDFAエンジンが扱う文法を解釈するコンパイラを作成します。

対象読者

• 正規表現をもっと知りたい方
• 情報科学分野に興味がある方
• 正規表現エンジンを実装する必要がある方

正規表現のコンパイル

　前回、正規表現の仕様の中で正規表現の文法を定めました。これから、この文法を解釈できるコンパイラを作成します。コンパイラの仕事は、文字列を解釈して計算機が扱いやすいデータ方式に変換することです。

　なお、今回のコンパイラの実装の解説は、実は正規表現エンジンの理論とは直接関係のない一般論的な内容です。ですので、もし興味がなければこの部分は軽く読み流して頂いても構いません。

　さて、コンパイラを実装するにあたり、以下の二つのパートに分けて説明をします。

• 字句解析
• 構文解析

字句解析

　コンパイラが最初に行う仕事が、字句解析です。「字句解析」とは、入力された長い文字列を意味のある「トークン」の単位で分割する作業を言います。この正規表現では1文字を1トークンとしますので、文字列を単純に1文字ずつに分解すると良さそうです。ただし後述するように、エスケープシーケンス（\）があるため、全てを単純に1文字で1トークンとすることはできません。

トークンの種類

　各トークンには、種類を持たせます。今回の文法には、以下のような種類のトークンがあります。

　ここで一つ注意が必要なのは、 CHARACTER である '|' や '*' 、 '(' 、 ')' も存在するということです。最初に定義した文法では、バックスラッシュをエスケープ文字と決めましたので、これらのトークンは文字列上では '\|', '\*', '\(', '\)' で表されます。このように、エスケープ文字に続く文字に関しては、2文字分をまとめて1つの CHARACTER トークンとしなければなりません。

Tokenクラス

　トークンを表すクラスです。クラス内に、先ほど説明した6つの型を整数値で持っています。インスタンスは単に情報を保持するだけです。valueとkindと言うフィールドを持っていて、kindフィールドに、種類を表す定数を値として持ちます。

class Token(object):
    # トークンの種類
    CHARACTER  = 0
    OPE_UNION  = 1
    OPE_STAR   = 2
    LPAREN     = 3
    RPAREN     = 4
    EOF        = 5

    def __init__(self, value, kind):
        # このトークンが持つ値
        self.value = value
        # このトークンの種類
        self.kind  = kind

Lexerクラス

　字句解析を行うクラスです。解析する文字列を自身のstring_listフィールドに、1文字ずつばらばらにした形で持ちます。そして、scanを呼ばれるごとに、生成したTokenインスタンスを一つずつ返します。文字が無くなってからは、Token.EOF型のトークンを返し続けます。EOFはEnd Of Fileの略で、文末を表す略号です。

class Lexer(object):
    def __init__(self, string_):
        # 文字をリスト化して保持
        self.string_list = list(string_)

    def scan(self):
        if not self.string_list: 
            # 文字がなくなったらEOFトークンを返す
            return Token(None, Token.EOF)

        ch = self.string_list.pop(0)

        if ch == u'\\':
            # エスケープ文字の処理。次の文字を文字トークンとして返す
            return Token(self.string_list.pop(0), Token.CHARACTER)
        elif ch == u'|': 
            return Token(ch, Token.OPE_UNION)
        elif ch == u'(': 
            return Token(ch, Token.LPAREN)
        elif ch == u')': 
            return Token(ch, Token.RPAREN)
        elif ch == u'*': 
            return Token(ch, Token.OPE_STAR)
        else: 
            # 通常の文字
            return Token(ch, Token.CHARACTER)

　エスケープ文字の処理は、if文の最初の判定で行っています。エスケープ文字（バックスラッシュ:\）が現れた場合は、その場で次の文字を読み込んで、強制的にCHARACTERのトークンとみなして返します。

　エスケープ文字以外の文字は、その文字に対してそれぞれ適切な種類のトークンを生成して返します。

構文木

　字句解析が終わると、コンパイラはトークンと文法規則を照らし合わせて構文木を作ります。「構文木」とは、演算の入れ子の関係をツリー状に表した物です。正規表現の持つ演算に合わせ、Union（和集合）、Concat（連結）、Star（繰り返し）の3つのノード(節となる部分)と、葉となる Character（文字） の、計4種類のノードから構成されます。

　例えば、'a|(bc)*' と言う正規表現では以下のような構文木が作られます。今回の文法では文字列リテラルを用意しないので、文字列"bc"ではなく、文字'b'と文字'c'の連結、と解釈されることに気をつけて下さい。

a|(bc)*の構文木（図）