ホーム » スタッフ » 斉藤徹 » 実験(斉藤) » コンパイラの技術と関数電卓プログラム(1-2)

コンパイラの技術と関数電卓プログラム(1-2)

投稿者: in 実験(斉藤), 斉藤徹 投稿日:

前回の実験資料では、再帰下降パーサについて説明し、サンプルプログラムを示した。

演算子の左結合・右結合

ここで、プログラムの実際の動きについて考えてみる。前回の乗除式の BNF 記法による定義は以下のようであった。

exp_乗徐式 ::= DIGIT '*' exp_乗徐式
            | DIGIT '/' exp_乗徐式
            | DIGIT
            ;

このBNFによる文法において、1*2*3 を考えると、以下のように解析がすすむ。
しかし、これでは　1*(2*3) であり、右結合にて処理が行われたことになる。

   exp_乗徐式
　　／｜＼
DIGIT｜ exp_乗徐式
 ｜  ｜   ／｜＼   
 ｜  ｜DIGIT｜ exp_乗徐式
 ｜  ｜  ｜ ｜ ｜
 ｜  ｜  ｜ ｜ DIGIT
 ｜  ｜  ｜ ｜ ｜
  １  ＊  ２  ＊  ３

左結合とするには

これをC言語で一般的な、(1*2)*3 といった左結合の処理になるように、BNF 記法の文法を下記のように書き換えるかもしれない。

exp_乗徐式 ::= exp_乗徐式 '*' DIGIT
            | exp_乗徐式 '/' DIGIT
            | DIGIT
            ;

しかし、このBNF記法をそのまま下記のような再帰に置き換えると、再帰が無限に続き異常終了してしまう。

int exp_MUL_DIV( ... ) {
   int left = exp_MUL_DIV( ... ) ;
   if ( **endp == '*' ) {
      (*endp)++ ;
      if ( isdigit( **endp ) ) {
         int right = **endp - '0' ;
         (*endp)++ ;
         return left + right ;
      }
   } else ...
      :
}

左結合のプログラムにする場合は、BNF記法の処理を杓子定規に再帰プログラムで記述する必要はない。

空白除去

プログラム中の空白を無視するのであれば、以下のような補助関数を作っておくと便利かな。使い方は考えること。

void skip( char**ppc ) {
   while( isspace( **ppc ) )
      (*ppc)++ ;
}

タグ: ,