Rust+LLVMでコンパイラを作る：#2 概要と方針

本連載のバックナンバー

• #1: 環境構築
• #2: 概要と方針
• #3: 大枠づくり
• #4: 電卓づくり
• #5: ファイルの分割と単体テスト

はじめに

本記事は、 Rust 言語と LLVM を用いてプログラミング言語のコンパイラを作成するチュートリアルの連載第二回です。
前回の記事 では、コンパイラ作成のための環境構築を行いました。

前回の投稿から一ヶ月たってしまい¹、そろそろ第二回を投稿しないとまずいかなーという気がしてきたので、今後必要となる用語等の簡単な説明や、本連載で作成するコンパイラの方針について取り急ぎ投稿します。

今回から読み始めた方は、前回の記事を参照して環境構築をおこなうか、

FROM alpine:edge
RUN apk add --no-cache llvm8-dev llvm8-static zlib-static libxml2-dev gcc g++ cargo rust && \
    mkdir work
ENV LLVM_SYS_80_PREFIX=/usr/lib/llvm8
ENV PATH=/usr/lib/llvm8/bin:$PATH
WORKDIR /work
ENTRYPOINT ["cargo"]

このような Dockerfile で Rust とLLVM, gcc がある環境を構築しておいてください²。

各種概要

本連載ではコンパイラの仕組みや Rust に馴染みのない読者も対象にしています。ここではそうした方々に向けて、いくつかのトピックについて簡単に解説しておきます。Rust や コンパイラ実装に慣れている方は、この節を読み飛ばしていただいても構いません³。

Rust 言語について

Rust は実行速度と安全性の両立を目指した、比較的新しいプログラミング言語です。この言語にはいくつかの特徴的な概念があり、特に所有権（ownership）や借用（borrowing）、生存期間（lifetime）といった概念は、他の言語のユーザにとっては習得しづらい概念かと思います。

本連載でも必要に応じて、こうした概念についての解説を細かく入れていきたいとは思いますが、筆者の下手な解説よりは、The Book（邦訳）に一通り目を通してみたほうが理解しやすいではないかと思います。

コンパイラの構成について

コンパイラは典型的に、以下のようなフェーズから構成されます。そこで我々が実装するコンパイラも、このオーソドックスなスタイルに従いたいと思います。また、今後使用する（可能性が高い）用語は初出時に 強調 して示します。

1. 文字列として入力されたソースコードを意味のある単位で切り分けたり、スペースや改行を読み飛ばしたりして、トークン列 を生成する 字句解析 フェーズ。これを行うモジュール等を、 トークナイザ （tokenizer, 別名 lexer や scanner） と呼びます。
2. トークン列を解析し、トークン間の関係を木構造で表した 抽象構文木 （Abstract Syntax Tree; AST）を生成する 構文解析 フェーズ。これを行うモジュール等を パーサ と呼びます ⁴ 。
3. 抽象構文木を解析し、そのプログラムに含まれる処理の意味を解析する 意味解析 フェーズ。ここでは、プログラム中の型が正しいかを調べる 型検査 を始めとする様々な処理を行います。
   • またこのあたりで、ASTを今後の処理が楽になるような形式に変換します。この形式を 中間表現 ⁵⁶（Intermediate Representation; IR）と呼びます。
4. 中間表現を操作し、より実行効率のよい形に変換する 最適化 フェーズ。
5. 最適化が終わった中間表現から、目的とするコード（実行バイナリやアセンブラ、他の言語のソースコードなど）を生成する コード生成 フェーズ

それぞれのフェーズについてより詳しく学びたい方は、ドラゴンブックなどの書籍や、「低レイヤを知りたい人のためのCコンパイラ作成入門⁸」などのwebページを読むことをお勧めします。

LLVM について

LLVM は2000年にイリノイ大学で開発が開始された、オープンソースのコンパイラ基盤です。

