(575)
はじめに
こんにちは、unifarといいます。
Androidアプリを七個ぐらい作った。
随分前に、ruiさんの低レイヤを知りたい人のためのcコンパイラ作成入門
を読んで「これなら作れそう!」と思い、大胆にも、Cコンパイラ作成入門を読んでKotlinコンパイラを作成し始めてしまった。
それから、
195日が過ぎ、
112コミットが積まれ、
本体は1827行になり、
私の受験勉強はいよいよ終盤に差し掛かかった。
そして、現状がこちら(github)。
今現在動かせるのはこんな感じ
//まあまあ複雑なテストコード
class TestClass(n) {
val a = 4
fun get42(m): Int {
return n + m + a
}
}
fun func(x): TestClass {
val instance = TestClass(x)
return instance
}
fun main(): Int {
val instance = func(26)
return instance.get42(12)
} //->42
//フィボナッチ数列
fun fib(n): Int {
if (n == 1) {
return 1
}
if (n == 2) {
return 1
}
return fib(n - 1) + fib(n - 2)
}
fun main(): Int {
return fib(5) //->5
}
最初の内は「セルフホストしてやんよ!」と思っていたが、次第に雲行きが怪しくなり、他に作りたいものも出来て、一旦開発を止めることにした。しかし、ここまでの開発でも多くのことを学べた。例えば、再帰下降分析、アセンブラでのmain、加算、関数、文字の実装、など。ここからは、具体的な作成方法をコミットを追って解説していく。
1コミット目
fun main() {
val input = readLine()
println(input?.let { parse(it) })
}
fun parse(likScript: String): String {
val tokens = tokenize(likScript)
return "default"
}
fun tokenize(str: String): List<Token> {
val spaceRemoved = str.split(space)
var temporaryNumberList = mutableListOf<String>()
val resultList = mutableListOf<Token>()
spaceRemoved.forEach { char: String ->
if (!(numbers.contains(char))) {
resultList.add(Token(TokenType.NUMBER, numberList2number(temporaryNumberList)))
temporaryNumberList = mutableListOf()
}
if (operators.contains(char)) {
resultList.add(
when (char) {
plus -> Token(TokenType.PLUS)
minus -> Token(TokenType.MINUS)
multiply -> Token(TokenType.MULTIPLY)
divide -> Token(TokenType.DIVIDE)
else -> Token(TokenType.NULL)//絶対来ない
}
)
return@forEach
}
if (numbers.contains(char)) {
temporaryNumberList.add(char)
return@forEach
}
}
return resultList
}
fun numberList2number(list: List<String>): Int {
val buffer = StringBuilder()
list.forEach {
buffer.append(it)
}
return Integer.parseInt(buffer.toString())
}
これは主に入力を分解する関数（1+3 ->1,+,3)。
書き忘れていたけど、このKotlinもどき言語は、KotlinのKとLとIを並び替えて、Likという名前にしてある(どう発音するんだろうね？)。
本家のファーストコミットとはだいぶ違い、はなからCコンパイラ作成入門に従っていないのが分かる。
(最初はインタープリタを作るつもりだった)
4コミット目
fun parseAdd(innerList: List<Token>): Int? {
var cursor = 0
innerList[cursor].value ?: run {
throw IllegalArgumentException("first element must be number")
}
var result = innerList[cursor].value!!
cursor++
while (innerList.size - 1 > cursor)
if (innerList[cursor].type == TokenType.PLUS) {
cursor++
innerList[cursor].value?.let {
result += it
cursor++
}
} else if (innerList[cursor].type == TokenType.MINUS) {
cursor++
innerList[cursor].value?.let {
result -= it
cursor++
}
}
return result
}
これは加算のトークン列を受け取って結果をかえす関数(21 ,+ ,4 ,- ,2 -> 23 )
久々にこのコードを見たが、把握するのに結構時間がかかった。
おそらくこれはあまり良くないコードなのだろう。
しかし、コンパイラになる気配がない。
20コミット目
fun main() {
val input = mutableListOf<String>()
var next = readLine()
while (next != "***") {
input.add(next!!)
next = readLine()
}
println(".intel_syntax noprefix")
println(".global main")
println("main:")
println(" mov rax, ${input[0]}")
println(" ret")
}
20コミット目にしてやっとアセンブリが出てきた。今まで何をやっていたんだ。(本当はインタープリターとしてif文くらいまで実装していた)。
これは「標準入力から受け取った数字を返却するアセンブリ」を出力するプログラム。
Kotlinプログラムは内部でアセンブラに変換され実行される。
解説すると、
println(".intel_syntax noprefix")
訳↑「これからintel記法を使うよ～」
- アセンブラにはintel記法とAT&T記法がある
println(".global main")
訳↑「main関数を公開するよ～」
- アセンブラもmainから実行される
println("main:")
訳↑「main関数 はっじまっるよ～～」
println(" mov rax, ${input[0]}")
訳↑「raxレジスタにinput[0]を入れるよ～」
- アセンブラではレジスタという場所に値を保管する
- raxはレジスタの名前
- ${input[0]}はテンプレート記法
- mov x, y はyをxに入れる、というアセンブラの命令
- 行頭を開けないと特殊な文として解釈される
- 開けると普通の命令
println(" ret")
訳↑「撤退するよ～」
(ret命令で関数から抜ける際raxの値が戻り値となる)
という感じ。
コンパイラと聞くと難しそうな感じがするが、これもコンパイラの一種だと(私は)思う。
34コミット目
fun printAssembly() {
when (token.type) {
PLUS -> {
println(" push ${leftNode!!.token.value}")
println(" push ${rightNode!!.token.value}")
println(" pop rdi")
println(" pop rax")
println(" add rax, rdi")
}
NUMBER -> {
println(" mov rax, ${token.value}")
}
}
}
このprintAssebmly関数はNodeクラスの関数である。Nodeはtokenを本体として持っている。
これはアセンブラのmain関数の中身を出力する部分。3+4とかのコードがコンパイルできるようになった。
そろそろ疲れたので、解説はこれでおしまいにする。
前提としては、
- アセンブラでもスタックが利用できる
- push x はxの値をpushする
- pop x はスタックトップの値をxに入れる
- add x, yはx+yの結果をxのレジスタに代入する
- x + yは内部で↓のような構造になっている
.......x
.../
+
...\
.......y （わかりずらいね）
要するに、+ノードを親として左右にx,yという値を子として持っているということである。
(実は、1コミット目のトークン化する関数は、このような木構造を作るための下準備でもあった。)
ここでは、左右のノードの値をpushして、raxとrdiレジスタにそれぞれ保存(pop)、そして両者を加算し(add)、raxに値を保管する(自動的に保存される)、ということをやっている。この後ret命令を呼べば、めでたく戻り値もセットされた状態で関数から帰還できる。
最後に
コンパイラを作るのは難しいことではない―――コンパイラの定義によっては。
関係ないけど、下に好きな曲を貼っておくので聞いてほしい。鳥肌立った。