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

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

一般的なコンパイラの雑談ということで、字句解析(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 ;
}

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

 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2012年3月27日 17:38に書いたブログ記事です。

ひとつ前のブログ記事は「PC管理ソフトのインストール」です。

次のブログ記事は「実験実習安全必携」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。