どのようにパーサを作るか

文法定義には解析表現文法 (Parsing Expression Grammar, PEG) を採用します。 古くからある文脈自由文法 (Context Free Grammar, CFG) と比べて新しい手法で、曖昧さがない利点があります。 最大の利点は、字句解析と構文解析を同時に行うことで柔軟な文法定義が可能になる点であろうと思います。 一方で言語サーバの実装を見据えると、エラー回復をどうすれば良いかよく分からない点は心配です。

ここまでは決めましたが、現段階ではあまりパーサにこだわらないことにします。 既存ライブラリを使うより、できるだけ自作した方が理解が進むでしょうから、最初は粗末なパーサを手書きします。 Packrat Parser もエラー回復もない PEG パーサです。 最初は正規表現ライブラリだけ使いますが、ゆくゆくは正規表現レベルのパーサコンビネータも自作します。 外部ライブラリへの依存をなくすことで、遠い将来コンパイラのセルフホストをしたくなったとき楽になります。

実のところパーサを書いたのは3年以上前の授業の課題としてなので、細かい工夫はあまり覚えていません。 左再帰の問題を回避する対策も、コードを見れば何をしているか大体分かるものの、なぜこれで良いのかは説明できません。 こうならないよう次の記事からは思考過程をできるだけ残していくようにしましょう。

どのようにASTを実行するか

最初の目標は自作VMによるバイトコード実行ですが、 その前に「自作言語を動かせている感」を感じたいため抽象構文木 (Abstract Syntax Tree, AST) を直接実行する実行器を作ります。

このインタプリタ実行では、関数や変数を Rust の HashMap で管理しています。 HashMap のキーとなる Identifier 構造体では Eq, Hash trait を実装します。 Identifier 構造体は実質的に String 構造体そのものなので Eq, Hash trait は既に実装されているようなものです。

HashMap は関数呼び出しが行われるごとに追加され、関数がリターンされると破棄されます。 追加されたり破棄されたりする HashMap をフレームと呼ぶことにします。 通常コンパイル実行ではスタック領域とヒープ領域に分けてメモリを管理することになるでしょうが、 関数呼び出しにより伸長したスタック領域がスタックフレームと呼ばれるようなイメージです。 フレームが1つだけですと、全ての変数がグローバル変数になってしまいます。 まだ言語仕様において関数や変数のスコープを厳密に定義していませんが、 最低限としてローカル変数というか関数スコープは扱える必要があるでしょう。

関数や変数を定義したら、最もスコープの狭いアクティブなフレームの HashMap に追加します。 HashMap には関数の AST への参照または変数の中身が入ります。 関数と変数の HashMap は共通ですので、同じ識別子は使えません。 ビルトイン関数には AST が存在しないため、ビルトイン関数であることだけ記録しておきます。 ビルトイン関数は任意に定義できず、現在はデバッグ用として実行前に定義された print 関数のみが存在します。

定義された関数や変数が参照されると、最もスコープの狭いアクティブなフレームと、最もスコープの広いインアクティブなフレームの1つの順に検索されます。 前者は関数スコープに、後者はグローバルスコープに相当します。 この簡素な実装ではグローバル変数と同じ識別子のローカル変数を定義することができ、グローバル変数が参照できなくなります。 関数呼び出し式の評価では関数が、識別子の評価では変数が読み出されることが期待されます。 現段階では関数を第一級オブジェクトとして扱えないため、関数または変数が読み出されることが期待される場面で違うものが読み出されると実行時型エラーを出します。 未定義の場合は未定義エラーを出します。

最後にその他の工夫について述べます。 関数の引数は、呼び出す側のスコープで実引数を評価した後、呼び出される側のスコープが新しく作られるときの初期値として仮引数の名前に対し評価された値を格納することで、実現します。 加減乗除などの演算子の評価は、素朴に行えば良いのですが、実行時型検査を演算子オーバーロードを行う std::ops::Add などのトレイト実装内に閉じ込めることで、少しは読みやすくなるかと思います。