2013

演習課題

課題 1: 式のインタプリタ

  1. かけ算、割算の優先度をいれたインタプリターを作成しなさい。 tokenの種類に*や/に対応した演算子が増えることになる。 入力として、
     12*3 + 3*4 - 10
    
    を入力、正しく実行できることを確認しなさい。
  2. さらに、括弧をいれた式が正しく処理できるように拡張しなさい。 tokenの種類に括弧に対応するものが増えることになる。 入力として、
      12*(3+13)-10
    
    をいれて正しく実行できることを確認しなさい。

課題 2: 数式のインタプリタの製作

変数とプリント関数を持つ式を計算する言語の構文解析プログラムをyaccを用 いて作成し、インタプリタを作成しなさい。例を入力し、正しく実行できることを確かめなさい。

構文規則は以下のものとする:

<program> := {<statement> ';'}* 
<statement> := <assignment> | <print_statment>
<assignment> := <variable> '=' <expression>
<print_statemnt> := 'print' <expression>
<expression> := <expression> <op> <expression> |
                <variable> |
                <nubmer> |
                '(' <expression>')'
<variable> := {英字}*
<nubmer> := {数字}*
<op> := '+' | '-' | '*' | '/'
<variable>は、アルファベットからなるシンボルで、<nubmer>は数字の並びで、 各tokenはCと同様に空白で区切られているものとする。演算子の優先度を考慮 すること。

これは、Cのmainのみの機能がある言語である。例えば、以下のようなプ ログラムをかくことができる。

x = 1+2;
y = 100;
z = (x+y)*10+34;
print z+1;

課題 3:tiny-Cインタープリタによる8クイーン問題の実行

講義(講義資料6,7)で説明したtiny Cで、8クイーン問題のプログラムを書き、 インタプリターを用いて、この問題を解きなさい。

以下のものを提出すること:

課題 4: スタックマシンへの式のコンパイラの製作

課題2で作った変数とプリント文がある数式を計算するプログラムを講義 (講義資料8,9)で説明したスタックマシンにコンパイルするプログラムを作成しなさ い。課題2にある例を入力し、正しく実行できることを確かめなさい。

課題 5: レジスタマシンへの式のコンパイラの製作

課題2で作った変数とプリント文がある数式を計算するプログラムをx86にコン パイルするプログラムを作成しなさい。 課題2にある例を入力し、正しく実行できることを確かめなさい。

課題6: 最終課題

これまで説明したtiny Cのコンパイラでは大域変数や配列宣言を処理していな い。講義で解説した、スタックマシンへのコンパイラ、もしくは、 レジスタマシンへのコンパイラを演習4で実行した8 queenのプログラムが実行できるように拡張しなさい。 具体的には、配列宣言と配列参照を処理できるようにすることが必要である。 演習3の8 queenのプログラムを、コンパイル、実行し、 レポートにはどのように拡張したのか、その結果はどうだったかについて、 詳しく解説すること。

ヒント(レジスタマシンへのコンパイラの場合):

ヒント(スタックマシンへのコンパイラの場合):