コード生成（２）
http://cis.k.hosei.ac.jp/~asasaki /lect/compiler/2007-1211.pdf
概要
• 宣言文と記号表
宣言
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 AD 0 0 STV 0 1 LDV 0 1 WRI 0 0 POP 0 26 HLT 0 0宣言
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 AD 0 0 STV 0 1 LDV 0 1 WRI 0 0 POP 0 2 HLT 0 0記号表（変数表）を使った記憶域の管理（再掲）
• 宣言された変数の記憶場所などを管理するために、記号表
が必要となる。
int main() { int abc; int cd; int efg; cd = 10; putint(cd); } ident=“abc” address=0 ident=“cd” address=1 ident=“efg” address=2記号表
ident=“abc” address=0名前（エントリ）..
記号表に登録する内容 つづり 値を保持する アドレス宣言(Declaration)
<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;
http://cis.k.hosei.ac.jp/~asasaki/lectureCompiler/problem3.htm
宣言部の文法
int main() main Block { IDECLLIST } IDECL int IDENT:a IDECL int IDENT:b a = 1; STMLIST b = a+ 2; putint(b) int main(){ int a; int b; a = 1; b = a+2; putint(b); }
構文木（概要）
宣言と記号表への登録
IDECLLIST IDECL int IDENT:a IDECL int IDENT:b addName(“a”) addName(“b”) ident=“a” address=0 ident=“b” address=1記号表
メモリ（記憶域）の確保
Block { IDECLLIST } IDECL int IDENT:a IDECL int IDENT:b a = 1; STMLIST b = a+ 2; putint(b) PUSH 0 2 POP 0 2 LDC 0 1 STV 0 0 LDV 0 0 LDC 0 2 AD 0 0 STV 0 1 LDV 0 1 WRI 0 0練習問題1
• 下記のプログラムに対する構文解析木を書け。また、構文
解析と同時にコード生成をする過程を、スライド9を参考に図
示せよ。(文の部分の木も省略せず書いてみよ）
int main(){ int abc; int de; int fghi; abc = 1; fghi = 4; de = (2 + abc) * fghi; putint(de); }配列(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 S（スタック） PUSH 0 4 LDC 0 0 STV 0 1 LDC 0 1 STV 0 2 … a[3]のための領域配列(2)
int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } a[7]の値 …… a[0]の値 iの値 8 … 1 0 a[8]の値 9 S（スタック） PUSH 0 10 LDC 0 3 LDC 0 4 AD 0 0 STV 0 0 LDC 0 1 STV 0 8 LDC 0 2 STV 0 9 …配列(3)
int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=2; } a[7]の値 …… a[0]の値 iの値 8 … 1 0 a[8]の値 9 S（スタック） PUSH 0 10 LDC 0 3 LDC 0 4 AD 0 0 STV 0 0 LDC 0 1 STV 0 8 LDC 0 2 STV 0 9 … int main(){ int i; int a[9]; i = 1; while (i <9){ a[i]=i; i=i+1; このような場合、配列への代入ロード命令、ストア命令(暫定版再掲）
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以外 の場合については後の講義で説明する。ロード命令、ストア命令(暫定版２）
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++STI命令
STI 0 0 間接ストア命令 S[S[sp-1]]←S[sp]; sp=sp-2; pc++; STI 0 0 1000 2 sp sp-1 S（スタック） (s[sp]=1000, s[sp-1]=2) …… … 0 2 1 0 S（スタック） …… … 1000 2 1 0 s[s[sp-1]]←s[sp] s[2]←1000 格納する値 格納する アドレス LDA 0 2 LDC 0 1000 STI 0 0 LDC 0 1000 STV 0 2 STV命令 は左の形 に書き換 えられる配列(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 AD 0 0 STV 0 0 LDA 0 1 LDV 0 0 AD 0 0 LDC 0 1 STI 0 0 a[7]の値 …… a[0]の値 iの値 8 … 1 0 a[8]の値 9 1+i (= 8) a[i]のiの値を求める(=7) aの開始アドレス=1をロード 左辺の定数1をロード a[i] (S[8])にストア 格納するア ドレス 格納する 値配列(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 AD 0 0 AD 0 0 LDC 0 2 STI 0 0 POP 0 10 a[7]の値 …… a[0]の値 iの値 8 … 1 0 a[8]の値 9 aの開始アドレスにi+1を足す(=9) aの開始アドレス=1をロード a[i+1]のi+1(=8)の計算 左辺の2をロード a[8] (S[9])へストア 格納する値 格納する アドレスLDI命令
LDI 0 0 間接ロード命令 S[sp]←S[S[sp]]; pc++ LDI 0 0 2 sp S（スタック） (s[sp]=2) …… … 1000 2 1 0 S（スタック） …… … 1000 2 1 0 s[sp]←s[s[sp]](=s[2]) s[sp]←1000 1000 sp ロードしたい変 数のアドレス LDA 0 2 LDI 0 0 LDV 0 2 LDV命令 は左の形 に書き換 えられる配列(6)
int main(){ int i; int a[9]; i = 3 + 4; a[i]=1; a[i+1]=a[i]+2; } LDA 0 1 LDV 0 0 LDC 0 1 AD 0 0 AD 0 0 LDA 0 1 LDV 0 0 AD 0 0 LDI 0 0 LDC 0 2 AD 0 0 a[7]の値 …… a[0]の値 iの値 8 … 1 0 a[8]の値 9 a[7](=S[8])の値をロード aの開始アドレスにi+1を足す(=9) aの開始アドレス=1をロード a[i+1]のi+1(=8)の計算 a[i]のアドレス計算 (=1+7=8) +2 格納する値 格納する アドレス =ロードしたい変 数のアドレス宣言と記号表登録（配列）
int i; int a[10], j; a[8]の値 …… a[0]の値 iの値 9 … 1 0 a[9]の値 10 jの値 11 ident=“i” address=0 ident=“a” address=1 ident=“j” address=10記号表
宣言と記号表登録（配列）
int i; int a[10], j; a[8]の値 …… a[0]の値 iの値 9 … 1 0 a[9]の値 10 jの値 11 ident=“i” address=0 ident=“a” address=1 ident=“j” address=10記号表
type=var size=1 type=array size=10 type=var size=1記号表の拡張
ident=“abc” address=0名前（エントリ）..
記号表に登録する内容（拡張版） つづり 値を保持する アドレス type=variable size=1 変数の種類 variable or array 記憶域の大きさ Intならば1, 配列ならば 配列のサイズ配列要素の代入、参照
<STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' ... <SUBSTITUTION>::= <IDENT> | <IDENT> '[' <EXPRESSION> ']' <EXPRESSION>::= .. <TERM>::= <UNARY>::= <FACTOR>::= <IDENT> | <IDENT> '[' <EXPRESSION> ']' | <NUMBER> | '(' <EXPRESSION> ')'
代入文(1)
<STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' <SUBSTITUTION>::= <IDENT> | <IDENT> '[' <EXPRESSION> ']' a[8]=200; 格納するアドレ スを計算する コード 格納する値を計 算するコード LDA 0 1 (aのアドレス） a[8]の値 …… a[0]の値 iの値 9 … 1 0 a[9]の値 10 jの値 11 LDC 0 8 AD 0 0 LDC 0 200
代入文(2)
<STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' <SUBSTITUTION>::= <IDENT> | <IDENT> '[' <EXPRESSION> ']' a[i+3]=200; 格納するアドレ スを計算する コード 格納する値を計 算するコード LDA 0 1 (aのアドレス） a[8]の値 …… a[0]の値 iの値 9 … 1 0 a[9]の値 10 jの値 11 LDV 0 0 (LDA 0 0; LDI 0 0 ) LDC 0 3 AD 0 0 AD 0 0 LDC 0 200
= STM a[i+3]=200;
代入文の構文木（配列の場合,,概要）
SUBSTITUTION IDENT:a [ EXP ] EXP NUM:200 + IDENT:i NUM:3 LDA 0,「aのアドレス」 LDV 0,「iのアドレス」 LDC 0 3 AD 0 0 AD 0 0 LDC 0 200 STI 0 0= STM i=200;
代入文の構文木（概要）
SUBSTITUTION IDENT:i EXP NUM:200 LDA 0,「iのアドレス」 LDC 0 200 STI 0 0 LDC 0 200 STV 0 「iのアドレス」 LDA 0 「iのアドレス」 LDC 0 200配列参照式
<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 AD 0 0 LDI 0 0 LDC 0 200+ EXP a[i-3]+200;
配列参照の構文木（概要）
F IDENT:a [ EXP ] F + IDENT:i NUM:3 LDA 0,「aのアドレス」 LDV 0,「iのアドレス」 LDC 0 3 SB 0 0 AD 0 0 LDC 0 200 AD 0 0 NUM:200 LDI 0 0練習問題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) コード生成の過程入出力文
<STATEMENT>::= <SUBSTITUTION> '=' <EXPRESSION> ';' | '{' <STATEMENTLIST> '}' | 'putchar' '(' <CHARACTER> ')' ';' | 'getchar' '(' <SUBSTITUTION> ')' ';' | 'putint' '(' <EXPRESSION> ')' ';' | 'getint' '(' <SUBSTITUTION> ')' ';' | 'putnl'';' putchar 引数文字をコンソールに出力 getchar <SUBSTITUTION>に割り当てられた場所にコンソールからの入力文字の コードの値（整数値）を代入する． putint <EXPRESSION>の値を整数で出力 getint <SUBSTITUTION>に割り当てられた場所にコンソールからの入力整数を 代入する． putnl 改行コードをコンソールに出力する
