文
変数
=
式;
a
式+
式変数
b
定数
1
●
準備
– 構文木の節点（ノード）
Node n;
– 節点の子節点
n.child(k)
– 節点の種類
n.type == “
文”構文木から 4 つ組の生成
文
変数
=
式;
a
式+
式変数
b
定数
1
●
準備
– 構文木の節点（ノード）
Node n;
– 節点の子節点
n.child(k)
– 節点の種類
n.type == “
文”構文解析ルールの例
●
プログラム：文
●
プログラム：プログラム 文
●
文：変数 = 式 ;
●
式：変数
●
式：定数
●
式：式 + 式
●
式：式 – 式
4 つ組生成手続き（文）
Generate(Node n) { If (n.type == “
式” and
n.child.type == (“
変数” “=” “
式” “;”)) { tmpvar =
一時変数名GenerateExpression(n.child(2), tmpvar) Output(“=”, tmpvar, null, n.child(0))
}
}
4 つ組生成手続き（式）
GenerateExpression(Node n, String tmpvar) { If (n.child(0).type が “変数” または “定数” ) { Output(“=”,n.child(0).child(0), null,tmpvar) } Else if (n.child(1).type が “ +” または “ -”) { t1 = 一時変数名 ; t2 = 一時変数名
GenerateExpression(n.child(0), t1) GenerateExpression(n.child(2), t2)
Output(n.child(1).type, t1, t2, tmpvar)
}
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n.child(2), tmpvar)
Output(“=”, tmpvar, null, n.child(0)) n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1")
Output(“=”, tmpvar, null, n.child(0)) n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2")
GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1")
Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2")
GenerateExpression(n.child(2), "T3") Output(n8.type, "T2", "T3", "T1")
Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2")
Output(“=”,n.child(0).child(0), null,"T2") GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2")
GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2")
GenerateExpression(n.child(2), "T3") Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3")
Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3")
Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3")
Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3")
Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2) (=, 1, , T3)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3")
Output(n.child(1).type, "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2) (=, 1, , T3)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2) (=, 1, , T3) (+, T2, T3, T1)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1") Output(“=”, "T1", null, n.child(0))
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2) (=, 1, , T3) (+, T2, T3, T1)
4 つ組の生成例
文
変数
=
式;
a
式+
式変数
b
定数
1
Generate(n1)
GenerateExpression(n4, "T1") GenerateExpression(n7, "T2") Output(“=”,n12, null,"T2") GenerateExpression(n9, "T3") Output(“=”,n13, null,"T3") Output("+", "T2", "T3", "T1") Output(“=”, "T1", null, a)
n1
n2 n3 n4 n5
n6 n7 n8 n9
n10 n11
n12 n13
(=, b, , T2) (=, 1, , T3) (+, T2, T3, T1) (=, T1, ,a)
効率の良い中間表現生成
●
前ページの中間表現は実は 1 行で書ける
–
(+, b, 1, a)
– 最初からこういう中間表現を生成するには？
– 中間表現の生成ルールを細かくする
– 中間表現を生成した後、コードの無駄を省く処理を行う
（最適化）
細かいコード生成ルール
●
「式 1 ＋式 2 」の場合
– 最後に格納する一時変数を
T1
とする式
1
の先変数 定数 その他
式
2
の 先変数 (+,変数1,変数2,
T1） (+,定数1,変数2,
T1）
式1の四つ組を生成し てT2に格納
(+,T2,変数2,T1)
定数 (+,変数1,定数2,
T1） (+,定数1,定数2,
T1）
式1の四つ組を生成し てT2に格納
(+,T2,定数2,T1)
その他 式1の四つ組を生成
してT2に格納 (+,T2,変数2,T1)
式1の四つ組を生成 してT2に格納
(+,T2,定数2,T1)
式1の四つ組を生成し てT2に格納
式2の四つ組を生成し てT3に格納
(+,T2,T3,T1)
最適化の例
●
中間表現があるパターンに合致する場合には置き換 えを行う
– 例：ある一時変数に何かを代入し、そのあとその一時変数 が
1
回しか使われていなければ、後者の一時変数を前者 の変数または定数に置き換える。– ある一時変数に結果を代入し、それをすぐに別な変数に 代入しているとき、一時変数をその変数に置き換える。
(=, x, ,T3) :
(+, T3, T4, T2)
(=, x, ,T3) :
(+, x, T4, T2)
(+, x, y, T1)
(=, T1, , z) (+, x, y, z)
(=, T1, ,z)
最適化の例
(=, b, ,T2) (=, 1, ,T3)
(+, T2, T3, T1) (=, T1, ,a)
(=, b, ,T2) (=, 1, ,T3)
(+, b, T3, T1) (=, T1, ,a)
(=, 1, ,T3)
(+, b, T3, T1) (=, T1, ,a)
(=, 1, ,T3) (+, b, 1, T1)
(=, T1, ,a) (+, b, 1, T1)
(=, T1, ,a) (+, b, 1, a)
(=, T1, ,a)
コード生成
●
四つ組の列を命令列に変換
– 変換ルール例