インタプリタ

コンパイラを記述するものは大体C言語であるが、C言語はPerlやPythonのようにStringのような形式は無い。 Cの文字列はあくまでCharの配列にすぎない。 コンパイラ/インタプリタを作る際はこの性質が以外と便利である。

構文解析

前回の問題でも触れているが、例えば 1+1 は 1 と + と 1 にそれぞれ分解される。 ここで1 はtermと呼ばれる最小ブロックであると考えると + は termを2つ取る関数であると言える。 つまり + ==> term + term と捉える事ができる。

では 10+10 はどうだろうか。我々は10 と + と 10 に分解されると考えてしまうがこれはCには出来ない。 最初に述べたとおり、Cには文字列が無い。その為 10 はあくまでも 1 と 0 がメモリ上に並んでいるだけである。 この問題を解決するには,例えば1 を示しているポインタをインクリメントし,次が0 であったら10と考えるなどの処理が必要となる。

簡単なインタプリタ

簡単なインタプリタの例題を見ていこう。この例題のコードの流れは次の通りである。

  • はじめに文字列をbufとして読み取る
  • それを大域変数ptrに代入するk
  • ptrに入っている文字を先頭から1文字ずつexpr,axpr,mexpr,termの順で読んでいく
  • 各prがついているものは演算を行うものである。
  • 読んでいるtermが何であるか(数値,変数,コメント)はtokenで処理をする
  • tokenからこのtermが何であるかが識別子last_token に入り、それによって分岐される
  • 例えば1+1 は 1はtermでありlast_token は'0' , + は + としてaexprで返される
/*
    Very Simple Calculator
    $Id$
 */

#include "s-compile.h"

int  variable[48];

static int  expr();
static int  aexpr();
static int  mexpr();
static int  term();


static int
expr()
{
    int d,assign;

    d = aexpr();
    assign = lvalue;
    while(last_token!=EOF) {
    switch(last_token) {
    case '>': 
        d = (d > aexpr()); 
        break;
    case '=': 
        if(assign>=0) {
        d = expr(); 
        variable[assign] = d;
        break;
        } else {
        error("Bad assignment");
        break;
        }
    case ')': 
        return d;
    default:
        error("Bad expression");
        return d;
    }
    }
    return d;
}

static int
aexpr()
{
    int d;

    d = mexpr();
    while(last_token!=EOF) {
    switch(last_token) {
    case '-': 
        d -= mexpr(); 
        break;
    case '+': 
        d += mexpr(); 
        break;
    default:
        return d;
    }
    }
    return d;
}

static int
mexpr()
{
    int d;

    d = term();
    while(last_token!=EOF) {
    switch(last_token) {
    case '*': 
        d *= term(); 
        break;
    case '/': 
        d /= term(); 
        break;
    default:
        return d;
    }
    }
    return d;
}

static int 
term()
{
    int d;

    lvalue= -1;
    token();
    if(last_token==EOF) {
    error("Term expected");
    }
    switch(last_token) {
    case '0':
    d = value;
    token();
    return d;
    case 'v':
    d = lvalue = value;
    token();
    return variable[d];
    case '(':
    d = expr();
    if(last_token != ')') {
        error("Unbalanced parenthsis");
    } 
    token(); 
    return d;
    default:
    token();
    error("Unknown term");
    return 0;
    }
}

int
main() 
{
    int d;
    char buf[BUFSIZ];

    while (fgets(buf,BUFSIZ,stdin)) {
    ptr = buf;
    d = expr();
    printf("%s = 0x%08x = %d\n",buf,d,d);
    fflush(stdout);
    }
    return 0;
}

/* end */

つまり文字列が何であるかを判定するのがトーカナイズ(s-token.c)であり、それによって処理を分岐させるのがs-calc.cである。

数値判断

例えば数値判断を見てみよう.

