演習課題

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

1. かけ算、割算の優先度をいれたインタプリターを作成しなさい。 tokenの種類に*や/に対応した演算子が増えることになる。 入力として、

    12*3 + 3*4 - 10
   

   を入力、正しく実行できることを確認しなさい。
2. さらに、括弧をいれた式が正しく処理できるように拡張しなさい。 tokenの種類に括弧に対応するものが増えることになる。 入力として、

     12*(3+13)-10
   

   をいれて正しく実行できることを確認しなさい。

課題2: 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> := '+' | '-' | '*' | '/'

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

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

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

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

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

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

• 8クイーン問題とは、8×8のチェス版に8個のクイーン（縦横斜めに移動 できる）をおいて、お互いにぶつからない位置にクイーンを置く問題である。 なお、問題は解が何個あるか求めるだけでよい（実際の位置を出力する必要は ない）。
• この問題を解くために必要な機能があれば、適宜追加製作すること。

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

• 実行した８クイーン問題のtiny-Cプログラムと８クイーン問題の解答 （いくつ解があったか）
• インタプリターのプログラムとどのような機能を追加したかの説明

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

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

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

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

課題7: 最終課題

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

• 課題 7-1： これまで説明したtiny Cのコンパイラでは大域変数や配列宣言を処理していな い。配列宣言と配列参照を処理できるように拡張して、8 queenのプログラム を書き、コンパイル、実行しなさい。

  ヒント：

  • まずは,適当なプログラムを作ってみて、-Sのオプションを付けてコンパ イルして、どのようなコード変換されるかを調べること。
  • Cの大域的な宣言 int a[10]は、.comm a,40, 32のようにコンパイルされている
  • 適当な中間コードを加えて、それに対するgenFuncCodeのルーチンを書けばよい。

• 課題7-2：

  XMLのparserを製作し、簡単な文書のフォーマット機能を持つプログラム を書きなさい。

  例えば、

  • <heading> ...</heading> で見出しを定義(フォントがないので、大文字 にする)
  • <p> </p> でパラグラフを定義 (１字さげ)
  • <itemize> ... </itemize> でリストを定義
  • <enumerate> ... </enumerate> で、番号ずけリストを定義
  • <item> </item> で、リストの項目を定義
  これを用いれば、

  <heading> introduction </heading>
  <p> This is sample introduction.
  </p>
  </enumerate>
  <heading> sample </heading>
  <p>
  <enumerate>
  <item> This is item a </item>
  <item> This is item b </item>
  <item> This is item c </item>
  </p>
  

  は、

   INTRODUCTION
   This is sample.
   
   SAMPLE
  1. This is item a
  2. This is item b
  3. This is item c
  

  仕様等は、自分で設計し、定めること。