Nimで自作インタプリタ① Lexerを作った
2018/12/23
Nimでインタプリタを作っているのですが、その第一段階として字句解析器の部分をひとまず作り終えたので、その直後の感想なりをまとめます。 概要
少し前から言語処理系に興味を持ち始め、そろそろ何か作ってみようと思い、オライリーの「『Go言語でつくるインタプリタ』」という本を購入しました。これはタイトルの通りGo言語でインタプリタを作っていく本です。まず、字句解析器を作り、その後、構文解析器、評価器を作っていきます。最初は本の通りにGoで書いていたのですが、インタプリタを作る分には学びがあるのですが、手を動かす部分が頭を使わない写経作業になりがちだったので、他の言語でやってみることにしました。まず候補に挙がったのは絶賛勉強中のRustですが、知らないことが多すぎて調べながら進めると、Goなら10分で終わるところに2,3時間かかってしまうほどでした。これはちょっと最初にやるには大きすぎるかと思い、もう少し書きやすいNimで書いてみようということになりました。ちなみにRustは中断してるだけなので、気が向いたら再チャレンジしてみます。(気が向いたら) なぜNimか
システムプログラミングっぽいことをするならやっぱ速い言語っしょ！と思ったのですが、CやC++は書きたくないし、GoとRustは上の理由で却下だし、どーしよーとなっていたときにNimの存在を思い出しました。去年の終わりに競プロをちょっとやってみようと思い、最初Pythonでやっていたのですが、もっと速度が欲しいなと調べていたらNimに出会いました。競プロのために始めたのですが、競プロ自体が自分の中で優先順位の高いものではないなと感じ始め、競プロから距離を置くと同時にNimとも距離を置くことになりました。それから存在を忘れていたのですが、良い機会だしこれで良いか！ってことでNimでこの本を進めることにしました。
良いところと良くないところ
自分の中ではPythonは比較的書き慣れており、それに文法が似ているNimは割ととっつきやすく意外とすらすらと書けました。基本的な文法に関しては日本語の記事も意外とあり、調べれば答えが見つかる感じでした。が、少し込み入ったことをしようとすると一気に情報が少なくなり、英語のドキュメントやフォーラムを読む必要が出てくるのですが、これが結構わかりにくく他の言語にない機能(PragmaとかConseptとか)を理解するのは大変でした。(まだしてない)
インタプリタとはなにか
前置きが長くなってしまいましたが、本題に入っていきます。
コードを処理してくれるいわゆる「言語処理系」には、コンパイラやインタプリタがあります。コンパイラはご存知の通り、コードを事前に機械語に翻訳してくれるやつのことです。一方でインタプリタとはなにか、wikipediaから引用させていただきます。インタプリタとは、以下のいずれかの動作をするプログラムのことです。
1. parse the source code and perform its behavior directly;
2. translate source code into some efficient intermediate representation and immediately execute this;
3. explicitly execute stored precompiled code made by a compiler which is part of the interpreter system.
僕は触ったことがないですが、LispやBrainfuckなどが1つ目にあたるようです。
2つ目の「何らかの中間表現に変換しながら実行する」というのは、PythonやRubyですね。
3つ目の「事前コンパイル」とかの話はJavaとかの話ですね。
JITとかもこの辺に絡んでくるのかな(わからん)
「Go言語でつくるインタプリタ」では、この中でも2番目にあたるREPLを作っていきます。
REPLは、Read、Eval、Print、Loopの略で対話的に一行ずつ解釈して実行するプログラムのことです。
PythonやJavaScriptやHaskellなどで使える一行ずつコードを実行できるあれのことです。
字句解析器(Lexer)とはなにか
インタプリタを作る第一段階目として字句解析器を作ります。
字句解析というのは、入力(コード)をスキャンしていき、最小の単位(Token)に分割していく作業のことで、この字句解析を行うプログラムのことを字句解析器(以下Lexer)と呼びます。
Lexerまで作り終えたところを貼っておきます。(ちょっと汚いですが)
プログラムの内容は大まかには、入力を一文字ずつ読んでいってswitch文で解析し、Tokenを作っていくだけです。
さきほどもさらっと書きましたが、Tokenというのはプログラム上の最小単位です。
実際に例を見てみましょう。
例えば、Lexerに以下のような入力をすると
code:nim
let five = 5
let ten = 10
以下のようなTokenを出力をします。
code:nim
[
LET,
IDENT("five"),
ASSIGN,
INT(5),
LET,
IDENT("ten"),
ASSIGN,
INT(10),
]
「let」や「(」や「=」なども一つのTokenで、予約語以外を任意の変数名「five」なども変数としてTokenを作り、「5」などの値も文字列で読み込まれているので数値の「5」としてTokenを作ります。
イメージ的には以下の関数のようにcase..of文(他の言語のswitch文のようなもの)で、読み込まれた文字が該当する分岐へ進み、それのTokenを作成します。
code:nim
proc nextToken*(self: Lexer): token.Token =
var tok: token.Token
self.skipWhiteSpace()
case self.ch
of ':':
tok = newToken(COLON, self.ch)
of '(':
tok = newToken(LPAREN, self.ch)
of ')':
tok = newToken(RPAREN, self.ch)
of ',':
tok = newToken(COMMA, self.ch)
of '+':
tok = newToken(PLUS, self.ch)
of '-':
tok = newToken(MINUS, self.ch)
else:
if isLetter(self.ch):
let l = self.readIdentifier()
let t = LookUpIdent(l)
return Token(Type: t, Literal: l)
elif isDigit(self.ch):
let t = token.INT
let l = self.readNumber()
return Token(Type: t, Literal: l)
else:
tok = newToken(token.ILLEGAL, self.ch)
self.readNextChar()
tok
最初は身構えていましたが、実際に書き始めると、なぁ〜んだ、というほど単純なものでした。
当たり前ですが、Tokenは自分で定義できます。
ですので、例えば//と#のどちらをコメントにするかや、|>のようにメソッドチェーンできる文法を入れようとか、極端なことを言えば和算の記号に-を使うみたいなこともできます。
自分で新たな言語の文法を作っていくイメージです。
今回作ったもののTokenはこの部分で定義してあります。 お！って思ったところ
基本的には上のようなcase..of文を書くだけで事足りるのですが、例外が少しありました。
等価演算子の「==」と「!=」です。
例えば値の束縛を示す「=」と、論理演算子の「!」があり、一文字だけ読んだだけではどちらなのかを判断できないので、二文字目が「=」なのかどうかを先読みする必要があります。
そこで、先読みするプロシージャ「peekChar()」を作り、以下のように、case..of文の中で条件分岐をし、どちらかを判断して適切なTokenを作ります。
code:nim
case self.ch
of '=':
if self.peekChar() == '=':
let ch = self.ch
self.readNextChar()
let l = $ch & $self.ch
tok = Token(Type: EQ, Literal: l)
else:
tok = newToken(ASSIGN, self.ch)
今回の例では、たかだか二文字目まで先読みすればそれで事足りますが、tcfm 第10回の34:22からお話されているように、C言語のような昔の言語は、関数も変数も「int hoge ~~」って書き、先読みする機会が増えるので、その辺が大変そうだなと感じました。
逆にモダンな言語である、NimやRustやGoなどでは、1トークン目を見ればそれが関数かどうかなどがわかるように設計されていて、なるほど、学びだなと感じました。
自作言語
この本では、「monkey」という名前のC言語風の言語を作っていきます。
これをそっくりそのまま真似てもいいのですが、ちょっと面白みに欠けそうなので一部Nimっぽい文法で掛けるように僅かなオリジナリティを入れたりしています。
行末セミコロンがなかったり、できればインデントで入れ子を表現したりしたいのですが、難しいのではとビビっております。
所感
最後に所感です。
テストファースト
この本はなんとテストファーストで書かれています。
まずはテストコードを書いて実行してレッドになるのを確認してから作っていきます。
僕はまだテストコードを書くことに慣れていないので、これも良い勉強だなぁと思いながら進めています。
型の話
僕が読み進めているところまででは、あまり型を意識しない言語を作っています。
実際、言語を作るとなると動的型付けと静的型付けはどちらの方が大変なのかなとも思ったりしました。
先日、こんなスライドを作りましたが、実際、動的型付けの言語の中でどのように処理されているのかあまり理解できておらず若干ブラックボックスなのでそこも勉強したいです。 型理論や、関数型プログラミングにも最近興味を持ち始めいろいろ読んだりしてるので、それも応用できると面白いだろうなぁと思っています。
次はParserを作る
この本では、1章でLexerが一先ず終わり、2章からParserを作っていきます。
実装の上でインターフェースやポインタを扱っていくのですが、これに関してはNim言語そのものに対する理解も含めていかなくてはいけなさそうです。
NimのポインタやConceptsやPragmaやマクロなど、一段階あがった機能も取り入れつつ、Parserを作っていきたいです。
また、2章を終えた時点で記事を書こうかと思います。
参考