元のウェブページは退官のため消失 https://web.archive.org/web/20070823212408/http://www.watalab.cs.uec.ac.jp/tinyCabs.html
Tiny C コンパイラ解説 2002/6 電気通信大学 情報工学科 渡邊坦
はじめに コンパイラの仕組みと作り方を例に基づいて説明しよう。そのために、まず、対 象とするプログラミング言語の仕様を定めるところから考えてみよう。この言語は、 コンパイラ技術の説明用であって、実用することをそれほど重視するわけではない が、実用的コンパイラにおける技術を説明するのに必要な基本機能は備えており、 コンピュータに行なわせる簡単な仕事を表現できるものとして考えよう。現在、C言 語が流布しているので、その言語はC言語の基本機能のみで構成される小さい言語と することにし、それを Tiny C と名付けることにする。 Tiny C のコンパイラは、説明も理解も容易なように、小さく作るが、コンパイラ の基本機能を含んだものにする。また、わかりやすい形にコーディングする。
１． 単純なプログラミング言語 Tiny C の設計
１．１ 言語設計の方針
（１）プログラミング言語はどうあるべきか 「コンピュータにやらせたい仕事をコンピュータで処理可能な形で記述したもの」 がプログラムであり、それをコンピュータで実行できる形式に変換するのがコンパ イラである。プログラムを記述する言語がプログラミング言語である。それは、人 間からコンピュータへの指示に適しており、コンピュータの動作を正確に表現でき るものでなければならない。したがって、次のようなことが要求される。 ・必要な表現能力がある（記述したいことを十分記述できる）。 ・正確に表現できる（表現があいまいでない）。 ・明解に書ける（人間にわかりやすい）。 ・誤用が少ない。 ・修得しやすい。 ・実行性能の良いプログラムを書くことができる。 ・コンパイラを作り易い。 ・用途が広い。 ここで設計する Tiny C は、言語処理に関する実用的な技術の説明に例題として 使えるようにするために、とくに次の要件を満たすことが望まれる。 ・コンピュータを使うのに最低限必要な機能は持つ。 ・現実のコンピュータで効率よく実行可能である。 ・そのコンパイラは４、５回の講義で説明可能である。
（２）プログラミング言語として何が本質的に必要か コンピュータを使うのに最低限必要な機能を持たせるために、プログラミング言 語として何が本質的に必要かを考えてみよう。 コンピュータはデータ処理を行なう。したがって、対象となるデータを表現でき なければならない。個々のデータは定数として表現されるので、当たり前すぎるこ とであるが、プログラミング言語は定数を表現できなければならない。最も基本と なるデータは数値である。 コンピュータのとりえは計算が速いことである。計算は式で表現されることが多 い。したがって、プログラミング言語は式を表現できなければならない。式の基本 は加減乗除などを表す算術式である。 定数と式だけでも電卓のような使い方はできるが、同じ手順の計算をデータを変 えながら行なえるようにするためには、式を記号で表し、１つの記号が幾つものデー タを、取り替え引き替え、表現できるようにする必要がある。すなわち、数学にお ける変数表現ができなければならない。 コンピュータでデータ処理をするということは、コンピュータにデータを入力し、 結果を出力させることである。したがって、入力と出力の操作を指示できなければ ならない。 コンピュータの主な用途の１つに、情報を記録しておき、求めに応じて提示する 使い方がある。また、複雑な計算の場合は、１つの長大な式として表現するのでは なく、部分的な計算を幾つか行なって、その結果を合成して最終的な結果を得るよ うに表現する。したがって、データの記録や移動、計算結果の一時保管などを可能 にする代入文が必要不可欠である。 変数を用いて計算する場合、データの値に応じて処理の仕方を変えなければなら ないことがある。したがって、場合分け処理を記述する選択文が必要になる。場合 分けするには、判定をするための比較式が必要になる。 コンピュータが最も能力を発揮するのは、同じ手順による計算をデータを変えな がら繰り返し実行することである。このために、反復文も基本機能であるといえる。 また、同じ扱いのできる複数のデータを表せるようにするために、配列と添字つき 変数も必要となる。 選択文や反復文では、選択的に実行されるものや、繰り返し実行される部分は、 １つの文とは限らず、幾つかの文で構成されることがある。このようなことを表現 するには、幾つかの文をひとまとめにして扱う記述形式（ブロック）があればよい。 同じ処理を異なる状況のもとであちこちに記述することや、数学の関数のように、 いろいろのプログラムで同じ処理が必要になったりすることがある。このために、 副プログラム（関数や手続き、サブルーチンなど）も基本機能といえる。副プログ ラムは、大きいプログラムを作るときに、それを幾つかの部分に分割して作り、あ とで結合できるようにするためにも必要である。 これらのことから、実用的なプログラミング言語に必要な基本機能としては、次 のものをあげるべきであると言える。 データを表現 → 定数 演算 → 算術式 一般解を表現 → 変数（定数だけだと電卓としてしか使え ない） （同じ処理をデータを換えて実行可能） 入出力 → 入出力文（ややこしいので後で考える） データの記録、移動 → 代入文 場合分け処理 → 選択文（変数の値によって処理を変える） 判定 → 比較式 繰り返し処理 → 反復文 「以下同様に処理」 → 配列 （同じ扱いのできるデータ） 変数を実行時に選択 → 配列 （添字つき変数） 複数の文をひとまとめにする → ブロック 同一処理をあちこちで実行 → 副プログラム （procedure, function, subroutine） プログラムを分割作成 → 分割コンパイル、コンパイル単位
１．２ 言語仕様の設定
（１）素案の作成 Tiny C の言語機能としては、以上のものを含めることにし、その言語形式として はＣ言語にならうことにする。また、それぞれの機能は、Ｃ言語の最も基本的な形 のみに限定することにする。誤りを誘発しやすい書き方は取り入れない。具体表現 を明確にするために、この範囲で試みにプログラムの例を１つ書いてみよう。
（a[i] に 0, 1, 2, .... , i までの数の和を入れるプログラム） int a[10]; int i; main( ) { a[0] = 0; i = 1; while (i<10) { a[i] = a[i-1] + i; i = i+1; } } 図 1.1 記述例（数の和）
これだけの機能でも、簡単なプログラムなら書けることがわかる。 この例では注釈の機能を入れていなかったが、プログラムは人にもわかりやすい ものでなくてはいけないので、やはり注釈は必須である。そこで、/* */ で囲む 形の注釈を追加することにする。また、入出力文をどうするかはっきりさせていな かったが、これは入出力を行なう副プログラムを呼び出すことで実現することにす る。それはすでに何らかの手段で記述済みで、各プログラムの中で毎度記述する必 要はないものとしよう。これを実現するためには、外部で定義される副プログラム の指定をできるようにすればよい。そのために、関数の呼び出し形式だけ指定し、 その本体は指定しない書き方を追加することにする。 この言語でも少し実際的な処理を記述できることを確かめるために、小さい順番 に n 個の素数を求めるプログラムを書いてみると図 1.2 の通りとなる。この単純 な言語でも一通りのことは書けることが分かるであろう。
/* Get n prime numbers in ascending order. */
int candidat, quotient, remaindr, index, nth, primenum, loopend; int primeNumbers[100]; int print(int pvar); /* External routine for printing. */
void getPrime(int primevec[100], int count) { primevec[0] = 2; nth = 1 ; candidat = 3; /* Candidate of a prime number. / while (nth < count) { remaindr = 1; index = 0; loopend = 0; while(loopend == 0) { primenum = primevec[index]; quotient = candidat / primenum; remaindr = candidat - quotient * primenum; if (remaindr == 0) loopend = 1; / Not a prime number / if (quotient * quotient < candidat) loopend = 1; / No other factor is remaining. / index = index + 1; if (index >= nth) loopend = 1; } if (remaindr != 0) { / candidat is a prime number. / primevec[nth] = candidat ; nth = nth + 1; } candidat = candidat + 2; / Advance to the next candidate. / } nth = 0 ; while (nth < count) { / Print the prime numbers. */ print(primevec[nth]); nth = nth + 1; } return; }
int main() { primeNumbers[0] = 2; getPrime(primeNumbers, 100); /* Get 100 prime numbers. */ return 0; }
図 1.2 Tiny C のプログラム例（素数を求める）
１．３ 言語仕様の記述
（１）バッカス記法（BNF）による構文記述 プログラミング言語を定めたとき、それを使い間違いのないように説明するとか、 そのコンパイラを作れるようにするには、言語の仕様を明確に書かなければならな い。Tiny C のプログラム形式を振り返ってみると、 「プログラムは 変数宣言、または 関数定義の並び である。 変数宣言は 型名 変数指定の並び ； である。 変数指定は 変数名または変数名 "[" 定数 "]" である。」 のような指定の仕方ができる。これでは、「... は ... である。」、「... の並び 」、 「または」という言葉だけ使って書いているので、それらの意味をはっきりさせれ ば全体も明確になるであろう。このようなやりかたを整理して定められたのがバッ カス記法（BNF, Backus Naur Form）である。 バッカス記法（BNF）とは 数字 → "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 英字 → "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" 定数 → 数字 | 定数 数字 識別子 → 英字 | 識別子 英字 | 識別子 数字 変数 → 識別子 | 識別子 "[" 式 "]" のような構文の記述方法であり、それは α→β : 記号列βにαという名前を付ける（αはβで置き換えられる） a b : a の後ろに b を付けた記号列 a | b : a 叉は b という規則で表現される。即ち、 記号の集合や記号列の集合に名前を付け、 記号や記号列集合の配列順序を指定する 記法である。ここで、使う用語を 終端記号（terminal） : 0, 1, 2, ... や a, b, c, ... のように実際にプログラムに 現れる記号で、次の非終端記号などと区別するために、引用符 で囲んで表す 非終端記号（nonterminal） : 矢印の左辺に現われて、記号や記号列の集合名を表す記号 生成規則（production） : α→βのように、αはβで置き換えられることを表す規則 と定義する。また、省略できる部分を示すためには ε : 何もない空記号 を使う。開始記号は、「プログラム」のように、BNF で構文を表現しようとする記 号列の全体を表す非終端記号である。 BNF を使って、Tiny C の構文規則を記述したものを図 1.4 に示す。
Program → ExternalDeclaration | ExternalDeclaration Program ExternalDeclaration → FunctionDef | FunctionDecl | VariableDecl FunctionDef → FunctionDeclaratorBlock FunctionDecl → FunctionDeclarator ";" FunctionDeclarator → TypeName FuncName "(" ParamList ")" ParamList → TypeName NameSpec ParamListTail | ε ParamListTail→ "," TypeName NameSpec ParamListTail | ε NameSpec → Id | Id "[" IntConstant "]" VariableDecl → TypeName NameSpec NameListTail ";" NameListTail → "," NameSpec NameListTail | ε Block → "{" StatementSeq "}" StatementSeq → Statement | Statement StatementSeq | ε Statement → Variable "=" Expression ";" | "if" "(" ConditionExp ")" Statement ElsePart | "while" "(" ConditionExp ")" Statement | FuncName "(" ExpressionList ")" ";" | Block | "return" ";" ElsePart → "else" Statement | ε ExpressionList → Expression ExpListTail | ε ExpListTail → "," Expression ExpListTail | ε Expression → SignPart Term ExpTail ExpTail → AddSub Term ExpTail | ε Term → Factor TermTail TermTail → MultDiv Factor TermTail | ε Factor → IntConstant | Variable | "(" Expression ")" Variable → Id SubscriptPart SubscriptPart→ "[" Expression "]" | ε ConditionExp → Expression CompOperator Expression CompOperator → "==" | "!=" | ">" | ">=" | "<=" | "<" AddSub → "+" | "-" MultDiv → "*" | "/" SignPart → "+" | "-" | ε FuncName → Id TypeName → "int" | "void" Id → Alpha IdTail IntConstant → Digit ConstTail IdTail → Alpha IdTail | Digit IdTail | ε Alpha → "a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"| "n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"| "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"| "N"|"O"|"P"|"Q"|"R"|"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z" Digit → "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" ConstTail → Digit ConstTail | ε 記法： α→β : 記号列βにαという名前を付ける（αはβで置き換えられる）。 (BNF) b : 記号列 a の後ろに記号列 b を置いた記号列 a | b : 記号列 a または記号列 b " で囲まれた記号は終端記号（"xx"は xx そのもの）、 εは空記号。 本例での用法： 英大文字で始まる語は非終端記号（構文要素名）。
図 1.4 Tiny C の構文規則
２． Tiny C コンパイラの概要
２．１ 作成方針
Tiny C コンパイラは、コンパイラの基礎技術を実例で説明するためのものなので 、 小さく、分かりやすく作る。そのほかに、アーキテクチャの進化にも容易に追随で きるよう、対象機種を比較的容易に変えることができるようにしたい。その１つの 方法は、現実のコンピュータではなく、仮想的なコンピュータを対象とすることで ある。しかし、それでは対象を単純化しすぎて、現実のコンピュータで出会う問題 を回避したものになりがちである。Tiny C コンパイラでは現実のコンピュータの機 械語を生成することにする。 開発目的： コンパイラを短期間で具体的に説明可能にする。 （コンパイラの基本機能を含める。分かりやすく小さく作る。） 入力言語： Tiny C （言語の基本機能を持ちながら、コンパイラを小さく作ることがで きる。） 対象機種： MIPS R2000/R3000 （命令セット・アーキテクチャが規則的であり、この機種の命令は 他の機種にも対応する命令があるようなものが多いので、特定機種 への偏りが少ない。フリーソフトとしてのシミュレータもあり、 実機がなくても、生成されたオブジェクトコードを実行させる ことができる (http://www.cs.wisc.edu/~larus/spim.html)。） オブジェクト・コード形式： MIPSアセンブリ言語 記述言語： C++ （改良、拡張を容易にするためにオブジェクト指向言語を選択する。）
２．２ 方式
（１）全体構成 コンパイラは、一般に、入力されたプログラムを字句（単語）に切り分ける字句 解析部と、構文規則との対応付けを明らかにする構文解析部、対象機種の命令列を 生成するコード生成部に大きく分かれる。コンパイラを小さく作るには、構文解析 しながらコード生成部を呼ぶ１パス・コンパイラとすればよい。構文解析部を機種 に依存しないようにするため、構文解析部では仮想的な機械命令を生成するように 見せかけたルーチンを呼ぶが、その中で現実のコンピュータの命令を生成すること にする。この仮想的な機械命令を抽象レジスタマシン語 と呼ぶことにする。このよ うにすると、対象機種を変えても呼び出し側を変える必要はなく、コード生成ルー チンのみを変えればよい。 このような考えのもとに、コンパイラの全体構成を図 2.1 のようにする。
ソース・プログラム -- inFile (xx.c) ↓ 字句・構文解析 -- 構文解析部で字句解析ルーチンと ↓ コード生成ルーチンを呼ぶ。 抽象レジスタマシン語 -- 引数列としてのみ存在 ↓ コード生成 ↓ MIPSマシン命令 -- objFile (xx.s)
図 2.1 Tiny C コンパイラの全体構成
（２）各部の形態 字句解析部は手続き書きくだし型とする。簡単な言語ではこれが一番単純であり、 実行効率もよい。構文解析部は再帰的下向き構文解析系とする。 中間語としての抽象レジスタマシン語は、命令列として格納されるのではなく、 コード生成ルーチンの引数として、１語ずつ瞬間的に構成されるものである。本中 間語は、レジスタの有効利用を機種に依存しない形である程度実行できるように、 レジスタを表面に出した形態とする。 入力されるプログラムに現れる記号を登録する記号表を作り、コンパイの過程で 必要な情報を全部この記号表に記載する。字句解析がすむと、コンパイラの中では、 すべての記号を、その記号表における記載位置で、画一的に表現する。
２．３ コンパイラのプログラム構成
（１）ファイル構成 コンパイラのソース・プログラムを次のように区分してファイルに入れる。 sub.h コンパイラの見出し部、 記号表などの共通情報と、それに関連する変数などの記号の定義 tinyC.C メイン、構文解析 arm.h 抽象レジスタマシンの仕様とそれに関連する記号の定義 arm.C 抽象レジスタマシンの実現部（レジスタ割り付けの主要部も含む） mips.h MIPS 固有部分の仕様とそれに関連する記号の定義 mips.C MIPS の機械語生成 sub.C 記号表など、共通に使われるものの実現部と、字句解析 ここで、対象機種に依存するのは mips.h と mips.C のみであり、他は機種に依存 しない。このコンパイラのソース・プログラムは 2000 行以下であり、そのコンピュ ー タ処理可能なファイルはネットワークを通じて、 http://watalab.cs.uec.ac.jp より入手できる。
（２）クラス定義 sub.h StringT 文字列表（記号の字面をまとめて記録） Token 字句解析で認識される単語 （識別子、定数、演算子、区切り記号等） SymbolT 記号表 VarInf 変数の詳細情報 FuncInf 関数の詳細情報 arm.h RegInf 抽象レジスタ詳細情報 Rcode 抽象レジスタマシン命令 mips.h MachineReg MIPS マシン・レジスタ
２．４ コーディング様式
プログラムは、説明書が別になくても、読めばわかるように、分かりやすく書く ことを心がける。また、対象機種変更などの改造を容易にできるようにする。その ため、次のようなスタイルでコーディングする。 ・仕様の記述と実現部の記述をファイルとして分離する（xx.h と xx.C）。 ・共通情報となるクラスや大域的記号は、その意味を注釈で説明する。 ・副プログラムの機能とその引数の意味を注釈で説明する。 機能の説明では、生成するものや、共通変数の状態変更を明示する。 ・入力を直接的または間接的に読む副プログラムでは、終了時にどこまで 読み進んでいるかを注釈で説明する（外部に対する影響を明示する）。 ・副プログラムの区切りを明示する。 ・系統的な名前付けを行なう。 クラスや関連する関数をまとめたグループに、４文字までの接頭辞を対応 させる。 クラス名と副プログラム名は大文字の後に小文字列をつける。 マクロ名は２文字以上の大文字列で始める。 xxx_yyy はクラスまたはグループ Xxx に関連する大域的変数とする。 l （エル）で始まる識別子は１つの副プログラムの中だけで使う局所変数 とする。 p で始まる識別子は仮引数とする。 ・構文構造に合わせて書き出し位置をずらす（インデンテーション）。 ・同種のものの桁位置を揃える（同種の語、注釈）。
３． テーブル仕様
（１）記号表の構造（SymbolT） ソース・プログラムに現れる変数や副プログラム名ばかりでなく、キイワードや 演算子など、プログラムで使われる記号をすべて記号表に登録する。このように画 一的に扱うことにより、コンパイラを小さく作る。以下、記号表の主な記載項目を 述べるが、詳しくは SymbolTクラス を参照されたい。 共通情報 (SymbolT) : すべての記号に共通の情報として、次のものを記載する。 name 記号の綴り next 次に登録した記号（すべての記号を登録順につなぐリンク） size 値を持つ記号（変数、定数、関数）の場合はそのバイト数 vType 記号の型名へのポインタ hashChain ハッシュ値の同じ記号で１つ前に記録したものへのポインタ kind 記号の種類 詳細情報 変数、関数、レジスタに対しては、それぞれ、変数情報 (VarInf) 、 関数情報 (FuncInf)、レジスタ情報 (RegInf) のクラスへの ポインタがある。 変数情報 (VarInf)： 配列要素数、番地、割り付けレジスタ、仮引数の時は次の仮引数へのポインタ 関数情報 (FuncInf)： 第１仮引数、引数の数、処理部へのポインタ（外部関数なら NULL） レジスタ情報 (RegInf)： 対応する変数、対応する MIPS レジスタ、待避用変数、レジスタ種別、番号、 レジスタ割り付け用チェイン、レジスタ内容の種別、レジスタ値（定数に対応 する場合）、レジスタの割り付け状態（unused/reserved/hold/nohold/saved） 、 他
（２）記号表の探索 記号表はハッシュ法でアクセスする。ハッシュ関数としては (((文字数*128 + 先頭文字コード)*128 + 中間文字コード)*128 + 末尾文字コード) mod ハッシュ表長 を使う。ハッシュ値の同じ記号があればポインタでつなぎ、新しい物から順次古い 物へと、そのポインタをたどって探せるようにする（SearchOrAdd ルーチン参照）。 探索例： "bsort" → ハッシュ値 → ハッシュ表の対応項＝NULL → 新記号として記号表に登録しその位置をハッシュ表に記載し、 その位置を返す。 "boost" → ハッシュ値 → "bsort" と同じハッシュ値 → "bsort" と比較 → 不一致 → 新記号として登録 → 前の記号("bsort")の次ポインタ（hashChain）で "boost"を接続 → 新記号の位置を返す。
４． 言語解析部
（１）主要部分の構造 主プログラムとそれから直接に呼ばれる副プログラムでは、tinyC の主要部構文 プログラムは外部宣言の列 外部宣言は変数宣言または関数宣言 変数宣言は型名の後ろに変数指定の列 関数宣言は関数見出し部の次にブロック ブロックは波括弧の中に実行文の列 .... をプログラム構造にそのまま反映して、 準備 外部宣言の処理の繰り返し if （変数宣言） 変数宣言の処理（VarDecl） if （関数宣言） 関数宣言の処理（FuncDecl） とし、 関数宣言では 関数見出し部の処理 ブロックの処理（Block） ... とするような構造にする。 コンパイラでは次のファイルを使う。 inFile 入力プログラム（xx.c の形） prtFile プログラム・リストと誤りの診断文、デバッグ情報 objFile オブジェクト・プログラム （入力が xx.c ならオブジェクトは xx.s）
（２）共通手続きと初期設定 StringT::Initiation( ) 記号の文字列を並べて入れるストリング・ブロックのリストを初期設定。 Token::Initiation( ) 第１文字でトークンの種別を判定するtkn_chKindT表などを初期設定する 。 SymbolT::Initiation 記号表を初期設定し、キィワードや演算子、区切り記号などを登録する。 そのほか、抽象レジスタやマシンレジスタの初期設定などをする。 SymbolT::Error ソース・プログラムの文法誤りに対して、それを検出した所で ** ERROR ** エラー番号 関連記号 診断文 の形のメッセージを出力する。関連記号は、誤り検出時に処理していた 変数名などの記号である。 その他 2 進 10 進変換等。 ここで、StringT::Initiation( ) のように、クラス名の後ろに関数名を書いたも のは、クラス StringT の関数 Initiation を指す記法とする。
（３）字句解析 (Token::Get ) 字句解析をする Get ルーチンでは、次には識別子がくるはず、次はコンマのはず というような、予測される記号の種類を指定可能にすることにより、誤り処理を短 く記述できるようにしている。単語切り出し時には、入力文字に対する字種コード （tkn_chKindT 表）を見て、識別子や定数の判定をすばやく行なう。単語を切り出 すと、それが記号表にあればその位置を求め、なければ登録する (SymbolT::SearchOrAdd)。記号の種別は、新規単語は字句解析時に決めた種別とし、 キィワードなど、既登録の単語は記号表での登録種別から求める。 記号を構成する文字列は、文字列表に記録する（StringT::Append）。文字列表は 固定長（STR_blkSize）のブロックで構成し、一つのブロックが一杯になったら次の ブロックのメモリを確保する。このようにして、小さいプログラムにも大きいプロ グラムにも、うまく対応できるようにする。 字句解析のあと、構文解析やコード生成では、各字句は記号表の登録位置で表現 する。現在見ている記号（読んだ直後の字句）は sym_curr 変数で指す。
（４）構文解析 構文解析では、入力言語の構文規則をそのまま反映したプログラム構造とし、宣 言文の処理、副プログラムの処理、その実行部を表すブロックの処理というように 進める。エラー処理を簡単にするため、ここには閉じ括弧がくるはず、ここにはセ ミコロンがくるはず、というような場所には、Expect(閉じ括弧);、Expect(セミコ ロン); という文を置き、それ以外の記号が入力点にあると、その記号がくるまで読 み飛ばすことにする。 変数宣言の処理 (VarDecl) では、宣言された変数を記号表に登録し、型情報を記 号表に記載する。副プログラム宣言の処理 (FuncDecl) では、その見出し部を見て、 副プログラム名や引数名とそれらの属性を記号表に登録するとともに、１つの副プ ログラムの引数群は引数ポインタ (paramChain) を使ってつないでゆき、リストに する。副プログラムの実行部は、プログラムの実行部と同じく、ブロック処理ルー チン (Block) で処理する。 実行部の処理 (Block) は実行文の処理 (ExecStatement) の繰り返しである。実 行文は変数で始まっていれば代入文とみなし、if や while などのキィワードで始 まっていればそれに対応する文とし、副プログラム名で始まっていれば副プログラ ム呼出しとみなす。式の処理 (Expression) では、構文規則に従って、式を項 (Term)、因子 (Factor) と分解してゆく。因子が変数であれば、後ろに角い開き括 弧 '[' があれば配列要素、なければ単純変数として処理する。式の構文解析では仮 引数も通常の変数も同じ扱いをする。 変数の処理ルーチン (Variable) では、変数が算術式として使われていれば値を 求めるもの (rValue) として扱い、代入文の左辺変数や配列引数として使われてい れば、番地を求めるもの (lValue) として扱う。添字がついていれば添字つき変数 の番地計算用の命令を生成する。
（５）構文解析に伴う処理 構文解析の時、構文規則に合っているか否かの識別ばかりでなく、オブジェクト・ コードとしての機械命令列も生成する。コード最適化はごく限られたことしか行わ ない。 式や変数を処理する関数に対しては、その値をどのレジスタに入れるのが望まし いかを引数で示し、結果としてどのレジスタに入れたかを関数値として返す。これ により、実引数の計算では結果を実引数レジスタに、関数値の計算では結果を関数 値レジスタに入れるようにする。また、複合演算式では、部分式の値の入っている レジスタをオペランドとして、上位の式の値を計算する命令列を容易に生成できる ようにしている。 選択文 if (条件式) 文1; else 文2; では、条件式が偽の時に else 部へとぶた めに、条件式の処理ルーチン（Condition）には、判定が偽であった時の飛び先ラベ ルを引数として渡し、偽のときに対するジャンプ命令を Condition ルーチンで生成 する。
５． コード生成部
５．１ 抽象レジスタマシン語
コード生成は、構文解析時にコード生成ルーチン GenCode を呼び出すことによっ て行なう。GenCode の引数としては 命令形式、命令コード、オペランド・レジスタ1, 2, 3、オペランド記号、 オペランド値 を与える。これらは対象計算機の命令コード等を直接与えるのではなく、抽象レジ スタマシンの仮想命令とそのオペランドを与える。この抽象レジスタマシンは図 5.1 の命令を持つものとする。 load reg1,disp(reg2) 番地disp(reg2)のメモリ内容をreg1に取り出す。 load reg1,const 定数constをreg1に入れる。 store reg1,disp(reg2) reg1の内容をdisp(reg2)番地に格納する。 add reg1,reg2,reg3 reg2にreg3を加え、結果をreg1に入れる。 sub reg1,reg2,reg3 reg2からreg3を引き結果をreg1に入れる。 mult reg1,reg2,reg3 reg2にreg3をかけ、結果をreg1に入れる。 div reg1,reg2,reg3 reg2をreg3で割り、結果をreg1に入れる。 comp reg1,reg2,reg3 reg2とreg3の大きさを比較し、 結果をreg1に入れる。 brcc label 比較結果が条件ccに合えばlabel番地にとぶ。 cc は eq, ne, gt, ge, le, lt のいずれかである 。 jump label label番地にとぶ。 call label label番地の副プログラムを呼び出す。 return 副プログラムから復帰する。 subp label 名前がlabelの副プログラムの先頭を表す。 prolog label 副プログラムの入り口処理を表す。 epilog label 副プログラムの出口処理を表す。 sect sectid コードセクションやデータセクションを開始する。 label label labelの示す名前を定義する。 dword leng lengバイトのメモリ領域を定義する。 extern abel labelが外部名称であることを宣言する。 prog label labelを名前とするプログラムの開始を表す。 end 副プログラムの終わりを表す。 pend プログラムの終わりを表す。
図 5.1 抽象レジスタマシンの命令
オペランド・レジスタ１は結果を入れるレジスタを表し、オペランド・レジスタ ２は第１オペランド、オペランド・レジスタ３はベース・レジスタまたは第２オペ ランド・レジスタを表す。オペランド記号は変数名またはラベル名、オペランド値 は命令形式の指定により、 const 定数 disp ベース・レジスタを基点とする変数の変位 などを表す。変位の具体値は変数表に記載されているが、アセンブラ命令ではそれ を変数名で表す。sectId や leng は定数の一種として扱う。副プログラムの入り口 処理や出口処理など、機種ごとに大きく異なる部分は、prolog, epilog のような１ つの仮想命令で表している。 この抽象レジスタマシンを経由することにより、字句解析部、構文解析部を対象 機種に依存しないように作ることができる。コード生成部にも機種に依存しない部 分がある。対象機種に依存する部分は mips.h, mips.C であり、全体の１／４以下である。
５．２ コード生成のパタン
算術式や各種の実行文に対するコード生成の主なパタンを示す。ここで、$r0, $r1, $r2, ... はレジスタを表すとする。 (1) 代入文 variable = 式 ; 式を計算し、その値をレジスタ $r1 に入れる命令列。 store $r1,variable $r1 の内容を変数 (variable) に格納する。 (2) 加減算 a + b, a - b load $r1,a a が変数ならｓの値を $r1 に取り出す命令列。 a が式ならその式の値を計算して $r1 に入れる 命令列。 load $r2,b add $r3,$r1,$r2 $r1 と $r2 を加えた結果を $r3 に入れる。 a - b の時は add の代わりに sub を使う。 (3) 単純変数 a 右辺値（算術演算などのオペランドとなるもの） load $r1,a a の値を $r1 に取り出す。 左辺値（番地を渡す実引数などの場合） loada $r1,a a の番地を $r1 に入れる。 左辺値（代入文左辺の場合） store $r2,a $r2 の内容を a に格納する。 (4) 添字付き変数 右辺値 x[添字式] 添字式の値を $r1 に算出する命令列 mult $r1,$r1,s $r1の内容に配列要素の大きさsを掛けて、答えを$r1 に入れる。s が２の累乗ならばシフト命令で代行でき る。 loada $r2,x x の先頭番地を $r2 に入れる。 adda $r1,$r1,$r2 $r1 に $r2 を番地として加えた結果を $r1 に入れる。 load $r3,$r1 $r1 の示す番地の内容を $r3 に取り出す。 １つの命令で基底レジスタとインデックス・レジスタ を指定できるコンピュータでは、adda をしないで load $r3,0[$r2,$r1] のように書けばよい。 左辺値 x[添字式] 添字式の値を $r1 に算出する命令列 loada $r2,x adda $r1,$r1,$r2 番地を渡す実引数などの場合はここまでで止める。 store $r3,$r1 代入文左辺ならここまで作る。 (5) 一般の２項演算 オペランド1 演算子 オペランド2 オペランド1 の内容を $r1 に入れる命令列。 オペランド2 の内容を $r2 に入れる命令列。 $r1 と $r2 から演算子で示される演算を行なって結果を $r3 に入れる命令。 (6) 分岐文 if (条件式) 文1; else 文2; 条件式を計算して結果を $r1 に入れる命令列。 breq $r1,L1 $r1 がゼロ（偽）ならラベル L1 の命令へ跳ぶ。 文1 の命令列。 jump L2 L2 へ無条件に跳ぶ。 L1: 文2 の命令列。 L2: (7) 反復文 while (条件式) { 文1; 文2; ....} L1: 条件式を計算して結果を $r1 に入れる命令列。 breq $r1,L2 $r1 がゼロ（偽）ならラベル L2 の命令へ跳ぶ。 文1 の命令列。 文2 の命令列。 .... jump L1 L1 へ無条件に跳ぶ。 L2: (8) 副プログラム呼び出し call sub(式1, 式2, ...); 式1 の演算結果を引数レジスタ 1 に入れる。 式2 の演算結果を引数レジスタ 2 に入れる。 ... call sub 副プログラム sub を呼び出す。 (9) 復帰文 return 式; 式の演算結果を関数値レジスタに入れる。 return 副プログラムから帰る。
５．３ レジスタ割り付け
コンパイラで生成するオブジェクト・プログラムの性能を上げるには、レジスタ をうまく使うことがきわめて重要である。レジスタの種類や構成は機種ごとに大き く異なるが、このコンパイラでは、抽象レジスタに幾つかの種類を設けることによ り、レジスタ割り付けの処理をかなり機種に依存しない形で行なっている。 コード生成の初期設定ルーチンの１つである RegInf::Initiation() では、抽象 レジスタのリストを種類別に１つずつ作り、必要な抽象レジスタを種類別にその後 ろに追加できるようにする。 定数や変数をレジスタに取り出すルーチン (Rcode::Load) では、変数に既にレジ スタが割り付けられているならばそれにロードし、割り付けられていなければ新た に割り付けてそれにロードする。レジスタの割り付けは抽象レジスタ割り付けルー チン (RegInf::RegAlloc) で行なう。割り付けたレジスタは、それが使われるまで 他の目的に使わないよう保持（hold）し、一度使ったら暫定解放（nohold）するが、 同じ変数が再度使われると、前回割り付けたレジスタが他の目的に使われていなけ ればそれを再利用する。ラベル定義点や副プログラム呼び出し直後では、使ったレ ジスタを完全解放する (RegInf::RegFree)。このような、レジスタ再利用の処理を 機種に依存しない抽象レジスタの段階で行なう。抽象レジスタを対象機種のマシン レジスタに対応させる処理は、機械語を生成する最後の段階で行なう (MipsReg)。
５．４ 対象機種の機械語への変換
この抽象レジスタマシンの各々の命令から、コード生成ルーチンMachineCodeで対 象機種 MIPS R2000/3000 のアセンブラ命令を生成する。その対応関係の多くは add や sub のようにほとんど１対１であるが、prolog や epilog、return のよう に何命令にも対応するものもある。しかし、その変換は単純であり、コンパイラの 対象機種を変更するのも比較的容易にできる。
６． オブジェクト・コード
（１） オブジェクト・コードの構造 機械命令列としてのオブジェクト・コード、アセンブラの入力形式に合わせて、 次の構造をとる。 データ・セクション指定（.sdata） -- prog 変数名（データ名）定義 -- VarDeclでdword命令経由で生成 .en 関数名 関数名: -- FuncDecl で生成 入り口処理（レジスタ待避等） -- prologで生成 副プログラム内の実行命令列 -- ExecStatement 等で生成 ... 出口処理（レジスタ回復等） -- epilog で生成 .end 関数名 ... 外部副プログラム（int print(int pvar); 等）に対しては、 .global 関数名 というアセンブラ制御命令を生成する。 プログラムは、全体を一度にコンパイルしなければならないわけではなく、分割 してコンパイルし、リンカで結合してもよい。そうすると命令やデータの入れ場所 をコンパイル時には確定できないので、コンパイル時はベースとして使うレジスタ に対する相対番地で、命令やデータを表現する。リンカでは複数のコンパイル単位 から来る同じ種類のものをまとめ、コード領域、大域的変数領域、局所的変数領域 というように分ける。局所的領域はスタック・フレームの中にとる。何をどこに置 くかは中間語の sect 命令で指示する。
（２） オブジェクト実行環境 このコンパイラで生成するオブジェクト・コードでは、コンパイラを単純にする ため、演算はレジスタ間でのみ実行することにし、オペランドはすべて一旦レジス タにロードする。 メモリは基底レジスタとそれにに対する相対番地形式 disp(reg2) でアクセスす る。アセンブラ形式のオブジェクトでは、この相対番地を変数名称で表せる場合は 変数名称で表す。添字つき変数は、その番地を計算してレジスタに入れ、それを使っ て間接的にアクセスする。 整数データはすべて４バイト整数として扱う。ただし、かけ算の結果は４バイト の範囲におさまっているものと想定する。 副プログラムを呼ぶ時は、実引数があれば４つまでを引数レジスタにのせ、戻り 番地を戻り番地レジスタに入れて、呼出し先の副プログラムの先頭に飛ぶ。主プロ グラムや副プログラムの入り口では、レジスタを退避し、レジスタ退避領域などの 局所データ領域を確保し、それに合わせてスタック・ポインタ $sp を設定する。こ の設定がすむと、局所データ領域としてのスタック・フレームは図 6.1 の構成をと る。
高位番地
仮引数 n
...
仮引数 5
仮引数 4
仮引数 3
仮引数 2
仮引数 1
frame ptr $fp → 局所変数や (old $sp) 一時変数の領域
戻り番地 $31
レジスタ $23
待避領域 $22
$21
実引数 n 設定場所
...
実引数 5 設定場所
実引数 4 退避場所
実引数 3 退避場所
実引数 2 退避場所
実引数 1 退避場所
stack ptr $sp → 低位番地
図 6.1 Tiny C におけるスタック・フレーム
入り口処理の具体的命令列は次のようにする。 subu $sp,96 スタック領域を確保する（スタック・ポインタを進め る）。 sw $31,72($sp) 戻り番地をスタック・フレームに待避 sd $22,64($sp) レジスタをスタック・フレームに待避 ... .frame $sp,96,$31 スタック・ポインタ、スタック長、戻り番地レジスタ .mask 0x80ff0000,-24 待避したレジスタ、フレーム・オフセットの表示 局所変数や仮引数は、スタック・ポインタをベースとして、disp($sp) の形でア クセスする。 副プログラムから親ルーチンへ戻る時は、レジスタを呼び出し直後の状態に回復 したのち、スタックを解放して親プログラムへ復帰する。この出口処理の具体的命 令列は次のようにする。 lw $16,x 関数値 lw $31,72($sp) 戻り番地を回復 ld $22,64($sp) レジスタを回復 ... addu $sp,96 スタック領域を解放 j $31 親へ戻る
（４）オブジェクトの生成例 図 1.2 にあげた素数を求めるプログラムをこの Tiny C コンパイラでコンパイル し、生成したオブジェクト・コードを図 6.2 に示す。
.sdata
.comm candidat,4
.comm quotient,4
.comm remaindr,4
.comm index,4
.comm nth,4
.comm primenum,4
.comm loopend,4
.comm primeNumbers,400
.globl getPrime
.text
.ent getPrime
getPrime: subu $sp,96 sw $31,32+40($sp) sd $22,24+40($sp) sd $20,16+40($sp) sd $18,8+40($sp) sd $16,0+40($sp) sd $6,8+96($sp) sd $4,0+96($sp) .frame $sp,96,$31 .mask 0x80ff0000,-24 lw $8,96($sp) li $9,2 sw $9,0($8) li $8,1 sw $8,nth li $9,3 sw $9,candidat $lab1: lw $8,nth lw $9,100($sp) bge $8,$9,$lab2 li $10,1 sw $10,remaindr li $11,0 sw $11,index li $12,0 sw $12,loopend $lab3: lw $8,loopend li $9,0 bne $8,$9,$lab4 lw $9,index lw $16,96($sp) sll $9,$9,2 addu $17,$16,$9 lw $10,0($17) sw $10,primenum lw $11,candidat div $11,$11,$10 sw $11,quotient lw $12,candidat mul $11,$11,$10 sub $12,$12,$11 sw $12,remaindr li $13,0 bne $12,$13,$lab5 li $13,1 sw $13,loopend j $lab6 $lab5: $lab6: lw $8,quotient mul $8,$8,$8 lw $9,candidat bge $8,$9,$lab7 li $10,1 sw $10,loopend j $lab8 $lab7: $lab8: lw $8,index li $9,1 add $8,$8,$9 sw $8,index lw $9,nth blt $8,$9,$lab9 li $10,1 sw $10,loopend j $lab10 $lab9: $lab10: j $lab3 $lab4: lw $8,remaindr li $9,0 beq $8,$9,$lab11 lw $9,nth lw $16,96($sp) sll $9,$9,2 addu $10,$16,$9 lw $11,candidat sw $11,0($10) lw $10,nth li $12,1 add $10,$10,$12 sw $10,nth j $lab12 $lab11: $lab12: lw $8,candidat li $9,2 add $8,$8,$9 sw $8,candidat j $lab1 $lab2: li $8,0 sw $8,nth $lab13: lw $8,nth lw $9,100($sp) bge $8,$9,$lab14 lw $16,96($sp) sll $8,$8,2 addu $17,$16,$8 lw $4,0($17) jal print lw $8,nth li $9,1 add $8,$8,$9 sw $8,nth j $lab14 $lab14: lw $31,32+40($sp) ld $22,24+40($sp) ld $20,16+40($sp) ld $18,8+40($sp) ld $16,0+40($sp) addu $sp,96 j $31 .end getPrime .globl main .text .ent main main: subu $sp,96 sw $31,32+40($sp) sd $22,24+40($sp) sd $20,16+40($sp) sd $18,8+40($sp) sd $16,0+40($sp) sd $6,8+96($sp) sd $4,0+96($sp) .frame $sp,96,$31 .mask 0x80ff0000,-24 la $4,primeNumbers li $5,100 jal getPrime li $16,0 addu $2,$16,$0 lw $31,32+40($sp) ld $22,24+40($sp) ld $20,16+40($sp) ld $18,8+40($sp) ld $16,0+40($sp) addu $sp,96 j $31 .end main
図 6.2 Tiny C コンパイラで生成したオブジェクト・コード （図 1.2 に対応）
渡邊 坦 電気通信大学 情報工学科 〒182 調布市調布ケ丘 1-5-1 E-mail: [email protected] URL: http://watalab.cs.uec.ac.jp