Super Technique 講座

ungetc ってどう使う?

stdio.h には、あまり使わない関数も多いが、特にこの ungetc(3) は、特別なテクニックと共に使われるものなので、知らないプログラマは絶対知らないが、使い方を知っているプログラマにとっては、非常に汎用的に使える関数(というかアイデア)なのである。筆者はインタプリタが得意なので、この ungetc(3) は必須アイテムの一つなのである。というわけで、ungetc(3) の使い方を解説しよう。

とはいえ、この ungetch.htm は結構気合いを入れて書いたにも関わらず、アクセスが少ない! 重要なテクニックなんだけど、一般認知が低いな! これがクヤシイので、ここにBNFのちゃんとした解説を入れることにする。前半もちゃんと読むのだぞ!


字句の先読み

ungetc(3) は文字列をトークンに分解するために使う。Java だと PushbackInputStream や PushbackReader クラスに相当するインターフェイスである。これは一旦読み込んだ文字をもう一度ストリームに戻す操作である。何でこんなものがあるのだろうか。

単純な式を分解することを考えてみよう。たとえば、次のような文字列があるとする。

13+4356+421
13  + 4356  + 421

一般に空白文字はいくらでも入れて良いとするのが、普通の式の文字列だろう。これを分解する関数は次のような雰囲気である。

#include <stdio.h>
#include <ctype.h>

char *parse( char *buff )
{
   int c;
   int at = 0;

   while( (c = getchar()) != EOF ) {
      if( isdigit( c ) ) {  /* 数値ならバッファに保存 */
         buff[at++] = c; 
      } else if( isspace( c ) ) {  /* 空白文字ならば */
         if( at == 0 ) {    /* バッファに数値がなければ読み飛ばし */
             continue;
          } else {          /* バッファに数値があるので、それを返す */
              buff[at] = '\0';
              return buff;  /* 空白文字は単なるターミネータ */
          }
      } else {              /* 数字でも空白文字でもない(演算子) */
         if( at == 0 ) {    /* バッファに数値がないので */
             buff[0] = c;
             buff[1] = '\0'; /* その演算子を返す */
         } else {            /* バッファに数値があるので、それを返したい */
             ungetc( c, stdin ); 
             buff[at] = '\0';  /* 演算子は後回しにして数値を返す */
         }
         return buff;
      }
   }
}


void main( )
{
    char buff[256];
    char *s;
    while( (s = parse( buff )) != NULL ) {
        printf( "read %s\n", s );
    }
}

つまり、数値が終りかどうかは、1文字先を読んでみないと判らない。1文字先が空白文字ならば、空白文字は数値の終りをマークする以外の機能がないので、バッファに貯めておいた数値を返せばよい。しかし、1文字先が空白文字ではなくて、意味のある文字(演算子)の場合には、とりあえず貯めておいた数値を返すのが先決で、読み込んだ演算子文字の処理は後回しにしたいのである。この要求に答えるのが ungetc(3) なのである。

つまり、ungetc(3) は一旦読んだ文字を読まなかったことにして、ストリームに返す。そして、次に getchar(3) で読み込んだときに、先程返された文字をもう一度読み直すのである。このロジックによって、数値のパースを合理的に書くことが出来るのである。このロジックを一般に「先読み」と呼ぶ。

この実装は簡単である。どうせ標準入出力はバッファリングを行っている。だから、getchar(3) で読み込めば、バッファサイズで読み込んだ内容の、現在位置の文字を返し、現在位置を進めているに過ぎない。この場合に getchar(3), ungetc(3) を模倣すれば大体次の通りである。

static char vbuff[256];  /* バッファ */
static int vp = 0;       /* 現在位置 */
static int size = 0;     /* バッファに読み込んでいる字数 */
static int save = EOF;   /* ungetch(3) された内容を保存 */

int my_getchar( void )   /* getchar(3) を模倣 */
{
    if( save != EOF ) {  /* save に ungetc(3) された内容がある */
        int ret = save;
        save = EOF;
        return ret;
    }
    if( vp == size ) {   /* 読み込んだ内容すべてを処理したら */
        if( fgets( vbuff, 255, stdin ) == NULL ) { /* 新たに読む */
            return EOF;
        }
        size = strlen( vbuff );
        vp = 0;
    }
    return vbuff[vp++];
}

