記事一覧
対象読者
- コンパイラの内部構造について興味がある方
- コンパイラに関して精通している方（批評お待ちしております）
ワンパスコンパイラ
突然ですが，初めてコンパイラを作るのであれば，大抵次のような構造になると思います．
図中の赤い部分は，どんなにシンプルなコンパイラでも含まれているだろうという意味を込めたものです．字句解析や中間言語生成はそれぞれ構文解析やコード生成と区別化がつかなくなっている場合もあるかと思います．
ここで図中に，一つのパスと書かれているのが気になった方もいるかと思います．
パス
プログラムのとある表現（ソースコードや中間言語）は，ある操作を施されて別の表現へと移っていきます．この時，ある操作やそれを行うためのルーチン群のことをパスと呼びます．
この説明だと，ASTが中間言語へ変換されるのも一つのパスだと数えられないのか？という疑問が浮かびます．
しかし，おそらくシンプルなコンパイラならば，字句解析からコード生成までが逐次行われていて，「構文解析が完全に済んだから，ASTに対してコード生成を始めよう」，というような構造にはなっていないかと思います．そういう意味で，シンプルなコンパイラはワンパスと言われています．逆にそのような構造ではなくて，段階ごとにしっかり分離された設計になっているのならば，次に説明するマルチパスコンパイラであると言えます．
マルチパスコンパイラ
マルチパスコンパイラは以下のような構造をしています．
マルチという言葉の通りパスが複数ありますね．何が増えたのかというと，最適化パスが増えています．
ワンパスコンパイラのような逐次処理では困難だったコンパイル単位での処理が，マルチパスコンパイラでは可能になります．最適化が実装しやすくなるので，マルチパスコンパイラは最適化コンパイラとも呼ばれます．
実例
世の中で使われているコンパイラはマルチパスのものが多いですが，実際どのような構造なのでしょうか．
具体例を見たほうが分かりやすい方も多いと思うので紹介します．
GCC
GNU C Compiler Internals/GNU C Compiler Architecture
画像はgccの内部構造です．一目見るだけでマルチパスだとわかります．GIMPLEやRTLなど見慣れない言葉もあるかと思いますが，とりあえず今は気にしなくて大丈夫でしょう．
LLVM
Design and Implementation of a TriCore Backendfor the LLVM Compiler Framework (p.10)
画像はLLVMの構造です．(LLVMはコンパイラ基盤なので，中間言語以降を対象にしていると思えばよいです．)
とにかくたくさんの工程を経てアセンブリが出力されていることが分かります．この画像では中間言語(LLVM-IR)に対する最適化が描かれていないので，実際にはもっと長くなります．
一つ一つのパスは広大で，小さなコンパイラほどの規模を持ちます．私は高校3年生の時の通学時間をスマホでLLVMのソースコードリーディングをすることに割きましたが，どのパスも最後まで読むことはできませんでした．もっとコードリーディングが上手くなりたいですね．
次の記事
coming soon
いよいよ具体的な最適化手法の説明に入ります．まずは身近で簡単なものからです．