D言語の構文を拡張する

  • 5
    いいね
  • 1
    コメント
この記事は最終更新日から1年以上が経過しています。

D言語 Advent Calendar 2014の23日目の記事です。
更に、Aizu Advent Calendar 2014の23日目の記事でもあります。

D言語には文字列mixin(宣言)とCTFE(コンパイル時関数実行)という機能があります。
文字通り、文字列mixinは文字列の中身をソースコードとして展開する機能で、
CTFEはコンパイル時に関数を実行する機能です。
上の2つの機能を組み合わせて、D言語の構文を拡張できるライブラリを作りました。

TL;DR

構文拡張ライブラリ:Tcenal
Swap演算子追加の例:swapop

Tcenal

D言語の構文拡張ライブラリです。
https://github.com/youxkei/tcenal

どうやって拡張するの?

Tcenalは内部でD言語の大部分のパーサを持っていて、そのパーサをオーバーライドする形で拡張します。
その後、パースツリーからD言語のソースコードを生成して文字列mixinします。

使っている構文解析のアルゴリズム

直接左再帰に対応したPackrat Parsingを使っています。

例:Swap演算子の追加

本当はパターンマッチとかやりたかったんですが、大変そうなので・・・

dubでTcenalを使う

dub.json
{
    "dependencies": {
        "tcenal" : "~>0.0.1"
    }
}

パーサをオーバーライドする

Tcenalのviews/drules.pegを見て、パーサをオーバーライドします。

source/swap_op.d
import parser_combinator.parsing_result : ParsingResult;
import parser_combinator.memo : Memo;
import parser_combinator.combinators;

import tcenal.dparsers : skip;
import tcenal.dsl.generate_parsers : generateParsers;


mixin (generateParsers(`
    AssignExpression <- SwapExpression / super;
    SwapExpression <- ConditionalExpression ":=:" ConditionalExpression;
`));

PEGに似たDSLを使います。ほとんどPEGですが、セミコロンで区切る必要があります。
規則の右辺でsuperを使うことによって、元々のD言語パーサのAssignExpressionを指定しています。
ParsingResultParseTreeNodeMemogenerateParsersが生成するコードに含まれるので、必ずimportしてください。このへんは後々どうにかしたいと思ってます。
今回はimportすることによって元々のD言語パーサのskipを使っていますが、importせずに自分で定義したskipを使うことも出来ます。

パーサをインスタンス化する

パーサは、RuleSelectorを渡してインスタンス化する必要があります。
RuleSelectorは、実際にオーバーライドの処理を行っているテンプレートです。

source/swap_op.d(続き)
import tcenal.rule_selector : createRuleSelector;
import tcenal.dparsers : Module, skip;

alias parse = Module!(createRuleSelector!().RuleSelector);

とりあえず一番外側のパーサであるModuleにRuleSelectorを渡してパーサをインスタンス化してます。
createRuleSelectorをインスタンス化するモジュールが重要で、
例えばcreateRuleSelectorをインスタンス化したモジュール内にAssignExpressionが存在する場合にはそれを使い、
存在しなかった場合はtcenal.dparsers.AssignExpressionが使われます。
このようにオーバーライド的な挙動を実現しています。

パースツリーを見てみる

この時点でパースツリーを見てみます。

source/app.d
import parser_combinator.memo : Memo;
import std.stdio : writeln;
import swap_op : parse;