int my_ungetc( int c )  /* ungetc(3) を模倣 */
{
    if( vp == 0 ) {
        save = c;   /* 無条件にこれだけでも同様に動作する */
    } else {
        vp--;
    }
}

バッファ内容が更新されていた時には、別個の変数が ungetc(3) された内容を保持する必要があるわけである。

単純な数式処理

さて、このように数値と演算子を読み込むロジックを構築したのだが、多少の式演算をしてみよう。式演算では数値と演算子を区別して返した方がやりやすいので、次の構造体 struct Item * を parse() は返すことにする。この例では最小限のケースで、演算子は「+」と「*」だけがあることにしよう。

struct Item {
    int kind;
    int v;
};

#define ITEM_ENDLINE -1
#define ITEM_NUMBER  0
#define ITEM_PLUS    1
#define ITEM_MUL     2

それに合わせて、parse() を変更する。実際には malloc(3) はする必要がないケースが多いが、ここではこれでやっておく(現実的なインタプリタなどではどうせガベージコレクタなどのお世話になる)。

struct Item *newItem()
{
    void *ret;
    ret = malloc( sizeof(struct Item) );
    if( ret == NULL ) {
        printf( "cannot malloc!\n" );
        exit( 1 );
    }
    return (struct Item *)ret;
}

struct Item *parse()
{
    int c;
    int val = 0;
    struct Item *ret;
    int at = 0;

    while( (c = getchar()) != EOF ) {
        if( isdigit( c ) ) {
            val = val * 10 + (c - '0'); 
            at++;
        } else if( isspace( c ) ) {
            if( at == 0 ) {
                if( c == '\n' ) {
                    ret = newItem();
                    ret->kind = ITEM_ENDLINE;
                    return ret;
                } else {
                    continue;
                }
            } else {
                if( c == '\n' ) {
                    ungetc( c, stdin );
                }
                ret = newItem();
                ret->kind = ITEM_NUMBER;
                ret->v = val;
                return ret;
            }
        } else {
            if( at == 0 ) {
                if( c == '+' ) {
                    ret = newItem();
                    ret->kind = ITEM_PLUS;
                } else if( c == '*' ) {
                    ret = newItem();
                    ret->kind = ITEM_MUL;
                } else if( c == '\n' ) {
                    return NULL;
                } else {
                    continue;
                }
                return ret;
            } else {
                ungetc( c, stdin );
                ret = newItem();
                ret->kind = ITEM_NUMBER;
                ret->v = val;
                return ret;
            }
        }
    }
    return NULL;
}

とりあえず、いわゆる「電卓方式」で計算ができるようにしよう。つまり、「*」の結合力が「+」よりも強く、優先するという一般的な式の規則ではなくて、登場順だけで演算をするというルール(1+2*3=9)である。このmain()関数は次の通り。

int main( )
{
    struct Item *val = NULL;
    struct Item *op  = NULL; 
    struct Item *s;

    while( (s = parse()) != NULL ) {
        switch( s->kind ) {
        case ITEM_ENDLINE:
            printf( "result=%d\n", val->v );
            op = NULL;
            val = NULL;
            break;
        case ITEM_NUMBER:
            if( val == NULL ) {
                val = s;
            } else if( op == NULL ) {
                printf( "disposed %d\n", val->v );
                val = s;
            } else if( op->kind == ITEM_PLUS ) {
                val->v += s->v;
                op = NULL;
            } else if( op->kind == ITEM_MUL ) {
                val->v *= s->v;
                op = NULL;
            } else {
                printf( "NO kind = %d, dispose %d\n", op->kind, val->v );
                val = s;
                op = NULL;
            }
            break;
        case ITEM_PLUS:
        case ITEM_MUL:
            op = s;
            break;
        default:
            printf( "cannot happen\n" );
            exit( 1 );
            break;
        }
    }
    return 0;
}

自然数式処理

