CodeZine(コードジン)

特集ページ一覧

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

コンパイラの作成

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

目次

(F)factorルール(factor -> '(' subexpr ')' | CHARACTER)

 factorルールの実装は以下の通りです。

Parserクラス(2)
    def factor(self):
        if self.look.kind == Token.LPAREN:
            # factor -> '(' subexpr ')'
            self.match(Token.LPAREN)
            node = self.subexpr()
            self.match(Token.RPAREN)
            return node
        else:
            # factor -> CHARACTER
            node = Character(self.look.value)
            self.match(Token.CHARACTER);
            return node

 factorルールでは、最初の1トークン(self.look)を見ると、どちらのルールを適用するかを決定できます。左括弧('(')が現れた場合は、左側のルール(subexpr 全体を括弧で包むルール)ですので、 '('、subexpr、')' の順でトークンが現れるはずです。matchsubexprメソッドを使い、この規則に沿って忠実にコーディングします。

 各ルールからは、そのルールによって生成されるノードを返さなければなりません。括弧でsubexprを包むと言うルールは、計算の優先順位を表しているだけで特に演算は必要ないので、subexpr を表すノードが単純にそのままこのルールのノードとなります。

 1つめのトークンがそれ意外の場合はelse:側に書かれており、2つ目のルールを適応します。このルールは任意の1文字を表すルールなので、Characterノードを生成して返します。matchを使い、このルール(ここにはToken.CHARACTERが現れる)の適用を終わらせておくことも忘れないようにしましょう。

(E)starルール(star -> factor '*' | factor)

 starルールの実装は以下です。

Parserクラス(3)
    def star(self):
        # star -> factor '*' | factor
        node = self.factor()
        if self.look.kind == Token.OPE_STAR:
            self.match(Token.OPE_STAR)
            node = Star(node)
        return node

 まず、左右どちらのルールになったとしても、最初はfactorです。factorメソッドを呼び、factorを表すノードを得ておきます。

 次のトークンを見た時に '*' であれば、左側のルールと言うことになります。このルールはスター演算を意味しますので、 元のノードからStarノードを作成してこのルールを表すノードとして返します。

 それ以外の場合は右側のルールで、これはfactorのノードをそのまま返すだけで大丈夫です。

(D)seqルール(seq -> subseq | '')

 このルールでは、どちらのルールを利用すべきかを決定するのに少し考える必要があります。

 まず、後者の''(空文字)であると言うルールが適応されたとしましょう。このとき、次のトークンが何になっているか考えてみます。seqが現れるのは、規則(B)です。規則(B)で左側のルールが適応されていれば seq の次は '|' です。また、subexprの展開元は規則(A)か(F)です。よって、規則(B)で右側が適応されている場合、展開元が規則(A)であれば次に続くのは文末(Token.EOF)、規則(E)であれば次に続くのは ')' となります。以上を総合すると、次に現れるトークンは '|' か Token.EOF か ')' と言うことになります。

 続いて、前者のsubseqと言うルールが適応される場合、この次に続くトークンを考えてみます。subseqは規則(D)よりstarから始まります。starは規則(E)よりfactorから始まります。規則(F)により、factorは '(' か CHARACTER から始まります。

 以上をまとめると、以下のようにルール分けが出来そうです。

  • 最初のトークンが、'(' か CHARACTER → 左側のルール
  • それ以外('|'かEOFか')') → 右側のルール

 これにそって場合分けして実装します。実装は以下です。

Parserクラス(4)
    def seq(self):
        if self.look.kind == Token.LPAREN \
           or self.look.kind == Token.CHARACTER:
            # seq -> subseq
            return self.subseq()
        else:
            # seq -> ''
            return Character("")

 後者のルールの場合は、空文字を表すCharacterノードを返します。

(C)subseqルール(subseq -> star subseq | star)

 左右どちらのルールでも、最初はstarなのでまずこのルールを適用します。その次にsubseqが続くかどうかを先ほどと同じように考察すると、(D)のときと同様の判定となることがわかります。よって、コードは以下となります。

Parserクラス(5)
    def subseq(self):
        node1 = self.star()
        if self.look.kind == Token.LPAREN \
           or self.look.kind == Token.CHARACTER:
            # subseq -> star subseq
            node2 = self.subseq()
            node  = Concat(node1, node2)
            return node
        else:
            # subseq -> star
            return node1

 左のルールは、starで得られるノードとsubseqで得られるノードの連結演算を意味してます。よって、それぞれのノードをConcatノードにまとめて返します。

(B)subexprルール(subexpr -> seq '|' subexpr | seq)

 subexprルールの実装は以下です。

Parserクラス(6)
    def subexpr(self):
        # subexpr    -> seq '|' subexpr | seq
        node = self.seq()
        if self.look.kind == Token.OPE_UNION:
            self.match(Token.OPE_UNION)
            node2 = self.subexpr()
            node = Union(node, node2)
        return node

 どちらのルールもseqから始まるので、最初にこれを適用します。

 その次のトークンが '|' であれば、ルールの左側を適用します。'|' 、subexpr、と順番に現れることが期待されるので、その通りにルールを適用します。このルールは和集合演算を表していますので、seqで得られるノードとsubexprで得られるノードをUnionノードにまとめて返します。

 次のトークンが '|' 以外の場合はルールの右側を適用し、seq で 得られるノードをそのまま返すだけです。

(A)(expression -> subexpr EOF)

 このルールは分岐がありません。subexprの後に Token.EOF が来ることを確かめます。

Parserクラス(7)
    def expression(self):
        # expression -> subexpr EOF
        node     = self.subexpr()
        self.match(Token.EOF)

        # 構文木を実行し、NFAを作る
        context  = Context()
        fragment = node.assemble(context)
        return fragment.build()

 これでpredictive parserの実装が終わりました。最上位規則であるexpressionメソッドを呼ぶことで、ノードがツリー状になった構文木を生成することができます。expressionメソッドでは、さらに、構文木にNFAを作成させる処理も実装しています。この処理に関しては、次回のNFA生成の説明の最後で解説します。

まとめ

 今回は、以下の内容を説明しました。

  • 正規表現のコンパイル
    • 字句解析
    • 構文解析

 次回は、完成した構文木をNFAに変換します。

参考資料

  1. 計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月
  2. Compilers Principles, Techniques, & Tools』 Alfred V. Aho・Monica S. Lam・Ravi Sethi・Jeffrey D. Ullman 著、Addison-Wesley、2007年10月


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

バックナンバー

連載:正規表現エンジンを作ろう

著者プロフィール

  • hiratara(ヒラタラ)

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

あなたにオススメ

All contents copyright © 2005-2021 Shoeisha Co., Ltd. All rights reserved. ver.1.5