演習課題

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

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

課題 2: lexによる浮動小数点数の認識

標準入力から、文字列を入力し、浮動少数点数を入力した場合、YES、それ以 外の場合、NOを標準出力するプログラムをlexを使って作りなさい。浮動少数 点の正規表現は、以下の通り。

浮動少数点 := 少数点数(<empty>|指数部) | 数字列 指数部
少数点数 :=  (<empty>| 数字列)  .  数字列 | 数字列 .
指数部 :=  E (<empty>| 符号) 数字列
数字列 := 数字 | 数字列 数字
符号 := - | +
<empty>は空を表す。 なお、数字は0から9までの数字、浮動少数点数の符号は考えない。

課題3: yaccによる数式の構文解析

変数とプリント関数を持つ式を計算する言語の構文解析プログラムを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;
このプログラムを入力し、認識できることを確かめなさい。 なお、構文木は必ずしもつくらなくてもよい。

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

課題3で作った数式を計算するプログラムのインタプリタを作成しなさい。 課題3にある例を入力し、正しく実行できることを確かめなさい。

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

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

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

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

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

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

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

課題8: 最終課題

 以下の2つの課題のどちらかを選択し、レポートを提出すること。