システムプログラム'04 第2回レポート課題

この課題は、「システムプログラム（旧）」受講者（98t～02t）用です。
以下の問をすべて解いて下さい。

課題その1

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

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

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

ヒント:

xの y乗を計算する C言語の関数は double pow(double x, double y)、なお、この関数を使うには #include <math.h>が必要である。
（#include <math.h>を含めて）3行付け加えるだけで良いはず。
次のような例で実際に試しておくこと。
1. 3-2-1 … 0 になるはず。
2. 3-2*2 … -1
3. 2^2*3 … 12
4. 2^2^3 … 256
5. 2^(2*3) … 64
6. (2^2)^3 … 64

課題その2

ぶら下がりのelse:

  if(条件式₁) if(条件式₂) 文₁ else 文₂

がどちらのifと対応しているか、確かめるためのプログラムを作成し、実行せよ。

実行結果をプログラムソースの冒頭に、次のようなコメントの形で挿入すること。

/*
このプログラムを実行すると、結果は…となるので、
ぶら下がりのelseは（近い方の・遠い方の）ifと対応している。
*/

課題その3

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

  E -> id
    |  E "[" E "]"
    |  E "." id
    |  E "(" X ")"
  X -> E X'
  X' -> "," E X'
     |  ε

に対して、

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

次の文法（開始記号は 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用紙に印刷し、ホッチキスで左上を綴じたものを学務係前のレポートボックスに提出してください。

オンラインの提出場所は

\\stfile\Report\kagawa\2004\SysProg\Report2\

の各自の学籍番号のフォルダです。必要なファイルは

レポートのファイル
Cのソースファイル

です。（ファイル名は英数字のみを用いること。）

レポート作成上の注意

最初のページに表題「システムプログラム第2回レポート」・名前・学籍番号が入っていること。
1. オンライン提出したソースのファイル名
2. プログラムソース
3. 実行例 2個以上（課題その2を除く）
が入っていること。
最後に（授業とレポートの）感想が数行以上入っていること。

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

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

システムプログラムのホームページ

Koji Kagawa (kagawa@eng.?????)