Zenn
Open5

C コンパイラ作成入門を参考にGoコンパイラを作成する

Go
C
assembly
compiler
低レイヤ
N9tE9N9tE9

お約束

.intel_syntax noprefix をつける
出力するアセンブラは、Intel記法を利用するため

こんなふうに作っておく

func init() {
  fmt.Printf(".intel_syntax noprefix\n")
}

コマンドライン引数で受け取った値を exit コードとして出力する

ゴールのイメージ

$ go build -o main main.go
$ ./maiin 123 > out.as
$ as -o out.o out.as
$ ld -o a.out out.o
$ ./a.out

$ echo $?
123 # コマンドライン引数で渡した値が出力される

中間で生成されるアセンブラは以下のような形で出力されれば良い

.intel_syntax noprefix
.globl main

main:
    mov rax, %d
    ret

go で実装するとこんな感じ

package main

func init() {
  fmt.Printf(".intel_syntax noprefix")
}

func main() {
  flag.Parse()
  arg := flag.Arg(0)

  
	fmt.Printf(".globl main\n")
	fmt.Printf("main:\n")
	fmt.Printf("  mov rax, %s\n", arg)
	fmt.Printf("  ret\n")
}

トークナイザを使って加減算ができるものを作る

トークナイザを導入する理由

式を柔軟に表現するため
トークンという概念を導入し、トークンに項か符号かといった識別子を付与することで、トークン → アセンブル を吐き出すといった形にする。
トークナイザは、木構造のデータ構造を返す。
トークナイザが無いとスペースやコメントアウトといったものをプログラム上で表現が難しくなる。

イメージはこんな感じ

123 + 20

↓ tokenize

123(token.Number)
↓
+(token.Reserved)
↓
20(token.Number)

↓ assemble

.intel_syntax noprefix
.globl main

main:
  mov rax, 123
  add rax, 20
  ret

go で実装するとこんな感じ

package main

import (
	"flag"
	"fmt"
	"strconv"
	"unicode"
)

func init() {
	fmt.Printf(".intel_syntax noprefix\n")
}

type Kind string

const (
	Reserved Kind = "Reserved"
	Number   Kind = "Number"
	EOF      Kind = "EOF"
)

type Token struct {
	Kind  Kind
	Value int
	Name  byte
	Next  *Token
}

func (k Kind) IsReserved() bool {
	return k == Reserved
}

func (k Kind) IsNumber() bool {
	return k == Number
}

func (k Kind) IsEOF() bool {
	return k == EOF
}

func NewToken(k Kind, v int, name byte, cur *Token) *Token {
	t := &Token{
		Kind:  k,
		Value: v,
		Name:  name,
		Next:  nil,
	}
	cur.Next = t
	return t
}

func Tokenize(src string) *Token {
	head := new(Token)
	cur := head
	i := 0
	for i < len(src) {
		if isSpace(rune(src[i])) {
			i++
			continue
		}

		if src[i] == '+' || src[i] == '-' {
			cur = NewToken(Reserved, -1, src[i], cur)
		}

		if isDigit(rune(src[i])) {
			end := getLastDigitIndex(src, i)
			v, err := strconv.Atoi(src[i:end])
			if err != nil {
				panic(err)
			}

			cur = NewToken(Number, v, src[i], cur)
			i = end
			continue
		}

		i++
	}

	NewToken(EOF, -1, byte(0), cur)

	return head.Next
}

func isSpace(o rune) bool {
	return o == ' ' || o == '\t'
}

func isDigit(o rune) bool {
	return unicode.IsDigit(o)
}

func getLastDigitIndex(src string, start int) int {
	for start < len(src) {
		if !isDigit(rune(src[start])) {
			return start
		}
		start++
	}
	return start
}

func consume(t *Token) *Token {
	return t.Next
}

func main() {
	flag.Parse()
	src := flag.Arg(0)
	t := Tokenize(src)

	fmt.Printf(".globl _main\n")
	fmt.Printf("_main:\n")
	fmt.Printf("  mov rax, %d\n", t.Value)
	t = consume(t)

	for !t.Kind.IsEOF() {
		if t.Kind.IsReserved() && t.Name == '+' {
			t = consume(t)
			fmt.Printf("  add rax, %d\n", t.Value)
			continue
		}

		if t.Kind.IsReserved() && t.Name == '-' {
			t = consume(t)
			fmt.Printf("  sub rax, %d\n", t.Value)
			continue
		}

		t = consume(t)
	}

	fmt.Printf("  ret\n")
}
N9tE9N9tE9

エラー出力するように改修する

Token にソースの解析箇所を渡すようにし、それを pos として出力するように改修した。
Token の解析では err に具体的なエラー内容を含め、errorAt でエラー箇所とエラー内容を出力する関数を作った。

具体的な実装は、以下になる。

package main

import (
	"flag"
	"fmt"
	"os"
	"strconv"
	"unicode"
)

