プログラム言語論'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