しかし、一般に式演算は、自然演算ルールにより、「*」の結合強度は「+」よりも強く、優先すべきである。つまり、1+2*3=7 にならなくてはならない。これを処理するためにも、「先読み」が必要である。つまり、数値が現われた時に計算するのではなくて、数値(2)の次の演算子(*)が、未処理の演算子(+)よりも結合強度が強いかどうかを判定して、もし結合強度が強ければ一旦棚上げ(スタック!)しておき、後で計算する。しかし、結合強度が弱ければ即刻計算する、というやり方が必要になる。これは実は先程の「先読み」と同じ話なのである。

つまり、スタックに struct Item を積んで、計算式を処理する。この時、数値スタックと演算子スタックの2つのスタックがあるものとする。このやり方では、次のルールに従う。

  1. 数値は単純にスタックに積む。
  2. 読み込んだ演算子が、現在のスタックトップにある演算子よりも結合力が強ければ、スタックに積む。
  3. 読み込んだ演算子が、現在のスタックトップにある演算子と同じか結合力が弱ければ、スタックトップの演算子について演算をする。つまり、2つの数値オペランドを数値スタックからPOPし、演算子スタックからPOPした演算子によって計算した後、演算結果を数値スタックに積む。この処理をする前に、読み込んだ演算子は unget しておく。

1+2*3*4+5*6 の場合には次のように両方のスタックが変化していく。これを見てイメージを掴まれたい。unget された演算子を更にもう一度読み込んだ際には (演算子) で示している。

入力数値スタック演算子スタック処理
11数値を積む
+1+演算子スタックが空なので、読み込んだ演算子を積む
21 2+数値を積む。
*1 2 + *現在演算子スタックにある + より、新たな演算子 * の方が結合力が強いので、積む。
31 2 3+ *数値は積む。
*1 6+現在演算子スタックにある * と読み込んだ演算子 * は同じである。だから、読み込んだ演算子 * を押し戻し、2 * 3 を計算する。
(*)1 6+ *unget された * 演算子をもう一度読み込んで、現在演算子スタックにある + より、新たな演算子 * の方が結合力が強いので、積む。
41 6 4+ *数値は積む。
+1 24+現在演算子スタックにある * より読み込んだ演算子 + は結合力が弱い。だから、読み込んだ演算子 + を押し戻し、6 * 4 を計算する。
(+)25現在演算子スタックにある + と読み込んだ演算子 + は同じである。だから、読み込んだ演算子 + を押し戻し、1 + 24 を計算する。
(+)25+現在演算子スタックには演算子がなくなった。だから、ようやく読み込んだ演算子 + を積むことができる。
525 5+数値を積む
*25 5 + *現在演算子スタックにある + より、新たな演算子 * の方が結合力が強いので、積む。
625 5 6+ *数値を積む
改行25 30+改行を最弱の演算子と考えてやる。だから、読み込んだ改行を押し戻し、5 * 6 を計算する。
(改行)55押し戻された改行はやはり最弱の演算子なので、また押し戻し、25 + 30 を計算する。
(改行)更に押し戻された改行を読み込み直すが、もう演算子スタックは空なので改行を処理できる。数値スタックから結果をPOPして表示し、サイクルを終了する。

このやり方は、演算子の結合強度の定義にだけ依存している。だから、さらに別な結合強度を持った演算子が増えたとしても、充分対応が可能であることに注意されたい。では、これをこの「先読み」ロジックによって実装してみよう。だから、get_symbol() という先読み可能な(unget_symbol()によって「押し戻す」ことができる)関数を定義する。

struct Item *saved_symbol = NULL;

struct Item *get_symbol(void)
{
    if( save != NULL ) {
      struct Item *ret = saved_symbol;
      saved_symbol = NULL;
      return ret;
    }
    return parse();
}

void unget_symbol( struct Item *at )
{
    saved_symbol = at;
}

また、数値スタック、演算子スタックについては、次のような PUSH, POP 手続きがあることになる。(スタックの判らない人はスタックを見よ!)

#define STACKSIZE  3  /* 配列がいくつ必要かは後で検討する */
struct Stacks {
    struct Item *stack[STACKSIZE];
    int SP;
};

struct Stacks Values, Ops;

void push( struct Stacks *st, struct Item *at )
{
    if( st->SP < STACKSIZE ) {
        st->stack[st->SP++] = at;
    } else {
        printf( "stack overflow!\n" );
        exit( 1 );
    }
}

