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

問 1

提出ファイル名 rdp2.c

次のような BNFで表された文法（idは終端記号とする。）:

  E  → id
     |  E “[” E “]”
     |  E “.” id
     |  E “(” X “)”
  X  → E X'
  X' → “,” E X'
     |  ε

に対して、

E の生成規則から左再帰を除去せよ。（左再帰を除去するために、新しい非終端記号を導入する場合、 E' という名前をつけよ。）
左再帰を除去した文法に対して、構文解析表を作成せよ。

次の文法（開始記号は Expr）:

   Expr    → CON
           |  FID '(' Expr2 ')'
   Expr2   → Expr Rest
   Rest    → ',' Expr
           |  ε

   -- 以下は終端記号: 字句解析部で処理
   EOL     → '\n'                    -- End Of Line
   CON     → '0' | '1' | ... | '9'   -- 簡単のため一桁の数のみ
   FID     → '+' | '-' | '*' | '!'

に対する再帰下降構文解析プログラムの例を参考にして、問の文法に対する再帰下降構文解析プログラムを作成せよ。

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

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

#define ID  256
#define EOL 257

「簡易字句解析ルーチン」は代わりに

/* 簡易字句解析ルーチン */
int yylex(void) {   
    int c;

    if (token==EOL) { /* 前のトークンが改行だったら */
        column=0;
    }
    
    do { 
        c = getchar ();
        column++; 
    } 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)] E: Unexpected token: '(' at column 3.

a.t Correct!

f() X: Unexpected token: ')' at column 3.

f(x) Correct!

f(x, y) Correct!

f(x, y,) E: Unexpected token: ')' at column 8.

f(x.t.x, a[x][y], z) Correct!

レポートにはこれ以外の実行例を2個以上入れて下さい。

入力	結果
`a[x]`	`Correct!`
`a[(x)]`	`E: Unexpected token: '(' at column 3.`
`a.t`	`Correct!`
`f()`	`X: Unexpected token: ')' at column 3.`
`f(x)`	`Correct!`
`f(x, y)`	`Correct!`
`f(x, y,)`	`E: Unexpected token: ')' at column 8.`
`f(x.t.x, a[x][y], z)`	`Correct!`

提出などについて

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

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

オンラインの提出に必要なファイルは

レポートのファイル（report.doc、Word以外のソフトで作成した場合は PDFファイルで report.pdf）
Cのソースファイル（rdp2.c）

です。

アップロードページからオンライン提出して下さい。（report.doc, report.pdfはどちらか片方を提出して下さい。）（授業用ページのパスワード発行はこのページで行なって下さい。）

レポート作成上の注意

最初のページに表題「プログラム言語論レポート」・名前・学籍番号が入っていること。
1. プログラムソース
2. 実行例 2個以上
が入っていること。
最後に（授業とレポートの）感想が数行以上入っていること。

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

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

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

Koji Kagawa