Dragon Book
# Preface
Reference: [Aho] コンパイラ 原理・技法・ツール ("Dragon Book")
\pagebreak
# コンパイラ
~~~
計算機のプログラムをわかりやすい形で書き、それを機会で実行できるようにしたいという願いから、
コンパイラは高級言語のプログラムを計算機自身の言葉に翻訳するプログラムとして、1950年代に誕生
人間の話すプログラミング言語 → コンパイラ → 計算機が理解できる機械語
ストリーム → 文法 → 解析木
文法をアセンブリで書くことができたらいい訳だ。
アセンブリは機械語と一対一だが、
コンパイラは複数の機械に命令を出すことができる。
ある言語で書かれたプログラムを読み込んで、
それを等価な別の言語のプログラムに翻訳するプログラム
原始言語 → コンパイラ → 目的言語
↓
誤りメッセージ
原始言語：
Fortran：（コンパイラでは最初となるFortranコンパイラではコンパイラの実現に18年人を要した。）
Pascal
etc
目的言語：機械語の事
パス：入力ファイルを一回読み込んで処理する単位のこと
~~~
## 構文解析
構文解析のフロー図
~~~
position := initial + rate * 60
↓
字句解析routine
↓
id1 := id2 + id3 * 60
↓
構文解析routine
↓
:=
/ \
id1 +
/ \
id2 *
/ \
id3 60
↓
意味解析routine
↓
:=
/ \
id1 +
/ \
id2 *
/ \
id3 inttoreal
|
60
↓
中間コード生成routine
↓
temp1 := inttoreal (60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
↓
コード最適化routine
↓
temp1 := id3 * 60.0
temp2 := id2 + temp1
↓
コード生成ルーチン
↓
MOVF id3, R2
MULF #60.0, R2
MOVF id2, R1 ← アセンブリコード
ADDF R2, R1
MOVF R1, id1
~~~
コンパイラが関係する処理系
-----------------------------------------------------------------------
前処理系
1. マクロ処理
綴りの長い構文要素を略記するために、使用者はマクロを定義する事ができる。
2. ファイルの挿入
Cの前処理系はプログラムに 文 `#include ` があると、その文をファイル `` の内容に置き換えてしまう。
3. ”言語の合理化のための”前処理系
古い言語に新しい制御の流れに関する機能やデータ構造か機能を加えて、言語の増強をはかる。
たとえば、プログラム言語自身に `while`文 や `if`文 のような構文要素がなかったとすると、
それらを組み込みマクロとして用意し、前処理系によってそれらを利用できるようにする。
4. 言語の拡張
たとえば、Equal言語 ( Stonebraker ほか 1976 ) は、データベース問合せ言語をCの中に埋め込んだ形をとっている。
前処理系が `##` で始まる文を見つけると、それはC言語の文ではなく、データベース アクセス文とみなす。
TEX清書システムには汎用のマクロ機能がある。マクロ定義の形式は次の通りである。
~~~tex
\define <マクロ名> <テンプレート> { <本体> }
\define \JACM #1;#2;#3.
{ { \sl J.ACM } {\bf #1}:#2, pp. #3.}
~~~
* `\sl` はイタリック体にするための指定
* `\bf` 太字で表示するための指定
たとえば、`\JACM 17;4;715-728` と書くと
~~~tex
J.ACM 17:4 ,pp. 715-728
~~~
が得られる。
アセンブラと機械コードの関係
-----------------------------------------------------------------------
アセンブリコード：機械コードを記号化したものであり、２進数コードの代わりであり、
名前を用いる。
~~~asm
MOV a, R1
ADD #2, R1 (1.6)
MOV R1, b
~~~
これによって `b := a + 2` が計算できる
### ２パス アセンブル
アセンブラの最も簡単な処理は、入力に２つのパスをかけること
パス：入力ファイルを一回読み込んで処理する単位のこと
２つ目のパスは、もう一度入力を走査し、各走査コードは、
機械語での走査を表す２ビット列に変換し、
記憶場所を表す識別子を番地に変換する。
２つ目のパスは、ふつう、出力として再配置可能な機械コードを作り出す。
~~~
識別子 番地
a 0
b 4
V O O
0001 01 00 00000000 *
0011 01 10 00000010 (1.7)
0010 01 00 00000100 *
V O O
ロード R１ 次に表すのはメモり番地 データ”０” ※これは再配置ビットであり実際のメモリ番地とは違う
加算 R１ 次に表すのは即値 データ”２”
格納 R１ 次に表すのはメモり番地 データ”４” ※これは再配置ビットであり実際のメモリ番地とは違う
~~~
ここでは、簡単な命令後を想定する。
１番目の４ビットは、
~~~
0001 ロード：メモリからレジスタへのデータの転送
0010 格納：レジスタからメモリへのデータの転送
0011 加算
~~~
２番目の２ビットはレジスタの指定、ここではすべてR１を参照している。
３番目の２ビットは”タグ”の指定で、
~~~
00は普通の番地付けモードで、４番目の８ビットがメモリ番地の参照である事を示す。
10は”即値”モードで、 ４番目の８ビットは定数で、自身が演算数を表す。
~~~
*：再配置ビット：演算数が再配置可能な機械コードの中で定義されている事を示す。
いま、データを含む番地空間が記憶場所Lから始まり、そこへプログラムをロードするものとする。
`L=00001111` つまり `L=15` とすると、aとbの記憶場所は15と19になる。
~~~
0001 01 00 00001111
0011 01 10 00000010 (1.8)
0010 01 00 00010011
~~~
となる。
## loader & link-editor
ローダと呼ぶプログラムは、以下の機能を持つ
1. ロード：再配置可能な機械コードを読み込み、再配置可能な番地を指定し、命令とデータをメモリ中の適切な記憶場所に格納する
2. リンクエディタ：再配置可能な機械コードのファイルを集めて、１つのプログラムを作り出す。
### external reference
~~~
複数ファイルを一緒に有効に使えるためには、あるファイルのコードの中から、別のファイルにある記憶場所が参照する必要がある。
これを、 外部参照 という。
外部参照されるためには、indexをつけておくのがよい。
例えば、(1.7)のコードの前に、次のようなものをつけておく。
a 0
b 4
b＝a+2を行うアセンブラ
a 0
b 4
再配置バットでの0番地には a が格納されている
再配置ビットでの４番地には bが格納されている
V O O
0001 01 00 00000000 *
0011 01 10 00000010 (1.7)
0010 01 00 00000100 *
次の場所にその次に書かれたものをロード レジスタ１ 次に表すのはメモり番地 データ”０” ※これは再配置ビットであり実際のメモリ番地とは違う
次の場所にその次に書かれたものを加算 レジスタ１ 次に表すのは即値 データ”２”
次の場所にその次に書かれたものを格納 レジスタ１ 次に表すのはメモり番地 データ”４” ※これは再配置ビットであり実際のメモリ番地とは違う
もし、外部参照しているファイルの中にbへの参照があったとすると、
その参照は(1.7)の記憶を再配置したときの先頭番地L’ に4を加えた値で置き換えられる。
~~~
## フェーズのグループ化
~~~
phase：
記号表管理
|
+--------+---------+-------+----+---------------+-----------+
| | | | | |
字句解析 構文解析 意味解析 中間コード生成 コード最適化 コード生成
| | | | | |
+--------+---------+-------+----+---------------+-----------+
|
誤り修正
フロントエンド：原始プログラムに依存する処理
字句解析・構文解析・記号表の作成・意味解析・中間コードの生成
コード最適化の一部・各フェーズごとの単独謝り処理
バックエンド：中間言語を処理
コード最適化・コード生成・それらに付随した誤り処理・記号表操作
パス：state-path 形式におけるpath
いくつかのフェースをまとめ、「パス」として実現
~~~
### 「構文解析ルーチン」は指揮者
字句解析、構文解析、意味解析、中間コード生成を一つのパスにまとめると、
字句解析で得られるトークン ストリームが直接、中間コードに翻訳できる。
ここでは、構文解析ルーチンが「指揮者」の役割を果たす。
トークンから文法構造をみつけるために、字句解析ルーチンを呼び出し、
文法構造が明らかになれば、中間コード生成ルーチンを呼び出して、
意味解析をし、コード生成をする。
### パスを減らすときの問題p25
~~~
字句解析→構文解析 smoothy stream
中間コード生成 tree map 全体を必要とする→memory が必要
~~~
パスは通常小さくまとめるのがよい。
コード生成 have to wait 中間コード生成
そこで「後埋め」という技法がもちいられる
PL/I、Algol 68のような言語では、宣言よりも前に変数が使用できる。
同様に、多くの言語では、
`GOTO` による前方への飛び越しを認めている。
前方参照を含むアセンブリ文、たとえば
~~~
GOTO target
~~~
が出てきたら、`GOTO` に対する操作コードと空欄の番地部を持つ仮の機械語を生成する。
`target` を参照する命令でも、空欄の番地部の命令は、すべて、リストに保持し、そのリストを`target`に対する記号表エントリに結びつけておき
~~~
target : MOV foobar, R1
~~~
というような命令が出てきたら、`target`の値を確定し、
各命令に置ける空欄の箇所を、その値で埋める。
それまで、命令をメモリに保持すればよい。
~~~
アセンブラ
中間表現と最終表現とがほぼ同じ、長さもほぼ一致
↓
プログラム全体にわたって「後埋め」できる
コンパイラ
中間コードが大きな記憶空間を必要とする
↓
後埋めが起きるときの距離（どこまで遡るか）is big issue.
~~~
## コンパイラ作成ツール
~~~
コンパイラ コンパイラ（コンパイラ生成系、翻訳系記述システム）
：コンパイラの作成を支援するシステム
~~~
1. 構文解析ルーチン生成系
2. 走査ルーチン生成系
create 字句解析ルーチン
3. 構文主導エンジン
create 解析木を巡回し中間コードを生成するルーチン
4. 自動コード生成系
create 中間言語→目的機械語translater
5. データの流れエンジン
コードを最適化するとき、プログラムのある箇所から別の箇所へ
どのような値が伝達されるか、という情報を収集する
「データの流れ解析」をつくる
References
- Knuth コンパイラ作成の歴史に関する文献 1962
- Trabb Pardo 1977
- Wexelblat 1981
- Rosenコンパイラに関する初期の論文 1967
- Pollack 1972
- RndellとRussell Algol 60の初期のコンパイラについて 1964
# 簡単な１パス コンパイラ
## 簡単な１パス コンパイラ
~~~
言語は、構文と意味によって定義される
構文の規定
・文脈自由文法：構文の規定のほかに、プログラムの翻訳の仕方も示唆する
・BNF(Backus-Naur Form)
意味の規定
more difficult than 構文の規定
構文主導翻訳
：文法思考のコンパイル技法
フロントエンドをつくる上で大きな助けになる
たとえば、
中置形 →（翻訳） 後置形
９−５＋２ ９５ー２＋
を考える。すべての演算をスタックで行う計算機には
後置記法から直接変換できる
↑
ここでは構文解析ルーチンと
中間コード生成ルーチン
~~~
## 構文の定義
C言語のif-else文は `if (式) 文 else 文` で定義されるが、
この構成規則を以下のように表すことができる
~~~
stmt → if '(' expr ')' stmt else stmt
~~~
* `stmt` : 文を表す変数
* `expr` : 式を表す変数
* `→` : 〜は、次の形式である
~~~
トークン(終端記号) : if , '(' , else
非終端記号 : stmt, expr などトークンの列を表す変数
~~~
### 文脈自由文法の構成要素
1. トークンの集合
2. 非終端記号の集合
3. 生成規則の集合：
生成規則は、左辺（非終端記号）, →, 右辺（非終端記号や終端記号の列）からなる
4. 開始記号という非終端記号
~~~
空列 : ε
Italic : 非終端記号
Bold : 終端記号
~~~
### 解析木
1. 根は開始記号をラベルに持つ
2. 各葉はトークンまたはεをラベルとして持つ
3. 各内部節点は１つの非終端記号をラベルに持つ
4. 内部節点にラベルづけた非終端記号をAとし、Aの子を左から順にX1、X2、・・・Xnとすると、A → X1 X2 ・・・ Xn は生成規則である。X1、X2、・・・Xnは終端記号または非終端記号を表す。A → ε であれば、Aの節点は、εをラベルとする子をもつ。
~~~
list = list + digit
list = list - digit
list = digit
digit = 0|1|2|3|4|5|6|7|8|9
~~~
ここに `9 - 5 + 2` のストリームが流れてくると
~~~
digit = 0|1|2|3|4|5|6|7|8|9 より
9 は digit
list = digit より
9 は list
list = list - digit
9 - 5 は list
list = list + digit より
9 - 5 + 2 は list
~~~
となる。
仮に `list` と `digit` の区別がなかったとすると
~~~
string = string + string
string = string - string
string = 0|1|2|3|4|5|6|7|8|9
~~~
`9 - 5 + 2` は、
~~~
９ は string
９−５ は string
９−５＋２ は string
↓
9 - 5 + 2 = 6
~~~
という解釈と
~~~
9 は string
5 + 2 が string だから
9 - 5 + 2 が string
↓
9 - 5 + 2 = 2
~~~
の二通りの解釈ができる
これを「曖昧」という
~~~
string
/ | \
string + string
/ | \ |
string - string 2
| |
9 5
string
/ | \
string + string
| / | \
9 string - string
| |
5 2
~~~
Pascal のhello world!
ソース１-1:
~~~
program TST01;
var s:string;
begin
writeln(‘Hello World!’);
read(s)
end.
~~~
begin ; end はc言語の{ ; } にあたる
begin end ブロックの生成規則は
~~~
block → begin opt_stmts end
opt_stmts → stmt_list | ε
stmt_list → stmt_list ; stmt | stmt
~~~
となる。
＝は右結合の演算子である。
a = b = c は 右下がり
~~~
right → letter = right | letter
letter→ a | b | c |…| z
right
/ | \
letter = right
| / | \
a letter = right
| |
b letter
|
c
~~~
- program：プログラムの著者によってかかれたもの
- hook：
programの中から呼び出すように設定された
外部にあるプログラムで、著者とは別の人によって
付け加えられたもの
### 左結合と右結合
９＋５ー２
５はどちらの演算子と結びつくか？
左側の＋と結びつく。
＋は左結合の演算子である。
＝は右結合の演算子である
### 式の構文
９＋５＊２
＊は＋より順位が高い
同順位のものをまとめると
左結合：＋ ー
左結合：＊ /
~~~
term → term＊factor
｜ term / factor
｜ term
expr → expr + term
｜ expr - term
｜ term
factor → digit ｜(expc)
~~~
括弧を使えば、括弧でくくった式も因子だから、
任意の深さの式が表現できた。
### 文の構文
Pascalの文は、代入文と手続き呼出を除き、
必ずキーワードで始まる。
Pascalの文を定義する構文の例として
~~~
stmt →id := expr
｜if expr then stmt
｜if expr then stmt else stmt
｜while expr do stmt
｜begin opt_stmts end
~~~
idは、識別子を表す
opt_stmtは、文をセミコロンで区切った並びであり、
空であってもよい
~~~
opt_stmt → stmt_list｜ε
stmt_list → stmt_list ；stmt ｜stmt
~~~
## 構文主導翻訳
翻訳に必要なもの
- 各要素に対するコード
- 構成要素の属性
1. 構成要素の型
2. 目的コードにおける最初の命令の格納場所
3. 生成した命令の個数
4. etc
構文主導定義
：構文要素に属性をつなぎあわせ、その属性でもって構文を規定しようというもの
以下、構文主導定義を説明する
### 後置記法 (逆ポーランド記法)
式Eの後置記法は帰納的に定義できる
1. E が変数または定数であれば、Eの後置記法はE自身である。
2. 任意の二項演算子をopとしたとき、EがE1 op E2 という形の式であれば、Eの後置記法は、E1’ E2’ op である。ここで、E1’ とE2’ はそれぞれ、E1 とE2 の後置記法だある。
3. E が (E1) という形の式であれば、E の後置記法はE1 の後置記法そのものである。
~~~
（９−５）＋２ は ９５ー２＋となり、
９−（５＋２）の後置記法は９５２＋ーとなる。
~~~
翻訳は入力から出力への変換でくぅ。
節点nにおける文法記号をXとし、
Xの属性aの値を X.a で表す。
nにおけるX.aの値をもとめるには、属性aの意味記号を用いる。
合成属性：解析木の節点の属性の値が、その子の属性から決まれば、それを合成属性と呼ぶ。
中置形で書かれた式を後置記法変換するための構文主導定義
~~~
生成規則 意味規則
expr → expr1 + term expr.t := expr1.t || term.t || ‘+’
expr → expr1 - term expr.t := expr1.t || term.t || ‘ -’
expr → term expr.t := term.t
term → 0 term.t := ‘0'
term → 1 term.t := ‘1'
・・・ ・・・
term → 9 term.t := ‘9'
(|| は文字列の連結を示す)
expr.t = 95-2+
/ | \
expr.t = 95- | term.t = 2
/ | \ | |
expr.t=9 | expr.t = 5 | |
| | | | |
term.t=9 | | | |
| | | | |
9 - 5 + 2
~~~
東西南北に１ずつ動くロボットの文法
~~~
seq → seq instr｜begin
instr → east ｜north ｜west ｜ south
~~~
例えば以下のように命令をだすと、
xy平面上における(0,0)のロボットは(2,1)へ移動する。
~~~
begin west south east east east north north
~~~
この文法の意味規則
~~~
seq → begin seq.x := 0
seq.y := 0
seq → seq instr seq.x := seq1.x + instr.dx
seq.y := seq2.y + instr.dy
seq → east seq.x := 1
seq.y := 0
seq → north seq.x := 0
seq.y := 1
seq → west seq.x := -1
seq.y := 0
seq → south seq.x := 0
seq.y := -1
~~~
### 深さ優先巡回
~~~
procedure visit (n：節点)；
begin
for nの各子供mを左から右へ順にdo
visit(m);
節点nの意味規則を評価
end
~~~
木の深さ優先巡回の例
翻訳スキーム：
文脈自由文法に置いて、右辺に意味動作と呼ばれるプログラムのコードを埋め込んだもの。
意味規則の評価順序を明確に規定する構文主導定義
スキーム：
scheme「枠組みを持った計画」というギリシア語由来
~~~
rest → + term {print(‘+’)} rest1
~~~
右辺に意味動作 {print(‘+’)} が埋め込まれている
基底文法：翻訳スキームのもとになる文法
基底文法から生成される文をxとすると、翻訳スキームは、`x`の解析木を深さ優先巡回しながら、その途中で出会う動作を順に実行していく。
図2.14 ９−５＋２を９５−２＋に翻訳するときの動作
~~~
expr → expr + term { print(‘+’) }
expr → expr - term { print(‘- ’) }
expr → term
term → 0 { print(‘0’) }
term → 1 { print(‘1’) }
・・・
term → 9 { print(‘9’) }
~~~
図2.13 式を後置記法に翻訳するための動作：翻訳スキームの例
~~~
構文解析の方法は、一般的に”欲張り法”
と呼ばれる特徴を持つアルゴリズムがほとんどで、
入力を左から右へと走査しながら、次のトークンを読み込む前に
できるだけ大きな解析木を作ろうとする。
単純翻訳スキームの動作も左から右なので、
単純翻訳スキームは、構文解析をしながら
意味動作を実行する形の実現ができる。
この方法を用いれば、解析木を作らなくてすむ
~~~
## 構文解析
~~~
構文解析：トークン列が字句解析から生成できるか決定する処理
~~~
n 個のトークンの列を解析するのに、
なかには $O(n^3)$ に比例する場合もあるが、たいてい入力を左から右へ一回走査するだけですむ.
構文解析法は、
- 上向き: 根から葉に向かう解析
- 下向き:葉から根に向かって木を作成
に分類される
- 下向き: 効率の良いルーチンが手作業で簡単に作成できるので広く普及
- 上向き: 翻訳スキームのクラスが大きく、文法から直接、構文解析ルーチンを作成するツールはこの方法を用いる傾向が大きい。
図 2.8 下向き Pascal における型宣言の一部
~~~
type → simple | ↑ id
| array [simple] of type simple → integer
|char
|num dotdot num
~~~
1. 下向き解析木をつくる手順
次の2つのステップを繰り返す
a. 非終端記号 A のついた節点 n について、A の生成規則を1つ選び出し、 その規則の右辺の記号に対して n の子をつくる.
b.
次に部分木を作ろうとする節点を見つける.
~~~
type
array [ simple ] of type
array [ num dotdot num ] of integer
~~~
2. 予測型構文解析
再帰下降構文解析は下向き解析の一種で, 非終端記号に対して1つの手続き を用意しておく。
~~~ Pascal
procedure match(t:token);
begin
if lookhead = t
then lookahead := nexttoken
else error end;
procedure type ;
begin
if lookahead は integer, char, num のどれか then simple
else if lookahead = ’ ↑’ then
begin
match(’ ↑’); match(id)
end ← what it starts with? 先頭の記号で判断
else if lookahead = array then
begin
match(array); match(’[’); simple; match(’]’); match (of); type
end
else error
end;
procedure simple;
begin
if lookshea = integer then match (integer)
else if lookahead = char then match (char)
else if lookahead = num then
begin
match (num); match (dot dot); match (num)
end
else error
end;
end;
~~~
図 2.17 予測型構文解析ルーチンの疑似コード
match:引数 t と先読み記号が一致すれば次の入力 token まで進める手続き
3. lookahead:現在走査中のトークンを保持する変数 予測型構文解析は、生成規則の右辺の記号列のうち先頭がどのような記号で始まるか
~~~
FIRST (simple) = {integer, char, num} FIRST(↑id) = {↑}
FIRST(array[simple]oftype) = {array}
~~~
非終端記号 A に対して、2つの生成規則 A →α と A →βがあったとする と、先ほどの予測型構文解析をするためには、FIRST(α) と FIRST(β) が 互いに素でなければならない。
~~~
stmt → begin opt stmts end (1) optstmts → stmt list | ε (2)
~~~
opt stmts の解析において、先読み記号が FIRST ( stmt list ) になければ、 ε を生成規則を使用してもよいだろう. ただし、この選択が正しいのは、先読 み記号が end の時だけである.
※右辺に ε をもつ生成規則があると面倒なことになる。たとえば、次の生成 規則 A → BC の非終端記号 B が ε を持てば、FIRST(A) には、C から生成 される記号列の先頭の記号を含めなければならない.
4. 予測型構文解析 routine は、全ての非終端記号に対する手続きの集まりか らなる。各手続きでは次の 2 つを処理する.
a. 先読み記号を調べて、どの生成規則を使用するか決める。生成規則の右辺 を α とすると、先読み記号が FIRST(α) にあれば、その規則を使用。1 つの 先読み記号に対して、2 つの右辺が適用できる文法では、この解析法は用い ることはできない。先読み記号がどの FIRST() にもなければ、ε を返す。
b. 選ばれた生成規則を用いて、 右辺に現れる非終端記号については、それ に対応する手続きを呼び出し、トークンについては、先読み記号と照合。if success then next, if fail then return ”error”
以上の規則を文法 (2.8) に当てはめると図 2.17 が得られる。
図 2.17 を拡張すると構文主導翻訳 routine ができる。ここでは、非終端記号 に属性は結びつけないので、今のところ次のようにして、翻訳スキームから 予測型構文解析 routine を実現する。
生成規則中の動作は考えないで、まず予測型 routine を作成する。
2. 翻訳スキームの動作を次のようにして、その routine の中に書き写す。 翻訳スキームの中で、動作が文法記号 X のあとに現れれば、X を実現する 為のコードのあとに、その動作を複写する。また、動作が生成規則の先頭に あれば、生成規則を実現するコードの直前に、その動作を書き出す。
5. for 文を入力できる言語 (下向き構文解析)
~~~
stmt → expr; (3)
* | if (expr)stmt
* | for(optexpr; optexpr; optexpr; )stmt
* | other
optexpr → ε
| expr
~~~
入力記号列が次の通りだとする
~~~
for ( ; expr ; expr ) other
~~~
これをさらに拡張して expr が終端記号ではなく、非終端記号 expr で表され る場合が一般化された for 文である。
~~~
optexpr → expr (4) |ε
~~~
6. _
7. 実行時環境
heap & stack
入れ子上のメソッドを呼び出すことにより、
駆動レコードがスタック上に上積みされていく
これを駆動木という。
# _
# _
## Exercises
### consider
~~~
S -> (L) | a
L -> S,L | S
~~~
### `(a,a)`
~~~
S
+(L)
+L, S
+S +a
+a
~~~
### `(a,(a,a))`
~~~
S
+(L)
+L, S
+S +( L )
+a +L , S
+S +a
+a
~~~
### how is this language
~~~
a
~~~
# コード生成
最適なコードを生成するという問題は、数学的には、決定不能である。
## コード生成ルーチン設計上の問題点
コード生成ルーチンへの入力
* 中間コード
* 記号表
* 線形表現
* 後置記法
* 3番地表現
* 四つ組
* tree および dag による表現
目的プログラム
* 絶対機械語
* 再配置可能な機械語
* アセンブリ言語
~~~
絶対機械語 WATFIV, PL/C
再配置可能な機械語 実行にはリンキングローダを使用する
リンキングローダ : 再配置可能な目的モジュールをリンクして、ロードする
~~~
# self compile
コンパイラが育っていくにつれて、セルフコンパイラがつくられるポイントがあるが、
~~~
asm : compiler
cc : compiler compiler : p → asm
c1,c2, ... : compiler
t : target language
~~~
とすると
セルフコンパイラは `cc(c1)` であり従って、それがもとのコンパイラと同じ動作をするので
~~~
cc : c1 ↦ cc(c1)
cc(c1) : c1 ↦ (cc(c1))(c1) ≡ cc(c1)
~~~
でないといけない
あるいは、
~~~
∀p. (cc(c1))(c1)(p) = cc(c1)(p)
~~~