Kotlinでインタープリターを実装してみる(1): Tokenizer編

## 前書き
これは自己満足記事なので解説は省いてコードだけボン！と載せていきます。

一応動くので、コード読み解けば参考にはなるかもしれません。
全部出来上がったら整理して解説をするかもです。

[ソースコード](https://github.com/programmerkgit/kt1)


## Kotlinでインタプリターを実装してみるの動機
自分がプログラミングを初めて触れた時、Code Academyというオンラインプログラミング学習サイトでした。

その時に自然とプログラミングを通じて思ったのは
1. プログラミング学習サイトを作ってみたい
2. プログラミング言語を作ってみたい
3. プログラミング言語を作る仕組みを作ってみたい
ということでした。

最初はどれもとても遠いように思ったのですが「1のプログラミング学習サイトを作ってみたい」というのはブロックチェーンのオンライン学習サイトという形でリリースして達成する事ができました 

- 学習サイト: [enterchain](https://enterchain.online/)
- 以前書いた記事: [ブロックチェーン学習サイトを作ったので紹介](https://qiita.com/kubocchi/items/46761fa1416817489a25)

コードを書いて4年近くになりますが、残りの「プログラミング言語を作ってみたい」「プログラミング言語を作る仕組みを作ってみたい」というのもそろそろ実装したいと感じて着手してみることにしました。

言語がKotlinの理由は自分がKotlinがマイブームで書き始めているところであり、言語の練習にもなって一石二鳥だと思ったためです。

インタープリター実装では手続きっぽい書き方が多そうなのでGoなどの方が簡単そうに思うのですが、あえてKotlinを利用して複雑な作りをいろいろ試して遊んでみようと考えたりもしています。

## 実装
今回は以下の内容まで実装しました。

1. Tokenの定義
2. Tokenizer

Consoleで以下のようにTokenizeされます。

<img width="327" alt="Screen Shot 2020-05-15 at 1.47.02.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200431/5edd20ab-373b-af72-0ff7-7baf8b3541f0.png">

### Demo
![compiledemo.mov.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200431/40003288-00e3-9787-ff7b-bd3459991657.gif)


### 各ファイル

#### Main 
空行が入力されるまでTokenizerをループします。

```kotlin:main.kt
package org.example

fun main() {
    do {
        val line = readLine()
        if (line != null) {
            val tokenizer = Tokenizer(line)
            do {
                val token = tokenizer.nextToken()
                println(token)
            } while (token !is EOFToken)
        }
    } while (line != null && line != "")
}
```

#### Token定義

```kotlin:token.kt
package org.example

enum class TokenKind {
    /* SPECIAL */
    EOF, //end of file
    ILLEGAL, // not recognized

    /* Noramal */
    IDENTIFIER, //
    INT, //

    /* Delimiters */
    LPAREN,//(
    RPAREN,//)
    LBRACE, // {
    RBRACE, // }
    COMMA, //,
    SEMICOLON, //;

    /* Op */
    ASSIGN, // =

    /* Operators */
    PLUS, // +
    MINUS, // -
    MULTI, // *
    DIV, // /
    BANG, // !

    /* MATH */
    LSS, //<
    GRT, //>
    LSSEQ, //<=
    GRTEQ, //>=
    EQUAL, // ==
    NOTEQ, // !=

    /* KEYWORDS */
    FUNCTION, // fn,
    RETURN, // return

    /* DEC */
    VAR, //var
    LET, //let
    CONST, //const
    VAL, // val

    /* SENTENCE */
    IF, // if
    ELSE, // else
    WHILE, // while,
    WHEN, //when,
    THEN, // then

    /* BOOL */
    TRUE, //true
    FALSE, // false
}

open class Token(
    private val kind: TokenKind,
    private val literal: String
) {
    override fun toString(): String {
        return "{Kind: ${kind}: Literal: $literal}"
    }
}

class IllegalToken(value: String) : Token(TokenKind.ILLEGAL, value)
class EOFToken() : Token(TokenKind.EOF, "")
class IdentifierToken(value: String) : Token(TokenKind.IDENTIFIER, value)
class IntToken(value: String) : Token(TokenKind.INT, value)

/* Math */
class PlusToken() : Token(TokenKind.PLUS, "+")
class MinusToken() : Token(TokenKind.MINUS, "-")
class MultiToken() : Token(TokenKind.MULTI, "*")
class DivToken() : Token(TokenKind.DIV, "/")
class BangToken() : Token(TokenKind.BANG, "!")

/* Op */
class AssignToken() : Token(TokenKind.ASSIGN, "=")

/* DelimiterToken */
class LParenToken() : Token(TokenKind.LPAREN, "(")
class RParentToken() : Token(TokenKind.RPAREN, ")")
class LBraceToken() : Token(TokenKind.LBRACE, "{")
class RBraceToken() : Token(TokenKind.RBRACE, "}")
class CommaToken() : Token(TokenKind.COMMA, ",")
class SemicolonToken() : Token(TokenKind.SEMICOLON, ";")

/* Comp */
class EqualToken() : Token(TokenKind.EQUAL, "==")
class NotEqToken() : Token(TokenKind.NOTEQ, "!=")
class LssToken() : Token(TokenKind.LSS, "<")
class LssEqToken() : Token(TokenKind.LSSEQ, "<=")
class GrtToken() : Token(TokenKind.GRT, ">")
class GrtEqToken() : Token(TokenKind.GRTEQ, ">=")

/* keywods */
class FuncToken() : Token(TokenKind.FUNCTION, "fn")
class IfToken() : Token(TokenKind.IF, "if")
class WhenToken() : Token(TokenKind.WHEN, "when")
class ElseToken() : Token(TokenKind.ELSE, "else")
class ThenToken() : Token(TokenKind.THEN, "then")
class ReturnToken() : Token(TokenKind.RETURN, "return")
class TrueToken() : Token(TokenKind.TRUE, "true")
class FalseToken() : Token(TokenKind.FALSE, "false")

/* Assign Keyword */
class LetToken() : Token(TokenKind.LET, "let")
class ValToken() : Token(TokenKind.VAL, "val")
class VarToken() : Token(TokenKind.VAL, "var")
class ConstToken() : Token(TokenKind.CONST, "const")
```

#### Tokenizer
When is, when inの分岐や、return ifなどの処理がKotlinの文法によって気持ちよく書けています。


```kotlin:tokenizer.kt
package org.example


private operator fun Regex.contains(char: Char?): Boolean {
    return if (char == null) {
        false
    } else {
        matches(char.toString())
    }
}

/* Tokenize input file */
class Tokenizer(private val input: String) {

    private fun isWhiteSpace(char: Char?): Boolean {
        return if (char == null) false else Regex("\\s").matches(char.toString())
    }

    private val ch: Char?
        get() = input.getOrNull(p)

    /* pointer to current ch */
    private var p: Int = 0

    /* position after tokenized */
    private var position: Int = 0

    private fun incP(): Int {
        if (p < input.length) {
            p++
        }
        return p
    }

    private fun isEnd(): Boolean {
        return p == input.length
    }

    private fun ensureSetPosition(token: Token): Token {
        position = p
        return token
    }

    fun nextToken(): Token {
        if (isEnd()) return EOFToken()
        while (isWhiteSpace(ch)) {
            incP()
            position = p
        }
        val startPosition = position
        return when (ch) {
            /* math */
            '+' -> {
                incP()
                ensureSetPosition(PlusToken())
            }
            '-' -> {
                incP()
                ensureSetPosition(MinusToken())
            }
            '*' -> {
                incP()
                ensureSetPosition(MultiToken())
            }
            '/' -> {
                incP()
                ensureSetPosition(DivToken())
            }
            /* Compare */
            '>' -> {
                incP()
                return when (ch) {
                    '=' -> {
                        p++
                        ensureSetPosition(GrtEqToken())
                    }
                    else -> {
                        ensureSetPosition(GrtToken())
                    }
                }
            }
            '<' -> {
                incP()
                return when (ch) {
                    '=' -> {
                        incP()
                        position += p
                        LssEqToken()
                    }
                    else -> {
                        position += p
                        LssToken()
                    }
                }
            }
            '=' -> {
                incP()
                when (ch) {
                    '=' -> {
                        incP()
                        position += p
                        return EqualToken()
                    }
                    else -> {
                        return AssignToken()
                    }
                }
            }
            '!' -> {
                incP()
                return when (ch) {
                    '=' -> {
                        incP()
                        position = p
                        NotEqToken()
                    }
                    else -> {
                        BangToken()
                    }
                }
            }
            ',' -> {
                incP()
                position = p
                CommaToken()
            }
            ';' -> {
                incP()
                position = p
                SemicolonToken()
            }
            '(' -> {
                incP()
                position = p
                return LParenToken()
            }
            ')' -> {
                incP()
                return RParentToken()
            }
            '{' -> {
                incP()
                return LBraceToken()
            }
            '}' -> {
                RBraceToken()
            }
            /* number */
            in Regex("[1-9]") -> {
                incP()
                while (ch in Regex("[0-9]")) {
                    incP()
                }
                ensureSetPosition(IntToken(input.slice(startPosition until p)))
            }
            else -> {
                return when {
                    isEnd() -> {
                        EOFToken()
                    }
                    ch in Regex("[a-zA-Z_]") -> {
                        while (ch in Regex("[a-zA-Z_]")) {
                            incP()
                        }
                        when (val text = input.slice(startPosition until p)) {
                            "fn" -> {
                                ensureSetPosition(FuncToken())
                            }
                            "return" -> ensureSetPosition(ReturnToken())
                            "let" -> ensureSetPosition(LetToken())
                            "val" -> ensureSetPosition(ValToken())
                            "true" -> ensureSetPosition(TrueToken())
                            "false" -> ensureSetPosition(FalseToken())
                            "if" -> ensureSetPosition(IfToken())
                            "when" -> ensureSetPosition(WhenToken())
                            else -> ensureSetPosition(IdentifierToken(text))
                        }
                    }
                    else -> {
                        incP()
                        ensureSetPosition(IllegalToken(input.slice(startPosition until p)))
                    }
                }
            }
            /* Op */
        }
    }

}

```