言語処理系入門2～処理系の一連の流れ～（勉強メモ）

このシリーズは自分の勉強の形跡のために残したメモとなります。間違いを正すことも目的の一つなので間違いや違和感があれば何でも指定してください。

今回はコンパイラがどういった順番で入力プログラムを解析し、実行可能な機械語まで変換しているのかをメモしていきます。

勉強のために参考にしているもの

• 「最新コンパイラ構成技法」Andrew W. Appel (著), 神林 靖 (監修, 編集, 監修), 滝本 宗宏 (編集)
• 「実践コンパイラ構成法 (電子通信情報系コアテキストシリーズ)」滝本 宗宏 (著)

言語処理系入門シリーズ目次

• 言語処理系とは
• 処理系の一連の流れ ←ここ
• 字句解析フェーズ

用語の定義

まず最初にこの記事から出てくる用語の確認をしていく。

• フェーズ
  コンパイラ（または処理系）における処理の意味のあるまとまりのこと。例として構文解析、字句解析、フロントエンドがあげられる。
• フロントエンド
  プログラムを解析する処理の集まりのこと。入力プログラムを分解・解析するフェーズである字句解析、構文解析、意味解析、翻訳のフェーズからなり（簡単なコンパイラなら翻訳がないことも）、目的コードに変換しやすい形式へと変換する。最近では特定のプログラミング言語や目的マシンのアーキテクチャに依存しない形式まで変換するのが主流。このフェーズで解析された入力プログラムは一般に中間言語や抽象的な木構造でバックエンドに渡す。
• バックエンド
  フロントエンドから渡されたデータを最適化して目的のコードを生成する処理の集まりのこと。フロントエンドによって渡された中間プログラムを整理・変換するフェーズであるコード最適化、コード生成のフェーズからなる。
• トークン列
  意味のある単語のシークエンスのこと。例えば int main(void){hoge}というプログラムのトークン列はint, main, (, void, ), {, hoge, }となる。
• 再配置可能オブジェクトコード
  アセンブラが生成する"機械語とそれに付随するシンボルの情報やアドレスの参照先情報といった付加情報をもつ特殊なフォーマットを持つファイル"のこと。この参照先の情報を用いてリンカ（詳しくは以下の説明）によって配置され実際に実行できるようにされる。詳しくはWikipedia参照。

フェーズの一連の流れ

処理系は大体次のような順番で上から順に処理される。簡略化や複雑化、まとめ方の違いなどで詳細は変わることが多いので要注意。詳しくは次で解説する。

番号	フェーズ名	入力プログラム	出力プログラム	分類
1	字句解析	ソースコード	トークン列	フロントエンド
2	構文解析	トークン列	抽象構文木	フロントエンド
3	意味解析	抽象構文木	抽象構文木	フロントエンド
4	翻訳	抽象構文木	中間表現木	フロントエンド
5	最適化	中間表現木	中間表現木	バックエンド
6	コード出力	中間表現木	アセンブリ言語→次へ その他→終了	バックエンド
7	アセンブラ	アセンブリ言語	再配置可能オブジェクトコード	バックエンド
8	リンカ	再配置可能オブジェクトコード	機械語	バックエンド

フロントエンド

1. 字句解析(Lexical analysis)

文字列の集まりでしかないソースコードを意味のある単語のトークンに分割する解析を行い入力として扱いやすいトークンの列（トークン列）を生成するフェーズ。ここでコメントや余分な空白など目的のコード生成に必要ないものは破棄される。
この字句解析フェーズの実装において一から手作業で字句解析プログラムを書いても良いが、Lex（名前は生成するプログラムの使用言語によって変化する）というツールで正規表現から字句解析プログラムを有限オートマトンという有向グラフで形式化されたプログラムとして生成することで済ませることが多い。

2. 構文解析(Syntax analysis)