struct Item *pop( struct Stacks *st )
{
    if( st->SP > 0 ) {
       return st->stack[--st->SP];
    } else {
       printf( "stack underflow!\n" );
       exit( 1 );
    }
}

struct Item *peek( struct Stacks *st )
{
    if( st->SP > 0 ) {
       return st->stack[st->SP - 1];
    } else {
       printf( "stack underflow!\n" );
       exit( 1 );
    }
}

int isEmpty( struct Stacks *st ) {
    if( st->SP == 0 ) {
      return 1;
    }
    return 0;
}

void clear( struct Stacks *st ) {
    st->SP = 0;
}

ということは、それぞれの処理は次のように定義できる。

int main( )
{
    struct Item *s, *top, *op1, *op2;
    while( (s = get_symbol()) != NULL ) {
        if( s->kind == ITEM_NUMBER ) { /* 数値は PUSH */
            push( &Values, s );
        } else {
            if( isEmpty( &Ops ) ) {   /* 演算子スタックが空 */
                if( s->kind == ITEM_ENDLINE ) { /* の時しか改行は処理できない */
                    end_proc();           /* 結果の表示 */
                } else {
                    push( &Ops, s );  /* 他の演算子は PUSH */
                }
            } else {                      /* 演算子結合強度の比較が必要 */
                top = peek( &Ops );   
                if( s->kind > top->kind ) { /* 新たな演算子の方が強い */
                    push( &Ops, s );  /* 演算子を PUSH */
                } else {                  /* 新たな演算子の方が弱い */
                    unget_symbol( s );    /* 後回し! */
                    /* スタック分を計算する! */
                    top = pop( &Ops );
                    op1 = pop( &Values );
                    op2 = pop( &Values );
                    push( &Values, calc( top, op1, op2 ) );
                }
            }
        }
    }
    return 0;
}

大変単純なメインルーチンになる。しかし、これによってどんな結合強度でも対応できることに注意されたい。そして、サブルーチンとして calc() と end_proc() を使っているが、これは次の通り。

void end_proc( void )
{
    struct Item *result;
    if( isEmpty( &Values ) ) {  /* エラーチェック */
        printf( "数値スタックが空である!\n" );
    } else {
        result = pop( &Values ); /* 数値スタックから結果を得る */
        if( isEmpty( &Values ) ) { /* それで空になれば正常 */
            printf( "result=%d\n", result->v );
        } else {
            printf( "演算子が抜けてるんじゃない?\n" );
        }
    }
    clear( &Values );  /* スタックの初期化 */
    clear( &Ops );
}

struct Item *calc( struct Item *op, struct Item *v1, struct Item *v2 )
{
    if( v1->kind != ITEM_NUMBER || v2->kind != ITEM_NUMBER ) {
        printf( "数値スタックに数値以外が積まれている!\n" );
        exit( 1 );
    }
    if( op->kind == ITEM_PLUS ) {
        v1->v += v2->v;
    } else if( op->kind == ITEM_MUL ) {
        v1->v *= v2->v;
    } else {
        printf( "知らない演算子が演算子スタックに積まれているよ!\n", op->kind );
        exit( 1 );
    }
    return v1;
}

それぞれのスタックに積まれる演算子の数は有限になる。つまり、演算子スタックに積まれる要素の最大数は結合強度の種類数であり、数値スタックに積まれる最大数は演算子スタックに積まれる要素数+1になる(この場合は 2 + (2+1) = 5)。 だから、実際には malloc(3) で struct Item を確保しなくても良いことになり、この場合では6つの配列で struct Item を確保して、順繰りに使って行けばよいことを付言しておく。

また、これに演算子を増やして行けば、同一レベルの結合強度のものが出て来るので、適当に Level[] 配列などでシンボルに対応する結合強度を拾うようにすれば良いし、'(' ')' の処理でも、基本的にこれを一捻りするだけである。演算子を増やすのは読者の宿題としよう。

lex と yacc

