コンパイラ 2011年10月27日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html

中間表現 前回までの内容 今回の内容 次回の内容 字句解析 構文解析 構文木や４つ組みとして表されるものをきちんと説明。 意味解析 ソースプログラムという文字の並びから、字句の並びへ変換。 ただし、字句は構造を持ったデータ。つまり少し抽象化したデータの並び。 構文解析 字句の並びから、構造を持ったデータの集まりへ変換。 名前やデータ構造は名前表に出力する。 では、制御構造（文の構造）はどうする？？？ とりあえずは、構文木や４つ組として出力する、と説明した。とりあえず... 今回の内容 構文木や４つ組みとして表されるものをきちんと説明。 次回の内容 意味解析

二分木 二項演算や代入は二分木で表現可能。 関数呼び出しは特殊ノードとして表現する。 後順走査することで、後置記法のオブジェクトコードを生成可能。 演算・代入は子を２つもつノード。 ノードは、その結果を親ノードへ返す。 変数や定数はリーフ。 参照した値を親ノードへ返す。右辺値を返す？ 代入ノードの左の子 親ノードが代入ノードである場合を判断し、左辺値を返す。 右辺値を返し、代入ノードでその右辺値の指す先に値を置く。 関数呼び出しは特殊ノードとして表現する。 引数の数だけ子を持つノード。 戻り値を親ノードへ返す。

式y+find_max(a+b, c, 0)/(x-1)の構文木 〈式〉ノードの種類 (call,+,-,*,/,>,>=,<,<=,<>,=) 子ノードへのポインタ１ 子ノードへのポインタ２ 型 語長 call find_max arg_vector + y / - x 1 a b c 〈リーフ〉ノードの種類 (名前(変数, 関数), 定数) 名前表へのインデックス 定数値 ※　この例では代入や左辺値を必要とする演算は表されていない。

左辺値と右辺値 左辺値(l-value) 右辺値(r-value) 代入の左辺に置けるもの。代入先に指定できるもの。 言語によるが、たいていは変数。 実行環境が許せば、＊((int ＊)0x1000) でも左辺値になる。 右辺値(r-value) 代入の右辺に置けるもの。 左辺値になれなくても、右辺値になるものはある。 Ｃ言語における、関数名・配列名は左辺値にはなれない。 式の返す値。 x++は、右辺値にしかなれない。++(x++)はエラー。 ＊p = 10; と書けるとき、＊p が代入の左辺値である。 pが左辺値かどうかは、pの定義しだい。 pが＊演算子で参照された結果が左辺値だ、というだけ。

四つ組 木として保持するより小さく、外部ファイルに出しやすい。 つぎの情報をひとつの四つ組として持つ 保持する情報は木と変わらない。 つぎの情報をひとつの四つ組として持つ 演算子の情報 第一オペランドの情報 第二オペランドの情報 演算結果の保存先 保存先にコンパイラが生成した一時的な変数も存在する。 木の場合には、演算ノードが保持している、ということに対応。

