プログラム言語論'04 第2回レポート課題

この課題は 「プログラム言語論」受講者(学籍番号 03t***)用です。


課題

次のような BNFで表された文法(idは終端記号とする。):
  E -> id
    |  E "[" E "]"
    |  E "." id
    |  E "(" X ")"
  X -> 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)) { /* IDは一文字のアルファベット */
        yylval = c;
        return ID;
      }
    
      if (c == '\n') { /* 行末が $(入力の終わり)に対応する */
        return EOL;
      }
      
      if (c == EOF) {  /* ファイルの終 */
        exit(0); 
      }
      /* 上のどの条件にも合わなければ、文字をそのまま返す。*/
      return c;   /* '(', ')', '*', '[', ']'など */
    }
    
    を用いよ。(プログラムのテンプレート

提出などについて

上の問題を解いて、プログラムを作成し、 またそれに対するレポートを作成して下さい。 (締切 2月 15日火曜日 18時)

レポートはワード(もしくは同等のワープロソフト)で作成します。 作成したソースファイルとレポートのファイルをオンラインで提出してください。 (ワード以外のワープロの場合は、RTF, PDF, PostScriptなど、そのソフトを持っていなくても読める形式に変換して下さい。) また同時に、レポートをA4用紙に印刷し、 ホッチキスで左上を綴じたものを学務係前のレポートボックスに提出してください。

オンラインの提出場所は

の各自の学籍番号のフォルダです。必要なファイルは
  1. レポートのファイル
  2. Cのソースファイル
です。 (ファイル名は英数字のみを用いること。)

レポート作成上の注意

この注意が守られていないレポートは減点の対象になります。

問題を数人で相談しながら解くのはもちろん構いませんが、 実行例とレポートは各自で作成してください。 実行例まで同一のレポートは不正レポートと見なします。


プログラム言語論のホームページ
Koji Kagawa (kagawa@eng.?????)