このように先読みとスタックをうまく使えば、プログラミング言語レベルの構文解析も可能になるのである。実はこのテクニックは実質上 lex や yacc でやっているやり方の基礎になるものである。本格的にインタプリタやコンパイラを作成する時には、正規表現を使って字句を抽出する lex(flex)、BNF(バッカス=ナウア記法)を使って記述した「文法」から、それを処理するC言語プログラムを作成する yacc(bison) らがあり、可読性・メンテ可能性から見ても有利なために、こちらを使うのが普通である。しかし、このような便利なツールが行っていることの基礎は、今述べたような先読み+スタックの技なのである。

lex, yacc を使えばインタプリタ・コンパイラの作成は随分と楽になるし、何よりもソースの可読性が向上する。だから、インタプリタ・コンパイラの作成では lex, yacc を使うのが普通だが、さすがにこれの使い方はホームページで書く内容を越えている。良い成書「lex&yaccプログラミング」(Levine,Mason,Brown 邦訳:アスキー出版局)があるのでこれを読まれたい。

とはいえ、この ungetch.htm は結構気合いを入れて書いたにも関わらず、アクセスが少ない! 重要なテクニックなんだけど、一般認知が低いな! これがクヤシイので、ここにBNFのちゃんとした解説を入れることにする。前半もちゃんと読むのだぞ!

BNF(バッカス=ナウア記法)とは、堅く言えば「文脈自由文法」を記述する記法である。もちょっと平たい言い方をすれば、いわゆる「文法」を記述する記法であり、ちょっと気をつける点もあるが、これを守れば BNF から自動的にそれを処理するプログラムが生成できてしまう、というありがたいものである。

ちなみにバッカスさんは FORTRAN の作者の一人で、BNF を考えた人である。惜しいことに FORTRAN を作る前に BNF を考えつかなかったので、FORTRAN の文法はあんなにもダサいのだ。その BNF にヒントを得て作られたのが Algol60 で、Alogol60 ではしっかりとこのBNFで文法定義をしている。これをしたのがナウアさんというわけだ。まあ、この2人を記念して、BNFという名前になっているんだけどね。

ではどうやって文法を書くのだろう? とりあえず四則演算を例に取ってみよう。次のようなものが「演算式」であるのは当り前だ!

123
1 + 2
3 * 4 + 10
(1 + 3 + 4) * 11

じゃ、「演算式」ではないのはどういうものかな?