字句解析によって得られたトークン列を入力に用いたプログラミング言語（原始言語という）の文法にあっているかを解析し、元のソースコードの実行順序を表す構文木を作成する。このトークン列の解析に用いられる手法として、入力を左から右に読んでいくLR(n)、その単純な拡張のSLR、状態数を減らしたLALR(n)などがある。（括弧内のnは先読みするトークンの個数）この構文解析の手法にはそれぞれ解析できる文法とできない文法が異なってくるので一律にこれを使うべきだという手法はないが、一般的なプログラミング言語はLALR(1)が機能的に十分で比較的素早く動いてくれることからLALR(1)の手法を構文解析時に扱っている。
そして構文の解析後にいらないトークンを捨てただけでは解析結果の構文木（具象構文木という）は区切りトークンなどの無駄が多く扱いにくい。そこで構文木の"木構造がトークン列の構造情報を要領よく伝達している"性質を用いて今後の処理で扱いやすく、あまり文法に依存しない構文木である抽象構文木に変換する。この具象構文木から抽象構文木への変換処理を一つのフェーズとみなして構文解析動作フェーズと言ったりする。
構文解析もYaccというツールで自動で生成できる。ただしソースコードの文法を指定するのに正規表現ではなく、BNF形式などの文脈自由文法といわれる文法生成規則を入力とする。最近では文法が難しいプログラミング言語が普通になってきたのでYaccを使わず構文解析のコードを書くのは大変難しい作業となっている。

3. 意味解析(Semantic analysis)

意味解析は構文解析によって得られた抽象構文木から型や変数、関数といった識別子の意味である対応表となる記号表を用いて型に関する正しさを解析するフェーズである。記号表というのは{a → int, s → string}のように表示できる束縛の集合のことである。この記号表を基に追加・探索・更新・削除を繰り返しながら識別子の有効範囲（スコープともいう）を調べていく。ここで記号表を一つだけとして局所変数の対応を削除するとその上位の同じ名前の変数の情報がなくなってしまうので記号表を変更するときは記号表の前の情報と変更する情報を使って新しい記号表を作成し、古い方をどこかにストックしておき、新しい方を使うようにするといった対策が必要になる。またこの記号表の対応先として追加できる型や変数名、関数名を保持するための環境も用意しておく必要がある。

4. 翻訳(Translate)

コンピュータの細かい仕様に依存せずに目的とするマシンの操作を表現できる抽象マシンコードからなる木構造（中間表現木すなわちIR木）に変換するフェーズ。このフェーズはフロントエンドとバックエンドをつなぐ一種の糊みたいな役割を果たす。次の最適化フェーズをここでまとめて行うことも多い。
実はこの翻訳フェーズで最適化して直接機械語へと変換することもできる。ただし、それを行うとN種類のソースコードをM種類の環境にコンパイルしようとするとN*M種のコンパイラを作成する必要がある。N=1ならまだいいかもしれないがコンパイラのフロントエンドとバックエンドが密接すぎるのは変更などが行いにくく、コンパイラの移植性とモジュール性が悪くなってしまう。ちなみにこのフロントエンドとバックエンドの独立性を高め中間表現木で張り合わせることを特化させたのがLLVMである。LLVMはフロントエンドとバックエンドをつなげるときに最適化も行い、バックエンドで目的マシン毎に最適化している。

バックエンド

アセンブラのフェーズ以降の情報が不足している為、情報収集の必要あり。

5. 最適化(Optimisation)

中間表現木の制御フロー（命令の並び方）の解析とデータフローの解析（変数の使用、未使用の解析など）を行うことで、命令をまとめたり不必要な命令や未使用変数の宣言を削除したりすることで生成するコードを最適化するフェーズ。この最適化が上手なコンパイラほど生成するコードが同種のコンパイラが生成するコードより高速に動作する。

6. コード出力(Generate code)

最適化によって整理された中間表現木をアセンブリ言語に逆変換するフェーズのこと。雑に説明すると木構造を文字列に変換するだけなのでアセンブリ言語を知っていれば他のフェーズと比べて比較的簡単に実装ができるはず。アドベントカレンダー2017 24日目: [コンパイラ] コード生成とかも参考になる。
最初のフェーズ一覧で機械語を出力して終了することもあると書いたが、人が読みやすいアセンブリ言語に変換するのが普通のようだ。

7. アセンブラ(Assembler)

コード出力によって得られたアセンブラをアセンブラでコンパイルするフェーズ。このフェーズによって拡張子がoである hoge.oのようなファイルが作られる。
手元にここら辺の情報がそんなにないので、ここら辺を詳しく書いた本がほしい。

8. リンカ(Linker)

アセンブラによって生成された再配置可能なオブジェクトファイルをリンカ（リンケージエディタ）と呼ばれるソフトウェアで実行できるように参照情報をリンクさせて実行ファイルへと変換する。ここでライブラリのファイルパスやアドレスの問題が解決される。詳しくはWikipedia参照とのこと。
手元にここら辺の情報がそんなにないので、ここら辺を詳しく書いた本がほしい。