コンパイラ原理再訪

コンパイラ

コンパイラもまたプログラムであり、ある言語（ソース言語）で記述されたプログラムを読み取り、それを別の言語（ターゲット言語）で記述された等価なプログラムに翻訳します。

すなわち、ソースプログラムを入力し、ターゲットプログラムを出力するプログラムであり、ソースプログラムを意味的に等価なターゲットプログラムにマッピングすることができます：

       コンパイラ
ソースプログラム -------> ターゲットプログラム

ソースプログラムは一般的に可読性の高い文字列であり、ターゲットプログラムにはさまざまな形式があります：

マシンコード。例えば、C言語をコンパイルして得られる実行可能なバイナリプログラムなど
中間バイトコード。例えば、JVM向けの .class ファイルを生成するJavaのコンパイルなど
文字列。例えば、Babelによって変換されたJavaScriptコードなど

実のところ、これは翻訳です。例えば、文字列からマシンコードへのコンパイルは、人間が理解できるコード言語を、マシンが「理解」（認識・実行）できるマシン言語に翻訳することです。これにより、ユーザーはターゲットプログラムを介してマシンと対話できるようになります：

         ターゲットプログラム
ユーザー入力 ---------> 输出

P.S. コンパイラとよく似ているものにインタプリタがありますが、違いはターゲットプログラムを生成するプロセスがない点です：

                 インタプリタ
ソースプログラム & ユーザー入力 -------> 输出

実行時に解釈して実行するため、一般にインタプリタ型言語の実行効率はコンパイラ型言語よりも低くなります。

コンパイルプロセス

2つの部分に分かれます：

分析：ソースプログラムを複数の部分に分解し、文法構造を加えて、中間表現形式と記号表（symbol table）を生成します
合成：中間表現形式と記号表に基づいてターゲットプログラムを構築します

典型的なコンパイラの処理手順は以下の通りです：

（入力）文字ストリーム
|
|- 字句解析器（lexer）
|  （生成）トークンストリーム
|  （生成）記号表
|- 構文解析
|  （生成）構文木
|- 意味解析
|  （生成）構文木
|- 中間コード生成器
|  （生成）中間表現形式
|- マシン非依存コード最適化器
|  （生成）中間表現形式
|- コード生成器
|  （生成）ターゲットマシン言語
|- マシン依存コード最適化器
v
（出力）ターゲットマシン言語

主な手順は字句解析、構文解析、意味解析、およびコード生成であり、中間コード生成と2段階の最適化はオプションです。

字句解析（lexical analysis）

コンパイル作業の第一歩であり、文字ストリームを字句単位（token）のシーケンスに変換することを目的とします。

Takes raw input, which is a stream of characters, and converts it into a stream of tokens, which are logical units, each representing one or more characters that "belong together."

例えば：

// 入力
position = initial + rate * 60

// 出力
[
  (id, 1),
  (=),
  (id, 2),
  (+),
  (id, 3),
  (*),
  (number, 4)
]

具体的なプロセスは、文字を1つずつスキャンし、コメントや空白文字を取り除き、文字ストリームを語彙素（lexeme）に分割することです：

position,=,initial,+,rate,*,60

次に、語彙素をトークン形式に変換します：

(token-name, attribute-value)

トークンは文字の上に構築された第一層の抽象化です。このようなキー・バリューペアの形式をとるのは、その後のプロセスの多くでタイプ（token-name）のみに注目すればよく、最終的なコード生成時にのみ詳細な値情報（attribute-value）が必要になるためです。そのうち token-name は構文解析ステップで必要な抽象記号（例えば、識別子を表す id）であり、attribute-value は記号表におけるその語彙素のインデックスです：

[
  (1, position),
  (2, initial),
  (3, rate),
  (4, 60)
]

記号表

記号表は、コンパイラがソースプログラムの構造に関する様々な情報を保存するために使用するデータ構造です。

分析フェーズで生成され、合成フェーズで使用されます：

効果の面から見ると、記号表の役割は、情報を宣言された場所から実際に使用される場所へと伝達することです。

字句解析器が持つ情報は限られているため（語彙素のリテラル）、生成される記号表には基本情報（語彙素のリテラルと識別子のマッピング関係）のみが含まれます。その後、構文解析器が意味情報に基づいて、既存の記号表のエントリを使用するか、新しいエントリを作成するかを決定します。

また、記号表はグローバルに1つだけ存在するのではなく、スコープごとに独立した記号表が存在します。その目的は、プログラムの異なる宣言ブロックで同一の識別子を繰り返し出現させることができるようにすること、つまり異なるスコープ下で変数名が衝突しないようにすることです。同時に、文ブロックの最近接（most-closely）入れ子規則をサポートするために、これらの記号表を入れ子レベルに従ってリンクさせ、ツリー構造を形成して、継承やクロージャなどの言語特性をサポートする必要があります。

P.S. キーワードも識別子と同じように記号表に格納され、表を検索する際にリターンコードによって区別されます。

構文解析（syntax analysis）

構文解析フェーズでは、token-name を受け取り、構文構造を記述するためのツリー状の中間表現を作成すると同時に、構文エラーをチェックします。

Check input is well-formed and build a parse tree or similar representation of input.

例えば、抽象構文木（abstract syntax tree）は一般的な中間表現形式であり、ソースプログラムの階層的な構文構造を記述できます。ツリーの各ノードは演算を表し、子ノードはその演算のオペランド（演算対象）を表します：

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      (number, 4)

