D言語で構文解析器をつくる(2) セマンティック・アクション編

はじめに

前回までのあらすじ

　禁じられた現代魔術言語「D」の封印を解き、簡単なパーサー・コンビネーターを作りあげたカラス。
　それを手にいにしえの極悪大魔導士「EBNF」に挑みかかる！　しかし、そこには巧妙な罠が張られていた……。

「うわわわわわー！！！」

　EBNFが発生させた時空断層に引きずり込まれ、カラスは為す術もない。悲鳴だけを後に残して、スキマ次元の闇の中へ消えていく……。

……そして、目を覚ますと、そこは何と１週間前の世界だった！

もくじ

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

今回つくるもの

　とりあえず今回でできるもののデモです。
　wcコマンドの実装です。

import std.array;
import std.stdio;

import yadc.peg;

/// メイン関数
void main() {
    // 改行文字
    alias ch!'\r' cr;
    alias ch!'\n' lf;

    // 改行
    alias addLine!(sel!(lf, seq!(cr, opt!(lf)))) newLine;

    // 空白。改行か空白文字のいずれか
    alias sel!(newLine, set!" \t\v\f") whiteSpace;

    // 単語
    alias more1!(seq!(not!whiteSpace, any)) word;

    // 単語カウントアクション
    size_t count = 0;
    alias action!(
        (s) {}, // 解析開始時
        (s) {++count;}, // 解析成功時
        (s) {}, // 解析失敗時
        word) wordCount;

    // 単語カウント解析処理全体のパーサー
    alias seq!(more0!(sel!(wordCount, whiteSpace)), end) parseText;

    // 標準入力を読み込む
    auto app = appender!(ubyte[])();
    ubyte[128] buffer = void;
    for(ubyte[] s; !(s = stdin.rawRead(buffer)).empty;) {
        app.put(s);
    }

    // 読み込んだ内容の解析
    auto src = textRange(app.data);
    auto result = parseText(src);

    // ふつう解析成功する
    assert(result);

    // 結果の出力。行数・単語数・バイト数
    writefln("%d %d %d", src.line, count, src.position);
}

実行結果

$ cat source/yadc/peg.d | ./parser
968 1856 20317

(結果は今後の修正に応じて変わります)

Github

今回やること

　前回まででやったのは、単純に文字列をチェックすることだけです。
　今回では、認識した文字列に応じて"何か"を行う、いわゆるセマンティック・アクションの機能を追加していきます。

やることリスト

• 行番号をカウントする
• 位置を記録する
• 一般的なアクションの実行

行番号をカウントする

　構文解析を行うためには、文字列を認識するだけでなく、認識結果に応じて何かをしなければなりません。
　今回は行番号をカウントすることを通じて、その「何か」をどこにどのように実装するか考えます。

改行を認識する

　改行を認識するパーサーを書くのは、前回までの内容で簡単に実現できます。
　CR・LFどちらにも対応した改行パーサーは下記のようになります。

unittest {
    // 改行文字を認識
    alias sel!(seq!(ch!'\r', opt!(ch!'\n')), ch!'\n') newLine;

    // 改行1つの解析
    foreach(nl; ["\r", "\n", "\r\n"] ) { 
        assert(newLine(nl) && nl.empty);
    }   

    // これは2つの改行になる
    auto s = "\n\r";
    assert(newLine(s) && s.front == '\r');
    assert(newLine(s) && s.empty);
}

改行を数える

　改行を認識することは簡単にできました。
　改行を__数える__には、どうすれば良いでしょうか？

案その1 素朴にカウントする

　ごく素朴に考えると、こうなります。

while(newLine(s)) {++line;}
// 何かの解析...
while(newLine(s)) {++line;}
// 何かの解析...
while(newLine(s)) {++line;}
// 何かの解析...

　このソリューションには下記のような問題があります。

• 改行がある場所で毎回カウントアップのコードを書くのが面倒
• 書き忘れたらバグ
• パーサー・コンビネーターの中にうまく統合できていない。

　逆に言えば、次のような仕組みができれば嬉しいことになります。

• カウントアップのコードを毎回書かなくても、改行を認識したらカウントアップしてくれる
• コードを書かないで良いので書き忘れもない
• パーサー・コンビネーターの中に統合されていて、既存のコードの延長で自然に使える。

案その2 変数をパーサーのパラメーターに渡す