static int
term()
{
    int d;

    lvalue= -1;
    token();
    if(last_token==EOF) {
        error("Term expected");
    }
    switch(last_token) {
    case '0':
                d = value;
                token();
                return d;
    case 'v':
                d = lvalue = value;
                token();
                return variable[d];

上のコードでは '0' は数値の識別子である。 valueにはtokenの結果で数値そのものが入っている為、これをdとして返す。 変数サポートの場合variable という配列から d 番目の値を返している。 tokenを読んでいるが、これは数値の次にくるものが何であるかを判定するためである。

10進数

では実際にトーカナイズする所を見てみよう。


    if('0'<=c && c<='9') {     /* Decimal */
        d = c-'0';
        while((c= *ptr++)) {
            if('0'<=c && c<='9') {
                d = d*10 + (c - '0');
            } else {
                break;
            }
        }
        if (c!=0) ptr--;
        value = d;
        last_token = '0';
        return last_token;

上記は数値判断をしているところである。 ここでcにはchar型1文字,*ptr はcの次の実体が入っている。例えば 10 の場合　c は1で*ptrは0である。

if文で数値を文字として見ているのは、この時点ではcはchar型の文字が入っているためである。 その為、文字を人力でdに数値として起こしている。

変数と記号

    } else if ('a'<=c && c<='z') {    /* variable */
        value = c-'a';                /* return variable reference */
        last_token = 'v';
        return last_token;
    } else {
        last_token = c;
        return last_token;
        return c;
    }
}

変数の実装はs-calc.cが行っており,tokenはあくまでトークンとして切り分けるにすぎない。 ここでvalueには配列の添字を数字にするために文字列aから引いている。 つまり変数b を設定する場合,配列の添字として1 が使用される。 その他の記号はelseに吸収され,その文字がtokenとして返ってくる。

8/16進数

では8/16進数を実装してみよう。 8/16進数とも数値である為、識別子は'0'で良いと考えられる。つまり、s-tokenでこれは16進数であった数値であると解釈すれば良さそうである。

8進数

まずは8進数で考えてみよう。 8進数とは 011 とか　077 など先頭が0で以降が0~7までの数である。

先程の10進数の例を考えると次のように書ける。

    if ( c == '0' && '0' <=(*ptr) && (*ptr)<= '7' ){    /*  octal number  */
        d = 0;
        while((c= *ptr++)) {
            if ('0' <= c && c <= '7'){
                d =  d*8 + (c - '0');
            } else {
                break;
            }
        }
        value = d;
        last_token = '0';
        if (c!=0) ptr--;
        return last_token;
    }

ここでは最初に '0'が来るかどうか判定し,次の値が '0'~'7'であるかどうかを確認している。

これを満たしている場合、8進数が来ているから処理を行う。

実際に行う処理は、それまでの桁を8倍し、現在c に入っている値をintに直した後に加算している。

結果として値がdになり、それをvalueとして設定し、s-calc.cに戻している。

16進数

16進数はほぼ8進数と同じであると考えられる。

つまり'0x'の順で文字が並んでいると16進数となる

    if ( c == '0' && *ptr == 'x'){
        ptr++;      /*  this increment ptr == x -> ptr==1  */
        d = 0;
        while((c = *ptr++)){
            if ( ('0' <= c && c <= '9' )|| ('a' <= c && c <= 'f' )|| ('A' <= c && c <= 'F' )){
                d = d*16 + hex_to_int(c);
            } else {
                break;
            }
        }

        value = d;
        last_token = '0';
        if ( c!= 0) ptr--;
        return last_token;
    }

ここで重要なのは if文の次に ptr をインクリメントしているところである。 ptr には現在 0x の x が入っているが,xは16進数の判定のみしか使用されない。

そこでptrの値をインクリメントし、以降処理を書く必要がある。 若干情調になるため,ループ内での16進数判定は次のように関数化している。

int
hex_to_int(char c){
    c = tolower(c);

    if ( '0' <= c && c <= '9'){
        return c - '0';
    } else if ( 'a' <= c && c <= 'f'){
        return c - 'a' + 10;
    }

    return -1;
}

まぁこの辺は趣味

results matching ""

    No results matching ""