Goで作るインタプリンタを読んだ ①字句解析


Goで作るインタプリンタを読みました。忘れないうちに内容を整理しておきます。

字句解析

ソースコード(文字列)を構文規則に従って、意味のある集合(トークン)へ変換することです。

言語処理を行う最初のステップに当たります。

0824a

トークン

let hoge = 10;

例えば上記のようなソースコードがあったとすると、以下のように細かく分解できます。

let
hoge
= 
10
;

このように分解された、キーワードletやhoge、10といった数値は、これ以上細かく意味を持ちません。そのような、これ以上細かく分解できないかたまりをトークンといいます。

字句解析器(レキサー)

ソースコードを入力で受け取り、出力として対応するトークン列を返します。

字句解析器では、単純にソースコードを細かく分解するだけではなく、トークンの種類である「タイプ」を付与し、トークンを分類します。

例えば、5や10、15といった数値はトークンタイプを区別する必要がないので同じINTに、同様にhogeやadd、foobarといった変数名に関しても、タイプを区別する必要がないので、変数を表すIDENTをトークンタイプとして使用します。

上述したソースコードは、以下のようにリテラル + タイプに分解されます。

0824b

実装

以上を踏まえて、実装部分をざっくりと見てきます。

大まかな流れを掴むのが目的なので、ソースコードは一部抜粋です。

トークンのデータ構造は構造体を用いて表します。構造体は、トークンのタイプとリテラルをフィールドとして持ちます。

type Token string {
  Type TokenType
  Literal string
}

続いて、字句解析器の実装です。ヘルパーメソッド等を含めて複数のメソッドを作成しましたが、重要なのは、レキサーのデータ構造と、NextToken()メソッドです。

type Lexer struct {
	input        string
	position     int
	readPosition int
	ch           byte
}

func (l *Lexer) NextToken() token.Token {
	var tok token.Token

	l.eatWhitespace()

	switch l.ch {
	case '=':
		if l.peekChar() == '=' {
			ch := l.ch
			l.readChar()
			literal := string(ch) + string(l.ch)
			tok = token.Token{Type: token.EQ, Literal: literal}
		} else {
			tok = newToken(token.ASSIGN, l.ch)
		}
	case ';':
		tok = newToken(token.SEMICOLON, l.ch)
	case '(':
		tok = newToken(token.LPAREN, l.ch)
	case ')':
		tok = newToken(token.RPAREN, l.ch)
	case ',':
		tok = newToken(token.COMMA, 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()
			literal := string(ch) + string(l.ch)
			tok = token.Token{token.NOT_EQ, literal}
		} else {
			tok = newToken(token.BANG, l.ch)
		}
	case '*':
		tok = newToken(token.ASTERISK, l.ch)
	case '/':
		tok = newToken(token.SLASH, l.ch)
	case '<':
		tok = newToken(token.LT, l.ch)
	case '>':
		tok = newToken(token.GT, l.ch)
	case '{':
		tok = newToken(token.LBRACE, l.ch)
	case '}':
		tok = newToken(token.RBRACE, l.ch)
	case 0:
		tok.Type = token.EOF
		tok.Literal = ""
	default:
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = token.LookupIdent(tok.Literal)
			return tok
		} else if isDigit(l.ch) {
			tok.Literal = l.readNumber()
			tok.Type = token.INT
			return tok
		} else {
			tok = newToken(token.ILLEGAL, l.ch)
		}
	}
	l.readChar()
	return tok
}

レキサーのデータ構造は、以下の4つから成りたっています。

また、レキサーのNextToken()メソッドを呼び出すことで、現在読んでいるbyteに対してトークンタイプを振り分ける処理を行い、読んでいる位置を進めた上で、対応するTokenを返します。

さらに、fnや==, let, hogeといった複数の文字列からなるトークンに対応するために、ヘルパーメソッドを作成して、NexToken()メソッド内で、レキサーを読み進めながら細かくトークンタイプを振り分けられるように拡張します。

実装の細かい部分は、GitHubを参照ください。

https://github.com/takeru56/minimonkey/pull/1

実行結果

入力

ソースコードを入力。

let hoge = 10; 

if hoge > 5 { 
  return true; 
} else { 
  return false; 
}

出力

対応するトークン列を出力。

{Type:LET Literal:let}
{Type:IDENT Literal:hoge}
{Type:= Literal:=}
{Type:INT Literal:10}
{Type:; Literal:;}
{Type:IF Literal:if}
{Type:IDENT Literal:hoge}
{Type:> Literal:>}
{Type:INT Literal:5}
{Type:{ Literal:{}
{Type:RETURN Literal:return}
{Type:TRUE Literal:true}
{Type:; Literal:;}
{Type:} Literal:}}
{Type:ELSE Literal:else}
{Type:{ Literal:{}
{Type:RETURN Literal:return}
{Type:FALSE Literal:false}
{Type:; Literal:;}
{Type:} Literal:}}

まとめ

インタプリタが最初に行う処理、字句解析についてまとめました。

字句解析の役割としては、入力されたソースコードを最小の単位であるトークンに分解し、トークンタイプを付与することで、分類を行った上で、トークン列として出力を返すことでした。

字句解析を実装する第1章は、割と理解しやすかったです。次章の構文解析器からは、レベルが上がりそうなので、引き続き頑張って読み進めようと思います。

最後に、「Goでつくるインタプリンタ」で扱われるトークンタイプを一覧にまとめておきます。案外、少ないトークンの種類で、プログラミング言語を構築できることが見て取れます。

0824c

参考資料

O’Reilly Japan:Goで作るインタプリンタ

Wikipedia:字句解析

comments powered by Disqus