Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@youxkei

D言語の構文を拡張する

More than 5 years have passed since last update.

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]

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

動くコード

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

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

既知のバグ

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

まとめ

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

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
youxkei

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?