Go
golang

Writing An Interpreter In Go で Lexing

こんにちは。
層が薄いと嘆かれている, 40代ギリ前半のʕ•ᴥ•ʔです。若くて優秀な人がたくさん活躍されているリブセンスに今年の11月から仲間に入れてもらいました。

AdventCalendarが3枚もある狂ったすばらしい環境! しかも ってなんだ。どういうことなんだ。

Livesense - 関 Advent Calendar 2017の20日目を担当します。

ところで有名な話ですが, エンジニアの三大美徳として, 怠慢・短気・傲慢があります。

傲慢:

神罰が下るほどの過剰な自尊心。
または人様に対して恥ずかしくないプログラムを書き、また保守しようとする気質。

関羽は大変自尊心が高く, その傲慢さで自らの破滅を呼び込んだと言われています。
わたしはプログラマーの美徳として傲慢さを持ちたいな...と思います。

というわけで, つながっているようでまったくつながらない, つまり係がない。
.
.
.
.
.
突然ですが, 今さらですがWriting An Interpreter In Goを買いました。

なぜ読み始めたか

社内ではGoの標準ライブラリを読み解く会が毎週開催されています。
GoはGoそのものがGoで書かれており(一部そうではない部分もあるし, アセンブラは読めない...), しかもソースコードが大変シンプルでわかりやすく, 大変ためになります。
ところが, 自分がいかに雰囲気でGoと付き合っていたかが, 分かってしまいました...雰囲気 is 堕落...

そこで, 自分自身のGo力をより高めたく, この本を選択しました。
Goの基本機能のみで説明をしてくれているそうです。そこが大変魅力的でした。
また, 体系的な情報システムの教育を受けたことのない自分自身がどこまで理解を深めることができるのか, というところにも興味がありました。

やろうと決めたこと

  1. この本は200ページ程あります...!! 読みながら手ほどきを受けます。
  2. 好きなインタプリタを作ってみる。

学び方

本の流れの通り, 手を動かしていきます。本の中ではMonkeyという言語を実装するようです。
わたしはモチベーションを保つためにBear(ベアグラミング)という言語でがんばります。

  1. Lexing
  2. Parsing
  3. Evaluation

この本ではGo1.7で実装されたようですが, 手元のGo1.9.2で色々やります。

Lexing

Lexingのはじまり

Lexingとは字句解析(Lexical Analysisともいう)のことです。プログラム全体から, 定義された命令やリテラルを切り出す作業のことです。(と, 解釈した)

ソースコード -> トークン -> 抽象構文木

Lexingはソースコードからトークンへの変換を担い, その後はParsingによってトークンから抽象構文木に変換されます。
ココでは, 空白は単なるトークンのセパレータとして扱います。一部言語では空白の長さが重要なであることがあるようです。
また, 行・列番号やファイル名をトークンに付与すると, 構文解析時に役に立つということ。
大量データのインポートを取り扱うようなときも, そういったデータが欲しくなるし...心理的にはどこで何が発生したのかが分かると安心。
ただ, 初回は実装しません。あとで付け足そう...(TODO)

そしてついに書き始める...!! が, golintが色々と仰る...
by other packages系は, 今変えてしまうことでついていけなくなると困るので, ソノママ。
逆にそれ以外については極力対処しながら進めていきます。

まずは, ごく限られたトークンを定数で定義してしまいます。

const (
    ILLEGAL = "ILLEGAL"
    EOF     = "EOF"

    IDENT = "IDENT"
    INT   = "INT"

    ASSIGN = "="
    PLUS   = "+"

    COMMA     = ","
    SEMICOLON = ";"

    LPAREN = "("
    RPAREN = ")"
    LBRACE = "{"
    RBRACE = "}"

    FUNCTION = "FUNCTION"
    LET      = "LET"
)

このあとは, 実際にLexerを書くのですが, まずは実現したいことをテストから書いて, 中身を実装していく流れが段階的に説明されていまます。大変わかりやすいです。
一つずつ文字を調べ, その文字をswitchで振り分けてconstで定義したトークンを返却して次へ...という処理が行われます。
今回作成している言語は, 変数に_を利用できるようにしています。

func isLetter(ch byte) bool {
    return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

空白はただのセパレータとして扱うので, スキップする処理も追加します。
unicode.IsSpaceはRuneだけど, これを利用することもできるのかな...?

for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
    // readChar
}

また, ここで作る言語では整数のみをサポートします。
この時点でのテストはこんな感じ。

let black_bear = 5;
let polar_bear = 10;

let add = fn(x, y) {
    x + y;
};
let result = add(black_bear, polar_bear);

Lexingの拡張

各種演算子やif, else, returnを扱えるようにします。
==!=は2つで1つの意味を持つので, switchのcaseで1つ先の文字を見ることで演算子であることを判断する方法を知りました。

Bearのテストに処理追記しても, SUCCESSになるようになりました。

!-/*5;
5 < 10 > 5;

if (5 < 10) {
    return true;
} else {
    return false;
}
10 == 10;
10 != 9;

REPLのさわり

REPLを実装します。でもあくまでもさわりです。
でも, 第1章の段階でここまでできたので, とてもうれしい。
スクリーンショット 2017-12-17 22.14.25.png

さいごに(さいごじゃない)

本当はASTまで行きたかったのですが, Lexingまでしか辿り着けず...無念...!!
読んで頂くにはあまりにも日本語が崩壊していたり, 厳しい記事でごめんなさい。
でも, 懲りずに続けます...!! いやぁ, 楽しいʕ•ᴥ•ʔ

あと, あまりに楽しいので, 誰か一緒にやりませんか。

メモ

  • 言語の主要構成:
    • the lexer
    • the parser
    • the Abstract Syntax Tree (AST)
    • the internal object system
    • the evaluator
  • tree-walking
  • この本ではMonkeyと呼ばれる言語を解析して評価する。
    • ということはBearでもいいのか...!!
    • プログラミング言語Bear(ベアグラミング)
      • C言語的構文
      • 可変バインディング
      • 整数・真偽値
      • 詐術式
      • 組み込み関数
      • クロージャ
      • 文字列データ構造
      • 配列データ構造
      • ハッシュデータ構造