Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

正規表現エンジンを作ろう (3)

コンパイラの作成

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/11/19 14:00

 正規表現は、特に文字列操作が中心となるWEB分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第3回は、実装するDFAエンジンが扱う文法を解釈するコンパイラを作成します。

目次

はじめに

 こんにちは。hirataraです。

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

対象読者

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

正規表現のコンパイル

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

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

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

  • 字句解析
  • 構文解析

字句解析

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

トークンの種類

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

トークン
トークン種別 説明
CHARACTER 文字を表すトークン。'a'~'z'、'あ'~'ん'、等
OPE_UNION 和集合演算 '|'
OPE_STAR 繰り返し演算 '*'
LPAREN 左括弧 '('
RPAREN 右括弧 ')'
EOF 文末を表す

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

Tokenクラス

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

Tokenクラス
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の略で、文末を表す略号です。

Lexerクラス
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)*の構文木(図)
構文木

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • hiratara(ヒラタラ)

    1977年に苫小牧市で生まれる。北海道大学理学部数学科卒。小学生の頃、両親に買い与えられたMZ-2500でプログラミングを始めた。学生時代、CGIの自作に没頭し、それ以降WEB開発の魅力に憑かれる。社会人になっても数学好きは変わらず、専門書を買い集めるのが最近の趣味。 id:hirataraに...

バックナンバー

連載:正規表現エンジンを作ろう
All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5