コード生成 (2) http://cis.k.hosei.ac.jp/~asasaki /lect/compiler/2007-1211.pdf 1
概要 宣言文と記号表 ( 配列 ) 今日はやりません 2
宣言 a = 1; b = a+2; putint(b); int main(){ int a; int b; a = 1; b = a+2; putint(b); } PUSH 0 26 LDC 0 1 STV 0 0 LDV 0 0 LDC 0 2 STV 0 1 LDV 0 1 WRI 0 0 POP 0 26 HLT 0 0 3
宣言 a = 1; b = a+2; putint(b); int main(){ int a; int b; a = 1; b = a+2; putint(b); } PUSH 0 2 LDC 0 1 STV 0 0 LDV 0 0 LDC 0 2 STV 0 1 LDV 0 1 WRI 0 0 POP 0 2 HLT 0 0 4
記号表 ( 変数表 ) を使った記憶域の管理 ( 再掲 ) 宣言された変数の記憶場所などを管理するために 記号表が必要となる int main() { int abc; int cd; int efg; cd = 10; putint(cd); } 記号表 ident= abc ident= cd ident= efg address=0 address=1 address=2 名前 ( エントリ ).. 記号表に登録する内容 ident= abc つづり address=0 値を保持するアドレス 5
宣言 (Declaration) 宣言部の文法 http://cis.k.hosei.ac.jp/~asasaki/lecturecompiler/problem3.htm <MAIN>::= 'int' 'main' '(' ')' <BLOCK> <BLOCK>::= '{' <INTDECLLIST> <STATEMENTLIST> '}' <INTDECL>::= 'int' <IDENTLIST> ';' <IDENTLIST>::= <IDENT> <IDENT> '[' <NUMBER> ']' <IDENTLIST> ',' <IDENT> <IDENTLIST> ',' <IDENT> '[' <NUMBER> '] 宣言部の例 int a, array[3]; int b; 6
構文木 ( 概要 ) main int main() Block { IDECLLIST STMLIST } int main(){ int a; int b; a = 1; b = a+2; putint(b); } IDECL IDECL a = 1; b = a+ 2; putint(b) int IDENT:a int IDENT:b 7
宣言と記号表への登録 IDECLLIST IDECL IDECL int IDENT:a int IDENT:b addname( a ) 記号表 ident= a addname( b ) address=0 ident= b address=1 8
メモリ ( 記憶域 ) の確保 Block PUSH 0 2 { IDECLLIST STMLIST } POP 0 2 IDECL IDECL a = 1; b = a+ 2; putint(b) int IDENT:a int IDENT:b LDC 0 1 STV 0 0 LDV 0 0 LDC 0 2 STV 0 1 LDV 0 1 WRI 0 0 9
練習問題 1 下記のプログラムに対する構文解析木を書け また 構文解析と同時にコード生成をする過程を スライド 9 を参考に図示せよ ( 文の部分の木も省略せず書いてみよ ) int main(){ int abc; int de; int fghi; abc = 1; fghi = 4; de = (2 + abc) * fghi; putint(de); } 10
配列 (1) int main(){ int i; int a[3]; a[0]=0; a[1]=1; a[2]=2; } a[2] の値 a[1] の値 a[0] の値 iの値 3 2 1 0 a[3] のための領域 S( スタック ) PUSH 0 4 LDC 0 0 STV 0 1 LDC 0 1 STV 0 2 11
配列 (2) int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } a[8] の値 9 a[7] の値 8 a[0] の値 1 iの値 0 S( スタック ) PUSH 0 10 LDC 0 3 LDC 0 4 STV 0 0 LDC 0 1 STV 0 8 LDC 0 2 STV 0 9 12
配列 (3) int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } int main(){ int i; int a[9]; i = 1; while (i <9){ a[i]=i; i=i+1; } } a[8] の値 9 a[7] の値 a[0] の値 i の値 S( スタック ) 8 1 0 PUSH 0 10 LDC 0 3 LDC 0 4 STV 0 0 LDC 0 1 STV 0 8 LDC 0 2 STV 0 9 このような場合 配列への代入は STV 命令では対処できない i の値がループによって変わる ( 変数値を格納するアドレスが可変 ) 13
ロード命令 ストア命令 ( 暫定版再掲 ) STV 0 N ストア命令 S[N] S[sp]; sp--; pc++ LDV 0 N ロード命令 sp++; S[sp] S[N]; pc++ LDC 0 N 即値ロード命令 sp++; S[sp] N; pc++ Hsm の web ページの説明では STV p q s[base(p)+q]=s[t];t=t-1;pc=pc+1; となっている p=0 のときは base(p)=0 である p が 0 以外の場合については後の講義で説明する 14
ロード命令 ストア命令 ( 暫定版 2) STV 0 N ストア命令 S[N] S[sp]; sp--; pc++ STI 0 0 間接ストア命令 S[S[sp-1]] S[sp]; sp=sp-2; pc++; LDV 0 N ロード命令 sp++; S[sp] S[N]; pc++ LDC 0 N 即値ロード命令 sp++; S[sp] N; pc++ LDA 0 N アドレスロード命令 sp++; S[sp] N; pc++ LDI 0 0 間接ロード命令 S[sp] S[S[sp]]; pc++ 15
STI 命令 STI 0 0 間接ストア命令 S[S[sp-1]] S[sp]; sp=sp-2; pc++; LDA 0 2 LDC 0 1000 STI 0 0 STV 命令は左の形に書き換えられる LDC 0 1000 STV 0 2 格納する値 STI 0 0 1000 sp 格納するアドレス 2 sp-1 0 2 (s[sp]=1000, s[sp-1]=2) 1000 2 1 0 s[s[sp-1]] s[sp] 1 0 S( スタック ) s[2] 1000 S( スタック ) 16
配列 (4) int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } 格納するアドレス PUSH 0 10 LDC 0 3 LDC 0 4 STV 0 0 LDA 0 1 LDV 0 0 aの開始アドレス =1をロード a[i] のiの値を求める (=7) 1+i (= 8) a[8] の値 9 a[7] の値 a[0] の値 8 1 格納する値 LDC 0 1 STI 0 0 左辺の定数 1をロード a[i] (S[8]) にストア i の値 0 S( スタック ) 17
配列 (5) int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } 格納するアドレス 格納する値 LDA 0 1 LDV 0 0 LDC 0 1 LDC 0 2 aの開始アドレス =1をロード a[i+1] のi+1(=8) の計算 aの開始アドレスにi+1を足す (=9) 左辺の2をロード a[8] の値 9 STI 0 0 a[8] (S[9]) へストア a[7] の値 a[0] の値 iの値 8 1 0 POP 0 10 S( スタック ) 18
LDI 命令 LDI 0 0 間接ロード命令 S[sp] S[S[sp]]; pc++ LDA 0 2 LDI 0 0 LDV 命令は左の形に書き換えられる LDV 0 2 ロードしたい変数のアドレス LDI 0 0 2 sp 1000 2 1 (s[sp]=2) s[sp] s[s[sp]](=s[2]) 1000 sp 1000 2 1 0 0 S( スタック ) s[sp] 1000 S( スタック ) 19
配列 (6) int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=a[i]+2; } a[8] の値 9 格納するアドレス 格納する値 LDA 0 1 LDV 0 0 LDC 0 1 LDA 0 1 LDV 0 0 LDI 0 0 a の開始アドレス =1 をロード a[i+1] の i+1(=8) の計算 a の開始アドレスに i+1 を足す (=9) a[i] のアドレス計算 (=1+7=8) a[7](=s[8]) の値をロード = ロードしたい変数のアドレス a[7] の値 a[0] の値 8 1 LDC 0 2 +2 i の値 0 STI 0 0 a[8] (S[9]) へストア S( スタック ) POP 0 10 20
宣言と記号表登録 ( 配列 ) int i; int a[10], j; 記号表 ident= i address=0 j の値 11 a[9] の値 10 ident= a ident= j address=1 address=10 a[8] の値 a[0] の値 iの値 9 1 0 S( スタック ) 21
宣言と記号表登録 ( 配列 ) int i; int a[10], j; 記号表 ident= i address=0 type=var size=1 j の値 11 a[9] の値 10 ident= a ident= j address=1 address=10 type=array type=var size=10 size=1 a[8] の値 a[0] の値 iの値 9 1 0 S( スタック ) 22
記号表の拡張 名前 ( エントリ ).. 記号表に登録する内容 ( 拡張版 ) ident= abc address=0 type=variable size=1 つづり 値を保持するアドレス 変数の種類 variable or array 記憶域の大きさ Int ならば 1, 配列ならば配列のサイズ 23
配列要素の代入 参照 <STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';'... <SUBSTITUTION>::= <IDENT> <IDENT> '[' <EXPRESSION> ']' <EXPRESSION>::=.. <TERM>::= <UNARY>::= <FACTOR>::= <IDENT> <IDENT> '[' <EXPRESSION> ']' <NUMBER> '(' <EXPRESSION> ')' 24
代入文 (1) <STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' <SUBSTITUTION>::= <IDENT> <IDENT> '[' <EXPRESSION> ']' a[8]=200; jの値 11 a[9] の値 10 a[8] の値 9 a[0] の値 1 iの値 0 格納するアドレスを計算するコード 格納する値を計算するコード LDA 0 1 (aのアドレス) LDC 0 8 LDC 0 200 S( スタック ) STI 0 0 STI 0 0 25
代入文 (2) <STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' <SUBSTITUTION>::= <IDENT> <IDENT> '[' <EXPRESSION> ']' a[i+3]=200; jの値 11 a[9] の値 10 a[8] の値 9 a[0] の値 1 iの値 0 格納するアドレスを計算するコード 格納する値を計算するコード LDA 0 1 (a のアドレス ) LDV 0 0 (LDA 0 0; LDI 0 0 ) LDC 0 3 LDC 0 200 S( スタック ) STI 0 0 STI 0 0 26
代入文の構文木 ( 配列の場合,, 概要 ) STM a[i+3]=200; SUBSTITUTION = EXP STI 0 0 IDENT:a [ EXP ] LDA 0, aのアドレス NUM:200 LDC 0 200 IDENT:i + NUM:3 LDV 0, i のアドレス LDC 0 3 LDA 0, i のアドレス LDI 0,0 でもよい 27
代入文の構文木 ( 概要 ) STM i=200; SUBSTITUTION = EXP STI 0 0 IDENT:i LDA 0, i のアドレス NUM:200 LDC 0 200 LDC 0 200 STV 0 i のアドレス LDA 0 i のアドレス LDC 0 200 STI 0 0 28
配列参照式 <EXPRESSION>::=.. <TERM>::= <UNARY>::= <FACTOR>::= <IDENT> <IDENT> [ <EXPRESSION> ] a[i-3]+200 ロードする配列要素のアドレス計算のコード LDI 0 0 LDA 0 1 (a のアドレス ) LDV 0 0 LDC 0 3 SB 0 0 LDI 0 0 LDC 0 200 29
配列参照の構文木 ( 概要 ) EXP a[i-3]+200; F + F IDENT:a [ EXP ] LDA 0, aのアドレス LDI 0 0 NUM:200 LDC 0 200 IDENT:i + NUM:3 SB 0 0 LDV 0, i のアドレス LDC 0 3 LDA 0, i のアドレス LDI 0,0 でもよい 30
練習問題 2 int main(){ int i; int a[2], b[2]; a[0]=100; a[1]=200; i = 0; b[i]=a[1-i]*4; i = i + 1; b[i]=a[1-i]*4; } 左のプログラムについて下記を示せ (1) 記憶域の状態 (2) hsm のコード (3) (2) のコードの実行の状態 (4) 記号表の登録内容 (5) コード生成の過程 31
入出力文 <STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' '{' <STATEMENTLIST> '}' 'putchar' '(' <CHARACTER> ')' ';' 'getchar' '(' <SUBSTITUTION> ')' ';' 'putint' '(' <EXPRESSION> ')' ';' 'getint' '(' <SUBSTITUTION> ')' ';' 'putnl'';' putchar 引数文字をコンソールに出力 getchar <SUBSTITUTION> に割り当てられた場所にコンソールからの入力文字のコードの値 ( 整数値 ) を代入する. putint <EXPRESSION> の値を整数で出力 getint <SUBSTITUTION> に割り当てられた場所にコンソールからの入力整数を代入する. putnl 改行コードをコンソールに出力する 32
入力命令 RDI 0 0 整数入力命令 S[S[sp]] に読み込んだ整数を保存 ; sp--; pc++ RDC 0 0 文字入力命令 S[S[sp]] に読み込んだ文字コードを保存 ; sp--; pc++ 33
課題 3(Problem3) コンパイラの作成 3 自由に変数名をつけられる ( 配列を扱うことができる ) 今日は必要なし 入出力文を扱える http://cis.k.hosei.ac.jp/~asasaki/lecturecompiler/problem3.htm 34