システムプログラム'01 演習問題(3)


その 1

次のような BNFで表された文法(idは終端記号とする。):
  E -> id
    |  E "[" E "]"
    |  E "." id
    |  E "(" X ")"
  X -> E "," X
    |  ε
に対して、
  1. E の生成規則から左再帰を除去せよ。 (左再帰を除去するために、新しい非終端記号を導入する場合、 E'という名前をつけるとよいでしょう。)
  2. 左再帰を除去した文法に対して、構文解析表を作成せよ。
  3.  次の文法(開始記号は Expr):
       Expr    → CON
    	    | FunCall
       FunCall → FID '(' Expr ',' Expr ')'
    
       -- 以下は終端記号: 字句解析部で処理
       EOL     → '\n'                    -- End Of Line
       CON     → '0' | '1' | ... | '9'   --  一桁の数のみ
       FID     → '+' | '-' | '*' 
       VID     → 'a' | 'b' | ... | 'z'   	
    
    に対する再帰下降構文解析プログラムの例 を参考にして、問の文法に対する再帰下降構文解析プログラムを作成せよ。

    入力が E であれば、"Correct!"(または「正しい!」)と表示し、 間違っていれば、適当なエラーメッセージを出力するようにせよ。

    ただし、「終端記号に対応するマクロの定義」の部分は代わりに
    #define ID  256
    #define EOL 257
    

    「簡易字句解析ルーチン」は代わりに
    /* 簡易字句解析ルーチン */
    int yylex(void) {   
      int c;
      
      do {
        c = getchar ();
      } while (c == ' ' || c == '\t');
    
      if (isalpha(c)) {
        yylval = c;
        return ID;
      }
    
      if (c == '\n') {
        return EOL;
      }
      
      if (c == EOF) {
        exit(0); 
      }
      /* 上のどの条件にも合わなければ、文字をそのまま返す。*/
      return c;   /* '(', ')', '*'など */
    }
    
    を用いよ。(プログラムのテンプレート


その 2

Bisonについて例題を書き換えて、 さらに累乗の演算子(^)にも対応した Yaccによる構文解析・計算プログラムを作成せよ。

ただし 「^」は右結合で 「*」や「/」よりも、優先順位が高いものとする。

解釈備考
2*3^22*(3^2) *」よりも優先順位が高い
2^3^22^(3^2) 右結合

ヒント:


システムプログラムのホームページ
Koji Kagawa (kagawa@eng.?????)