18日目: [コンパイラ] ソースコードから機械語までの道筋
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の18日目の記事です。
今日からは、そのCPU上で動く機械語を吐くためのコンパイラを製作していく。 昨日まではCPUだのx86だの馴染みのない世界の話を続けてきたが、一気に日常世界にワープした。
製作の準備として、今日はコンパイラ自作最速マスターをやろうと思う。
// 簡単なC言語のソースコード int main () { int a ; a = 3 ; return 0 ; }
このソースコードがコンパイラ内部でどのように変換されていくか見てみよう。 この内容は、明日以降やる内容のダイジェスト版になっている。
1日目: 字句解析
コンパイラに文字列が渡されると、まず初めに字句解析 (lexical analysis) が実行される。
字句解析とは、あるルールに従ってソースコード内の単語に属性を与えることだ。 単語と属性のペアはトークンと呼ばれている。
ここでは以下のルールに従って字句解析を行う。
これはBNFという表記法で書かれた字句解析ルールで、左側で宣言された属性を、右側の正規表現(みたいなやつ)で定義している。
IDENTIFYとNUMBERの定義では、正規表現の(hoge|piyo)*が使われている。
BNFの重要なポイントは正規表現を代入できるところだ。
IDENTIFYとNUMBERの定義の中には、緑文字のCHAR_ALPHABETやCHAR_NUMBERが存在している。
正規表現を使って正規表現を定義しているので、一種の代入とみなせるだろう。
このルールを用いてソースコードを字句解析した結果は
各単語に緑文字の属性が付与された。
2,3日目: 構文解析
突然だが、以下の英文を読んで欲しい。
No one in the neighbourhood believed him to be a genius even after he had achieved world-wide fame.
(彼が世界的な名声を得た後でさえ、近隣住民は誰も彼のことを天才だと思わなかった。)
この文章の主語は No one in the neighbourhood だ。 5単語で主語を構成しているが、その中の No one が名詞句で、in the neighbourhood は形容詞句になっている。
文全体:No one in the neighbourhood believed him to be ... ↓ (主語:No one in the neighbourhood, 動詞句:believed him to be, ...) ↓ (名詞句:No one , 形容詞句 in the neighbourhood)
つまり文章はツリー構造を形成している。 文法規則に基づき、文章をツリー化することを構文解析という。 文章内の各単語の属性(名詞、形容詞等の種類のこと)に対し、SVOやSVOCなどの構文解析ルールを適用することで、ツリー構造が明らかになる。
コンパイラは、これと全く同じ操作をソースコードに対して行っている。 前節で行った字句解析は、No→形容詞, one→名詞という操作に対応している。 字句解析の結果をもとに構文解析を実行し、ソースコードのツリー構造を明らかにしたい。
ここでの構文解析ルールとして以下のBNFを使うことにしよう。
左側の赤字は、右側の赤字と緑字を用いて再帰的に定義されている。 英語に例えると、左辺の赤字で宣言したものは主語や名詞句、形容詞句に対応する。 右辺の緑字は名詞や形容詞に対応し、トークン(単語)の属性を表している。 混乱を避けるため、今後は緑字をトークン属性と呼び、赤字をノード属性と呼ぶことにする。
構文解析で得られたツリーのことを、解析木という。
4日目: 抽象構文木
解析木は構文解析ルールに基いてソースコードを厳密に解析したものだが、ややこしすぎる。
例えば3や0が連なってる部分は不要だろう。
これらのナンセンスな部分を削除し、シンプルなツリーに変換したものを抽象構文木という。
だいぶ見やすくなった。
5日目: シンボルテーブル
抽象構文木の赤枠のノードに着目して欲しい。 これらは関数や変数の宣言を表すノードだ。
F_DEC: 関数宣言V_DEC: 変数宣言PROTOTYPE: 関数プロトタイプ
これら宣言を表すノードを処理し、情報をまとめたものをシンボルテーブルと呼ぶ。
特に重要なのは、赤で書いた変数のアドレス。
アセンブラコードを生成する際に、メモリ上の変数の値を[変数のアドレス]で参照することになる。
6日目: コード生成
抽象構文木に含まれる、宣言以外のノードを処理しよう。
ノード属性毎に処理方法をまとめたテンプレートを作っておくと、処理しやすい。
抽象構文木の頂上はPROGRAMなので、最初に発動するテンプレートもPROGRAMになる。
PROGRAMの下のF_DECについては、シンボルテーブル作成時に処理済みなのでスキップする。
次に発動するのはmain関数のテンプレート。
こいつはPROGRAMテンプレートの(中のツリー処理)と書かれた部分に埋め込まれる。
更にASSIGNやRETURNのテンプレートも発動し、main関数テンプレートの中に埋め込まれる。
こうした手順で抽象構文木にテンプレートを適用していくと、以下のアセンブラコードが生成される。
ここまでくれば、一週間前に解説した x86の命令セット表 を参照して即座に機械語に変換できる。
以上でコンパイラの動作説明は終わりだ。 処理が数段階に別れているので、1日1ステップずつ詳細を解説しようと思う。
沿革
僕が始めてコンパイラを作ったのは2017年の2月だった。当時のコミットログを載せておく。
| 日付 | 時間 | 進捗 |
|---|---|---|
| 2/05 (日) | 13:13 | 字句解析と構文解析のBNFを策定 |
| 2/07 (火) | 02:47 | 字句解析が完了 |
| 2/08 (水) | 10:41 | 解析木の生成ルーチンを作り始める |
| 2/09 (木) | 19:55 | オレオレ単体テストフレームワークを追加 |
| 2/10 (金) | ----- | 解析木のテストコードを書きまくる |
| 2/11 (土) | ----- | 解析木のコードを書きまくる。 |
| 2/12 (日) | ----- | 解析木がなんとなく完成する(バグだらけ) |
| 2/12 (日) | 22:31 | 抽象構文木の生成ルーチンを作り始める |
| 2/15 (水) | 05:27 | 抽象構文木の生成が完了 |
| 2/16 (木) | 00:35 | シンボルテーブルの作成を開始 |
| 2/17 (金) | 09:02 | シンボルテーブルの作成が完了 |
| 2/18 (土) | 12:09 | コード生成のルーチンを作り始める |
| 2/19 (日) | 02:37 | 関数の再帰呼出によるフィボナッチ数fib(10)=55のコードがコンパイルできた |
ちょうど二週間で完成したらしい。 一番しんどかったのは解析木の作成だった。 今コミットログを見返しても、カオスすぎて何をやってるのかよくわからん。 当時、「このままじゃヤバい、先に自動テスト環境を整えよう」という危機感でマクロによるオレオレテストフレームワークを作った。 そしてテストコードを量産した後に、懸案の解析木を作るとうまくいった。
どうでもいい話
明日から解説するコンパイラはCで書かれているが、その理由は「Cっぽい言語のコンパイラをC言語で作っておけば、セルフコンパイルできるかも」という儚い夢に基づくものだった。 「正規表現ライブラリを使うのは、コンパイラ内部処理を知るという主旨に反するので、禁じ手」というレギュレーションも課した。
こういう野心は大切だと思うけど、今思うと、もっと文字列処理に向いた言語を使ったほう良かったかもしれない。 コンパイラの内部処理は変換の連続だし、関数型言語で書くのが簡単だったと思う。
ストイックなことを言えば、コンパイラを自作して内部処理を勉強する際に、既存のCコンパイラを使うのは反則だと思う。
例えば、標準出力の内部処理を理解したいとする。 そのときに「C言語のprintf関数を使って標準出力を自作した。よって理解できた」はダメだよね。 printfによって、システムコールのwriteや、その先にあるCPUの割り込みint 0x80が隠蔽されている。 C言語を使っている限り、C言語が隠蔽してしまった構造は見えないのだ。 そういう理由により、アセンブラだけで言語処理系を構築しないと真の理解には至らないはずだと思っている。
それでは、明日から字句解析をやっていこう～
