D言語 Advent Calendar 2014の23日目の記事です。
更に、Aizu Advent Calendar 2014の23日目の記事でもあります。
D言語には文字列mixin(宣言、文、式)とCTFE(コンパイル時関数実行)という機能があります。
文字通り、文字列mixinは文字列の中身をソースコードとして展開する機能で、
CTFEはコンパイル時に関数を実行する機能です。
上の２つの機能を組み合わせて、D言語の構文を拡張できるライブラリを作りました。
TL;DR
構文拡張ライブラリ：Tcenal
Swap演算子追加の例：swapop
Tcenal
D言語の構文拡張ライブラリです。
https://github.com/youxkei/tcenal
どうやって拡張するの？
Tcenalは内部でD言語の大部分のパーサを持っていて、そのパーサをオーバーライドする形で拡張します。
その後、パースツリーからD言語のソースコードを生成して文字列mixinします。
使っている構文解析のアルゴリズム
直接左再帰に対応したPackrat Parsingを使っています。
例：Swap演算子の追加
本当はパターンマッチとかやりたかったんですが、大変そうなので・・・
dubでTcenalを使う
{
"dependencies": {
"tcenal" : "~>0.0.1"
}
}
パーサをオーバーライドする
Tcenalのviews/drules.pegを見て、パーサをオーバーライドします。
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を指定しています。
ParsingResult、ParseTreeNode、MemoはgenerateParsersが生成するコードに含まれるので、必ずimportしてください。このへんは後々どうにかしたいと思ってます。
今回はimportすることによって元々のD言語パーサのskipを使っていますが、importせずに自分で定義したskipを使うことも出来ます。
パーサをインスタンス化する
パーサは、RuleSelectorを渡してインスタンス化する必要があります。
RuleSelectorは、実際にオーバーライドの処理を行っているテンプレートです。
import tcenal.rule_selector : createRuleSelector;
import tcenal.dparsers : Module, skip;
alias parse = Module!(createRuleSelector!().RuleSelector);
とりあえず一番外側のパーサであるModuleにRuleSelectorを渡してパーサをインスタンス化してます。
createRuleSelectorをインスタンス化するモジュールが重要で、
例えばcreateRuleSelectorをインスタンス化したモジュール内にAssignExpressionが存在する場合にはそれを使い、
存在しなかった場合はtcenal.dparsers.AssignExpressionが使われます。
このようにオーバーライド的な挙動を実現しています。
パースツリーを見てみる
この時点でパースツリーを見てみます。
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を書きます。
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は大文字にしています。
試す
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を使うと、inとtとして構文解析されてしまいます。
これは、ストレージクラスinがintよりも優先されているのが原因です。
D言語のパーサはgrammar.ddから自動生成したものなので、
これ以外にも、おそらくバグがあると思います。
さらに、文字列などのリテラルも、エスケープシーケンスに対応していないなど、実装がかなり適当です。
まとめ
アドベントカレンダー用にネタとして作り始めたTcenalですが、意外に時間がかかってしまいました。
現状かなり荒削りなので、その辺をどうにかしたいです。