D言語で構文解析器をつくる(1) パーサー・コンビネーター編

#はじめに

もくじ

1. D言語で構文解析器をつくる(1) パーサー・コンビネーター編 (本記事)
2. D言語で構文解析器をつくる(2) セマンティック・アクション編
3. D言語で構文解析器をつくる(3) アブストラクト・シンタックス・クリスマスツリー編

今回つくるもの

　この記事では、簡単なPEGパーサー・コンビネーターを実装します。
　こちらのデモのように動かせる物が出来上がります。
　以下は、3桁ごとにカンマで区切られている数字(1,000とか1,000,000とか)のチェックを行う簡単なユニットテストです。

unittest {
    // 1以上の数字
    alias rng!('1', '9') n1;

    // 0以上の数字
    alias rng!('0', '9') n0;

    // カンマ区切り数字の先頭。最初の1桁は[1, 9]で、カンマの出てこない最初の3桁まで
    alias seq!(n1, opt!n0, opt!n0) digitsHead;

    // 数字のカンマで区切られている末尾部分。
    alias seq!(ch!',', n0, n0, n0) digitsTail;

    // ゼロの場合
    alias seq!(ch!'0', end) zero;

    // 数字。ゼロまたは数字列
    alias sel!(zero, seq!(digitsHead, more0!digitsTail, end)) digits;

    // 以下は成功するソース
    foreach(s; [
            "0",
            "1",
            "12",
            "123",
            "1,234",
            "12,234",
            "123,234",
            "1,000",
            "10,000",
            "100,000",
            "1,000,000",
            ]) {
        auto src = s;
        assert(digits(src) && src.empty, s);
    }

    // 以下は失敗するソース
    foreach(s; [
            "01",
            "012",
            ",",
            ",1"
            ",12",
            ",123",
            "1,",
            "12,",
            "123,",
            "1234,",
            "1234,234",
            "1,",
            "1,2",
            "1,23",
            "1,2345",
            "0,234",
            ]) {
        auto src = s;
        assert(!digits(src) && src == s, s);
    }
}

今回のソース

対象読者

• D言語のプログラミングに興味があって、一般的なプログラムがどう書けるか知りたい方
• 構文解析で他の入門者(私のこと)がどんな感じにやっているか見てみたい方
• なんとなくD言語で何かが作られるのを眺めてみたい方

「焦るんじゃない、俺は構文解析したいだけなんだ」という方へ

　D言語には既に構文解析器ライブラリの実装がいくつかあるので、これらを活用するのが最初の選択肢となります。

• ctpg
  • 今回のACにも参加されているyouxkeiさん作
• Pegged

前置き

　まだまだプログラミング初心者だった高校1年生の頃、数学の授業で「プログラムで関数のグラフが描けたらテストに加点する」と言われて、頑張ってプログラムを作ったことがありました。
　DirectXのライブラリやWin32APIを使って教科書に出てくるグラフを描くことはできたけれど、そこからつい欲が出て「ようし、任意の数式のグラフを描けるようにしてやる！」と意気込んでしまいました。
　グラフを描くのは描画APIさえ呼べば割と簡単でしたが、__文字列の数式を読み込んで計算する__という部分が自分ではどう考えてもうまくいかず、結局プログラムとして中途半端なものになってしまい、加点ももらえませんでした。
　それから、「C++再考」という本に出会って、数式をツリーで表現するという方法を初めて知り、そうか、こうやれば良かったんだ！　とひとり感動する事になります。

　文字列・数式・言語を解析するプログラムを作るということは、それ以来の長い夢で、何度も中途半端に挑戦してはくじけている永遠のテーマです。
　そんな中途半端に終わり続けている作業の途中経過を、この記事で一旦まとめてみようと思います。似たような事に挑戦している人たちの一助になったり、D言語はなかなか面白いなあと思って頂けたら幸いです。

準備

構文を解析するということ

　構文解析とは……。正直、アカデミックな知識は乏しい野良プログラマーなので、あまりちゃんとした事は言えないのですが、ここでは以下のような事を扱おうと思います。

• 記号列を規則に従ってチェックし、合っているか判断する。
• 規則に従ってチェックした結果から、構文のデータ構造を作って処理できるようにする。

　たとえば、以下のような数式の__文字列__があったとします。

"x = 1 + 2;"

　これは人間が読めば「1 + 2という計算を行ってxに入れるのだな」と何となく分かります。
　しかし__文字列__なので、このままではコンピューターで計算を行えません。コンピューターで処理するには、下記のような__構造__で表現されていると都合が良いです。

