再帰下降パーサのサンプルコード

春休みだというのに、真面目に学校に来ている学生さんから、 数式のグラフ化アプリを作っている。 数式の処理をどうすればいいのか？ との質問で、再帰下読みでプログラムを書くのが定番ということで、 説明をする。

一般的なコンパイラの雑談ということで、字句解析(lex / flex) , 構文解析(bison / yacc) でコード生成といった話もしておく。

追記：『再帰下読み』って説明＆記事を書いたけど、 正しくは『再帰下降パーサ』みたいだな。

再帰下降パーサ・サンプル

授業でもやっていない再帰下読みの説明でもあり、 簡単なサンプルコードを示したいけど、Webで探しても全体的に大きなプログラムばかりで、 再帰関数をどう記述していくか解かりにくい。 ということで、+,-,*,/と数字1桁という条件で、字句解析無しのサンプルコードを書いてみた。

// 再帰下読みの基本の一番短いサンプル
//
//   字句解析は面倒なので、
//   演算子は1文字のみ、定数は数字1桁だけとする。

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

// 括弧の無い +,-,*,/ だけの式の処理
//
//   今回は以下の構文だけとする。
//   以下のような文法の書き方をバッカス記法(BNF)と言う。
//
// exp_PLUS_MINUS ::= exp_MUL_DIV '+' exp_PLUS_MINUS
//                  | exp_MUL_DIV '-' exp_PLUS_MINUS
//                  | exp_MUL_DIV
//                  ;
// exp_MUL_DIV    ::= DIGIT '*' exp_MUL_DIV
//                  | DIGIT '/' exp_MUL_DIV
//                  | DIGIT
//                  ;
// DIGIT          ::= [0-9] ;

int exp_PLUS_MINUS( char* , char** ) ;
int exp_MUL_DIV( char* , char** ) ;

// PLUS,MINUSだけの式
//   構文解析関数の引数
//   pc:   解析する文字列の先頭
//   endp: 解析が終わった場所
int exp_PLUS_MINUS( char* pc , char** endp ) {
   int left = exp_MUL_DIV( pc , endp ) ;

   if ( **endp == '+' ) {
     int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
     return left + right ;
   } else if ( **endp == '-' ) {
      int right = exp_PLUS_MINUS( *endp + 1 , endp ) ;
      return left - right ;
   } else {
      return exp_MUL_DIV( pc , endp ) ;
   }
}

// MUL,DIVだけの式
//   DIGITに相当する構文木の処理は、組み込んでしまう。
int exp_MUL_DIV( char* pc , char** endp ) {
   if ( isdigit( *pc ) ) {
      int left = *pc - '0' ;
      *endp = pc + 1 ;
      if ( **endp == '*' ) {
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left * right ;
      } else if ( **endp == '/' ) {
         int right = exp_MUL_DIV( *endp + 1 , endp ) ;
         return left / right ;
      }
      return left ;
   } else {
      printf( "Error\n" ) ;
      return 0 ;
   }
}

// 課題(1): () を含む処理にしたかったら、
//          BNF の構文木は、どう直すべきか？
// 課題(2): () を含む処理、空白を無視する処理、
//          定数式が複数桁を使える処理。

int main() {
   char* e = NULL ;
   printf( "%d\n" , exp_PLUS_MINUS( "1+2*3" , &e ) ) ;
   printf( "%d\n" , exp_PLUS_MINUS( "1*2+3" , &e ) ) ;
   return 0 ;
}

んで、このプログラムを読んだら、「このプログラムでは演算子は、右結合？左結合？」 と聞いてみるのが、理解度把握の定番ネタ。