はじめに
コンパイラ本の影響か最近巷ではコンパイラ自作がブームになっていますが、GoでCのコンパイラを書くというののN番煎じをやりました。その際に「Goの持つ表現能力を限界まで引き出す」というのをやってみたかったので、専用のDSLを作りならコンパイラを書いてみました。また、単体テストしやすいモジュール設計を採用しています。
今回作ったコンパイラの内部DSLや設計の特徴は以下のようになります。
型安全なアセンブリコード生成DSL
有効なインストラクション/アセンブリコードかどうかをコンパイル時にチェックするようなDSLを作りました。
パーサーコンビネータをベースとしたコンパイラ生成DSL
パーサーコンビネータは大きなパーサーを小さなパーサーから合成していくのに使われる高階関数ですが、これを使ってコンパイラを定義したり合成したりするDSLを作りました。
単体テスト可能な"小さなコンパイラ"を組み合わせていく設計
特定の構文に対応するパーサーとコードジェネレーターが一体化されたモジュール(=小さなコンパイラ)を作り、それを単体テストで動作検証した上でコンパイラ本体へとDSLを使って合成していくような設計にしました。
コンパイラの能力
現状のコンパイラの能力ですが、例えばクイックソートの実装をコンパイルして実行することができます。
int main(){
int size; size = 30;
int array[30]; int mem[30];
setInputArray(array, size);
printArray(array, size);
qsort(array, 0, size, mem);
printArray(array, size);
return 0;
}
int qsort(int* array, int head, int tail, int* mem){
int size; size = tail - head;
if(size < 2){ return 0; }
int i;
for(i=0; i<size; i=i+1){ mem[head+i]=array[head+i]; }
int cmp; cmp = array[head];
int leftTail; leftTail = head;
int rightHead; rightHead = tail;
for(i=1; i<size; i=i+1){
int val; val = mem[head+i];
if(val<cmp) {
array[leftTail] = val;
leftTail = leftTail+1;
}
if(cmp<val+1) {
array[rightHead-1] = val;
rightHead = rightHead-1;
}
}
array[leftTail] = cmp;
qsort(array, head, leftTail, mem);
qsort(array, rightHead, tail, mem);
return 0;
}
int setInputArray(int* array, int size){
int x; x = 1; int i;
for(i = 0; i<size; i=i+1){
x = x * 20021 + 1; x = x - (x/65536)*65536;
array[i] = x - (x/size)*size;
}
return 0;
}
int printArray(int* array, int size){
int i; int v;
for(i=0;i<size;i=i+1){
v = *(array + i);
printInt(v); put(32);
}
put(10);
return 0;
}
int printInt(int n){
int div; int rem;
div = n / 10; rem = n - div*10;
if(div != 0){ printInt(div); }
put(48 + rem);
return 0;
}
int put(int c) {
syscall 1 1 &c 1;
return 0;
}
$ make exec-qsort
SRC_PATH=./examples/quick_sort.c make exec
docker-compose exec main /bin/bash -c "go run ./src < ./examples/quick_sort.c > ./tmp/out.s; gcc -o ./tmp/out.o ./tmp/out.s; ./tmp/out.o"
12 17 20 11 28 19 0 23 16 9 6 25 28 13 2 5 16 13 16 1 24 29 20 27 26 5 4 21 14 27
0 1 2 4 5 5 6 9 11 12 13 13 14 16 16 16 17 19 20 20 21 23 24 25 26 27 27 28 28 29
実装済みの機能としては、四則演算/変数宣言・呼び出し/関数定義・呼び出し/制御構文(if/for/while/return)/ポインター/ポインターの加算/配列などです。まだまだ未実装の機能も多いのですが、特に目的もない(セルフホスト出来ない)ので、一旦このへんで区切りとしました。
DSLとモジュール設計を活用した開発の流れ
DSLを使ってモジュールを書き、単体テストを行い、それをコンパイラ本体へと合成する様子を紹介します。
(1) DSLでモジュールを書く
特定の構文、例えばif文に対応するモジュールはDSLを使って以下のように定義できます。
// 構文: "if" "(" <condition> ")" "{" <body> "}" に対応するコンパイラモジュール
func ifer(condition, body *Compiler) Compiler {
// パーサーコンビネータDSLを使ってコンパイラ/パーサーの組み立てる
return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
// アセンブリコード生成ルールをアタッチする
SetEval(func(nodes []*ast.AST, code asm.Code) {
nodes[0].Eval(code)
label := fmt.Sprintf("iflabel_%d", ifcount)
// アセンブリコード生成DSLでコードを書き出す
code.Ins(
i().Pop().Rax(),
i().Cmp().Rax().Val(0),
i().Je(label))
nodes[1].Eval(code)
code.Ins(i().Label(label))
ifcount++
})
}
パーサーコンビネータDSLとアセンブリコード生成DSLが使用されており、またパーサーとコードジェネレータが一体化されたモジュールとなっています。
(2) モジュールを単体テストする
各モジュールは単体テスト用に適当にインスタンス化して構文解析やコード生成を行うことができます。
単体テストは、生成されたコードをassertしたり、生成されたコードを実行することで行います。
```go:iferをインスタンス化して実行
ifCompiler := ifer(&numInt, &numInt) // "if" "(" ")" "{" "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}")) // パースしてコードジェネレータ付きASTを返す
ast.Eval(insts) // コード生成を実行
fmt.Print(insts.Show()) // コードを表示
// =>
// push 888
// pop rax
// cmp rax, 0
// je iflabel_0
// push 999
// iflabel_0:
## (3) モジュールをコンパイラ本体へと組み込む
モジュールをコンパイラ本体へとパーサーコンビネータDSLを使って組み込みます。
```go:コンパイラ本体へのモジュールの合成
bodies = ai().Rep(oi().Or(
ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
whiler(&expr, &bodies).P(), returner(&semi).P(),
ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
ai().And(&semi, &popRax).P()).P())
この記事の構成
まずこれらのDSL/設計の仕様を紹介し、次に実装方法について紹介します。
- 仕様紹介
- 実装方法紹介
型安全なアセンブリコード生成DSL
アセンブリコードを生成する際に、専用のDSLを介することでコンパイル時に有効なインストラクションかどうかチェックできるようにしました。
例えば以下のようなアセンブリコードを生成する場合
pop rdi
pop rax
add rax, rdi
push rax
以下のようなDSLで書けます。
code.Ins(
i().Pop().Rdi(),
i().Pop().Rax(),
i().Add().Rax().Rdi(),
i().Push().Rax())
このDSLでは有効なインストラクションが書かれた時のみコンパイルが通り、それ以外はエラーになります。
code.Ins(i().Add().Rax().Rdi()) // OK
code.Ins(i().Rax().Add().Rdi()) // エラー
code.Ins(i().Rax().Rdi().Add()) // エラー
code.Ins(i().Add().Rax()) // エラー
code.Ins(i().Add()) // エラー
code.Ins(i().Rax()) // エラー
パーサーコンビネータをベースにしたコンパイラ生成DSL
コンパイラを定義したり合成するのにパーサーコンビネータを使用しています。
例えば"if" "(" <condition> ")" "{" <body> "}"という構文のパーサーは以下のように組み立てられます。
combinedPsr := ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc)
ここでfunc (Compiler) Andとfunc (Compiler) Seqはパーサーを連結するコンビネータで、前者はASTへ構文木を追加し、後者は追加をスキップします。
他のコンビネータとしては、パースに成功するパーサーを選択するfunc (Compiler) Orや
oi().Or(xxx, yyy, zzz) // <xxx> | <yyy> | <zzz>
パーサーの繰り返しからなるパーサーを作るfunc (Compiler) Repがあります。
ai().Rep(x) // ε | <x> | <x> <x> | <x> <x> <x> | ...
これらのコンビネータを使い、以下のような感じでコンパイラを組み立てることができます。
bodies = ai().Rep(oi().Or(
ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(),
whiler(&expr, &bodies).P(), returner(&semi).P(),
ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
ai().And(&semi, &popRax).P()).P())
コンパイラを単体テスト可能なモジュールを合成して作る
そもそもモジュールを単体テストしたい理由ですが、モジュール内のバグをモジュールの単体テストで潰したいからです。
機能追加をしてバグが出たときに、その原因として
- 機能追加した分のコードに誤りがあった
- 追加したコードと既存コードとの相互作用でバグが生まれた
- 追加したコードによって既存のバグが明らかになった
などが考えられますが、1のような簡単なバグを原因箇所が限定された状態(=つまりモジュール内)で補足することでつまらないミスが原因のバグへの対処を短時間で済ませられます。
コンパイラモジュールを単体テストする方法
各モジュールの型はCompilerか、Compiler型の値を生成する関数になっています。モジュールの単体テストはCompiler型の値を作った上で実行する(コンパイルさせる)ことで行えます。
小さなコンパイラnumIntを例に取るとこれは以下のように数字1つのコードから作られたトークン列をアセンブリコードへと変換します。
tokens := tokenize("10") // コード"10"をトークン列化する
ast, _ := numInt.Call(tokens) // トークン列をコンパイルしてASTを返す
ast.Eval(insts) // ASTを評価してコード生成(instsへと書き出し)
fmt.Print(insts.Show()) // 書き出されたインストラクションを表示
// =>
// push 10 // 書き出されたアセンブリコード
もっと複雑な場合、例えばif文の場合はどうするかというと以下のようなシグネチャーを持った関数iferとしてモジュールを定義します。
func ifer(condition, body *Compiler) Compiler
これは以下のような構文をコンパイルするコンパイラを出力する関数です。
"if" "(" <condition> ")" "{" <body> "}"
iferをインスタンス化して実行する場合、例えばconditionとbodyとしてnumIntを渡すと以下のようになります。
```go:iferをインスタンス化して実行
ifCompiler := ifer(&numInt, &numInt) // "if" "(" ")" "{" "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}"))
ast.Eval(insts)
fmt.Print(insts.Show())
// =>
// push 888
// pop rax
// cmp rax, 0
// je iflabel_0
// push 999
// iflabel_0:
モジュールの単体テストは単体テスト用のコンパイラを作り、生成されたコードを実行することで行なえます。
```go:生成されたコードを実行して単体テスト
func TestIfer(t *testing.T) {
for _, c := range []psrTestCase{
{
"if(0) { return 1} return 2", // コンパイル対象のコード
[]asm.Fin{}, // 期待される出力アセンブリコード(省略可能)
true, // パースに成功すること
"2", // コード実行後に`rax`に積まれている値
},
{
"if(1) { return 1} return 2",
[]asm.Fin{},
true,
"1",
},
} {
prologue, ret := prologuer(newST()), returner(&numInt)
// 単体テスト用にコンパイラを組み立てる: "if" "(" <Int> ")" "{" "return" <Int> "}"
compCode(t, ai().And(&prologue, ifer(&numInt, &ret).P(), &ret), c)
}
}
コード実行だけではなく、吐かれたアセンブリコードをassertするような単体テストもできます。
func TestWhiler(t *testing.T) {
for _, c := range []psrTestCase{
{
"while(0) { 1 }", // コンパイル対象のコード
[]asm.Fin{ // 期待される出力アセンブリコード
i().Label("while_begin_0"),
i().Push().Val(0),
i().Pop().Rax(),
i().Cmp().Rax().Val(0),
i().Je("while_end_0"),
i().Push().Val(1),
i().Jmp("while_begin_0"),
i().Label("while_end_0"),
},
true, // パースに成功すること
"",
},
} {
// "while" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
compCode(t, whiler(&numInt, &numInt), c)
}
}
DSL使ったコンパイラモジュールの定義
DSLを使ったモジュールの定義は、パーサーコンビネータDSLでコンパイラを組み立てた後に、それにコード生成ルールのアタッチをすることで行います。
DSLを使ってコンパイラモジュールを定義する様子をnumIntとiferを例に紹介します。
var numInt Compiler = ai().And(Int).
SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット
n := nodes[0].Token.Vali() // Intの値を取り出す
code.Ins(i().Push().Val(n)) // スタックへとpushするコード生成
})
func ifer(condition, body *Compiler) Compiler {
// "if" "(" <condition> ")" "{" <body> "}" をパースする、ASTへの追加はconditionとbodyだけ
return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
// nodesはconditionとbodyのASTが入っている配列
SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット
nodes[0].Eval(code) // conditionのコードを書き出し
label := fmt.Sprintf("iflabel_%d", ifcount)
// 条件分岐のコード書き出し
code.Ins(
i().Pop().Rax(), // conditionのコードが実行された結果の値をスタックからpop
i().Cmp().Rax().Val(0),
i().Je(label)) // conditionの評価結果が0ならlabelへとジャンプ
nodes[1].Eval(code) // bodyのコード書き出し
code.Ins(i().Label(label)) // ラベル書き出し
ifcount++
})
}
func (Compier) SetEvalはコード生成時に呼び出させる関数func (ast.AST) Evalをセットする関数です。SetEvalに渡す値の型は``func(nodes []*ast.AST, code asm.Code)ですが、引数のnodes`は子のASTで、`nodes`の各要素の`func (ast.AST) Eval`を適宜呼び出しながら`code`へのインストラクションの書き出しを行います。
コンパイラ本体へとモジュールを合成する
コンパイラ本体はパーサーコンビネータDSLを使ってnumIntやifer含め各モジュールがインスタンス化され合成されることで構築されます。
func Generator() Compiler {
body := func(st *SymTable) Compiler {
var term, muls, adds, expr, bodies Compiler
ptrRef := ptrDeRefer(st, lvIdenter(st).P())
val := oi().Or(rvAddrer(lvIdenter(st).P()).P(), rvIdenter(st, &ptrRef).P())
adds, muls, ptrAdd := addsubs(&muls), muldivs(&term), ptrAdder(st, &val, &expr)
term = oi().Or(
ai().And(&ptrAdd, &deRefer).P(),
&numInt, syscaller(&expr).P(), funcCaller(&expr).P(), &val, // ここでnumIntを合成
ai().Seq(LPar).And(&adds).Seq(RPar).Trans(ast.PopSingle).P())
expr = oi().Or(assigner(oi().Or(&ptrAdd, &ptrRef).P(), &expr).P(), eqneqs(&adds).P())
semi := ai().And(&expr).Seq(Semi)
bodies = ai().Rep(oi().Or(
ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
whiler(&expr, &bodies).P(), returner(&semi).P(),
ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
ai().And(&semi, &popRax).P()).P())
return ai().And(&bodies)
}
return ai().And(ai().Rep(funcDefiner(body).P()).P()).Seq(EOF)
}
型安全なアセンブリコード生成DSLの実装方法
アセンブリコードを生成するDSLは型によってコンパイル時にインストラクションの有効性をチェックしています。
例えばインストラクションmov rax, 8を書き出す以下のようなコードがあったとして、
code.Ins(i().Mov().Rax().Vali(8))
ここで型は以下のように変化しています。
i() // Ini
i().Mov() // Oped
i().Mov().Rax() // Dested
i().Mov().Rax().Vali(8) // Fin
code.Ins // func(...Fin)
Mov, Rax, Valiはそれぞれ以下のような型を持ったメソッドで、レシーバーと返り値の型の指定で"型のステートマシン"のようなものを実装しています。
func (i Ini) Mov() Oped // Ini => Oped
func (i Oped) Rax() Dested // Oped => Dested
func (i Dested) Vali(int) Fin // Dested => Fin
また、code.Insの型はfunc(...Fin)なので、未完成なインストラクションを受け付けません。
正しい順番でインストラクションが組み立てられ、Valiのようなフィニッシャーによって完成された(Fin型になった)インストラクションのみ受理されます。
実装ですが、Ini, Opend, Dested, FinはそれぞれInsのエイリアスとなっており、
type Ini Ins
type Oped Ins
type Dested Ins
type Fin Ins
Insはインストラクションを表現する構造体です。
type Ins struct {
ope Ope
dest Reg
srcI int
...
}
Movなどの実装では、構造体への値のセットと型の変換を行っています。
func (i Ini) Mov() Oped {
i.ope = OMov
return Oped(i)
}
上記は説明のために単純化している部分もあるので、実装の詳細が知りたい人はこちらを参照。
パーサーコンビネータDSLの実装方法
コンパイラの定義や組み立てで使用するDSLは、パーサーコンビネータを使って実装しています。パーサーコンビネータ(Parser Combinator)とは複数のパーサーを合成して新しいパーサーを作る高階関数です。
まずパーサーコンビネータ一般について紹介し、その後でDSLの実装方法を紹介します。
パーサーの定義
パーサーの型Parserをトークン列[]Tokenを消費して、タプル("パースに成功したか" bool, "構文木" SyntaxTree, "消費された残りのトークン列" []Token)を返す関数とします。
type Parser func([]token) (bool, SyntaxTree, []token)
トークン列[]Tokenとは、プログラムの文字列を前処理して扱いやすい形にしたもので、例えばトークンの型を以下のように定義したとして
type Token struct {
Value string
Type string
}
文字列をトークン列化する関数tokenize(string) []Tokenは以下のような処理を行います。
tokenize("1+x") => []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}
構文木SyntaxTreeはトークン列をパースした結果得られるもので、プログラムを木構造で表現するものです。構文木から余計な枝を落としたものが抽象構文木(Abstract Syntax Tree)=ASTで、ASTをトラバースする(舐める)ことでコード生成が行われます。
パーサーがトークン列を消費して構文木を返す例です。
tokens := []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}
ok, st, rest := intParser(tokens) // パースを実行
// ok => true : パースに成功
// st => Int型の1つの値(=1)を表現する構文木
// rest => []Token{{"+", "Operator"}, {"x", "Variable"}} : `Token{"1", "Int"}`が消費されている
ok, _, _ = intParser(rest) // 続けてパースを実行
// ok => false : パースに失敗
パーサーコンビネータの定義
パーサーコンビネータとは、複数のパーサーを合成して新しいパーサーを返す関数です。
基本的な合成の仕方には二通りあり、1つは合成元のパーサーが受理するトークン列を連結したものを受け付けるパーサーを作るような合成で、もう1つは合成元のパーサーのどれか1つがパースに成功すれば、それを選択するような合成方法です。
andCombinedParser ::= leftParser rightParser // 連結的な合成(連結されたトークン列を受理する)
orCombinedParser ::= leftParsr | rightParser // 並列的な合成(受理に成功するパーサーを選ぶ)
合成元のパーサーleftParseとrightParserをそれぞれトークン列leftTokensとrightTokensを消費して、構文木leftSyntaxTreeとrightSyntaxTreeを返すものだとします。
ok, leftSyntaxTree, leftRest := leftParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest
ok, rightSyntaxTree, rightRest := rightParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest
このとき連結的な合成を行うパーサーコンビネータandParserCombinatorはleftParserとrightParserを合成し新しいパーサーcombinedParserを返します。combinedParserはleftTokensとrightTokensを連結したトークン列を先頭に持つトークン列をパースできます。
combinedParser := andParserCombinator(leftParser, rightParser) // パーサーの合成
combinedTokens := append(append(leftTokens, rightTokens...), Rest...) // トークン列の連結
ok, combinedSyntaxTree, rest := combinedParser(combinedTokens) // 連結されたトークン列をパースできる
// ok => true
// combinedSyntaxTree => Combine(leftSyntaxTree, rightSyntaxTree)
// rest => Rest
合成されたパーサーcombinedParserはそれぞれのパーサーが消費するトークン列の連結append(leftTokens, rightTokens...)を消費し、合成された構文木Combine(leftSyntaxTree, rightSyntaxTree)を返します。構文木の合成Combineはパーサーコンビネータとはあまり関係ないのですが、例えば片方の構文木の子ノードにもう片方を加えるなどをして返す関数です(実装の都合に寄ります)。
並列的な合成を行うパーサーコンビネータorParserCombinatorは２つパーサーの能力を合わせたようなパーサーを合成します。
combinedParser := orParserCombinator(leftParser, rightParser) // パーサーの合成
// leftParserと同じパースが可能
ok, leftSyntaxTree, leftRest := combinedParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest
// rightParserと同じパースが可能
ok, rightSyntaxTree, rightRest := combinedParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest
パーサーコンビネータの実装方法
andParserCombinatorとorParserCombinatorはそれぞれ戻り値のパーサーをクロージャーとして作る以下のような関数として実装できます。
func andParserCombinator(leftParser, rightParser Parser) Parser {
return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す
// 最初にleftParserを実行
ok, leftSyntaxTree, restTokens := leftParser(tokens)
if !ok {
return false, nil, nil // パースに失敗したらリターンする
}
// 続けてrightParserを実行(引数にrestTokensを渡しているのに注意)
ok, rightSyntaxTree, restOfRestTokens := rightParser(restTokens)
if !ok {
return false, nil, nil // パースに失敗したらリターンする
}
// 両方のパーサーに消費されたトークン列restOfRestTokensを返す
return true, Combine(leftSyntaxTree, rightSyntaxTree), restOfRestTokens
}
}
func orParserCombinator(leftParser, rightParser Parser) Parser {
return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す
// 最初にleftParserを実行
if ok, leftSyntaxTree, restTokens := leftParser(tokens); ok
return true, leftSyntaxTree, restTokens // パースに成功したらリターンする
}
// leftParserが失敗したらrightParserを実行
if ok, rightSyntaxTree, restTokens := rightParser(tokens); ok
return true, rightSyntaxTree, restTokens // パースに成功したらリターンする
}
// 両方のパーサーとも失敗したらパース失敗
return false, nil, nil
}
}
パーサーコンビネータを使ったDSLの実装
パーサーを合成するメソッドfunc (Parser) Andとfunc (Parser) Orですが、上記で説明したパーサーコンビネータのほぼそのままで、変更点としては、
- パーサーを構造体の中に関数
Parser.Callとして入れている(メソッドチェーンしたかったため) -
func (ast.AST) AppendNodeによって構文木の合成(子ノードとして追加)を行っている - パースの失敗を型
ast.ASTの定数ast.Failを返すことで表現している -
Andは構文木をASTに追加するかどうか引数addNodeで選択できる - 繰り返し合成
Repはパースに失敗するまでAndと同じ操作を繰り返す
などです。
// lhspがleftParser, rhspはrightParser, addNodeでASTへ追加するか選択
func (lhsp Parser) And(rhsp *Parser, addNode bool) Parser {
call := func(t []tok.Token) (ast.AST, []tok.Token) {
lhs, lhst := lhsp.Call(t)
if lhs.Fail() {
return ast.Fail, t // パースに失敗したのでリターン
}
rhs, rhst := rhsp.Call(lhst)
if rhs.Fail() {
return ast.Fail, t // パースに失敗したのでリターン
}
if addNode {
lhs.AppendNode(rhs) // 構文木の合成
}
return lhs, rhst
}
return Parser{Call: call} // 構造体`Parser`に包んで返す
}
func (lhsp Parser) Or(rhsp *Parser) Parser {
call := func(t []tok.Token) (ast.AST, []tok.Token) {
if lhs, lhst := lhsp.Call(t); !lhs.Fail() {
return lhs, lhst // パースに成功したのでリターン
}
if rhs, rhst := rhsp.Call(t); !rhs.Fail() {
return rhs, rhst // パースに成功したのでリターン
}
return ast.Fail, t // パースに失敗
}
return Parser{Call: call}
}
func (lhsp Parser) Rep(rhsp *Parser) Parser {
call := func(rest []tok.Token) (ast.AST, []tok.Token) {
var node ast.AST
lhs, lhst := lhsp.Call(rest)
if lhs.Fail() {
return lhs, rest
}
node, rest = lhs, lhst
for { // パースに失敗するまで繰り返す
rhs, rhst := rhsp.Call(rest)
if rhs.Fail() {
return node, rest // パースに失敗したら1つ前の結果をリターン
}
rest = rhst
node.AppendNode(rhs)
}
}
return Parser{Call: call}
}
これらをCompilerの型を返すようにラップしたものが実際に使用するDSLとなります。
func (c Compiler) And(cps ...*Compiler) Compiler {
for _, cp := range cps {
c = Compiler(p(c).And(pp(cp), true))
}
return c
}
func (c Compiler) Seq(cps ...*Compiler) Compiler {
for _, cp := range cps {
c = Compiler(p(c).And(pp(cp), false))
}
return c
}
func (c Compiler) Or(cps ...*Compiler) Compiler {
for _, cp := range cps {
c = Compiler(p(c).Or(pp(cp)))
}
return c
}
func (c Compiler) Rep(cp *Compiler) Compiler {
return Compiler(p(c).Rep(pp(cp)))
}
ASTからコードを生成するまでの流れ
コンパイラが返すASTにはコードジェネレーターが付属しており、このジェネレーターfunc (AST) Evalを呼ぶことでコードが生成されますが、この仕組について説明します。
コンパイラがトークン列をパースしてアセンブリコードを生成するプロセスは以下のようになりますが、
ast, _ := compiler.Call(tokens) // トークン列をパースしてASTを返す
ast.Eval(insts) // astを評価してコード生成(instsへ書き出し)
ここでコード生成を行っているastのメソッドfunc (ast.AST) Evalは以下のように定義されています。Evalは子ノードのASTのEvalを再帰的に呼び出してAST全体をトラバースすることでコードを生成します。
func (a AST) Eval(code asm.Code) {
if a.eval == nil {
for _, node := range a.nodes {
node.Eval(code) // もしevalがnilなら子のASTを評価する
}
} else {
a.eval(a.nodes, code) // evalがセットされていたらそれを評価
}
}
ここでコードジェネレータevalや子ノードnodesは構造体ast.ASTのフィールドです。
type AST struct {
nodes []*AST // 子ノード
eval func(nodes []*AST, code asm.Code) // コードジェネレータ
...
}
コードジェネレータevalが受け取る2つの引数のうちの1つcodeはfunc (ast.AST) Evalから渡されます。
もう1つの引数nodesはコンパイラを組み立てる要素、つまりAndの引数に渡されるコンパイラの返すASTを配列にしたものです。
例えばASTとしてast1、ast2を返すようなコンパイラcomp1、comp2があったとして、それらの合成
ai().And(comp1, comp2)
が返すASTは、ast.AST.nodesとしてast1とast2をアペンドしたものとなります。
ast, _ := ai().And(comp1, comp2).Call(tokens)
ast.nodes // => []ast.AST{ast1, ast2}
ast.Evalを呼ぶとast.evalがnilの場合コードジェネレータast1.Evalとast2.Evalが順番に呼びされることになります。
一方で独自のコードジェネレータast.evalがセットされている場合はそれを使ってコード生成が行われます。
構造体ast.ASTのフィールドevalに値をセットするのがメソッドfunc (Compiler) SetEvalです。
var c = ai().And(comp1, comp2).
SetEval(func(nodes []*ast.AST, code asm.Code) {
nodes[0].Eval(code) // comp1の返したASTのEvalを呼び出す
nodes[1].Eval(code) // comp2の返したASTのEvalを呼び出す
code.Ins(i().Push().Rax()) // 独自のコードを書き出す
})
func (Compiler) SetEvalの実装ですが、アイディアとしては以下のような感じです。
func (c Compiler) SetEval(eval func(nodes []*ast.AST, code asm.Code)) Compiler {
call := func(t []tok.Token) (ast.AST, []tok.Token) {
ast, rest := c.Call(t)
ast.eval = eval // 戻り地のASTに介入してevalをセットしている
return f(ast), rest
}
return Compiler{Call: call}
}
このDSLや設計を採用した感想
- 良かった点
このような設計にしたそもそもの目的は、バグを事前に、あるいは出来るだけ速い段階で潰すことで、これについては成功したと思います。
なぜバグを抑えたかったかというと、コンパイラのような比較的複雑なコードを書く場合、バグを潰すのにかかる時間が最も開発時間の多くを占めるだろうと考えられたからです。
DSLにはコードの表現能力を「制限する」ことで有効でないコード=バグったコードはそもそも書けないようにする効果があります。またロジックをシンプルに書けるので、その意味でもバグが混入しにくくなったのではないかと思います。
実際、DSLを使ってモジュールを書き、単体テストを通した段階でほとんどすべてのバグは潰せてたと思います。本体へとモジュールを合成した後の結合テストでバグが出る場合もありましたが、ここで出てくるバグは本質的に根深いもの、アルゴリズムや実装の根本的なあやまりに起因するものが多かったような気がします。そういったバグはどっちにしても時間を掛けて解決する必要/価値のあるものだったと思います。
- 悪かった点
DSLの設計で想定していなかったケース、モジュール間での情報のやり取りをさせるのに苦労しました。
モジュール間の関係性は「コード実行時にスタックに何個値を積むか」だけで、各モジュールはお互いのことを知りません。なので、モジュール間で情報のやり取りをさせる必要があるケース、たとえばポインターの足し算で、足される変数の型を変数モジュールから足し算モジュールへと伝えるのが素朴にはできません。
最終的にはシンボルテーブルを使うことである程度解消されましたが、モジュール間の情報のやり取りをサポートする基本的な仕組みを用意する必要があったのかも知れません。
DSLで開発プロセスを固めると、うまく行っている内はとてもうまくいくが、DSLで扱えないものが出てくると途端に面倒くさくなり、その意味でDSLの設計は根本的に難しいのかも知れません。