Writing  An Interpreter In Go - Lexing -

Writing An Interpreter In Goを読んで理解したことをまとめるnoteです。ソフトウェアエンジニアとして働いていて多くの技術を学ぶものの、なかなか手を付けられていなかったインタプリタ・コンパイラ周りの技術を学ぶための最初の一冊として読み始めました。

動機

私はもともとコンピュータサイエンスを学生の頃から学んでいたので、授業として字句解析・構文解析などの知識は最低限あったものの、当時はコードがほとんど書けず、内容としては片手落ちでした。ソフトウェアエンジニアとして働くようになってからコーディング能力が大幅にアップした今だからこそ、このような技術をコードを書いて学ぶことで理解が深まると思っています。

リポジトリはこちら

Lexical Analysis

コンピュータプログラムが実際に意味を解釈し、実行されるためにはいくつかのステップが存在します。簡略化して説明すると、以下の3つに分けることができます。

ソースコード

人間が書いたプログラムのソースコードそのもの。

トークン

parser(構文解析器)が理解しやすいようにソースコードの一つ一つの文字をデータ型に分解し、カテゴライズしたもの。

Abstract syntax tree(AST, 抽象構文木)

プログラミング言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した木構造のデータ構造。

Lexical Analysis(字句解析)とは、ソースコードからトークンに変換する処理のことを言います。

この本ではMonkeyという簡単なプログラミング言語を作り、それを実行できるインタプリタを作ることを目指します。そのため、まずは自分たちのLexerを定義し、実装していきます。具体的にはLexerの章が終わると、以下のプログラムをトークンに変換することができます。

https://github.com/m-nakamura145/wiig/blob/master/lexer/lexer_test.go#L9

let five = 5;
let ten = 10;
let add = fn(x, y) {
	x + y;
};
let result = add(five, ten);
!-/*5;
5 < 10 > 5;
if (5 < 10) {
	return true;
} else {
	return false;
}
10 == 10;
10 != 9;

Defining Our Token

与えられた文字列をいくつかのデータ型に分類するため、トークンを分類します。

・EOF: End of File
・Operators: 演算子
・Delimiters: 意味区切り。セミコロン、コロンなど
・Keywords: 予約語
・Identifiers: 変数名や関数名など、自分で定義した文字列

The Lexer

基本的な戦略としては、与えられたプログラムを一文字ずつ読み込み、その文字列を定義したトークンかどうかをチェックし、妥当なトークンに分類するという処理をEOFまで行います。

Lexer structのNextToken() methodで与えられたプログラムを一文字・または妥当な文字列数チェックし、分類します。

!-/*5のような、1文字でそれぞれ意味をもつ文字であれば解釈するのは簡単です。初期データセットではそれらをテストデータとして、実装していきます。

空白はこのMonkey言語においては意味をなさないので、空白や改行コードはskipWhitespace() methodでskipします。

Identifierやkeywordは複数の文字で表現される文字列です。よって、現在読み取る文字と次の文字を参照するポインタを持っておき、両者を使って文字列を読み取ってそれをIdentifierやkeywordかどうかを判定するreadIdentifier()とLookupIdent() methodがこのLexerのコアになると思います。

このあたりのmethodの実装からも分かる通り、このMonkey言語ではascii文字列のみを使えるプログラミング言語ということになります。この実装を少しずつ変化させていくことで、例えばC言語のlexerが作れたり、Rubyのlexerが作れたり、もっと複雑な自分の言語の解析ができるようになります。methodが細かく別れていてテストも書いているので、インクリメンタルに変更できてとても理解しやすいと思います。

Start of a REPL

Monckey言語の実行環境としてREPLを作ります。ただこれは簡単で、与えられた文字列を前の節で作ったLexerに渡してあげてそれを出力するだけで実現します。コードもとても短いです。

この章で作ったlexerで、入力したプログラムをトークンに変換することができました。

Hello m_nakamura145! This is the Monkey programming language!
Feel free to type in commands
>> let add = fn(x, y) { x + y; };
{Type:LET Literal:let}
{Type:IDENT Literal:add}
{Type:= Literal:=}
{Type:FUNCTION Literal:fn}
{Type:( Literal:(}
{Type:IDENT Literal:x}
{Type:, Literal:,}
{Type:IDENT Literal:y}
{Type:) Literal:)}
{Type:{ Literal:{}
{Type:IDENT Literal:x}
{Type:+ Literal:+}
{Type:IDENT Literal:y}
{Type:; Literal:;}
{Type:} Literal:}}
{Type:; Literal:;}

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

2

インタプリタ・コンパイラまとめ

インタプリタとコンパイラの理解のための記事をまとめたnoteです
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。