読者です 読者をやめる 読者になる 読者になる

GOでインタプリタ実装本を読んで1 lexer

去年末に購入してからずっと積読状態だった本をようやく読み始めた。 最近、朝活というものにハマっていて、ちょうど良い機会なので少しずつ読み進めている。

ちなみに、僕は英語が得意ではなくて、洋書を読むのにとても時間がかかってしまうのだけれど、とても役立っているのが Kindle for PC。

選択範囲の単語を即座に辞書で引けるので、割りとストレス無く読み進められている。まだ読んでいる途中ではあるけど、得られた知見をまとめておこうと思う。

本書について

Goでinterpreterを実装する過程を説明した本で、内容については @deeeet さんが簡潔にまとまったものを書かれている。

僕は仕事でプログラミングをしているけれど、情報系の大学出身というわけでも、コンピューターサイエンスに明るいというわけでもない。 それはいつしかちょっとした劣等感となっていて、でもそれが僕の技術に対する学びへのモチベーションに転嫁されている気がするのでそれはそれで良い。 そういった文脈があるわけだけれど、ずっとコンパイラインタプリタが一体どのように作られていて、具体的に何をしているのか、という分野にはすごく興味があった。特に、以下の記事を見たときは自分もいつかはやってみたいという気持ちが高まっていた。

本書は、Monkeyという名のインタプリタ言語を実際に実装する過程が書かれており、そういった初心者の欲求を満たすには十分な内容となっているように思う。

本書は主に、

  • Lexing
  • Parsing
  • Evaluation

という構成となっており、今回は途中手を動かしながらLexingを読みきったのでそれをまとめておく。

Lexing

僕はそもそもLexingが何なのかを知らなかったのだけれど、Lexingとは、ソースコードを意味のある最小単位(token)に分割する作業のことで、これをLexing(字句解析)と呼ぶ。 インタプリタソースコードを実行するにあたって、プレーンテキストをよりaccessibleな形式に変換、具体的には、プレーンテキストをAST(Abstruct Syntax Tree)へと変換したい。そのために2段階の変換をするわけだけれど、その1段階目の工程をLexingと呼んでいる。言語によって呼び方は様々なようで、tokenizerと呼んだりscannerと呼んだりする模様。

plain text ---> token ---> AST

そして、実際に字句解析を行う変換器をlexerと呼んでいる。 ちなみに、lexerによって分割されたtokenをASTへと変換するのがparserらしい。今まで聞いたことはあったけどその関係性についてはよく知らなかったのでちょっとクリアになった。

さて、字句解析とは具体的にどのようなものなのか。 以下に簡単な例を挙げてみる。

let x = 5 + 5;

というソースコードがあったとして、それを字句解析して以下のようにする。

[ 
    LET, 
    IDENTIFIER("x"), 
    EQUAL_SIGN, 
    INTEGER(5), 
    PLUS_SIGN, 
    INTEGER(5), 
    SEMICOLON 
]

これつまり、Lexerを作るということは当たり前だけど言語仕様が決まっているということで、もしかするとここが作っていて一番楽しいところなのかもしれないと思った。(逆にEvaluationはつらそうな気がする・・)

Monkey で注目すべきなのは、

  • INTEGERを見て分かる通り型情報がlexing時点で存在する
  • ホワイトスペースは無視する
  • ソースコードのattribute的な情報は無い
    • production readyなlexerを実装する場合はエラーをよりわかりやすくするためにファイル名、行番号、カラム番号などを付与しなければならん
    • これは本書がpractice的な位置づけであるためで、解説を本質的な部分に絞るため敢えて実装していない

こういった言語設計を前提に、ソースコードを解析して意味のある部品に分割していく。

興味深かったのはその実装で、面白いくらいに愚直に書くのだな〜ということ。例えば、部品(token)については以下のように定義し、ソースコードテキストを読み込んでswitch文でガリガリ分割するみたいな。

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

    IDENT = "IDENT" // add, foobar, x, y, ...
    INT   = "INT"

    ASSIGN   = "="
    PLUS     = "+"
    MINUS    = "-"
    BANG     = "!"
    ASTERISK = "*"
    ・・・

lexerの本体はこんな感じ。

   ・・・
    switch l.ch {
    case '=':
        if l.peekChar() == '=' {
            ch := l.ch
            l.readChar()
            tok = token.Token{Type: token.EQ, Literal: string(ch) + string(ch)}
        } else {
            tok = newToken(token.ASSIGN, l.ch)
        }
    case '+':
        tok = newToken(token.PLUS, l.ch)
    case '-':
        tok = newToken(token.MINUS, l.ch)
    case '!':
        if l.peekChar() == '=' {
            ch := l.ch
            l.readChar()
            tok = token.Token{Type: token.NOT_EQ, Literal: string(ch) + string(l.ch)}
        } else {
            tok = newToken(token.BANG, l.ch)
        }
    case '/':
    ・・・

雰囲気が伝わると嬉しいんだけど、コンパイラってなんかすごそう(笑)みたいな感じだったけど、考えてみればなるほどこうなるなという感じ。面白い。

本書はこれをテストドリブンで実装していくという特徴があり、それも達成感があって良い。

Lexingの章の最後に実装したlexerを使って簡単なREPLを実装する。入力したソースコードが字句解析されて出力される様を見るとちょっとおおおって感じで楽しい。

次はparserを読む。