• 代入演算子(=)
  • 左辺
    • 変数(x)
  • 右辺
    • 加算演算子(+)
      • 左辺
        • 整数値(1)
      • 右辺
        • 整数値(2)

　このようになっていると、まず一番上の「代入演算子」から処理を始め、右辺の処理を呼び出し、右辺では加算演算子の処理を行い、両辺を評価し……と再帰的に処理を呼び出して結果を左辺のxにセットする、といったふうに計算が行えます。
　その場で計算するだけでなく、xなどの出てくる変数名(シンボル)を集めて型チェックを行ったり、演算子に応じた機械語を生成したり(コンパイル)、まったく別の言語に変換するなど、色々な事ができて夢が広がります。

　構文解析とは、おおざっぱにいって、最初のx = 1 + 2;を上記のような構造に変換することです。
　そして、文字列などを読み込んでデータ構造へ解析するライブラリやプログラムのことを、構文解析器(parser)と呼びます。
　今回作ろうとしているのは、その構文解析器です。

実装するものについて

　構文解析器にはいくつか形式があって、再帰下降型(LL)構文解析器、LALR(1)構文解析器などがあります。
　今回作るのは表現解析文法(PEG)構文解析器と呼ばれるものです。
　これはLL構文解析器の一種で、とりあえずの実装がごく簡単(一番の理由!)で、文法や演算子が分かりやすく、制約も少なく、巷では正規表現の代わりに使おうという運動まであるくらい簡単なものです。
　速度的な面については、メモ化などを駆使して最適化するとそれなりになるようです。今回はきっとそこまでできません。

Rangeについて

　さて、D言語で構文解析を実装するにあたり、まず読み込む対象のソース文字列をどうするか決めなければなりません。
　そんなの普通のstringで良い気もするのですが、ここでは汎用性を考えて__Range__を使えるようにしたいと思います。
　ソース文字列をstringに限定しないことで、例えばubyteのバイナリソースを解析する時などにも、同じ構文解析器が使えるようになります。

　__Range__はD言語特有の概念なので、ここで少し解説します。

　__Range__とは、D言語の外部反復子の名前です。C++のiteratorに近い概念で、文字列や各種配列・無限数列なども含めた一般的な値の範囲(Range)を扱えるように決められています。

　基本的には、ある条件さえ満たせば、classでもstructでも組み込み配列でもどんな型の値でもRangeとして扱えるようになっています。
　その条件は、Rangeの種類によって違います。今回使おうと思っているForwardRangeは、下記の条件を満たす必要があります。

• rがRangeだとすると、
  • if(r.empty) {} // Rangeが空になっているかどうか判定できる
  • r.popFront(); // 先頭要素を捨てて1つ先に進められる
  • auto h = r.front; // 現在の先頭要素を参照できる
  • typeof(r) r2 = r.save; // 現在位置のRangeを保存できる

　この定義の中で、rやr.frontの戻り値の具体的な型は出てきません。Rangeを扱うライブラリ関数などでは、具体的な型は気にしないジェネリックな実装がされていて、どのような型のRangeでも(Rangeとしての条件さえ満たしていれば)同じように処理できるようになっています。
　また、D言語にはUFCSというフリー関数をあたかもメンバ関数のように使用できる仕組みがあります。その仕組みのお陰で、上記のemptyやfrontがフリー関数として定義されている場合でも、引数の型をRangeとして使用できるようになっています。
　メンバ関数の無い組み込み配列がRangeとして使用できるのは、まさにこのUFCSのお陰です。

　そんなわけで、Rangeがそのまま扱えると非常に強力です。そこで、今回実装する構文解析器も、Rangeを受け取り、その具体的な型にとらわれずに解析を行えるようにします。

この記事におけるパーサー(構文解析器)について

　この記事内での__パーサー__は、下記のような使い方ができる__何か__という事にします。

/**
 *  構文解析を行う。
 *
 *  Params:
 *      R = ソースとなるRangeの型
 *      src = 解析対象のソース。
 *            解析が成功した場合、読み込み位置が解析完了した位置まで進む。
 *            読み込み失敗した場合は呼び出し前の位置のままとなる。
 *  Returns:
 *      解析に成功したらtrue。失敗したらfalse。
 */
bool parse(R)(ref R src);

　上記のような使い方ができれば、function・delegate・opCallを定義したstructやclassのいずれでもパーサーと見なし、今回実装するパーサーと組み合わせて使えるようにします。

最初の一歩。単独で動作する基本的なパーサー

　これから各種パーサーを実装していきます。
　まずやるべきことは、下記の2つです。

• 文字列を先頭から呼んで、あるルールに合っているかチェックする。
• ルールに合っていたら、その分読み込み位置を進め、次のチェックが行えるようにする。

