Compiler Construction Lecture 11/26
Menu Menuだいぶ休みが入ってしまいましたが... さらに、12/4 の授業は休講とします。
先週の復習
簡単なインタプリタを作成し、Tokenizer の作り方、Parser の動き、そして、Parse しながら計算する手法について勉強した。
左再帰の問題
先週は、簡単なインタプリタを作成した。その文法の一部を思いだそう。
arithmetic : multiply '-' arithmetic
| multiply '+' arithmetic
| multiply;
このような文法を、そのまま再帰呼び出しの形でCに簡単に直すことができた。しかし、このままでは、3-2-1 は、3-(2-1)と解釈されて、2
と計算されてしまう。やはり、ここでは、(3-2)-1 と自然に解釈して欲しい。このためには、
arithmetic : arithmetic '-' multiply
| arithmetic '+' multiply
| multiply;
という形の文法に直せば良いのだが、これを素直にCに落とすと、
int
aexpr()
{
int d;
d = aexpr(); /* aexpr をまず計算する!? */
switch(last_token) { /* 先読みした結果が */
case '+': /* * だったら */
d += mexpr(); /* その先はmexprだから、それを計算して */
return d; /* それを d にたして、それを返す */
...
}
}
となるのだが、これは無限ループになってしまう。
これはLeft recursion (左再帰)と呼ばれる問題である。まず、この問題を解決することから始めよう。
Left recursionの処理
前の方法がまずいのは、なんの条件判断もせずに自分自身(aexpr())を呼び出してしまうからである。これでは、どんどん自分を呼び出してしまう。しかし、実際には、先頭に来るのは、より下位の文法要素、この場合は mexpr() である。従って、最初に呼び出すべきなのは、mexpr() であって、aexpr() ではない。その後に、+ または - が来て、今度は同じ状況になる。これは、文法を以下のように書き換えたことに相当する。
arithmetic : multiply arithmetic'
arithmetic' : '-' multiply arithmetic'
| '+' multiply arithmetic'
| '' ;
つまり最初の一つを特別扱いすれば良い。(問:この文法と、前の文法が等価であることを示せ)arithmetic' は末尾再帰と呼ばれるもので、ループに置き換えることができる再帰呼び出しである。これは正式な書き方とはいえないが、以下のような規則だともいえる。
arithmetic :
multiply
( '-' multiply | '+' multiply )*
ここで*は、closure とか star とか呼ばれる繰り返しを表す記号である。これにより、Cのプログラムは、
int
aexpr()
{
int d;
d = mexpr(); /* mexpr をまず計算する */
while(last_token!=EOF) {
switch(last_token) { /* 先読みした結果が */
case '-': /* - だったら */
d -= mexpr(); /* 次のmexprを計算し */
break; /* d を持って、もう一度、-があるかどうか見る */
...
}
}
}
となる。これで良いわけだ。これは左再帰の除去と呼ばれる方法である。
拡張に付いて
Interpreter の拡張はやさしい。特に動いているものを手直しするのは簡単である。最近の言語では、実行時に新しい関数や、外部とのInterface を許すものもある。なるべく、全体の文法構造を変えないように拡張するのがこつであり、言語も拡張が容易なように設計するべきである。先週の最後で示したように、実行する代わりに、「なにを実行するのか」を出力すれば、Interpreter は Compiler になる。今の簡単なInterpreterのためには以下の指示ができれば良い。
- 数字Nを、手もと(Accumulator or Register)に持ってくる
- 変数Vを、registerに持ってくる
- registerの値をstackにしまう。
- スタックの上の値とregisterの値とで計算をおこなう。
- registerの値を変数に書き出す。
emit_value(d) printf("\tmovl $%d,%%eax\n",d);
emit_load(d) printf("\tmovl _variable+%d,%%eax\n",d*4);
emit_push(d) printf("\tpushl %%eax\n");
emit_calc(+) printf("\tpopl %%ebx\n"); printf("\taddl %%ebx,%%eax\n");
emit_store(assign) printf("\tmovl %%eax,_variable+%d\n",assign*4);
これを計算する代わりにInterpreterに埋め込む。この場合、返す値は必要なくなる。ここで計算する必要はないのだから。例えば、
void
aexpr()
{
emit_comment();
mexpr();
while(last_token!=EOF) {
switch(last_token) {
case '-':
emit_push();
mexpr();
emit_calc(O_SUB);
break;
case '+':
emit_push();
mexpr();
emit_calc(O_ADD);
break;
default:
return;
}
}
return;
}
となる。ここで O_SUB, O_ADD は適当な定数であり、emit_calc は、その定数に対応する計算のためのコードを生成する。
より詳しく書くと、全体のプログラムは、 s-compile.c s-code-intel.c のようになる。(これらは、/usr/open/lecture/kono/compiler/examples の下にある。他のCPU用のコード生成も書いてみたので参考にして欲しい。)
これは、構文木を下から上、右から左に沿って、何をすればいいかを書いていくことに相当する。
部分評価としてのコンパイラ
しかし、このコンパイラ信じられないほど馬鹿である。1+1 の計算も、まじめに実行時に行う。このような計算は実は、コンパイル時におこなってしまって構わない。では、どこまでコンパイル時に計算できるのだろうか?このような考え方は、部分評価(partial evaluation) と呼ばれる。これを、プログラムからプログラムを計算するプログラム変換、α(アルファ)を使って以下のように記述する。
P'(Y)(X) = α(P(X,Y),X) P(X,Y)のうち、Xの値を定数として可能な部分を先に計算する。αはプログラムと入力変数の指定の2つの引き数を持つ。αは、Pと入力変数の値を受け取り、プログラムP'を出力する。P'は、Xの値を指定すると、それに対応するプログラムを返すプログラムである。P'を、入力の一部を前もって計算するので、部分計算と呼ぶ。
P''(Y) = P'(Y)(5) = α(P(X,Y),X)(5)とすると、X=5を仮定して計算を進めたプログラムを意味する。このαを二村射影(Futamura projection)と呼んでいる。例えば、i(P)(X)で、入力Xを持つプログラムP(X)をインタプリタiが実行することを表すことにしよう。ここでPは、Xを入力として持つ任意のプログラムを表す変数である。
これに、部分計算αを使って、
α(i(P),P) 入力X以外の部分Pを前もって実行する。とする。c(X)(p)は、pの字句解析やら構文解析やらの部分を前もって計算したプログラムである。これをコンパイルと考えることもできる。つまりコンパイラc(P)は、
c = α(i(P),P)となる。また、
y(P) = α(I(P),I)は、コンパイラコンパイラを表す。あるインタプリタiが与えられると、y(P)(i) は、Pをコンパイルするコンパイラ c(P) = α(i(P),P)(P) を返す。
問1
以下の二村射影を計算せよ- α(X*Y-X,Y)(5)
- α(for(d=0,i=0;i<X;i++){d += Y;},X)(20)
- α(for(d=0,i=0;i<X;i++){d += Y;},Y)(20)
インタプリタとコンパイラは、このようにプログラム変換で結びつけられている。部分計算を一般的に実現することは難しいが、PrologやLISPなどの言語では、実現されている。また、特殊な場合の部分計算は容易である。Cでは、この部分をマクロとしてプログラマに直接書かせるということになっている。また、inline という形で部分計算を行うことを指示する場合もある。
残念ながら、αは、一般的に非常に複雑なプログラムである。何故なら、αは対象となるプログラム言語に関する知識をすべて持っているからである。
さらに良いコードを出すためには
ここでは、少しだけ部分計算をおこなう努力をしてみよう。- わかっている結果の計算は先に行う
- 計算を順序を変える
- スタックでなくレジスタに割り付ける
- 同じ式が出てきたら、それを2度計算するようなことはしない
このためには、どうしても、一旦、プログラムを表す構造を作る必要がある。その構造を作る時、あるいは、作った後で解析して、より良いコード生成を行う。この構造は、もちろん、構文木である。コンパイラによって、単なる構文木ではなく、より複雑な構造を採用することもある。気にすると複雑になりやすいので、一旦、疑似コードを生成して、その後に、その最適化をおこなう方法もある。構文木自身も、post fix code (後置コード)と呼ばれる疑似コードとみなすこともできる。
中間木の生成
木を生成するのは、計算するのとほとんど同じで、下位の構文要素の木を下位の構文解析の関数から取りだし、上位に新しい木のノードをつけ加えて送れば良い。木のノードは例えば、
typedef struct node {
struct node *left;
struct node *right;
int type;
int value;
} node;
などのように表すことができる。これを生成するには、
node *
new_node(type,value,left,right)
int type;
int value;
node *left;
node *right;
{
node *d;
d = (node *)malloc(sizeof(node));
d->type = type;
d->value = value;
d->left = left;
d->right = right;
return d;
}
などとすれば良い。ここでtypeとvalueは、字句解析が返した値をそのまま使う。例えば、aexpr では、以下のように木を生成する。
node *
aexpr()
{
node *d;
d = mexpr();
while(last_token!=EOF) {
switch(last_token) {
case '-':
d = new_node('-',0,d,mexpr());
break;
case '+':
d = new_node('+',0,d,mexpr());
break;
default:
return d;
}
}
}
この時、new_node()は、mexpr()が二つ呼ばれてから呼ばれることに注意しよう。インタプリタと違ってdは、値ではなく木である。
new_node() では、mexpr()の値が分かった段階で呼ばれるのだから、もし、計算可能ならば、その場で計算をおこなうことが望ましい。
node *
new_node(type,value,left,right)
int type;
int value;
node *left;
node *right;
{
node *d;
if ((left && left-> type =='0') &&
(right && right-> type =='0')) {
switch(type) {
case '>':
right->value = (left->value > right->value);
free(left); return right;
break;
case '+':
right->value = left->value + right->value;
free(left); return right;
break;
...
}
}
d = (node *)malloc(sizeof(node));
d->type = type;
d->value = value;
d->left = left;
d->right = right;
return d;
}
などとすれば良い。 s-tree-compile.c
しかし、これで十分だろうか?
実際には、式の計算順序は、+, * などによって変更することができる。この変更によって定数として計算できる範囲が広がることがある。これは、定数を木の葉の方に移動させることによって実現することができる。あるいは、木を使って、共通の式を2度計算しているかどうかを調べることができる。(問:このようなアルゴリズムを考察してみよ)
実際のコンパイラでは、浮動小数点(floating point)と整数(integer)が混在することもあり、安易に計算順序を変更すると、かえって浮動小数演算が増えたり、誤差が大きくなったりすることがある。気を付けて計算する必要がある。
中間木からのコード生成
一旦、中間木ができてしまえば、コード生成は容易である。また、引き算の場合の引き数の順序の制御も楽になる。
code_generate(d)
node *d;
{
int assign;
switch(d->type) {
case '0':
emit_value(d->value);
return;
case 'v':
emit_load(d->value);
return;
....
default: /* calculation */
code_generate(d->right);
emit_push();
code_generate(d->left);
switch(d->type) {
case '+': emit_calc(O_ADD); break;
case '-': emit_calc(O_SUB_R); break;
case '/': emit_calc(O_DIV_R); break;
case '*': emit_calc(O_MUL); break;
default:
error("Internal Error, unknown opecode");
}
return;
}
}
となる。中間木を順序よくたどりながらコードを生成する。ただし、この方法では再帰呼び出しが多用されるので、それに対する工夫が必要となる場合もある。
実際のコンパイラでは、中間木は式だけなくて、手続き内のすべての文に対して生成することが多い。この時、case文のようなものは、超巨大になることがあるので、中間木も巨大になってしまう。この時に安易な木の扱いを行うと、非常に遅いコンパイラになってしまうことがある。
おまけ Intel x86の命令
宿題
上の構文木の生成では、malloc/free を繰り返している。これは、一般的には効率が悪い方法とされている。前もって、いくつかまとめてnodeをmallocし、それを再利用する方法を考案し、実装せよ。実際には、式の計算順序は、+, * などでは変更することができる。この変更によって定数として計算できる範囲が広がることがある。これは、定数を木の葉の方に移動させることによって実現することができる。あるいは、木を使って、共通の式を2度計算しているかどうかを調べることができる。このようなアルゴリズムを考察し、例題のコンパイラを変更して実装せよ。
宿題
Subject: Report on Compiler consturction Lecture 11/26
というSubjectのメールにして、kono@ie.u-ryukyu.ac.jp まで送ること。また授業を受けなかったものは、課題を、
Subject: Practice on Compiler consturction Lecture 11/26
というサブジェクトで送ること。
12/4 の授業は休講とします。