void main()
{
    Memo memo;
    writeln(parse("void f(){ int a,b; a :=: b; }", 0, memo).node);
}
$ dub
+-Module
  +-DeclDefs
    +-#repeat
      +-DeclDef
        +-Declaration
          +-FuncDeclaration
            +-#sequence
              +-#option
              +-BasicType
              | +-IdentifierList
              |   +-Identifier
              |     +-"void"
              +-FuncDeclarator
              | +-#sequence
              |   +-#option
              |   +-Identifier
              |   | +-"f"
              |   +-FuncDeclaratorSuffix
              |     +-#sequence
              |       +-Parameters
              |       | +-#sequence
              |       |   +-"("
              |       |   +-#option
              |       |   +-")"
              |       +-#option
              +-FunctionBody
                +-BlockStatement
                  +-#sequence
                    +-"{"
                    +-StatementList
                    | +-#sequence
                    |   +-Statement
                    |   | +-NonEmptyStatement
                    |   |   +-NonEmptyStatementNoCaseNoDefault
                    |   |     +-DeclarationStatement
                    |   |       +-Declaration
                    |   |         +-VarDeclarations
                    |   |           +-#sequence
                    |   |             +-#option
                    |   |             +-BasicType
                    |   |             | +-IdentifierList
                    |   |             |   +-Identifier
                    |   |             |     +-"int"
                    |   |             +-Declarators
                    |   |             | +-#sequence
                    |   |             |   +-DeclaratorInitializer
                    |   |             |   | +-VarDeclarator
                    |   |             |   |   +-#sequence
                    |   |             |   |     +-#option
                    |   |             |   |     +-Identifier
                    |   |             |   |       +-"a"
                    |   |             |   +-#repeat
                    |   |             |     +-#sequence
                    |   |             |       +-","
                    |   |             |       +-DeclaratorInitializer
                    |   |             |         +-VarDeclarator
                    |   |             |           +-#sequence
                    |   |             |             +-#option
                    |   |             |             +-Identifier
                    |   |             |               +-"b"
                    |   |             +-";"
                    |   +-StatementList
                    |     +-Statement
                    |       +-NonEmptyStatement
                    |         +-NonEmptyStatementNoCaseNoDefault
                    |           +-ExpressionStatement
                    |             +-#sequence
                    |               +-Expression
                    |               | +-CommaExpression
                    |               |   +-AssignExpression
                    |               |     +-SwapExpression
                    |               |       +-#sequence
                    |               |         +-ConditionalExpression
                    |               |         | +-OrOrExpression
                    |               |         |   +-AndAndExpression
                    |               |         |     +-CmpExpression
                    |               |         |       +-ShiftExpression
                    |               |         |         +-AddExpression
                    |               |         |           +-MulExpression
                    |               |         |             +-UnaryExpression
                    |               |         |               +-PowExpression
                    |               |         |                 +-PostfixExpression
                    |               |         |                   +-PrimaryExpression
                    |               |         |                     +-Identifier
                    |               |         |                       +-"a"
                    |               |         +-":=:"
                    |               |         +-ConditionalExpression
                    |               |           +-OrOrExpression
                    |               |             +-AndAndExpression
                    |               |               +-CmpExpression
                    |               |                 +-ShiftExpression
                    |               |                   +-AddExpression
                    |               |                     +-MulExpression
                    |               |                       +-UnaryExpression
                    |               |                         +-PowExpression
                    |               |                           +-PostfixExpression
                    |               |                             +-PrimaryExpression
                    |               |                               +-Identifier
                    |               |                                 +-"b"
                    |               +-";"
                    +-"}"

追加したSwapExpressionがちゃんと動いてますね!!!

パースツリーからD言語のソースコードを生成する

パースツリーなので、基本的に葉の値をつなげていけば元の文字列になります。
追加したSwapExpressionを特別に扱い、それ以外は単純に連結するようなVisitorを書きます。

source/swap_op(続き)
import parser_combinator.parse_tree_node : ParseTreeNode;

string generateVisitor(ParseTreeNode node)
{
    if (node.ruleName == "SwapExpression")
    {
        return "(){"
            "static import std.algorithm;"
            "std.algorithm.swap(" ~ node.children[0].children[0].generateVisitor() ~ ","
                                  ~ node.children[0].children[2].generateVisitor() ~ ");"
        "}()";
    }
    else if (node.ruleName.length > 0)
    {
        string codeSegment;
        foreach (child; node.children)
        {
            codeSegment ~= child.generateVisitor();
        }
        return codeSegment;
    }
    else
    {
        return node.value ~ " ";
    }
}

string SWAP_OP(string src)
{
    Memo memo;
    return parse(src, 0, memo).node.generateVisitor();
}

SwapExpressionの直下は#sequenceであることに気をつけてください。
swapの実装は、std.algorithm.swapをそのまま使っています。
マクロっぽさを出すために、SWAP_OPは大文字にしています。

試す

source/app.d
import swap_op;

mixin (SWAP_OP(q{
    void bubblesort(T)(T[] array)
    {
        foreach (base; 0 .. array.length - 1)
        {
            foreach_reverse (i; base .. array.length - 1)
            {
                if (array[i] > array[i + 1])
                {
                    array[i] :=: array[i + 1];
                }
            }
        }
    }

    void main()
    {
        import std.stdio : writeln;

        int[] array = [3, 1, 4, 1, 5, 9, 2];
        array.bubblesort();
        writeln(array);
    }
}));
$ dub
[1, 1, 2, 3, 4, 5, 9]

ちゃんと動いてます!!!!!

動くコード

https://github.com/youxkei/swapop

対応していないD言語の構文

  • C言語スタイルの宣言
  • asm文
  • 浮動小数点リテラル(!?)

既知のバグ

関数の仮引数の型にintを使うと、intとして構文解析されてしまいます。
これは、ストレージクラスinintよりも優先されているのが原因です。
D言語のパーサはgrammar.ddから自動生成したものなので、
これ以外にも、おそらくバグがあると思います。
さらに、文字列などのリテラルも、エスケープシーケンスに対応していないなど、実装がかなり適当です。

まとめ

アドベントカレンダー用にネタとして作り始めたTcenalですが、意外に時間がかかってしまいました。
現状かなり荒削りなので、その辺をどうにかしたいです。

この投稿は D言語 Advent Calendar 201423日目の記事です。