意味定義

9
意味定義
7 章で，プログラム言語処理系の字句解析器と構文解析器を実装した．字句解析器と構文解析器は，ソースプロ
グラムを抽象構文木という曖昧さを含まない形式に変換し，後のフェーズに引き渡す．抽象構文木を渡された後の
フェーズは，その抽象構文木に解釈を与える．解釈の仕方は，次の 2 とおりに分類できる．
1. 解釈の結果として計算結果を与える方法．
2. 解釈の結果機械コード（他のプログラミング言語のコードを生成してもよい）を生成し，実際の計算は機械
に任せる方法．
一般に，1. の解釈を行う処理系をインタプリタと呼び，2. の解釈を行う処理系をコンパイラと呼ぶ．
ここでは，Java 仮想マシンを機械とみなして，Java 仮想マシンコードを生成する，四則演算言語のコンパイラ
を実現する．Java 仮想マシンは，スタックマシンと呼ばれ，多くの命令がオペランドを必要としないことから，0
アドレスマシンと呼ばれることもある．
本章では，まず，スタックマシンがどのように命令を評価するのかを示し，スタックマシン用のコードをどのよ
うに生成すればよいかを示す．次に，Java で書かれたプログラムが，どのような Java 仮想マシンのコードに変換
されるのかを概観し，本演習に必要最小限の Java 仮想マシンコードを解説する．最終的に，構文木から Java 仮
想マシンコードを生成するコード生成器を実現し，コンパイラとして完成させることにする．
9.1
スタックマシン
コンピュータの評価方法としてよく知られているものに，レジスタマシンとスタックマシンがある．私たちが
PC として使っているコンピュータは，レジスタマシンに相当する．今，次の計算をレジスタマシンに実行させる
ことを考えよう．
x = (1 + 2) ∗ y
この式の計算は，先に 1 + 2 を計算し，その結果を y の値と乗算することになる．コンピュータは，1 + 2 の値
や変数 y の値（loada ddr(y)）の一時的な結果を，どのように扱うかで，レジスタマシンとスタックマシンには違
いがある．レジスタマシンでは，一時的な結果をレジスタに保存して，後の計算で使用する．例えば，t1，t2, t3
をレジスタとして，次のような計算になる．
t1
= 1 + 2
t2
= load addr(y)
t3
= t1 ∗ t2
addr(x)
= t3
計算結果は，変数 x に対応するアドレス addr(x) に得られる．
一方，スタックマシンは，レジスタの代わりに，スタックに一時的な結果を保存する．スタックマシンにおけ
る式の計算は，スタックのプッシュとポップに基づく次のような規則に基づいて実行される．
101
1. 定数や変数は，その値をスタックにプッシュする
2. 演算子は，計算に必要なオペランド数だけ，スタックをポップし，計算結果をスタックにプッシュする
3. “load addr(v)” 命令は，変数 v のアドレス addr(v) から値を読み出し，スタックにプッシュする
4. “store addr(v)” 命令は，スタックをポップし得られた値を，変数 v のアドレス addr(v) に格納する
スタックマシンは，このような単純な規則によって計算を行うので，式のオペランドと演算子を，スタックマシ
ンの計算順序に合わせて並べ替えておかなければならない．例えば，上記の計算は，次のようになる．
1 2 + load addr(y) ∗ store addr(x)
このようにオペランドよりも演算子を後ろに配置した表現を，後置記法と呼ぶ．これに対して，演算子をオペラ
ンドの間に配置する表現を中置記法と呼ぶ．
上記の後置記法の式を，規則にしたがって計算してみよう．計算は，左から順に行うことに注意しよう．ここ
で，変数 y には，3 が格納されているものとする．
1. 1 をスタックにプッシュする
スタックの状態： [1]
2. 2 をスタックにプッシュする
スタックの状態： [1,2]
3. スタックを 2 回ポップし，得られた値を加算した結果をスタックにプッシュする
スタックの状態： [3]
4. addr(y) から 3 を読み出して，スタックにプッシュする
スタックの状態： [3,3]
5. スタックを 2 回ポップし，得られた値を乗算した結果をスタックにプッシュする
スタックの状態： [9]
6. スタックをポップし，得られた値を変数 x のアドレス addr(x) に格納する
スタックの状態： [ ]
計算結果は，中置記法同様，変数 x に対応するアドレス addr(x) に得られる．
9.2
後置記法への変換
中置記法から後置記法への変換は，中置記法の抽象構文木を作成することによって，容易に実現できる．次の
図は，x = ( 1 + 2 ) ∗ y の構文木を表している．各節点のラベルは，演算子とオペランドを示している．
x= "store_addr(x)"
*
1
+
"+"
"1"
2
"*"
y
"2"
"load_addr(y)"
後置記法への変換は，木の根から各節点 n を深さ優先で辿りながら，次のように行う．
1. 節点 n に訪問する
2. n のすべて子供を左から順に訪問する
3. n のラベルに対応する命令を印字する
図の点線矢印は，節点の訪問順序を表しており，その途中に印字すべき命令を示してある．
9.3
Java 仮想マシン
この節では，Java プログラムをコンパイルして得られたクラスファイルを覗見ることで，Java 仮想マシン用の
コードを概観することにする．
クラスファイルの内容は，バイトコードと呼ばれ，人が読むのには，適していない．そこで，逆アセンブラを
用いて，人が読める形式に変換してみることにしよう．まず，次の Java プログラム Sample.java を作成する．
プログラム 80: Java プログラム Sample.java
class Sample {
public static void main (String[] args) {
int x, y;
y = 3;
x = (1+2)*y;
System.out.println(x);
}
}
次に，Sample.java を javac によってコンパイルすると，Sample.class が生成される．Sample.class を逆アセンブ
ルした結果が，Sample.j である．左端に，説明の都合上，番号をふってあるが，これはコードの一部ではないの
で注意してほしい．
コードの大枠は，次のとおりである．
1 行目：.class は，同期の有無と，クラス名を宣言する
2 行目：.super は，スーパクラスを指定する．スーパクラスが，java.lang.Object ならば，java/lang/Object
のように指定する
5-12 行目，14-28 行目：.method ∼ .end method は，メソッド定義を表している．.method の後に，Java と
同様の修飾子とメソッド名が続く．引数の指定は，型を記述する．例えば，クラス java.lang.String で型
を示すなら，Ljava/lang/String; のように指定する．14 行目の引数型 [Ljava/lang/String の [ は，続
く型の配列型を意味する．.method 行の最後には，返戻値の型を指定する．例えば，V は void を意味し，I
は int を意味する
5 行目の<init> は，コンストラクタを意味する．Java 仮想マシンコードのクラスには，必ずコンストラクタが必
要なので，コンストラクタを記述しなければ，このように自動生成される．コンストラクタのコードについては，
繁雑さを避けるために，これ以上説明しないことにする．
プログラム 81: Java 仮想マシンのコード Sample.j
1 .class synchronized Sample
2 .super java/lang/Object
3
4
5 .method <init>()V
6
7
.limit locals 1
.limit stack 1
8
9
aload_0
10
11
invokenonvirtual java/lang/Object.<init>()V
return
12 .end method
13
14 .method public static main([Ljava/lang/String;)V
15
.limit locals 3
16
17
.limit stack 2
18
19
iconst_3
istore_2
20
iconst_3
21
22
iload_2
imul
23
24
istore_1
getstatic java/lang/System/out Ljava/io/PrintStream;
25
26
iload_1
invokevirtual java/io/PrintStream.println(I)V
27
return
28 .end method
14 行目から始まる main メソッドが処理の中心である．まず，main に現れる命令や修飾子を説明しておく．
.limit locals（15 行目）：スタテックメソッドの場合，続く数字で，仮引数の数と局所変数の数の合計を指定
する．インスタンスメソッドの場合は，インスタンスの参照を渡す暗黙の引数が存在するので，さらに 1 を
加算する．
.limit stack（16 行目）：続く数字で，スタックの最大使用数を指定する．
iconst n（18，20 行目）：整数定数 n をスタックにプッシュする．
istore n（19，23 行目）：スタックをポップし，得られた整数値を，n 番目の局所変数に格納する．n はアドレ
スの役割をしている
iload n（21，25 行目）：n 番目の局所変数から整数値を読み出し，スタックにプッシュする
iadd（計算済み）：スタック [...,i1 ,i2 ] の i1 ,i2 を整数値としてポップし，i1 と i2 を加算した結果をスタックにプッ
シュする．上記の例では，1 + 2 を javac が計算して，3 に置き換えているので，iadd は現れない．これは，
定数の畳み込みというコード最適化の一種である
imul（22 行目）：スタック [...,i1 ,i2 ] の i1 ,i2 を整数値としてポップし，i1 と i2 を乗算した結果をスタックにプッ
シュする
getstatic svar type（22 行目）：svar で示されるスタティック変数の値を読み出し，スタックにプッシュする．
type は，svar の型である
invokevirtual sig （26 行目）：sig で指定したインスタンスメソッドを呼び出す．引数を 1 つ取るインスタン
スメソッドの呼び出しでは，次のようにスタックが変化する．
実行
スタックの状態：[..., obj,ap] −→ [..., rval]
ここで，obj は，インスタンスメソッドが所属するオブジェクト，ap は実引数，rval は返戻値である．
その他に，次のような四則演算命令がある．
bipush val ：8 ビットサイズの整数値 val を，スタックにプッシュする
sipush val ：16 ビットサイズの整数値 val を，スタックにプッシュする
isub ：スタック [...,i1 ,i2 ] の i1 ,i2 を整数値としてポップし，i1 から i2 を減算した結果をスタックにプッシュする
idiv ：スタック [...,i1 ,i2 ] の i1 ,i2 を整数値としてポップし，i1 から i2 を除算した結果をスタックにプッシュする
ineg ：スタックのトップを整数値としてポップし，正負を反転して，スタックにプッシュする
次に，アセンブラを用いて，Java 仮想マシンコードからクラスファイルを生成してみよう．ここでは，Java 仮
想マシンコード用アセンブラ jasmin を用いる．jasmin の使い方は，次のとおりである．
プログラム 82: アセンブラ jasmin の実行
> java -jar ~/jasmin-2.4/jasmin.jar Sample.j
Generated: Sample.class
> java Sample
9
練習 1 ：上記の仮想マシンコードが 9 の値を印字することを，実行をシミュレートして確認せよ．
練習 2 ：上記の仮想マシンコードを，jasmin によって Aout.class が生成されるように変更しなさい．
練習 3 ：iconst n 命令は，n が，-1（m1）∼5 の整数値である場合にしか使用できない．上記の仮想マシンコー
ドに現れる iconst n を，bipush n や sipush n で置き換えてみよ．
練習 3 ：畳み込まれた加算を記述せよ．
9.4
コード生成器
9.4.1
記号表
変数参照は，変数に対応するアドレスへのアクセスに変換されなければならない．四則演算言語では，“let 識
別子” によって変数が宣言されるので，ここで，各変数に唯一のアドレスを生成し対応付ける．アドレスは，変数
参照が出現するたびに取り出せなければならない．そこで，変数とアドレスの対応は，表で管理するようにする．
このような名前を管理する表を記号表と呼ぶ．四則演算言語の記号表は次のようになる．
プログラム 83: 記号表のストラクチャ Talbe
structure Table = struct
structure A = Ast
exception no declaration
val varSize = ref 0
val init = fn x => raise no declaration
fun update v offset env = fn x => if v = x
val stack = ref 0
then offset else env x
val maxStack = ref 0
fun setMaxSize () = if !stack > !maxStack then maxStack := !stack else ()
fun stackSize (A.Def ( , e1, e2)) =
(stackSize expr e1; stack := !stack-1; stackSize expr e2)
| stackSize (A.Expr e) = stackSize expr e
and stackSize expr (A.Num ) = (stack := (!stack)+1; setMaxSize())
| stackSize expr (A.Var ) = (stack := (!stack)+1; setMaxSize())
| stackSize expr (A.App ( , e)) = (stackSize expr e; stack:=(!stack)+1;
setMaxSize())
| stackSize expr (A.Pair (e1, e2))= (stackSize expr e1; stackSize expr e2;
stack := !stack-2)
end
記号表の本体は，init から update によって生成される探索関数である．この探索関数は，変数から対応する
アドレスを探索するとともに，関数自身に変数とアドレスの対を保持している（手続き抽象）．
関数 stackSize は，構文木を深さ優先で辿りながら，必要なスタックサイズ maxStack を計算する．このとき，
節点に訪問するたび，プッシュの数だけ，変数 stack を増加させ，ポップの数だけ stack を減少させる．
9.4.2
抽象構文木からアセンブリコードへの変換
抽象構文木から機械語への変換は，木の各節に対応したアセンブリコードのパターンをファイルに書き出す関
数 emit を実現することから始める．emit は，プログラムの開始に必要な前処理コードを生成した後，emit def
を呼出し，最後に後処理コードを生成する．前処理コードは，.class，.super の各宣言と，コンストラクタの定義，
および，メソッド main の宣言と，.limit locals，.limit stack の各宣言からなる．
各節を訪問して，その節に対応した操作を行うのは，emit def と emit expr である．これらの関数は，同じよ
うに節に対応した印字を行う print def や print expr と似た概観をもつ．
emit def で重要なのは，Def が表す変数宣言と代入の処理である．Def(s,e1,e2) における処理は次のように
なる．
1. 変数 s をアドレス値 1 に対応付けて新しい表 newEnv を生成する（update）．
2. e1 を元の表 env によって評価して，返って来た値を，変数にストアする命令を生成した後，newEnv によっ
て e2 を評価する．
プログラム 84: アセンブリコードパターンの生成 emit def， emit expr
structure A = Ast
structure T = Table
exception internal error
val OSTREAM = ref TextIO.stdOut
fun out str = TextIO.output(!OSTREAM,str)
fun emit def ast env = case ast of
A.Def(s,e1,e2) => let val addr = 1
val newEnv = T.update s addr env in
emit expr e1 env;
out ("\tistore "^Int.toString(newEnv s)^"\n");
emit expr e2 newEnv
end
| A.Expr e => emit expr e env
and emit expr ast env = case ast of
A.Var s => out ("\tiload " ^ Int.toString(env s)^ "\n")
| A.App(e1,e2) => (emit expr e2 env;
case e1 of
A.Var "+" => out ("\tiadd\n")
| A.Var "-" => out ("\tisub\n")
| A.Var "*" => out ("\timul\n")
| A.Var "/" => out ("\tidiv\n")
|
=> raise internal error)
| A.Pair(e1,e2) => (emit expr e1 (env); emit expr e2 (env))
| A.Num n => out ("\tsipush " ^ Int.toString(n) ^ "\n")
プログラム 85: 前処理コードと後処理コードを生成する関数 emit
fun emit ast localSize stackSize=
(out (".class synchronized Aout\n"
^".super java/lang/Object\n"
^".method <init>()V\n"
^"\t.limit locals 1\n"
^"\t.limit stack 1\n"
^"\taload_0\n"
^"\tinvokenonvirtual java/lang/Object.<init>()V\n"
^"\treturn\n"
^".end method\n\n"
^".method public static main([Ljava/lang/String;)V\n"
^"\t.limit locals "^(Int.toString localSize)^"\n"
^"\t.limit stack "^(Int.toString stackSize)^"\n");
out ("\tgetstatic java/lang/System/out Ljava/io/PrintStream;\n");
emit def ast T.init;
out ("\tinvokevirtual java/io/PrintStream.println(I)V\n"
^"\treturn\n"
^".end method\n"))
以上のコード生成アルゴリズムを，Lexer ストラクチャや Parser ストラクチャのようにストラクチャで囲むこ
とにしよう．
プログラム 86: コード生成器ストラクチャ Emitter
structure Emitter = struct
コード生成のプログラム
end
最後に，構文解析器とコード生成器を組み合わせよう．組合せは単に，emit の引数に parse の返値を渡すだけ
である．emit に渡す局所変数のサイズは，変数を 1 つしか宣言できないことから，main メソッドの引数と合わせ
て 2 を指定している．スタックのサイズは，関数 stackSize から得られた値に 1 を足していることに注意して欲
しい．これは，println のインスタンスをあらかじめプッシュしていたためである．
アセンブリコードの出力先は，tmp.j というファイルをオープンして指定している．生成した tmp.j は，jasmin
に渡すことによって，アセンブラを呼び出し，仮想マシンコードに変換することができる．
プログラム 87: 構文解析器とコード生成器を合成した関数 main
fun main () =
(Emitter.OSTREAM := TextIO.openOut "tmp.j";
let val ast = Parser.parse() in
Table.stackSize ast; Emitter.emit ast 2 (!Table.maxStack+1);
TextIO.closeOut (!Emitter.OSTREAM);
OS.Process.system "java -jar ~/jasmin-2.4/jasmin.jar tmp.j" end)

Download Report