シンプルな再帰下降のサンプル

+-*と数字1文字だけを受け付ける再帰下降パーサ

再帰下降は計算機業界のロンダートからの後方宙返り。
プログラムを書く人は知っていて決して損はしません。

再帰下降はオペレータの優先順位をどこかにデータで持っているのではなくて、より優先順位の高いオペレータを処理する関数を呼び出す親子関係で、優先順位の高い・低いを表現します。

再帰下降で検索すると立派なパーサはいっぱい出てくるけど、結局どういう事か良くわからないで終わりそうです。ここはひとつ、シンプルに + - * の3つのオペレータと、数字1文字だけを受け付けるパーサを書いてみましょう。
+-に対応するのは、優先順位の同じオペレータの処理の例として、それと * に対応するのは優先順位の高いオペレータをどう処理するかを示すためです。2桁以上の数字の対応は字句解析の範囲なので、1桁で充分でしょう。
あと、せっかくですから、結果を計算するためにスタックを用意します。
短いソースなので、読み解くのは難しくないと思います。

この例ではexpr()は一度しか呼ばれませんが、優先順位を指定する()を実装したら、括弧のなかで再帰的にexpr()を呼ぶようになるでしょう。
再帰は無いので、ただの下降パーサですが、優先順位をどう処理しているのか、感じはつかめると思います。

t1.c

/*
再帰下降サンプル
cc -o t1 t1.c
*/

#include <stdio.h>

char* text="2-3*4+5*6" ;
char* ptr ;
char token ;

//  計算結果を積むスタック
int stack[32] ;
int sp=0 ;

void push(int value){
    stack[sp]=value ;
    sp++ ;
}

int pop(void){
    sp-- ;
    return(stack[sp]) ;
}


void get_token(void){
    token=*ptr ;
    if(*ptr!=0){
        ptr++ ;
    }
}


//  数値
void digit(void){
    get_token() ;
    if(token>='0' && token<='9'){
        push(token-'0') ;
        printf("number(%d)\n", token-'0') ;
        get_token() ;
    }
}

//  掛け算   
void mul(void){
    digit() ;
    while(1){
        if(token=='*'){
            digit() ;
            printf("mul\n") ;
            push(pop() * pop()) ;
        }
        else{
            break ;
        }
    }
}

//  足し算と引き算
void add(void){
    mul() ;
    while(1){
        if(token=='+'){
            mul() ;
            printf("plus\n") ;
            push(pop() + pop()) ;
        }
        else if(token=='-'){
            mul() ;
            printf("minus\n") ;
            int top=pop() ;
            push(pop() - top) ;
        }
        else{
            break ;
        }
    }
}

//  式の評価
void expr(void){
    while(*ptr!=0){
        add() ;
    }
}

int main(void){
    ptr=text ;
    expr() ;

    printf("answer=%d\n", pop()) ;

    return 0 ;
}

実行結果

$ ./t1
number(2)
number(3)
number(4)
mul
minus
number(5)
number(6)
mul
plus
answer=20

---

()に対応したバージョンの シンプルな再帰下降のサンプル(2) を載せました。