プログラム言語論'07 レポート問題

問 1

提出ファイル名 rdp2.c
次のような 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     → '+' | '-' | '*' 
    
    に対する再帰下降構文解析プログラムの例 を参考にして、問の文法に対する再帰下降構文解析プログラムを作成せよ。

    入力が 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;   /* '(', ')', '*', '[', ']'など */
    }
    
    を用いよ。(プログラムのテンプレート

    少なくとも以下のような例については、テストして下さい。
    入力結果
    a[x]Correct!
    a[(x)]エラー
    a.tCorrect!
    f()エラー
    f(x)Correct!
    f(x, y)Correct!
    f(x, y,)エラー
    f(x.t.x, a[x][y], z)Correct!
    レポートにはこれ以外の実行例を2個以上入れて下さい。

提出などについて

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

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

オンラインの提出場所は

の s各自の学籍番号 のフォルダです。必要なファイルは
  1. レポートのファイル(名称指定なし)
  2. Cのソースファイル(rdp2.c)
です。

レポート作成上の注意

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

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

プログラム言語論のホームページ


Koji Kagawa