Explore "Full-Stack" in depth!

情報系の専門学校で、今は機械学習に的を絞って学習中。プログラミングを趣味でやりつつ、IT系のあらゆる知識と技術を身に付けるべく奮闘中。

Go Compilerの実装を読む(トークン編)

目次

概要

私は過去にプログラミングでいくつかのツールを作ってきました。

www.resume.id

ここにいろいろ載せてます。

github.com

ここにも。

しかし、より大きなものを、本気で作りたい!と考えた私は、
かねてよりめちゃくちゃ興味があったプログラミング言語の実装をしたいと考えました。

今は

Go言語でつくるインタプリタ

Go言語でつくるインタプリタ

という本で作成するmonkeyという言語を、
書籍を進めながら色々改良してみて、言語処理系の基礎を学んでいます。

しかしこれはインタプリタを作成するものですが、
私はコンパイラが作りたい。

そこで、やっぱり実際のコードを見ようと思いました。
それが一番勉強になるからですね。

今回はGo Compilerをコードリーディングすることでコンパイラの実装を学ぶ事を趣旨としています。
完全な理解は目的としていませんが、
出来るだけ深く掘り下げるつもりでいます。

長い記事になるので、今回はトークン編としておきます。

構文解析等は別の記事で読んでいきます。

対象読者

  • 言語処理系に興味がある!
  • Goの実装を深く知りたい!

本題

Goは代表的な自分自身で出来たプログラミング言語です。
Go CompilerGolangで実装されています。

そこで、本記事ではGo Compilerの実装をガンガン読んでいきます。

トーク

まずはトークです。
字句解析する際に使用される言語要素とも言えます。

私達が普段使ってるプログラミング言語について考えてみましょう。

package main

import "fmt"

func main(){
  fmt.Println("Hello World!")
}

このコードを、抽象的な視点から俯瞰します。

f:id:orangebladdy:20190220224736j:plain

予約語の概念は知っていますよね。
キーワードということもあります。

これらは既に定義されている識別子で、
それぞれが特別な意味を持ちます。

f:id:orangebladdy:20190220225014j:plain

とこのように、
プログラミング言語ではソースコードの各部分をジャンル分け出来ます。

この元になるのがトークです。
トークン化は、ソースコードトークンごとに切り出すような過程のことをいいます。

字句解析はこれらコードに存在する言語要素が何のジャンルなのかを示すプロセスです。

github.com

を見てみましょう。

go/tokenGo Compilerとは無関係である点に注意しましょう。
これは恐らく静的解析ツールの開発を目的としたパッケージ群でしょう。
基本的にsrc/go/*のパッケージはGoのコンパイルとは関係ありません。

package syntax

type token uint

//go:generate stringer -type token -linecomment

const (
    _    token = iota
    _EOF       // EOF

    // 以下続く

)

const (
    // for BranchStmt
    Break       = _Break
    Continue    = _Continue
    Fallthrough = _Fallthrough
    Goto        = _Goto

    // for CallStmt
    Go    = _Go
    Defer = _Defer
)

type token uintにより、各トークンを定義しています。
普段Goを書いていて見つけるような単語も多いのではないでしょうか。

私達が書くコードはこれら言語要素が組み合わさって出来たものといえますね。
実際にGoのコードをトークンに変換してみましょう。

package main

import "fmt"

func main(){
  s := "Hello World!"
  fmt.Println(s)
}

/* トークンに変換
_Package _Name

_Import _Literal

_Func _Name _Lparen _Rparen _Lbrace
       _Name _Assignop _Literal
       _name _Dot _Name _Lparen _Name _Rparen
_Rbrace
*/

となるかなぁ、と思います。
このように、普段のコードはトークに一般化する事が出来ます。

ソースコードトークン化する事を字句解析といいます。

// Make sure we have at most 64 tokens so we can use them in a set.
const _ uint64 = 1 << (tokenCount - 1)

// contains reports whether tok is in tokset.
func contains(tokset uint64, tok token) bool {
    return tokset&(1<<tok) != 0
}

