内部DSLとモジュール設計で作るGoによるCのコンパイラ

# はじめに

[コンパイラ本](https://www.sigbus.info/compilerbook)の影響か最近巷ではコンパイラ自作がブームになっていますが、GoでCのコンパイラを書くというののN番煎じをやりました。その際に「Goの持つ表現能力を限界まで引き出す」というのをやってみたかったので、専用のDSLを作りならコンパイラを書いてみました。また、単体テストしやすいモジュール設計を採用しています。


今回作ったコンパイラの内部DSLや設計の特徴は以下のようになります。

**型安全なアセンブリコード生成DSL**

有効なインストラクション/アセンブリコードかどうかをコンパイル時にチェックするようなDSLを作りました。

**パーサーコンビネータをベースとしたコンパイラ生成DSL**

パーサーコンビネータは大きなパーサーを小さなパーサーから合成していくのに使われる高階関数ですが、これを使ってコンパイラを定義したり合成したりするDSLを作りました。

**単体テスト可能な"小さなコンパイラ"を組み合わせていく設計**

特定の構文に対応するパーサーとコードジェネレーターが一体化されたモジュール(=小さなコンパイラ)を作り、それを単体テストで動作検証した上でコンパイラ本体へとDSLを使って合成していくような設計にしました。

**[コンパイラのリポジトリ](https://github.com/sxarp/c_compiler_go)**

## コンパイラの能力

現状のコンパイラの能力ですが、例えばクイックソートの実装をコンパイルして実行することができます。

```c:クイックソートのコード
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;
}
```

[コンパイル対象のコード](https://github.com/sxarp/c_compiler_go/blob/master/examples/quick_sort.c)




```sh:コンパイル&実行
$ 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を使って以下のように定義できます。

```go:if文のモジュールiferの定義
// 構文: "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" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
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](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#%E5%9E%8B%E5%AE%89%E5%85%A8%E3%81%AA%E3%82%A2%E3%82%BB%E3%83%B3%E3%83%96%E3%83%AA%E3%82%B3%E3%83%BC%E3%83%89%E7%94%9F%E6%88%90dsl)
  - [パーサーコンビネータをベースにしたコンパイラ生成DSL](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#%E3%83%91%E3%83%BC%E3%82%B5%E3%83%BC%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF%E3%82%92%E3%83%99%E3%83%BC%E3%82%B9%E3%81%AB%E3%81%97%E3%81%9F%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E7%94%9F%E6%88%90dsl)
  - [コンパイラを単体テスト可能なモジュールを合成して作る](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%92%E5%8D%98%E4%BD%93%E3%83%86%E3%82%B9%E3%83%88%E5%8F%AF%E8%83%BD%E3%81%AA%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%82%92%E5%90%88%E6%88%90%E3%81%97%E3%81%A6%E4%BD%9C%E3%82%8B)
- 実装方法紹介
  - [型安全なアセンブリコード生成DSLの実装方法](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#%E5%9E%8B%E5%AE%89%E5%85%A8%E3%81%AA%E3%82%A2%E3%82%BB%E3%83%B3%E3%83%96%E3%83%AA%E3%82%B3%E3%83%BC%E3%83%89%E7%94%9F%E6%88%90dsl%E3%81%AE%E5%AE%9F%E8%A3%85%E6%96%B9%E6%B3%95)
  - [パーサーコンビネータDSLの実装方法](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#%E3%83%91%E3%83%BC%E3%82%B5%E3%83%BC%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BFdsl%E3%81%AE%E5%AE%9F%E8%A3%85%E6%96%B9%E6%B3%95)
  - [ASTからコードを生成するまでの流れ](https://qiita.com/sxarp/items/e1ee0b25664ac932ee5f#ast%E3%81%8B%E3%82%89%E3%82%B3%E3%83%BC%E3%83%89%E3%82%92%E7%94%9F%E6%88%90%E3%81%99%E3%82%8B%E3%81%BE%E3%81%A7%E3%81%AE%E6%B5%81%E3%82%8C)

# 型安全なアセンブリコード生成DSL

アセンブリコードを生成する際に、専用のDSLを介することでコンパイル時に有効なインストラクションかどうかチェックできるようにしました。

例えば以下のようなアセンブリコードを生成する場合

```
pop rdi
pop rax
add rax, rdi
push rax
```

以下のようなDSLで書けます。

```go
code.Ins(
	i().Pop().Rdi(),
	i().Pop().Rax(),
	i().Add().Rax().Rdi(),
	i().Push().Rax())
```

このDSLでは有効なインストラクションが書かれた時のみコンパイルが通り、それ以外はエラーになります。

```go
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

コンパイラを定義したり合成するのに[パーサーコンビネータ](https://en.wikipedia.org/wiki/Parser_combinator)を使用しています。

例えば`"if" "(" <condition> ")" "{" <body> "}"`という構文のパーサーは以下のように組み立てられます。

```go
combinedPsr := ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc)
```

ここで`func (Compiler) And`と`func (Compiler) Seq`はパーサーを連結するコンビネータで、前者はASTへ構文木を追加し、後者は追加をスキップします。

他のコンビネータとしては、パースに成功するパーサーを選択する`func (Compiler) Or`や

```go
oi().Or(xxx, yyy, zzz) // <xxx> | <yyy> | <zzz>
```

パーサーの繰り返しからなるパーサーを作る`func (Compiler) Rep`があります。

```go
ai().Rep(x) // ε | <x> | <x> <x> | <x> <x> <x> | ...
```

これらのコンビネータを使い、以下のような感じでコンパイラを組み立てることができます。

```go
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. 機能追加した分のコードに誤りがあった
2. 追加したコードと既存コードとの相互作用でバグが生まれた
3. 追加したコードによって既存のバグが明らかになった

などが考えられますが、1のような簡単なバグを原因箇所が限定された状態(=つまりモジュール内)で補足することでつまらないミスが原因のバグへの対処を短時間で済ませられます。

## コンパイラモジュールを単体テストする方法

各モジュールの型は`Compiler`か、`Compiler`型の値を生成する関数になっています。モジュールの単体テストは`Compiler`型の値を作った上で実行する(コンパイルさせる)ことで行えます。

小さなコンパイラ`numInt`を例に取るとこれは以下のように数字1つのコードから作られたトークン列をアセンブリコードへと変換します。

```go:
tokens := tokenize("10")      // コード"10"をトークン列化する
ast, _ := numInt.Call(tokens) // トークン列をコンパイルしてASTを返す
ast.Eval(insts)               // ASTを評価してコード生成(instsへと書き出し)
fmt.Print(insts.Show())       // 書き出されたインストラクションを表示
// =>
//         push 10  // 書き出されたアセンブリコード
```

もっと複雑な場合、例えばif文の場合はどうするかというと以下のようなシグネチャーを持った関数`ifer`としてモジュールを定義します。

```go
func ifer(condition, body *Compiler) Compiler
```

これは以下のような構文をコンパイルするコンパイラを出力する関数です。

```xml
"if" "(" <condition> ")" "{" <body> "}"
```

`ifer`をインスタンス化して実行する場合、例えば`condition`と`body`として`numInt`を渡すと以下のようになります。

```go:`ifer`をインスタンス化して実行
ifCompiler := ifer(&numInt, &numInt) // "if" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
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するような単体テストもできます。

```go:想定通りのコードが生成されているか単体テスト
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)
	}
}
```

[他の単体テストの例はこちら](https://github.com/sxarp/c_compiler_go/blob/master/src/gen/generator_test.go)

## DSL使ったコンパイラモジュールの定義

DSLを使ったモジュールの定義は、パーサーコンビネータDSLでコンパイラを組み立てた後に、それにコード生成ルールのアタッチをすることで行います。

DSLを使ってコンパイラモジュールを定義する様子を`numInt`と`ifer`を例に紹介します。

```go:
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`含め各モジュールがインスタンス化され合成されることで構築されます。

```go:コンパイラ本体の組み立て
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)
}
```

[コンパイラ本体の定義](https://github.com/sxarp/c_compiler_go/blob/0f2e5a0005841184d0164857cafd4e7c01967ec7/src/gen/generator.go#L505-L530)

# 型安全なアセンブリコード生成DSLの実装方法

アセンブリコードを生成するDSLは型によってコンパイル時にインストラクションの有効性をチェックしています。

例えばインストラクション`mov rax, 8`を書き出す以下のようなコードがあったとして、

```go
code.Ins(i().Mov().Rax().Vali(8))
``` 

ここで型は以下のように変化しています。

```go
i()                     // Ini
i().Mov()               // Oped
i().Mov().Rax()         // Dested
i().Mov().Rax().Vali(8) // Fin
code.Ins                // func(...Fin)
```

`Mov, Rax, Vali`はそれぞれ以下のような型を持ったメソッドで、レシーバーと返り値の型の指定で"型のステートマシン"のようなものを実装しています。

```go
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`のエイリアスとなっており、

```go
type Ini Ins
type Oped Ins
type Dested Ins
type Fin Ins
```

`Ins`はインストラクションを表現する構造体です。

```go
type Ins struct {
        ope  Ope
        dest Reg
        srcI int
        ...
}
```

`Mov`などの実装では、構造体への値のセットと型の変換を行っています。

```go
func (i Ini) Mov() Oped {
	i.ope = OMov 
	return Oped(i)
}
```

上記は説明のために単純化している部分もあるので、実装の詳細が知りたい人は[こちら]()を参照。

# パーサーコンビネータDSLの実装方法

コンパイラの定義や組み立てで使用するDSLは、パーサーコンビネータを使って実装しています。[パーサーコンビネータ(Parser Combinator)](https://en.wikipedia.org/wiki/Parser_combinator)とは複数のパーサーを合成して新しいパーサーを作る高階関数です。

まずパーサーコンビネータ一般について紹介し、その後でDSLの実装方法を紹介します。

## パーサーの定義

パーサーの型`Parser`をトークン列`[]Token`を消費して、タプル`("パースに成功したか" bool, "構文木" SyntaxTree, "消費された残りのトークン列" []Token)`を返す関数とします。

```go
type Parser func([]token) (bool, SyntaxTree, []token)
```

トークン列`[]Token`とは、プログラムの文字列を前処理して扱いやすい形にしたもので、例えばトークンの型を以下のように定義したとして

```go
type Token struct {
	Value string
	Type  string
}
```
文字列をトークン列化する関数`tokenize(string) []Token`は以下のような処理を行います。

```go
tokenize("1+x") => []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}
```

構文木`SyntaxTree`はトークン列をパースした結果得られるもので、プログラムを木構造で表現するものです。構文木から余計な枝を落としたものが抽象構文木(Abstract Syntax Tree)=ASTで、ASTをトラバースする(舐める)ことでコード生成が行われます。

パーサーがトークン列を消費して構文木を返す例です。

```go:Int型を受け付けるパーサーintParserの例
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`を返すものだとします。

```go
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`を連結したトークン列を先頭に持つトークン列をパースできます。

```go
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`は２つパーサーの能力を合わせたようなパーサーを合成します。

```go
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`はそれぞれ戻り値のパーサーをクロージャーとして作る以下のような関数として実装できます。

```go
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`と同じ操作を繰り返す

などです。


```go:
// 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}
}
```

[パーサーコンビネータの定義ファイル](https://github.com/sxarp/c_compiler_go/blob/master/src/psr/parser.go)

これらを`Compiler`の型を返すようにラップしたものが実際に使用するDSLとなります。

```go
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)))
}
```

[ラッパーの定義ファイル](https://github.com/sxarp/c_compiler_go/blob/master/src/gen/psr_wrapper.go)

# ASTからコードを生成するまでの流れ

コンパイラが返すASTにはコードジェネレーターが付属しており、このジェネレーター`func (AST) Eval`を呼ぶことでコードが生成されますが、この仕組について説明します。

コンパイラがトークン列をパースしてアセンブリコードを生成するプロセスは以下のようになりますが、

```go
ast, _ := compiler.Call(tokens) // トークン列をパースしてASTを返す
ast.Eval(insts)                 // astを評価してコード生成(instsへ書き出し)
```

ここでコード生成を行っている`ast`のメソッド`func (ast.AST) Eval`は以下のように定義されています。`Eval`は子ノードのASTの`Eval`を再帰的に呼び出してAST全体をトラバースすることでコードを生成します。


```go:
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が定義されているコード](https://github.com/sxarp/c_compiler_go/blob/051d4bc9fd7d760d1120827508977406ae0dc521/src/ast/ast.go#L67)

ここでコードジェネレータ`eval`や子ノード`nodes`は構造体`ast.AST`のフィールドです。

```go:
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`があったとして、それらの合成

```go
ai().And(comp1, comp2)
```

が返すASTは、`ast.AST.nodes`として`ast1`と`ast2`をアペンドしたものとなります。

```go
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`です。

```go: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`の実装ですが、アイディアとしては以下のような感じです。

```go
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}
}
```

[実際に`SetEval`を定義しているコード。](https://github.com/sxarp/c_compiler_go/blob/0f2e5a0005841184d0164857cafd4e7c01967ec7/src/psr/parser.go#L150-L155)

# このDSLや設計を採用した感想

* 良かった点

このような設計にしたそもそもの目的は、バグを事前に、あるいは出来るだけ速い段階で潰すことで、これについては成功したと思います。

なぜバグを抑えたかったかというと、コンパイラのような比較的複雑なコードを書く場合、バグを潰すのにかかる時間が最も開発時間の多くを占めるだろうと考えられたからです。

DSLにはコードの表現能力を「制限する」ことで有効でないコード=バグったコードはそもそも書けないようにする効果があります。またロジックをシンプルに書けるので、その意味でもバグが混入しにくくなったのではないかと思います。

実際、DSLを使ってモジュールを書き、単体テストを通した段階でほとんどすべてのバグは潰せてたと思います。本体へとモジュールを合成した後の結合テストでバグが出る場合もありましたが、ここで出てくるバグは本質的に根深いもの、アルゴリズムや実装の根本的なあやまりに起因するものが多かったような気がします。そういったバグはどっちにしても時間を掛けて解決する必要/価値のあるものだったと思います。


* 悪かった点

DSLの設計で想定していなかったケース、モジュール間での情報のやり取りをさせるのに苦労しました。

モジュール間の関係性は「コード実行時にスタックに何個値を積むか」だけで、各モジュールはお互いのことを知りません。なので、モジュール間で情報のやり取りをさせる必要があるケース、たとえばポインターの足し算で、足される変数の型を変数モジュールから足し算モジュールへと伝えるのが素朴にはできません。
最終的にはシンボルテーブルを使うことである程度解消されましたが、モジュール間の情報のやり取りをサポートする基本的な仕組みを用意する必要があったのかも知れません。

DSLで開発プロセスを固めると、うまく行っている内はとてもうまくいくが、DSLで扱えないものが出てくると途端に面倒くさくなり、その意味でDSLの設計は根本的に難しいのかも知れません。