　まずはこれを行うごく基本的なパーサーを作ります。

とりあえず何か1文字認識する

　まず1文字、何でも良いから1文字認識し、その1文字すら無ければ(ソースが空)認識失敗する、といったものを作ります。
　名前はanyということにして、テスト・ファーストでまずunittestを書いてしまいます。

import std.range : front;

/// 任意の1文字認識する。未実装
bool any(R)(ref R src) {
    return false;
}

///
unittest {
    auto src = "test";

    // 次の1文字があればtrue
    assert(any(src));

    // 解析成功後はソースが次の文字を指す
    assert(src.front == 'e');

    // ソースが空であれば解析失敗
    src = "";
    assert(!any(src));
    assert(src == "");
}

　unittestが失敗したら実装します。

import std.range : empty, front, popFront;

/// 任意の1文字認識する
bool any(R)(ref R src) {
    if(src.empty) {
        return false;
    } else {
        src.popFront();
        return true;
    }
}

　簡単ですね。
　これからずっとこんな感じで、簡単なものをどんどん作っていくことになります。
　私の実装ではunittestを作りながらやっていく事にしますが、記事では省略します。
　ごく自然にunittestを書きながらプログラミングができるのは、D言語の大きな幸せですね。

決まった1文字認識する

template ch(alias C) {
    bool ch(R)(ref R src) if(isInputRange!R) {
        if(!src.empty && src.front == C) {
            src.popFront();
            return true;
        } else {
            return false;
        }   
    }
}

　さて、次は指定した文字を認識する構文解析器になります。
　__指定した文字__をコンパイル時の定数で設定できるようにするため、templateを2段階に使用しています。
こうすることで、「文字't'を認識する構文解析機」をch!'t'と表現できるようになります。
　(普通にbool ch(alias C, R)(ref R src)としても単体としては動く物ができますが、ch!'t'として構文解析器そのものを扱おうとすると、テンプレートパラメータRを指定していないためエラーになります)

　alias Cというテンプレートパラメータは、シンボルとか定数式をとりあえず何でも受け入れて使えるようにするという強力な機能です。
　このパーサは下記のように使えます。

auto src = "test";
assert(ch!'t'(src));

　't'という定数式を指定でき、それがそのままテンプレート関数内部で使えるわけです。

　また、こっそりif(isInputRange!R)というチェックを追加しました。これはRがInputRangeであることをコンパイル時にチェックするための構文です。

ソースの終わりを認識する

　解析を終了するためには、ソースの末尾を正しく認識できなければなりません。
　Rangeのemptyを確かめられる構文解析器が必要です。
　これも、実装そのものは簡単です。

bool end(R)(ref R src) if(isInputRange!R) {
    return src.empty;
}

文字列を認識する

　文字「列」を認識するには少し工夫が必要です。
　なぜなら、たとえば"test"という文字列を認識したい場合、ソースが"tess"だったら解析失敗する必要があります。このとき、"tes"までは解析成功しているのですが、最後の"s"を見た瞬間に全てを元に戻して失敗する必要があるわけです。
　いわゆる__バックトラック__です。
　D言語のRangeでは、saveメンバ関数を使用し、元のRangeを保存しておくことで実現できます。

template str(alias S) {
    bool str(alias S, R)(ref R src) if(isForwardRange!R && isInputRange!(typeof(S))) {
        // 最初の位置を覚えておく。例外発生時は元に戻す。
        auto before = src.save;
        scope(failure) src = before;

        // テンプレートパラメータの文字列の文字ごとにチェック
        foreach(c; S) {
            // ソースが空になったり違う文字が出てきたら解析失敗
            if(src.empty || src.front != c) {
                // ソースを元の位置に戻して終了
                src = before;
                return false;
            }

            // 合致する文字が出てくる限り先に進む
            src.popFront();
        }

        // テンプレートパラメータの文字列の文字全てがチェックできたら解析成功
        return true;
    }
}

　scope(failure)という構文は、この後で例外が発生した時に次の処理を実行するよ、といういわゆるスコープガードです。
　Rangeを操作している時に例外が発生しても、引数のsrcが半端に進められた状態にならないようにしています。

その他

　今までの構文解析器に加えて、下記も便利なので追加します。
　実装などは同様に簡単なので割愛します。

template set(alias S) {bool set(R)(ref R src);} // 文字集合Sのうち1文字にマッチすれば解析成功
template rng(alias C1, alias C2) {bool rng(R)(ref R src);} // 先頭文字が範囲[C1, C2]ならば解析成功

パーサーを組み合わせる