type LitKind uint

// TODO(gri) With the 'i' (imaginary) suffix now permitted on integer
//           and floating-point numbers, having a single ImagLit does
//           not represent the literal kind well anymore. Remove it?
const (
    IntLit LitKind = iota
    FloatLit
    ImagLit
    RuneLit
    StringLit
)

const _ uint64 = 1 << (tokenCount - 1)で、
トークンの種類が最大64種類である事を定義しています。

contains()トークンが64種類に収まっているのかを確認しています。

LitKindリテラルの種類です。

  • 整数(IntLit)
  • 浮動少数(FloatLit)
  • 虚数(ImagLit)
  • ルーン(RuneLit)
  • 文字列(StringLit)

が定義されていますね。
これらはそれぞれ

num := 10
floatnum := 3.5
imagnum := 2i
runechar := 'A'
str := "Hello World"

のようなリテラルの種類に対応しています。

type Operator uint

//go:generate stringer -type Operator -linecomment

const (
    _ Operator = iota

    // Def is the : in :=
    Def  // :
    Not  // !
    Recv // <-

    // precOrOr
    OrOr // ||

    // precAndAnd
    AndAnd // &&

    // precCmp
    Eql // ==
    Neq // !=
    Lss // <
    Leq // <=
    Gtr // >
    Geq // >=

    // precAdd
    Add // +
    Sub // -
    Or  // |
    Xor // ^

    // precMul
    Mul    // *
    Div    // /
    Rem    // %
    And    // &
    AndNot // &^
    Shl    // <<
    Shr    // >>
)

// Operator precedences
const (
    _ = iota
    precOrOr
    precAndAnd
    precCmp
    precAdd
    precMul
)

type Operator uintも同じく演算子の型ですね。

const (
    _ = iota
    precOrOr
    precAndAnd
    precCmp
    precAdd
    precMul
)

によって演算子の優先順位を定義しています。
掛け算は足し算より先に評価されますし、
比較演算子は算術演算子より後に評価されます。

Goはiotaで簡潔に定義できるのでわかりやすいですね。

これらトークンには、
Stringer(String()メソッドを自動生成)が用いられています。

github.com

を見てみましょう。

// Code generated by "stringer -type token -linecomment"; DO NOT EDIT.

package syntax

import "strconv"

const _token_name = "EOFnameliteralopop=opop=:=<-*([{)]},;:....breakcasechanconstcontinuedefaultdeferelsefallthroughforfuncgogotoifimportinterfacemappackagerangereturnselectstructswitchtypevar"

var _token_index = [...]uint8{0, 3, 7, 14, 16, 19, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 42, 47, 51, 55, 60, 68, 75, 80, 84, 95, 98, 102, 104, 108, 110, 116, 125, 128, 135, 140, 146, 152, 158, 164, 168, 171, 171}

func (i token) String() string {
    i -= 1
    if i >= token(len(_token_index)-1) {
        return "token(" + strconv.FormatInt(int64(i+1), 10) + ")"
    }
    return _token_name[_token_index[i]:_token_index[i+1]]
}

_token_indexは、_token_nameトークンの種類ごとに区切る為のインデックスです。

トークンはiotaによって、
uintのゼロ値から列挙された値が入っています。

uintにおけるiotaの挙動を復習しましょう。

package main

import "fmt"

const (
        a uint = iota
        b
        c
        d
        e
)

func main() {
        fmt.Println(a) //0
        fmt.Println(b) //1
        fmt.Println(c) //2
        fmt.Println(d) //3
        fmt.Println(e) //4
}

このように型のゼロ値からインクリメントされて定義されていますよね。

const _token_nameのインデックスをいい感じに操作して、
文字列に変換して出力しているようです。

自動生成のようなのでかなり分かりづらいですが…w


総評

今回はトークンの実装を見ていきました。
シリーズとしてもかなり長くなりそうですが、
少しずつ読み進めていきたいと思います。