構文木は文字の上の第二層の抽象化です。ここに至って、優先順位と結合性の概念��登場します。演算はこれらの規則に従ってオペランドを一致させ、一意のツリー構造を生成する必要があります（文法に曖昧さがないことが求められます）。このフェーズでは、入力されたソースプログラムの形式が正しいかどうか、例えば括弧が対応しているかなどを確認できます。

文脈自由文法

言語の文法構造は、通常、文脈自由文法（context-free grammar）によって定義されます。例えば：

if (expression) statement else statement

対応する生成規則（production）は次の通りです：

stmt -> if (expr) stmt else stmt

ここで expr や stmt といった変数は非終端記号（nonterminal）であり、終端記号（terminal、if や () といった字句要素）のシーケンスを表します。

文脈自由文法は4つの要素で構成されます：

終端記号集合：言語の基本記号の集合
非終端記号集合：文法変数とも呼ばれ、終端記号のシーケンスに置き換えることができます
生成規則集合：ある構造の記述形式を表すために使用されます
開始記号：開始記号として1つの非終端記号を指定します

開始記号から出発し、非終端記号を右側の生成規則の本体に置き換え続けるプロセスを導出と呼びます。開始記号から導出できるすべての終端記号シーケンスの集合が、その文法によって定義される言語です。逆に言えば、言語とは生成規則に従った一連の終端記号列です。

例えば、CSSのプロパティ宣言に対応する文法：

// 終端記号
ident	[-]?{nmstart}{nmchar}*
// 非終端記号
IDENT	{ident}
// 生成規則
property    : IDENT;

P.S. 開始記号は stylesheet であり、対応する生成規則は stylesheet : [ CDO | CDC | S | statement ]*; です。詳細はCSSコア構文を参照してください。

優先順位と結合性

演算の優先順位と結合性も、生成規則によって定義されます。例えば：

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

意味は以下の通りです：

factor：どの演算子によっても分割できない式。演算対象の最小単位であり、数値であるか、括弧で保護された式です。
term：高優先順位の演算子（* と /）によって分割できますが、低優先順位の演算子（+ と -）によっては分割できない式です。
expr：一般的な式。上記のどの演算子によっても分割できる式です。

したがって、優先順位を制御する考え方は、各優先順位に専用の非終端記号を割り当て、その優先順位またはそれ以上の優先順位の演算子によって分割できる式を表すことです。

意味解析

このフェーズでは、入力された構文構造が言語の要求を満たしているかどうかの静的チェックが行われます：

型チェック（type checking）：例えば、各演算子が一致するオペランドを持っているか、配列のインデックスのデータ型が正しいかなどを確認します。
型変換（coercion）：例えば、オペランドに対して暗黙の型変換を行います。

例えば：

=
  (id, 1)
  +
    (id, 2)
    *
      (id, 3)
      inttofloat
        (number, 4)

P.S. ここで inttofloat は整数型から浮動小数点型への単項演算を表しており、型変換の中で挿入される操作です。

中間コード生成

構文解析と意味解析が完了した後、次にマシン言語に近い中間表現を生成することがあります。この表現形式には2つの特徴があります：

生成が容易である（あくまで中間表現であり、生成コストが高すぎてはならない）。
マシン言語への翻訳が容易である（一歩ずつターゲット言語に近づいていく）。

例えば、三番地コード（three-address code）は、アセンブリ命令に似た一般的な中間表現形式です：

t1 = inttofloat(number4)
t2 = id3 * t1
t2 = id2 + t2
id1 = t3

コード最適化

2つのカテゴリに分かれます：

マシン非依存の最適化：より良いターゲットプログラムを生成するための中間表現に対する最適化。例えば、Closure Compiler が JavaScript コードに対して行う最適化（ループの最適化、デッドコード削除、冗長なコードの簡素化など）があります。
マシン依存の最適化：ターゲットプログラムに対する最適化。CPUレジスタやメモリ参照などが含まれ、並列性やメモリ階層構造などのコンピュータアーキテクチャの特性を最大限に活用することを目的とします。

前者は中間コード生成プロセスの後に行われ、後者はターゲットプログラム生成の後に行われる、出荷前の最後の工程です。

P.S. 例えば、前のステップの inttofloat 型変換はコンパイル時に完了させることができ（60 を 60.0 に変換する）、これはマシン非依存の最適化と言えます。

コード生成

中間表現形式を入力し、ターゲット言語を出力します。例えば、マシン言語を生成する場合、各変数にレジスタやメモリ位置を割り当て、中間表現を等価なマシン命令シーケンスに翻訳する必要があります。

最適化された三番地コードに対応するマシン言語（どの言語かは不明ですが、アセンブリのように見えます）は次の通りです：

LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1

2つのレジスタ R1 と R2 を使用し、id3 を読み込んで R2 に格納し、60.0 と乗算して、その積を R2 に格納します……最終的に R1 の値が id1 に対応するメモリ番地に格納され、代入が完了します。

マシン依存の最適化を考慮しない場合、コンパイルプロセスはここで終了します。論理的には字句解析、構文解析、意味解析、コード生成という4つの必須工程を経ることになります。実際の開発では、これらの工程が必ずしも明確な境界を持っているわけではなく、パフォーマンス向上のためにできるだけ1回のパスで複数の工程を完了させることがあります。

参考資料

『コンパイラ―原理・技法・ツール』（Dragon Book 第2版）
http://infolab.stanford.edu/~ullman/dragon/slides1.pdf
Compiler Design - Code Optimization
Compiled language