まず、大ざっぱなインタプリタの構造を見てみよう。
コンパイラは実行の代わりにcode genration (コード生成)をおこなう。
インタプリタでも最初の方法では、
例えば、loop (繰り返し)とかがあっても、その度
ごとにtokenize, parse をおこなう必要がある。これはうれしくな
い。そこで、一旦結果をintermediate code (中間コード)に落とす
ことも良く行われている。
実際のコンパイラは、より複雑な構造をしている。
とりあえず、簡単なインタプリタを作って見よう。簡単な四則演算(+,-,*,/,>) そして、一文字の変数(variable)への代入(assignemt)と参照(reference) だけを持つとする。例えば、以下のような式を計算できる。
まず、単語の切り分けをおこなう。 このルールは簡単で、
Tokenizer は、通常、そのtokenの型(type)と値(value)を返す。 プログラムは、 token.c このような感じになる。
実際には、適当な状態遷移(state transition)を作ってやれば良い。より 複雑な例は、また、あとで見ることにしよう。
このプログラムでは、token()を呼びだすことにより以下ようにtypeとvalue が返る。
例えば、 (2+1030/a)-2 という式は以下のように分解される。
式の構造を考えて見れば、構文解析も簡単である。式はいくつかの
tokenのまとまりが、入れ子になった構造をしている。
この入れ子構造は、式を考えた時に実はruleとして既に頭の中にできている ものである。これらのruleは、grammer rule (文法規則)と呼ばれる。grammer を表すのに、ここでは以下のような記号を使う。
expression : arithmetic '=' expression
| arithmetic '>' expression
| arithmetic;
arithmetic : multiply '-' arithmetic
| multiply '+' arithmetic
| multiply;
multiply : term '*' multiply
| term '/' multiply;
| term;
term : VARIABLE | VALUE
| '(' expression ')';
: が入れ子構造、| が選択、; が一つのruleの終わりを表す。
例えば、multiplyは、3*4 のようなものを表す。
parser は、このルールにだいたい対応したものを作れば良い。勝手な文法 を作っても、このようなもので表されるならば、必ず、プログラムで構文解析 できることはわかっている。(このような文法はCFG context free grammar と呼ばれている) しかし、効率的に構文解析できるとは限らない。また、このようにして 記述された文法には曖昧さがあることもわかっている。つまり、一つの 文を複数の方法で解釈できることもある。 例えば、 この部分を手助してくれるcompiler compilerとしてyaccというのがUnixに ある。しかし、yacc は記述された文法をすべてプログラムに変換してくれる わけではない。また、yacc は曖昧な部分は指摘するが、勝手に解釈して しまう。
ここでは、 手軽で、効率も良い構文解析である、Recursive Descent (再帰下降法) というのを用いる。これは、構文規則を、再帰呼び出しをおこなう 関数に対応させる。呼びだされる規則が、その場で決まるように文法を 作れば非常に効率の良い構文解析手法となる。一般的にいって、ほとんどの 文法は、同等な決定的な文法に変換できる。しかし、Recursive Descentでは 解析できないCFGの 文法を考えることもできる。そのような文法も、 文法規則の選択のやり直しを行うことにより構文解析することができる。 しかし、それは文法を複雑にし、構文解析に必要な表や領域を拡大し、 構文解析の手間も増やしてしまう。
Recursive Descent は、式の評価に向いている。何故なら再帰呼び 出しした関数が返す値を、そのまま式の値とすれば良いからである。 常に、tokenは、一つ先読みすることにする。(このように一つ先読 みを行うRecursive Descentで解析される文法をLL(1)と呼んでいる) するとtermの部分は以下のようにすれば良い。
int
term ()
{
int d;
token(); /* token を一つ読む */
switch(last_token) {
case '0': /* 数値だったら */
d = value; /* 値は value に入っている */
token(); /* token を 一つ先読みして */
return d; /* その数値を返す。value は破壊される */
....
}
}
このtermを使ってmultiplyは、
int
mexpr()
{
int d;
d = term(); /* term をまず計算する */
switch(last_token) { /* 先読みした結果が */
case '*': /* * だったら */
d *= mexpr(); /* その先はmexprだから、それを計算して */
return d; /* それを d に掛けて、それを返す */
...
}
}
とすれば良い。文法規則とRecursive descentをおこなう手続きの対応が良くわかる。
ここで、mexprをすぐに再帰呼び出ししているが、mexpr()はすぐにterm()を
呼びだすことを考えると、mexpr()の呼び出しを一つ減らして、その代わりに
while文を増やすことでも同じことが実現できる。この方が関数呼び出しが
入らない分だけ効率が良くなる。これは、プログラム変換と呼ばれる手法の
一つである。
int
mexpr()
{
int d;
d = term(); /* term をまず計算する */
while(last_token!=EOF) {
switch(last_token) { /* 先読みした結果が */
case '*': /* * だったら */
d *= term(); /* どうせtermが呼ばれるので、それを呼びだす */
break; /* d を持って、もう一度、*があるかどうか見る */
...
}
}
}
全体のプログラムは、 s-calc.c のようになる。
s-input.txt に入力が用意してあるので、
% s-calc < s-input.txt | moreのように実行して見よう。
この方法での実行では、変数dが特殊な役割を果たしている。この変数は、 再帰呼び出しの途中での中間結果を保持していることになる。例えば、 a=2として、(2+1030/a)-2 を考えて見よう。再帰呼び出しの数だけ、 dが存在する。
d d d d d d d d
expr() ?
| aexpr() ? ?
| | mexpr() ? ? ?
( | | | term() ? ? ? ?
| | | | expr() ? ? ? ? ?
| | | | | aexpr() ? ? ? ? ? ?
| | | | | | mexpr() ? ? ? ? ? ? ?
2 | | | | | | | term() ? ? ? ? ? ? ? 2
| | | | | | | ? ? ? ? ? ? 2
+ | | | | | | aexpr() ? ? ? ? ? 2 ?
| | | | | | | mexpr() ? ? ? ? ? 2 ? ?
1030 | | | | | | | | term() ? ? ? ? ? 2 ? ? 1030
| | | | | | | | | ? ? ? ? ? 2 ? 1030
/ | | | | | | | | mexpr() ? ? ? ? ? 2 1030 ?
a | | | | | | | | | term() ? ? ? ? ? 2 1030 2
| | | | | | | | | ? ? ? ? ? 2 515
| | | | | | | | ? ? ? ? ? 517
| | | | | | | ? ? ? ? 517
| | | | | | ? ? ? 517
| | | | | ? ? 517
| | | | ? 517
)- | | aexpr() ? 517 ?
| | | mexpr() ? 517 ? ?
2 | | | | term() ? 517 ? ? 2
| | | | ? 517 ? 2
| | | ? 517 2
| | ? 515
| 515
縦棒は手続きの寿命を表す。?は、まだ値が決まっていないdである。
手続きが呼び出されるとdが一つ増えて、? が延びる。手続きが
終わると、dの値が決まり、dの列が一つ短くなる。
? を省略すれば、木をたどりながら計算をする時に「とっておく必要のある 値」がなにかがはっきりわかる。これは実際 stack をとっておく場所に 使っている。Recursive call(再帰呼び出し)自身がstackを使って実現 されているので、これはある意味では自明なことである。
(
2 2
+ 2
1030 2 1030
/ 2 1030
a 2 1030 2 =a
2 515 =1030/2
)- 517 =515+2
2 517 2
515 =517-2
これがinterpreterの行っていることの本質である。
これを手順で示すと、
(
2 2をしまう 2
+ 2
1030 1030をしまう 2 1030
/ 2 1030
a aをしまう 2 1030 2 =a
1030/2を計算 2 515 =1030/2
)- 515+2を計算 517 =515+2
2 2をしまう 517 2
517-2を計算 515 =517-2
となる。計算する所では、stackの先頭と次の値を計算している
ことの注意しよう。ここまで分解すると、そのままmachine code(機械語)
に落とせそうである。interpreterは、これを直接に実行してしまうが、
その代わりに「こうしろ」という命令を出力すれば、compiler を
作れることになる。
実際、 6809の命令 を使えば、
** (
LDD #2 2をload
PSHS D それをしまう
** 2+
LDD #1030 1030 をload
PSHS D それをしまう
** 1030/
LDD 0,Y a を呼びだす
LDX ,S++ stack から取り出したものをXに
EXG D,X 割り算の仕様に合わせてD,Xを交換
LBSR _DIVIDE D = D/X
ADDD ,S++ 今の値と、stackの先頭を足す。stackは一つ減る
PSHS D それをしまう
** a)-
LDD #2 2をload
SUBD ,S++ 今の値と、stackの先頭から引く
NEGA 引き算の順序が違うので負の数をとっている
NEGB
SBCA #0 これで負の数がとれた
LBSR print
となる。
以下の式を木に変換して見よ。さらに、これを計算する 6809の命令に落として見よ。
s-calc.c の若干の改良を試みる。あとでコンパイラに書き換えることを 前提にいくつかの機能をつけ加えて見よう。
来週までに、 実行結果と、変更した主要な部分をメールにして、 Compiler Construction Lecture 11/9 のSubjectを付けて kono@ie.u-ryukyu.ac.jp までメールすること。