　文字や文字列の認識などで、今までパーサーのテンプレートパラメーターにリテラルを渡していました。
　同じように行番号をカウントするパーサーを作って、指定した変数にカウントアップするというのはどうでしょうか。

size_t line = 0;
auto s = "¥r¥n";
addLine!(newLine, line)(s);
assert(s.empty && line == 1);

　これはなかなか良さそうです。addLineをパーサーとすることで、パーサー・コンビネーターの中に自然に統合できます。改行位置でaddLineを使うことにすれば、行のカウント漏れもなくなります。

　しかし、まだ次のような問題があります。

• 行番号の変数lineが見えるスコープでしかパーサーを作れない。
  • テンプレートパラメーターに渡しているので仕方ありません。
  • refで持ち回っても良いですが、何にせよ面倒です。
• 行番号の概念がパーサー・コンビネーターの拡張というよりは外部にあって、統合感が薄い。
  • 正直、感性の問題かもしれませんが、今回は行番号という概念を構文解析の中に導入したいわけです。それを外付けの変数でカウントさせるのはまだやっつけ感があります。

　この辺りから、構文解析器ライブラリに関するスタンスや観点によって実装に色々違いが出てきそうです。
　私は今回、次のような方法を選びました。

案その3 Rangeをデコる(君に決めた！)

　行番号のような、ソースにずっと付いて回る値は、ソース自身が値を保持しているのが自然です。
　そこで、Rangeを拡張して__行番号付きRange__を作り、それに対して操作が行えるパーサーを書いていくことにします。

　Rangeの拡張といっても、classを使った継承などではなく、templateとalias thisによる静的な継承、というより__デコレーション__を行います。
　以下がその行番号付きRangeの定義です。行数はありますが大したことのない構造体です。

/// 行番号をカウントするRange
struct LineRange(R) if(isInputRange!R) {

    /// 内部Rangeを指定して生成する
    this(R r) {inner = r;}

    /// 行番号を返す
    @property size_t line() @safe @nogc nothrow pure {return line_;}   

    /// 行番号をカウントする
    void addLine() @safe @nogc nothrow {++line_;}

    // RがForwardRangeの場合のみ実装
    static if(isForwardRange!R) {
        /// 行番号と現在位置を記録する
        @property LineRange save() {
            LineRange result;
            result.inner = inner.save;
            result.line_ = line;
            return result;
        }   
    } 

    /// その他の呼び出しは内部Rangeに任せる
    alias inner this;

    /// 内部Range
    R inner;

private:

    /// 行番号
    size_t line_;
}

/// Rangeを行番号付きRangeに変換して返すユーティリティ関数
LineRange!R lineRange(R)(R r): {
    return LineRange!R(r);
}

　さらに、行番号カウントアップパーサーを書きます。

/// 指定パーサーが解析成功したら行番号をカウントアップする
template addLine(alias P) {
    /// ditto
    bool addLine(R)(ref LineRange!R src) {
        if(P(src)) {
            src.addLine();
            return true;
        } else {
            return false;
        }
    }
}

　これで、下記のようなユニットテストが通ります。

unittest {
    auto s = "\r\n";
    auto ls = lineRange(s);

    // 最初は行番号0
    assert(ls.line == 0);

    auto ls2 = ls.save;

    // 行番号をカウントアップ
    assert(addLine!(ch!'\r')(ls));
    assert(ls.front == '\n');
    assert(ls.line == 1);

    // saveした方は変わらない
    assert(ls2.front == '\r');
    assert(ls2.line == 0);

    // 元に戻せること
    ls = ls2;
    assert(ls.front == '\r');
    assert(ls.line == 0);
}

　LineRangeは行番号がついていること以外はただのForwardRangeです。よって、そのまま今までのパーサー・コンビネーターで扱えることになります。

位置を記録する

　行番号についてはカウントできるようになりました。
　構文解析の最中には、行番号だけでなく__文字単位の位置__が分かると便利な場合があります。
　例えばファイルポインタでソースを読んでいる場合や、メモ化を行う場合のマークに使用できます。
　これも、行番号と同じようにRangeのデコレーションで実現できます。

/// 文字単位の位置を保持しているRange
struct PositionRange(R) if(isInputRange!R) {

    /// 内部Rangeを指定して生成する
    this(R r) {inner = r;}

    /// 文字単位の位置を返す
    @property size_t position() const @safe @nogc nothrow pure {
        return position_;
    }   

