先週は、簡単なインタプリタを作成した。その文法の一部を思いだそう。
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 (左再帰)と呼ばれる問題である。 まず、この問題を解決することから始めよう。
前の方法がまずいのは、なんの条件判断もせずに自分自身(aexpr())を呼び出して しまうからである。これでは、どんどん自分を呼び出してしまう。しかし、 実際には、先頭に来るのは、より下位の文法要素、この場合は mexpr() である。 従って、最初に呼び出すべきなのは、mexpr() であって、aexpr() ではない。 その後に、+ または - が来て、今度は同じ状況になる。これは、文法を 以下のように書き換えたことに相当する。
arithmetic : multiply arithmetic'
arithmetic' : '-' multiply arithmetic'
| '+' multiply arithmetic'
| '' ;
つまり最初の一つを特別扱いすれば良い。(問:この文法と、前の文法が
等価であることを示せ)
arithmetic' は末尾再帰と呼ばれる
もので、ループに置き換えることができる再帰呼び出しである。これは
正式な書き方とはいえないが、以下のような規則だともいえる。
arithmetic :
multiply
LOOP{ '-' multiply | '+' multiply }
これにより、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の ためには以下の指示ができれば良い。
emit_value(d) printf("\tLDD #%d\n",d);
emit_load(d) printf("\tLDD %d,Y\n",d*2);
emit_push(d) printf("\tPSHS D\n");
emit_calc(+) printf("\tADDD ,S++\n");
emit_store(assign) printf("\tSTD %d,Y\n",assign*2);
これを計算する代わりに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-09.c のようになる。(これらは、/usr/open/lecture/kono/compiler/examples の 下にある。他のCPU用のコード生成も書いてみたので参考にして欲しい。)
これは、構文木を下から上、右から左に沿って、何をすればいいかを 書いていくことに相当する。
しかし、このコンパイラ信じられないほど馬鹿である。1+1 の計算も、 まじめに実行時に行う。このような計算は実は、コンパイル時に おこなってしまって構わない。では、どこまでコンパイル時に計算できる のだろうか?
このような考え方は、部分評価(partial evaluation) と呼ばれる。これを、 プログラムからプログラムを計算するプログラム変換、 α(アルファ)を使って以下のように記述する。
(問:以下の二村射影を計算せよ
インタプリタとコンパイラは、このようにプログラム変換で結びつけられている。 部分計算を一般的に実現することは難しいが、PrologやLISPなどの言語では、 実現されている。また、特殊な場合の部分計算は容易である。Cでは、この 部分をマクロとしてプログラマに直接書かせるということになっている。 また、inline という形で部分計算を行うことを指示する場合もある。
このα自身も部分計算することが可能であり、 α(α(α,α),α) は、自分自身を 部分計算することにより、一般的な部分計算を表現している。(これは、 いったい何なのかを考えてみよう) 残念ながら、 αは、一般的に非常に複雑なプログラムである。何故なら、αは対象となる プログラム言語に関する知識をすべて持っているからである。
ここでは、少しだけ部分計算をおこなう努力をしてみよう。
このためには、どうしても、一旦、プログラムを表す構造を作る必要がある。 その構造を作る時、あるいは、作った後で解析して、 より良いコード生成を行う。この構造は、もちろん、構文木である。コンパイラに よって、単なる構文木ではなく、より複雑な構造を採用することもある。 気にすると複雑になりやすいので、一旦、疑似コードを生成して、その後に、 その最適化をおこなう方法もある。構文木自身も、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文のようなものは、
超巨大になることがあるので、中間木も巨大になってしまう。この
時に安易な木の扱いを行うと、非常に遅いコンパイラになってしまう
ことがある。