Edited at
D言語Day 23

D言語の構文を拡張する

More than 3 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]

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


動くコード

https://github.com/youxkei/swapop


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


  • C言語スタイルの宣言

  • asm文

  • 浮動小数点リテラル(!?)


既知のバグ

関数の仮引数の型にintを使うと、intとして構文解析されてしまいます。

これは、ストレージクラスinintよりも優先されているのが原因です。

D言語のパーサはgrammar.ddから自動生成したものなので、

これ以外にも、おそらくバグがあると思います。

さらに、文字列などのリテラルも、エスケープシーケンスに対応していないなど、実装がかなり適当です。


まとめ

アドベントカレンダー用にネタとして作り始めたTcenalですが、意外に時間がかかってしまいました。

現状かなり荒削りなので、その辺をどうにかしたいです。