従来であれば、実用的なコンパイラのバックエンド部分を実装するには、各種最適化やレジスタ割り付け、アーキテクチャ別のコード生成など、非常に難しい課題をひとつひとつこなしていかなければなりませんでした。しかし、LLVM を使用することで、コンパイラ開発者は LLVM-IR という（比較的）高級な言語に対するコード生成部を書くだけで、前述の面倒事を LLVM に簡単に肩代わりさせられるようになりました。

最近の（ネイティブ向けの）メジャーなコンパイラはバックエンドに LLVM を使用していることが多く、コンパイラ基盤の最大手、あるいはデファクトスタンダードとも言える状況になっています。そのため、本連載でも LLVM を使っていきたいと思います⁹。

LLVM 自体は C++ によって書かれていますが、 LLVM を C++ 以外の言語から利用するために C 言語用のインタフェースが整備されています。
Rust 向けには、この C 用のインタフェースを利用するための llvm-sys というライブラリがあり、更に llvm-sys をより扱いやすくするための inkwell というライブラリがあります。本連載では、この inkwell を使用していきます¹⁰。

この連載の方針

本連載では、独自の言語（いわゆるオレオレ言語）のコンパイラを作成することとします。これは、

• 既存の言語のフルセットの実装は難しく、入門記事としてはふさわしくない
• 独自言語であれば、実装が困難な点について言語仕様の側を曲げられる
• 何より、独自言語のほうがモチベーションを保ちやすい¹¹

といった点が主な要因です。

また、可能な限り外部のライブラリ等を利用し、実装上の難点を極力回避することにより、読者が Rust という言語の面白さや言語処理系実装の雰囲気といったものを手軽に体感できるようにしていきたいと思います。

最後に

本記事では、典型的なコンパイラの構成および Rust, LLVM の概要について簡単に紹介し、今後の実装方針についていくつか記述しました¹²。
次回こそコンパイラの制作に入っていこうと思います。

それでは次回¹³をお楽しみに。

2022/06/30追記: 本連載の第三回はこちらです。

1. コンパイラ関係の用語の説明に労力を割きすぎてダルくなったのと、書いている途中で別プロジェクトのコーディングに夢中になってしまったので…… ↩

2. 今回は座学だけなので、構築した環境は使いませんが…… ↩

3. どちらにも習熟している方は、そもそもこの連載を読む必要はないかと思いますが…… ↩

4. パーサの種類によっては、このトークナイザが不要だったり、（狭義の）パーサとトークナイザをあわせて（広義の）パーサと呼んだりします（ややこしい）。 ↩

5. アセンブラ等の低級言語に似ている場合、中間言語（intermediate language）と呼んだりもします。 ↩

6. 実装によっては、中間表現を２段階以上持つ場合もあります（e.g. 我らが Rust （の公式実装である rustc ）では、HIR と MIR という二段階の中間表現を経てLLVM-IRに変換されます）。
   このうち、中間表現を生成するまでの 1. から 3. までをまとめて フロントエンド 、その後の 4. と 5. をまとめて バックエンド と呼びます⁷ 。 ↩

7. フロントエンドとバックエンドの境界は曖昧で、実装等によってまちまちです。 ↩

8. lld の作者である植山類さんが書かれている、C言語で C言語を実装するチュートリアルです。コンパイラ作成のチュートリアルとしてとても良質なのはもちろん、コラムがとても面白いので一読してみることをおすすめします。 ↩

9. 各種最適化やコード生成って正直難しすぎるし、筆者のような素人ではいくら頑張っても LLVM には勝てないので…… ↩

10. inkwell でも LLVM の基本的な概念をそのまま踏襲しているため、Rust 以外の言語から LLVM を触る場合でも役に立つ内容かと思います。 ↩

11. オレオレ言語だと、仕様を妄想してニヤニヤできるので ↩

12. 前回「次回からはいよいよコンパイラの制作に入っていこうと思います」とか書いたのにね ↩

13. もしあれば ↩