func init() {
	fmt.Printf(".intel_syntax noprefix\n")
}

type Kind string

const (
	Reserved Kind = "Reserved"
	Number   Kind = "Number"
	EOF      Kind = "EOF"
)

type Token struct {
	Kind  Kind
	Value int
	Name  byte
	Str   string
	Next  *Token
}

func (t *Token) expectNumber() (int, error) {
	if !t.Kind.IsNumber() {
		return -1, fmt.Errorf("expected a number, but got %s", t.Kind)
	}

	return t.Value, nil
}

func (k Kind) IsReserved() bool {
	return k == Reserved
}

func (k Kind) IsNumber() bool {
	return k == Number
}

func (k Kind) IsEOF() bool {
	return k == EOF
}

func NewToken(k Kind, v int, name byte, str string, cur *Token) *Token {
	t := &Token{
		Kind:  k,
		Value: v,
		Name:  name,
		Str:   str,
		Next:  nil,
	}
	cur.Next = t
	return t
}

func Tokenize(src string) *Token {
	head := new(Token)
	cur := head
	i := 0
	for i < len(src) {
		if isSpace(rune(src[i])) {
			i++
			continue
		}

		if src[i] == '+' || src[i] == '-' {
			cur = NewToken(Reserved, -1, src[i], src[:i], cur)
		}

		if isDigit(rune(src[i])) {
			end := getLastDigitIndex(src, i)
			v, err := strconv.Atoi(src[i:end])
			if err != nil {
				panic(err)
			}

			cur = NewToken(Number, v, src[i], src[:i], cur)
			i = end
			continue
		}

		i++
	}

	NewToken(EOF, -1, byte(0), src[:i], cur)

	return head.Next
}

func isSpace(o rune) bool {
	return o == ' ' || o == '\t'
}

func isDigit(o rune) bool {
	return unicode.IsDigit(o)
}

func getLastDigitIndex(src string, start int) int {
	for start < len(src) {
		if !isDigit(rune(src[start])) {
			return start
		}
		start++
	}
	return start
}

func consume(t *Token) *Token {
	return t.Next
}

func expect(t *Token, op byte) error {
	if t.Name != byte(op) {
		return fmt.Errorf("expected %c, but got %c", op, t.Name)
	}

	return nil
}

func errorAt(src string, t *Token, err error) {
	pos := len(t.Str)
	fmt.Printf("%s\n", src)
	fmt.Printf("%*s\n", pos, "^")
	fmt.Printf("%*s\n", pos, err)
	os.Exit(1)
}

func main() {
	flag.Parse()
	src := flag.Arg(0)
	t := Tokenize(src)

	fmt.Printf(".globl _main\n")
	fmt.Printf("_main:\n")
	fmt.Printf("  mov rax, %d\n", t.Value)
	t = consume(t)

	for !t.Kind.IsEOF() {
		if t.Kind.IsReserved() && t.Name == '+' {
			t = consume(t)
			v, err := t.expectNumber()
			t = consume(t)
			if err != nil {
				errorAt(src, t, err)
			}

			fmt.Printf("  add rax, %d\n", v)
			continue
		}

		if err := expect(t, '-'); err != nil {
			errorAt(src, t, err)
			break
		}

		t = consume(t)
		v, err := t.expectNumber()
		t = consume(t)
		if err != nil {
			errorAt(src, t, err)
		}

		fmt.Printf("  sub rax, %d\n", v)
	}

	fmt.Printf("  ret\n")
}

実行例

$ go build -o a.out main.go
$ ./a.out "1+1--11---"

.intel_syntax noprefix
.globl _main
_main:
  mov rax, 1
  add rax, 1
1+1--11---
    ^
expected a number, but got Reserved
N9tE9N9tE9

再帰下降構文解析

特定の生成規則に従って構文木を生成する手法
コンパイラは、文字列 → 構文木 → アセンブラ の順序でプログラミング言語から機械語に変換するものである。
再帰下降構文解析は、文字列 → 構文木 とスタックマシンの概念とマッチする部分がある。

四則演算 → 構文木を生成するルールは以下のようになる

expr = mul (+ mul | - mul)
mul = primary (* primary | / primary)
primary = num | ( expr )

例えば、　1 + 2 * 3　だと以下のような感じ
expr = 1 (+ mul)
mul = primary1 (* primary2)
primary1 = 2
primary2 = 3

この生成規則を golang で実装する

N9tE9N9tE9

再帰下降構文分析を golang で実装してみる

グローバル変数を用意しない形にしたため、関数間でソースの受け渡しはしていたり、手続き的に consume を実装している。
テストコードは、golang のテストのエコシステムを利用し、構文木がルールを基にソースから生成したものと同様のものかを検証している。
具体的な実装は、以下のコミットにある。
https://github.com/lkeix/go-compiler/commit/78cd5154ff788cff7b8c61d323a81d1d9f16ef04