四つ組と木構造 + = * a b c d 四つ組 (①＊，②ｃ，③ｄ，④tmp#1) (①＋，②ｂ，③tmp#1，④tmp#2) 四つ組の代入形式表現 tmp#1 := ｃ＊ｄ tmp#2 := ｂ＋tmp#1 ａ := tmp#2 代入のときの保存先は左辺値である。 四つ組で＠をつけているところで、アドレスで参照している。 一方の木構造の例では、名前で参照している。

四つ組と木構造の関係 木を後順走査した結果と四つ組表現がよく合う。 変数や定数 木は必ずしも２分木である必要はない。 子を先に走査することがオペランドを用意することに対応し、 演算子はそれらオペランドに作用することから後で出力する。 演算途中の値は、一時変数に置く。 変数や定数 木でも四つ組でも名前表に置き、インデックスなどで参照する。 木は必ずしも２分木である必要はない。 三項演算子・引数が２個より多い関数は多分木のほうがよい。 if-then-elseやforのような制御構造を表す場合も多分木 のほうがよく合う。 四つ組は書き方が機械命令に近い。 除算のように、戻り値が２つ以上ある演算も書けたりする。

z=y+1/(x-1)の木構造と四つ組 対応する四つ組 ①(-，x，1，tmp#1) ②(/，1，tmp#1，tmp#2) ③(+，y，tmp#2，tmp#3) ④(=，tmp#3，，@z) 対応する三つ組 ①(-，x，1) ②(/，1，①) ③(+，y，②) ④(=，③，@z) 代入形式 ①tmp#1 := x-1 ②tmp#2 := 1/tmp#1 ③tmp#3 := y+tmp#2 ④z := tmp#3 = ｚ + ｙ / １ - ｘ １

中間言語の必要性 四つ組は３オペランド形式の機械語に近いとはいうものの… 命令セットアーキテクチャは、マイクロアーキテクチャの影響 を受けて設計されるため、そのままでは使いにくい。 オペランドの組み合わせに関する直交性が限定的。 メモリ対メモリの演算ができない命令セットアーキテクチャが多い。 一時変数としてのレジスタ数に限りがある。 SPARC v9で３２個、IA-32で８個、だけど使途に制約あり。 即値・絶対アドレスといった値の大きさに制約がある。 たいていは倍精度浮動小数点数を即値で表せない。 レジスタの使途に制約がある場合がある。 整数演算用・浮動小数点演算用・アドレス保持用・暗黙的使用など。

例: IA-32とH8（単純なもの） IA-32(Intel表記) H8(gas表記) add eax,ebx add r0,r1 add [eax],ecx lea eax,[ebx+edx] lea eax,[esi+edi*4+8] mul eax,edx mov ecx,eax mov eax,[ebx+16] mov eax,[ebx+ecx*4] mov [edx],ecx H8(gas表記) add r0,r1 mulxu r0l,r1 mov r2,r5 mov @(12,r2),r0 mov r0,@r1 ＤＳＰの場合は３より多いオペランドを取る場合がある。古のSoundBlaster搭載のe-mu 8000や10k、組み込み用DSC dsPIC33Fなどを参照。

例：dsPIC33Fのmac命令（複雑なもの） Multiply and Accumulate命令 mac W4*W5,A, [W8],W6, [W10],W7, [W13] Ｗ４とＷ５の乗算結果をＡアキュムレータへ加算（積和） Ｗ８で指し示されるＸメモリからＷ６へロード（次命令のためのプリロード） Ｗ１０で指し示されるＹメモリからＷ７へロード（次命令のためのプリロード） Ｗ１３で指し示すメモリへＢアキュムレータの値を飽和・丸めの後でストア 先行命令の結果のストア、現在命令の演算、後続命令の オペランドのロード、を同時に１クロック時間で片付ける。 構文解析後に、いきなり生成することはできません！

ポインタや参照といったもの Ｃ言語は、高級アセンブリ言語Ｃと言い換えても 構わないくらい、機械語とつながりが深い。 Ｃ言語は、高級アセンブリ言語Ｃと言い換えても 構わないくらい、機械語とつながりが深い。 int *f(); /* fはintへのポインタを返す関数 */ int (*f)(); /* fはintを返す関数へのポインタ */ char **argv; /* charへのポインタのポインタ */ int (*daytab)[13]; /* daytabはintを要素とする要素数13の配列へのポインタ */ int *daytab[13]; /* daytabはintへのポインタを要素とする要素数13の配列 */ char (*(*x())[])(); /* xはcharを返す関数へのポインタの配列へのポインタを返す関数 */ char (*(*x[3])())[5];/* xはcharを要素とする要素数5の配列へのポインタを返す関数 へのポインタを要素とする要素数3の配列 */ 出典: "プログラミング言語Ｃ 第２版", 共立出版, 149ページ, 2001年. もちろん、typedefを使って複雑な記述を避けることが鉄則です。勉強のために極端な例を使ってます。 別のキーワードとしては、名前による参照、アドレスによる参照、からも勉強するといいでしょう。

例：char (*(*x[3])())[5];という定義 例の定義ではポインタ３個分の大きさのメモリがｘとして定義されます（ｘは名前による参照）。 ポインタの大きさは処理系依存ですが、大きさはintと同じことが多い。 ｘの要素を参照する、つまりプログラムの中で y = x[0](); としたときのｙは？ x: .word a, b, c ! a, b, cは関数のエントリーポイントであるとする。 y: .word 0 ! 戻り値を入れる場所とする。yの型はchar (*)[5] mov @x,r0 jsr @r0 ! x[0]()に対応し、呼ばれた関数がr0に値を返す。 ｙには関数から戻ったときのr0の値が入る。その変数の指す先に要素数５のcharの配列がある。 y

関数呼び出しの()と、キャストの() 下線をつけたところが関数呼び出しの()。 関数呼び出しのときの()の左側のオブジェクトは何？ 文脈で区別され、内側から読むと、「ｘは大きさ３の配列で、 その要素を参照することで関数が呼び出され、呼び出された 関数の返す値を参照すると大きさ５のchar配列にたどり着く。」 関数呼び出しのときの()の左側のオブジェクトは何？ エントリーポイントを保持する変数。関数へのポインタ。 ポインタを参照して得た値が関数へのエントリーポイント ポインタ変数は関数ではないが、感覚的に同じように使える。 アセンブリ言語レベルでは、ラベルでしかないもの。 ラベルは最終的にはldによりアドレスに変換されます。 感覚的には名前＝関数。 左辺値 char (*(*x[3])())[5]; 原理から考える習慣を身に着けてほしい。