　ここまでで、文字や文字列を認識するパーサーはある程度揃いました。
　次は、複数のパーサーを組み合わせて複雑な構文解析を行わせられるようにしていきます。

あるかどうかチェック

　ここでは、いわゆる__先読み__の機能を実装します。
　たとえば整数リテラルを構文解析するとき、0x1234とあった場合は16進数リテラルで、1234とあったら10進数リテラルとして読みたいとします。
　この場合、0xを先読みし、読み込み位置は一旦戻して、0xがあれば16進数リテラルパーサーを、無ければ10進数リテラルパーサーを呼び出すことになります。
　こういった先読み機能を実現するandパーサーおよびnotパーサーを実装します。
　andパーサーは、組み合わせたパーサーでの解析が成功すれば成功・失敗すれば失敗を返します。成功・失敗に関わらず、読み込み位置は必ず戻します。
　notパーサーはその逆で、組み合わせたパーサーでの解析が成功すれば失敗・失敗すれば成功となります。読み込み位置はやはり必ず戻します。

　実装はやはりごく簡単です。組み合わせるパーサーはテンプレートパラメータalias Pとして指定できるようにします。

template and(alias P) {
    bool and(R)(ref R src) if(isForwardRange!R) {
        auto before = src.save;
        scope(exit) src = before;

        return P(src); // Pを呼び出した結果を返す。このスコープを抜けるときにsrcは元に戻される。
    }   
}

　scope(exit)は、scope(failure)と同じようなスコープガードです。今回は__いかなる場合でも必ず戻したい__ので、例外発生時だけでなく普通のreturnなどでも呼び出されるscope(exit)を使用しています。

　notはandの単純な逆です。実装は割愛します。

繰り返し

　次はパーサーの繰り返しができるようにします。
PEGには、下記のような繰り返し演算子が定義されています。

• 0または1回繰り返す。(正規表現の?に該当)
• 0回以上繰り返す。(正規表現の*に該当)
• 1回以上繰り返す。(正規表現の+に該当)

　これらをそれぞれ実装していきます。正直どれもごく簡単です。

0〜1回繰り返し

template opt(alias P) {
    bool opt(R)(ref R src) {
        P(src); // とりあえず1回呼んでみてtrueで終了するだけ
        return true;
    }   
}

0回以上繰り返し

template more0(alias P) {
    bool more0(R)(ref R src) {
        while(P(src)) {} // 解析成功する限り呼び続ける
        return true;
    }
}

1回以上繰り返し

template more1(alias P) {
    bool more1(R)(ref R src) {
        bool result = false;
        while(P(src)) {
            result = true; // 1回でも成功すれば戻り値をtrueにする
        }
        return result;
    }
}

連接

　次はパーサーの__連接__です。つまり、パーサーを並べて、すべて解析成功したら成功・途中で失敗したら失敗とします。
　これは簡単に思えますが、途中で失敗した場合のバックトラックが必要になるため、思ったよりは複雑です。

　また、任意の数のパーサーの連続をテンプレートパラメーターで受け取れなければなりません。
　幸いなことに、D言語には強力な可変長テンプレートパラメータの機能があります。

template seq(P...) {
    bool seq(R)(ref R src) {
        auto before = src.save;
        scope(failure) src = before;

        foreach(p; P) { // 一見普通のforeachに見えるが、
                        // 実は可変長テンプレートパラメータPの個々の要素について繰り返すコンパイル時foreach
            if(!p(src)) {
                // 1つでも失敗したら巻き戻し・中断
                src = before;
                return false;
            }
        }

        // 全部解析成功したので成功
        return true;
    }
}

選択

　パーサー組み合わせ編の最後を飾るのは、パーサーの__選択__です。
　これは、指定された複数のパーサーのうちいずれか1つで解析成功すれば成功する、というパーサーです。
　パーサーの呼び出し順は、テンプレートパラメータに指定された順序となります。
　難しく見えて、実はバックトラックが不要(呼び出されるパーサー側の責任)のため、思ったより簡単です。

template sel(P...) {
    bool sel(R)(ref R src) {
        foreach(p; P) {
            if(p(src)) {
                return true;
            }   
        }   
        return false;
    }   
}

次回予告

　だいぶ日をまたいでしまったので、今回は一旦ここまでで区切らせて頂きます（汗）。
　とりあえず、PEGの基本的な機能はすべて実装されました。
　以下、次回予告です。カレンダーに載せるかどうかは分かりませんが、続編として書いていきます。

• 結果に従って処理を行う
  • 位置の記憶・行番号のカウント
  • アクション
• PEG自身の構文解析
  • ASTの構築
  • 構文の定義