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

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

1 コンパイラ 2011年10月27日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

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

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

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

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

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

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

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

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

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

11 例: 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 ＤＳＰの場合は３より多いオペランドを取る場合がある。古のSoundBlaster搭載のe-mu 8000や10k、組み込み用DSC dsPIC33Fなどを参照。

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

13 ポインタや参照といったもの Ｃ言語は、高級アセンブリ言語Ｃと言い換えても 構わないくらい、機械語とつながりが深い。
Ｃ言語は、高級アセンブリ言語Ｃと言い換えても 構わないくらい、機械語とつながりが深い。 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を使って複雑な記述を避けることが鉄則です。勉強のために極端な例を使ってます。 別のキーワードとしては、名前による参照、アドレスによる参照、からも勉強するといいでしょう。

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

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