CRAFTING INTERPRETERSというインタプリタの作り方が無料で知れちゃう教材があります。(ただし英語)
現在、この教材をもとにして勉強会を主催してるんですが、なかなか実装できていないのでアドベントカレンダーに便乗して1日1章ずつ実装していこうという個人アドカレです。
30章あるので、アドカレの期限を少し超えて12/30まで頑張ります。
1章
導入部分。
今回作るインタプリタはJavaとCで実装することや、yacc, bison等を使わずに全部自作することが説明されている。
あと注釈にちらっと書いていたカリー＝ハワード同型対応というのを初めて知った。
プログラミング言語の理論と数学が直接的に対応関係があるとのことで、そらそうと言われたらそうかも知れないけど面白いなと思った。
しかもそれを哲学的に考えることもやっているらしく興味深かった。
2章
この章はインタプリタの全容を知れる部分。
といってもよくある 字句解析 → 構文解析 → 意味解析 → 最適化 → コード生成 という流れ。
IRにもいくつかの形式があるらしく、これはこれで面白そうと思ったり。
コード最適化についても説明があった。今回は特に最適化はやらないらしい。
詳しい最適化については以下のページが詳しかった。
また、cloxではC言語でVMを作ってどのプラットフォームでも実行できるようにするとのこと。面白そう。
3章
Lox言語の仕様について解説した章。
C言語風だが動的型付けでJSっぽさもある。
海外では実引数を引数、仮引数をパラメータと言うらしくびっくりした。一応日本語と同じ用に呼ぶ流派もあるみたいだけど、これに関しては日本語の呼び方がわかりやすいなぁと。
クロージャをサポートしているのが不思議というか謎。筆者の好みなんだろうか。
あとクラスをサポートしているのが良い。
低レイヤを知りたい人のためのCコンパイラ作成入門もやったんだけど、残念ながらクラスは出てこなかったから知りたかった。
次回からコードを書き始めるらしい。がんばるぞ。
4章
今日から実装していく日々の始まり。
といってもWebサイトで完全に動くコードが提示されているのでコピペはできる。
写経しても結局脳死で丸写しだし、時間がかかるし、タイポするので今回はコピペメインでやろうかなと。
というわけで軽く実装する内容の紹介。
public class Lox {
public static void main(String[] args) throws IOException {
if (args.length > 1) {
System.out.println("Usage: jlox [script]");
System.exit(64);
} else if (args.length == 1) {
runFile(args[0]);
} else {
runPrompt();
}
}
}
jloxはファイルからの入力はもちろん、REPLとしても使える。
static void error(int line, String message) {
report(line, "", message);
}
private static void report(int line, String where,
String message) {
System.err.println(
"[line " + line + "] Error" + where + ": " + message);
hadError = true;
}
エラーハンドリングも行数を教えて指摘してくれる。
private void scanToken() {
char c = advance();
switch (c) {
case '(': addToken(LEFT_PAREN); break;
case ')': addToken(RIGHT_PAREN); break;
case '{': addToken(LEFT_BRACE); break;
case '}': addToken(RIGHT_BRACE); break;
case ',': addToken(COMMA); break;
case '.': addToken(DOT); break;
case '-': addToken(MINUS); break;
case '+': addToken(PLUS); break;
case ';': addToken(SEMICOLON); break;
case '*': addToken(STAR); break;
}
}
字句解析部分はemunで定義したトークンを元に愚直に場合分けする。
この際使用している advance() は1文字消費して文字を取得するメソッド。
private char advance() {
return source.charAt(current++);
}
後に必要になるが、文字を消費しない peek() というメソッドもある。
private char peek() {
if (isAtEnd()) return '\0';
return source.charAt(current);
}
演算子はトークンを取得したあと、更に1文字進めてみて ! か != どうかのように判定する。
case '!':
addToken(match('=') ? BANG_EQUAL : BANG);
break;
case '=':
addToken(match('=') ? EQUAL_EQUAL : EQUAL);
break;
case '<':
addToken(match('=') ? LESS_EQUAL : LESS);
break;
case '>':
addToken(match('=') ? GREATER_EQUAL : GREATER);
break;
private boolean match(char expected) {
if (isAtEnd()) return false;
if (source.charAt(current) != expected) return false;
current++;
return true;
}
/ が出てきても除算なのかコメントなのか1文字じゃわからないので1つ進めて見てみる。
Pythonとかみたいに # をコメントにしても良さそうと思ったり。
case '/':
if (match('/')) {
// A comment goes until the end of the line.
while (peek() != '\n' && !isAtEnd()) advance();
} else {
addToken(SLASH);
}
break;
あとは空白を読み飛ばしたり、改行で行数のカウントを増やしたり。
case ' ':
case '\r':
case '\t':
// Ignore whitespace.
break;
case '\n':
line++;
break;
jloxでは数値型を全部doubleとして扱うらしいので、 c >= '0' && c <= '9' で true なやつがここでパースされる。
private void number() {
while (isDigit(peek())) advance();
// Look for a fractional part.
if (peek() == '.' && isDigit(peekNext())) {
// Consume the "."
advance();
while (isDigit(peek())) advance();
}
addToken(NUMBER,
Double.parseDouble(source.substring(start, current)));
}
文字も予約後と衝突しないか確認するためにトークンを全部見て確認する。
private void identifier() {
while (isAlphaNumeric(peek())) advance();
addToken(IDENTIFIER);
}
という感じで字句解析を一通り？やって4章は終わり。
次は構文木とかのお話。