はじめに
こんにちは、Latte72です。
慶應義塾大学公認サークル Computer Society で低レイヤーを扱うシステム班の班長を務めることになったので、後輩たちに低レイヤー技術（特に自作言語やコンパイラ・インタプリタの実装）について興味を持ってもらうにはどうしたらいいかと考えながらこの記事を書いています。
この記事は私のサークルに入会した新入生や、プログラミング言語がどのようにして動いているのかに興味がある人、低レイヤーにあまり詳しくないけど自作言語や自作コンパイラに興味がある人たちに向けたものです。 プログラミングに関する事前知識がなくても読めるように、多くの補足をつけています。 既にプログラミングに精通している方にとっては説明が不適切に感じる部分があるかもしれません。温かい目でご覧いただき、コメント欄にてご指摘いただければありがたいです。
Part 1 の記事で低レイヤーに関連する用語の説明をしています。 今回のPart 2 の記事は、前回の記事を読んでいるか、低レイヤーに関してある程度の知識があることを想定して書いています。（用語に関してはリンクをつけているので、このまま読み進めてわからない用語があったら参照する形でも構いません。）
⇓ Part 1 の記事はこちら ⇓
この記事ではコンパイラやインタプリタを実装する流れを解説しています。
コンパイラやインタプリタのコードを紹介しながら実装をしていく記事ではありません。
コンパイラやインタプリタの実装
自作言語であるか、既存の言語の仕様に沿うのかに関わらず、コンパイラとインタプリタのどちらを実装するのかという選択が必要です。
また、実装にどの言語を使うのかという点も選択が必要です。
コンパイラとインタプリタ
この章には実装する処理系と実装に使うプログラミング言語の話が書かれています。どちらの話をしているのか注意して読み進めてください。
コンパイラとインタプリタのどちらを実装するか
コンパイラの実装とインタプリタの実装には大きな違いがあります。
それはインタプリタの実装ではその実装に使うプログラミング言語だけが使えれば基本的に問題ないのに対して、コンパイラの実装ではターゲットとなるアーキテクチャのアセンブリ言語やMLIRなどの知識も必要だということです。
実装にどのプログラミング言語を使うか
実装にどのプログラミング言語を使うかによっても難易度が変わってきます。これは別にコンパイラやインタプリタの実装に限った話ではないのですが、静的型付けの言語を使う場合は、動的型付けの言語に比べてコードの厳密さを要求されることが多いです。また、REPLがサポートされている言語では、実行中の変数の値が確認できるのでデバッグが容易です。そのため、もしあなたがプログラミングにまだあまり慣れていない場合は、REPLがサポートされている言語を使って実装することをおすすめします。
また、MLIRのような中間表現を活用すれば、ターゲットとなるアーキテクチャごとのアセンブリを直接書かなくても済みます。ただし、MLIRを使う場合でも、それらのフレームワークの構造や設計思想を理解する必要があり、結局のところ一定の学習コストが発生します。MLIRを使うにはC++を使える必要があるので慣れていない人には難易度が高いでしょう。
コンパイラとインタプリタの実装に共通する部分
実装前に注意すべきこと
コンパイラやインタプリタを実装するときには、最初から完璧なものを実装するのではなく、簡単な処理から実装していくのがおすすめです。例えば、最初は電卓程度の計算ができるだけの処理系を作成し、実際にプログラムを動かしながら動作を確認していくとよいです。
これは、初めから完璧な処理系を開発しようとすると、全てが完成するまでプログラムを動かしてみることができないので、全体が動き始めるまで自分の理解や設計が決定的に間違っていても気づくことができないからです。また、完成するまで何のプログラムも実行できないので、モチベーションを保つのが難しいという問題もあります。
（この部分は「低レイヤを知りたい人のためのCコンパイラ作成入門」の受け売りです）
字句解析
字句解析（Lexer）は、ソースコードの文字列を読み込み、意味のある最小単位であるトークンに分割する工程です。字句解析器は、正規表現などを利用して効率的にトークンを抽出し、後続の構文解析器へ正確な情報を渡します。この段階で不正な文字列や予期しない記号が検出された場合、早期にエラーとして報告することが求められます。
正規表現
正規表現（Regular Expression）とは、文字列の中から特定のパターンを見つけ出すための記法です。特定の形式に合致する文字列を効率的に抽出・検証する際に使われます。
たとえば、0[789]0-?\d{4}-?\d{4}という正規表現を用いることで簡単に文字列中の携帯電話番号を検出することができます。
正規表現については以下のサイトに詳しく載っています。
トークン
トークンとは、ソースコードの文字列から字句解析器によって抽出される、最小の意味単位です。プログラムの中の予約語や変数名、記号、数値など、言語が定義する基本的な要素がトークンとして切り出されます。各トークンはその種類と実際の文字列や数値といった属性情報を持ちます。
構文解析
構文解析は、字句解析で得られたトークン列を元に、プログラムの文法規則に基づいた解析を行い、抽象構文木を生成する工程です。BNF記法などで定義された文法に従い、各トークンが正しい構文を形成しているかを検証し、エラーがあれば適切なエラーメッセージを出力します。構文解析の結果得られる抽象構文木は、後の意味解析や最適化、コード生成において非常に重要な役割を果たします。
抽象構文木
抽象構文木（AST）は、構文解析で作成されたプログラムの本質的な構造を示す木構造です。抽象構文木は、ノードによって構成されています。
ノード
ノードとは、抽象構文木を構成する基本要素であり、プログラムの論理的な構造や意味を表現します。各ノードは、演算、制御構造、関数呼び出し、変数参照など、プログラム中で行われるさまざまな操作を示し、子ノードとの親子関係によって全体の構造が木状に形成されます。この抽象構文木はコード生成の際に重要な役割を果たし、プログラムの処理の流れを明確に把握するための基礎となります。
コンパイラの実装
何のためにコンパイラを作るのか
コンパイラを自作する基本的な目的は字句解析からコード生成までの一連の処理系の仕組みを深く理解することです。また、特定のハードウェアに最適化された言語の設計、さらには既存言語の拡張を行うことも目的の一つです。
どこを目標にするか
まずは四則演算や変数代入のみを扱う小規模な言語から始め、徐々に機能を拡張していくことがおすすめです。自分で作った言語を使ってその言語のコンパイラを実装するセルフホストは自作コンパイラをする人にとっての大きな目標の一つです。更に理解が深まったら高度な最適化の実装をするのも良いかもしれません。
実装する方法
コンパイラの実装は、字句解析と構文解析を行い、最後にターゲットとなるアーキテクチャのアセンブリ言語や機械語に変換するコード生成を行います。
C言語のコンパイラを実装し最終的にはセルフコンパイルを目指すサイトです。
非常に分かりやすく解説されておりおすすめです。
インタプリタの実装
何のためにインタプリタを作るのか
インタプリタを自作する基本的な目的は字句解析や構文解析を理解すること、そしてプログラムの動的な挙動を理解することです。また、教育目的のプログラミング言語や軽量なスクリプト言語を作ることも目的の一つです。
どこを目標にするか
まずは四則演算や変数代入のみを扱う小規模な言語から始め、徐々に機能を拡張していくことがおすすめです。インタプリタではセルフホストを目標にすることはあまりないです。より発展したインタプリタを作りたい場合は、ガベージコレクションによるメモリ管理や、ファイル操作やネットワーク通信などの標準ライブラリを構築すると良いかもしれません。
実装する方法
インタプリタは、まず字句解析と構文解析を行い、生成された抽象構文木の各ノードに対しての動作を決定することでREPLを実装します。
その他
テストの作成
実装が進んだら、各工程が正しく動作しているかを確認するためのテストを整備することが重要です。ユニットテストを導入して字句解析、構文解析、コード生成などの各フェーズごとに検証を行い、統合テストによって全体としての動作確認を実施します。
なぜテストを実施するのか
例えば、C言語のコンパイラを自作して、以下のようなプログラムを実行したとします。
int main() {
int a;
a = 4;
return a;
}
このプログラムの終了コード（main関数から返される値）が 4 であれば、作成したコンパイラの代入機構はうまく言っていると断言できるでしょうか？
答えは No です。
もしかしたら、以下のプログラムを実行すると終了コードは 7 にならないかもしれません。
int main() {
int a;
a = 4;
a = a + 3;
return a;
}
（内部の実装ミスによって、コンパイラが異常終了したり、終了コードが 4 になったりする可能性があります。）
このように、単一のテストケースが成功したからといって、コンパイラ全体の正しさが保証されるわけではありません。このような実装ミスを防ぐために網羅的なテストを作成することが重要です。
自作言語
まず自作言語にあまり詳しくない方々のために、自作言語の目標や目的について解説していこうと思います。
自作言語とは
自作言語とは、自分自身でプログラミング言語の仕様（構文や機能）を設計し、その処理系（コンパイラまたはインタプリタ）を実装することを指します。
何のために自作言語を作るのか
自作言語を作る目的は様々です。単純に自分だけの言語を作ってみたいという好奇心、プログラミング言語の仕様や内部動作を深く理解したいという学習目的、あるいは既存の言語では不足している機能や表現力を補うためという実用的な理由などが考えられます。実際に、多くの言語はが上記のいずれか、または複数の目的で設計されています。
決めるべきこと
自作言語を作る際に決めるべき主要な項目は以下のようなことです。
実用性を担保するためにはチューリング完全性の確保や、エラーメッセージの親切さといった点にも気を配る必要があります。
チューリング完全性
チューリング完全とは、理論上、ある計算モデルが、任意のアルゴリズムを実装できる能力を持つことを意味します。つまり、あるプログラミング言語がチューリング完全であれば、その言語を用いてどんな計算やアルゴリズムも記述可能であると考えられます。ただし、実用上はチューリング完全性を単に満たしているだけでなく、使いやすさや安全性、パフォーマンスなども考慮する必要があります。
Brainf*ck
Brainf*ckとは、コンパイラがなるべく小さくなる言語として考案されたプログラム言語です。非常に可読性・記述性が低いので実用性は期待できないですが、チューリング完全です。
以下のBrainf*ckプログラムは Hello World!を出力します。
とても可読性が低いので読みたくありませんね...
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>-[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.
以下のサイトが Brainf*ck の簡単な解説をしてくれていたので貼っておきます。
コンパイラ・インタプリタの実装を教えるにあたって
せっかく「低レイヤーを教えるにあたって」という名前で記事を書いたので、私が後輩に教えるときに意識したいこともここに書いておきます。
（私は教育の専門家でも熟練エンジニアでもありません。ご注意ください。）
私がコンパイラやインタプリタの実装を新入生に教える際に注意したいことの中で一番大きいのは、実装前に注意すべきことに書いた「最初から完璧なものを実装するのではなく、簡単な処理から実装していく」ということでしょうか。
私は「低レイヤを知りたい人のためのCコンパイラ作成入門」を読んでCコンパイラを実装しましたが、ステップ・バイ・ステップで解説してくれていて、それぞれのステップでプログラムを実行できたことが学習を続ける大きなモチベーションになりました。
サークルで教える際には、実際に一緒に活動することになった新入生のレベルを見て何を教えるかを考えていきますが、その中の選択肢の一つとして今回解説したコンパイラやインタプリタの実装を提案するつもりです。
（他には自作OSの制作やセキュリティ関連のことなどを提案するつもりです。）
低レイヤーはゲームやWebサイトと違って一般の人には身近ではない（本当は深く関わっているのに認識しづらい）分野なので、「面白い！」と思っていただけるような題材を用意することが大切だと考えています。
おわりに
低レイヤー技術や自作言語の世界は、一見難解に思えるかもしれません。しかし、小さなステップから始めれば、誰でも挑戦できます。
重要なのは 「完璧を目指しすぎず、動くものを作ること」 です。最初は少しの構文しかサポートしていなくても、エラーメッセージが不親切でも、実行速度が遅くても構いません。動くプロトタイプができた後の改良は、楽しみながら進められると思います。
今回の記事では、自作言語やコンパイラ・インタプリタの実装について解説しました。具体的なコードを用いた解説記事、OSやLLVMについての記事も機会があれば書こうと思っています。
この記事にはプログラミングに関する事前知識がなくても読めるように補足をつけたつもりですが、もしわからない点やおかしいと思った点があれば、コメント欄にて気軽に教えてください。
この記事を気に入っていただけた場合は、是非いいねとフォローをお願いします。記事執筆のモチベーションになります。
参考サイト