1 2 3
5 + * + 8
((((3

こいつらは「演算式」ではない。つまり「演算式」には「文法」があるのである。その文法は、一種の再帰によって記述できる。

  1. 数字は「式」である。
  2. 「数字 + 数字」も「式」である。
  3. しかし、「数字 + 数字 + 数字」も「式」であるが、これはすでに「数字 + 数字」が「式」なのだから、「「式」 + 数字」も「式」であると考えた方が楽だ。としてみれば、2. の考え方はまずくて、「「式」 + 「式」」を「式」と考えた方が良い。
  4. じゃ、「「式」* 「式」」「「式」- 「式」」「「式」 /「式」」も当然「式」だ。
  5. 同じように「( 「式」 )」も「式」だ。

こういう思考方でやっていけば、「演算式」はいくつかのルールで出来上がった「文法」として書くことができる。たとえば次のように書けばいい。

s :   -?[0-9]+   ルール1:これだけ正規表現風に書いてある
  |   s '+' s    ルール2
  |   s '*' s    ルール3
  |   s '-' s    ルール4
  |   s '/' s    ルール5
  |   '(' s ')'  ルール6
;

ここでは「s」を「式」の意味で使っているが、このような導入された記号を「非終端記号(このページではすべて小文字で表記)」と呼び、「-?[0-9]+」(正規表現で表した整数)や「'+'」のような演算子のような「終端記号(このページではすべて大文字で表記)」と分けて考える(BNFの中では同じように扱うが...)。つまり、「非末端記号」を導入することが、このBNFの技なのである。

ちなみにこれらの表記で使われるメタ記号は、本や著者などでまったくバラバラである。他の例はテキトーに類推して欲しい。特にコマンドラインなどの記述によく使われる「拡張BNF」というのがあるが、これは通常のBNFに加え次のようなメタ記号を使う。

( )
グループ化を示す。たとえば s : while (block|statement) など。
[ ]
省略可な部分(0回か1回出現)を示す。
{ }
0回以上の繰り返しを示す。

だから、時にコマンドラインがこの記法で書かれている場合がある。たとえば、

prog [-a|-b|-c] file {files}

この場合、コマンド prog は3つのオプション -a か -b か -c を取ることができ(この記法だとそのうちのどれかか、ないかのどっちか)、少なくとも1つのファイルを指定する、ということになる。ただし、実際のコマンドライン説明で書いてあるのは拡張BNFというよりも、もっとイイカゲンなものが多い...

話を戻そう。実際の式をこのルールに当てはめて、最後に「s」だけが残れば、それは「演算式」であると結論できるわけだ。やってみよう。

(1 + 3 + 4) * 11
→ (s + s + s) * s  ルール1で数字をすべてsに還元
→ (s + s) * s      ルール2で最初の「s + s」をsに還元
→ (s) * s          ルール2で「s + s」をsに還元
→ s * s            ルール6で「( s )」をsに還元
→ s                ルール3で「s * s」をsに還元。おめでとう!「s」だけだ!

で、この還元の処理の中で、副作用として計算値を返していくとか、構文木を作っていって後で構文木を評価する、ということをすると、電卓が出来てしまうわけだ。これを実現するキーとなるデータ構造は実はスタックだ。要するに文脈自由文法を受理する(要するに文法に一致しているかそうでないかを判定する)機械は「スタック付きオートマトンプッシュダウン・オートマトン とか略して PDAとかいろいろ呼ばれる...)」という機械で、これはその名の通り、有限状態機械に記憶装置としてスタックを装備したものなのである。このように BNFで文脈自由文法を定義すれば、それを受理する機械を作ることができるのである。

しかしここにはちょっとして問題がある。今「s + s + s」を「s + s」に還元したが、これは「(s + s) + s」なのか「s + (s + s)」なのか、今の定義では触れられておらず、どっちかに決めることができない。コンパイラの用語で言えば「左結合」なのか「右結合」なのか、決めることができないのだ。

要するにCで言えばこれ。「x = a + b + c;」は「x = a + (b + c);」であり、「x = (a + b) + c;」ではない(左結合)。しかし、「x = a = b;」は「x = (a = b);」であり、「(x = a) = b;」(代入できんぞ!)ではない(右結合)。「=」みたいに変態なものでなくても、演算子の中にも右結合の方が扱いやすいものがある。たとえば、「n乗」を表す演算子(COBOL&FORTRAN流では** とか BASIC流では ^ とか)を導入すると、「2^2^3」は「2^(2^3)==256」であって、「(2^2)^3==64」ではない(と考える人の方が多い...例外は COBOLER。なぜか COBOL の n 乗演算子 **左結合する。この事実を知ったときには筆者は天を仰いだ!)。

だから、一般の文脈自由文法は「曖昧」であり、同じ入力から別な構文木を生成する可能性があるのである。これは大変まずい。しかも、この文脈自由文法の「曖昧さ」は本質的なものであり、一般には同一の構文木を生成するまったく別なBNFがありえ、しかも結果として同じBNFを「同一である」と自動的に判定するアルゴリズムさえ存在しないのである。ここらへんが「有限状態機械」と違うところで、「有限状態機械」は NFA(非決定性オートマトン)で定義されていたとしても、それをアルゴリズムで唯一の DFA(決定性オートマトン)に変換でき、効率の良い機械を生成できるのだが、文脈自由文法にはこんな便利な性質はないのである。これは困った!

そこで取られた策が、文脈自由文法を制限する、という考え方である。つまり、特定のルールを導入して、これに合致した文法は「決定性文脈自由文法」となり、効率的にそれを受理する機械を構築できるようにしよう、というやり方である。このようなルールはあった。それが LR-LA(1) 文法である。これは文脈自由文法のサブクラスに相当することは言うまでもない。

これは LR文法(おおざっぱに言えば左結合優先でスキャンして処理する文法)で、先読み(Lead Ahead)が1つだけ出来る文法である。だから、次のような文法は文脈自由文法ではあるが、LR-LA(1) 文法ではない。

name :  boysname 'さんは' '男性'     「男ルール」と呼ぼう
     |  girlsname 'さんは' '女性' ;  「女ルール」と呼ぼう

boysname :  '雅夫' | '貴史' | '啓文' | '正美' などなど

girlsname : '雅子' | '寛子' | '孝子' | '正美' などなど

「正美」さんは男名前でも女名前でも使われるわけである。この時、上の文法はまずい。なぜなら、仮に「正美 さんは 男性」という入力があった時、「正美」という単語を受け取った時点で、先読みが1個許されているので、次の単語「さんは」を読むわけだ。しかし、この入力が「男ルール」で扱うべきものか、「女ルール」で扱うべきものか決めることができるためには、次の「男性」を読まなければ決定できないのである。つまり、先読みの個数によって、文脈自由文法ではあっても LR-LA(1) 文法にならないものがあるのである。勿論「正美」のように男名前でも女名前でもありうるものを排除したり、次のようにこの文法を変えればOKである。

name :  boysname 'くんは' '男性'     「男ルール」と呼ぼう
     |  girlsname 'さんは' '女性' ;  「女ルール」と呼ぼう

という具合に、ルールが意外に面倒であり、ちょっと複雑な文法を定義しようとすると、「シフト=還元衝突」とか「還元=還元衝突」といった専門用語で言うメッセージが出て叱られるのである。とはいえ、このような LR-LA(1) 文法で記述する限り、それを受理するスタック付きオートマトンを自動的に生成するアルゴリズムがあり、それを使って文法記述からそれを受理するパーサを生成するのが yacc というわけだ。

この yacc の超単純で有益な例を1つだけお見せしよう。

%{
#include <stdio.h>
#include <ctype.h>
/* C言語用のヘッダなんかが入るのさ! 
   つまり、yacc はこのプログラムをC言語のプログラムに変換するものだ*/
%}
/* 使う記号の宣言 */
%token DIGIT
/* 演算子優先順位の宣言。賢いだろ! */
%left '+' '-'
%left '*' '/'
%%
/* ここから文法記述 */
/* 要するに
シンボル :      文法    { それが一致したときのアクション }
         |      ..........
         ;
で一つ一つ文法を記述していく。最初はトップレベルの文法を書く。
*/
line    :       expr '\n'  { printf( "%d\n", $1 ); }
        ;

/* アクションの中では、登場シンボル順に $1 とかの記号が使え、左辺シンボルの値と
   して $$ が使われることになる。*/

expr    :       expr '+' expr   { $$ = $1 + $3; }
        |       expr '-' expr   { $$ = $1 - $3; }
        |       expr '*' expr   { $$ = $1 * $3; }
        |       expr '/' expr   { $$ = $1 / $3; }
        |       '(' expr ')'    { $$ = $2; }
        |       DIGIT           { $$ = $1; }
        ;
%%
/* 以降に補助的な関数を書いていく。*/
/* 変換されたソースは yylex() という関数を呼んで、入力シンボルを1つづつ取得していく。
   ホントは lex で生成したレクサが yylex() を作るのだが、今回は手作り。
   超手抜きであり、情けない。 */
int yylex( )
{
        int  c = getchar();
        if( isdigit(c) ) {
                yylval = c - '0';
                return DIGIT;
        }
        return c;
}

/* 補助的に関数が多少必要。何が必要かは yacc のバージョンに結構依存する */
/* とりあえず GNU bison 用で書いておく */
int yyerror( char *mes ) { printf( "%s\n", mes ); return 0;}
int main( ) { while(1) yyparse(); return 0; }

これは「% bison -d calc.y; gcc -o calc calc.tab.c」とでも言うようなコマンドラインを使えばコンパイルできる。とりあえずGNU版の bison(yacc) と gcc だが、標準 yacc などを使っている場合には、プログラムとコマンドラインがちょっと違うだろう。これだけで一応電卓(マガイ)なものが作れるのである。性能は極端に制限されていて恥ずかしい限りだが、これをマトモな電卓に直すのは大しては難しくない。しかし、yacc(とlex の連係プレーから)についてマトモに解説しようと思うと、超大変である。こればっかりは本(「lex&yaccプログラミング」(Levine,Mason,Brown 邦訳:アスキー出版局))を読みたまえ。これを読み終えた暁には(あと多少のプログラミング能力があれば)、簡単なインタプリタくらい朝飯前だ。



copyright by K.Sugiura, 1996-2006