    // RがForwardRangeの場合のみ実装
    static if(isForwardRange!R) {
        /// 現在位置を記録する
        @property PositionRange save() {
            PositionRange result;
            result.inner = inner.save;
            result.position_ = position;
            return result;
        }   
    } 

    /// 先頭要素を破棄する
    void popFront() {
        inner.popFront();
        ++position_; // ここで位置をカウント
    }

    /// その他の呼び出しは内部Rangeに任せる
    alias inner this;

    /// 内部Range
    R inner;

private:

    /// 位置
    size_t position_;
}

/// Rangeを位置付きRangeに変換して返すユーティリティ関数
PositionRange!R positionRange(R)(R r): {
    return PositionRange!R(r);
}

組み合わせる

　今回作った行番号Range・位置Rangeは、組み合わせて使うことができます。
　というか、普通組み合わせて使いそうなので1つにまとめても良いかと思いますが、今回は直交性を重視して2つに分けておきます。
　組み合わせて使うとしたら、下記のようにaliasでデコレーションしたRangeを定義しておけば良いと思います。

/// テキスト解析用の位置・行番号を保持したRange
alias TextRange(R) = LineRange!(PositionRange!R);

/// 指定RangeをTextRangeに変換
auto textRange(R)(R src) {
    return TextRange!R(positionRange(src));
}

///
unittest {
    auto s = "test\n2test";
    auto ts = textRange(s);

    // 最初は位置0
    assert(ts.position == 0);
    assert(ts.line == 0);

    auto ts2 = ts.save;

    // testを読み込み
    assert(str!"test"(ts));
    assert(ts.position == 4);
    assert(ts.line == 0);
    assert(ts.front == '\n');

    // saveしたものは変わらない
    assert(ts2.position == 0);
    assert(ts2.line == 0);
    assert(ts2.front == 't');

    // 改行を読み込み
    assert(addLine!(ch!'\n')(ts));
    assert(ts.position == 5);
    assert(ts.line == 1);
    assert(ts.front == '2');

    // 元に戻せること
    ts = ts2;
    assert(ts.position == 0);
    assert(ts.line == 0);
    assert(ts.front == 't');
}

セマンティック・アクションを追加する

　さて、この記事の最後に一般的な__セマンティック・アクション__を実装します。
　セマンティック・アクションとは、構文解析時のチェック結果などに応じて何かしら処理(アクション)を行うことです。
　実はこれを実装すれば行番号カウントや位置カウントも行えるのですが、一般的すぎて扱いづらいので、今回はRangeをデコレーションしました。
　今回ぐらいパーサーを書いたりRangeを拡張するのが簡単であれば実質必要ないかもしれないのですが、やはりユーティリティーとしてあると便利な場面もあると思われます。

　やることは単純で、テンプレートパラメーターに関数を取り、構文解析の開始・成功・失敗でそれを呼び出すだけです。

/**
 *  Params:
 *      B = 解析開始時の処理
 *      S = 解析成功時の処理
 *      F = 解析失敗時の処理。Pでの例外発生時にも呼び出される。
 *      P = 呼び出すパーサー
 *      R = ソースの型
 *      src = ソース
 *  Returns:
 *      Pの解析結果
 */
template action(alias B, alias S, alias F, alias P) {
    /// ditto
    bool action(R)(ref R src) {
        // 解析開始
        B(src);

        // Pの呼び出し。例外発生時はFを呼んで整合性を保つ
        bool result;
        {   
            scope(failure) F(src);
            result = P(src);
        }   

        // 結果を見て解析成功・失敗のどちらかを呼ぶ
        if(result) {
            S(src);
            return true;
        } else {
            F(src);
            return false;
        }   
    }   
}

///
unittest {
    // アクションで変更する変数
    bool begin = false;
    bool success = false;
    bool fail = false;

    // リセット用
    void reset() {
        begin = false;
        success = false;
        fail = false;
    }

    // 解析開始・成功・失敗でそれぞれ変数を設定するアクション
    alias action!(
        (s) {begin = true;},
        (s) {success = true;},
        (s) {fail= true;},
        ch!'t') p;

    auto s = "test";

    // 解析成功時。beginとsuccessが設定される
    assert(p(s));
    assert(s.front == 'e');
    assert(begin);
    assert(success);
    assert(!fail);

    reset();
}

　ローカルの関数リテラルをtemplateのパラメーターに指定できるのは何とも不思議な気がしますが、D言語だとできてしまうのです。すごいですね。

次回予告

いよいよASTの構築と、PEG自身の文法の解析に入ります。