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

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

その 1

(a|b)*abbという正規表現を認識する DFAの状態遷移表は次のようになる。

AC B D E

a B B B B

b AC D E AC

開始状態は AC、終了状態は Eである。

この状態遷移表を用いて、引数として渡された文字列が、正規表現 (a|b)*abbにマッチするならば 1をそうでなければ 0を返す関数 int ababb(char*)を定義せよ。

プログラムはこんな感じ

#include <stdio.h>

int table[?][?] = {?}; /* 遷移表を配列として表現 */
int ababb(char* str) {
  ?
}

int main(int argc, char** argv) {
  int i;
  for (i=1; i<argc; i++) {
    char* str = argv[i];
    if (ababb(str)) {
      printf("%sは正規表現 (a|b)*abbにマッチします。\n", str);
    } else {
      printf("%sは正規表現 (a|b)*abbにマッチしません。\n", str);
    }
  }
  return 0;
}

?の部分を埋めてください。

その 2

flexについてを読んで、その中の例題をコンパイルし実行してみてください。そしてこれらの例題を参考にして、次の問題をやってください。

入力中の「hello」という文字列を「sawadi」に書き換える flexプログラムを作成せよ。
入力中の「/*」と「*/」に囲まれた部分にのまわり～というタグを挿入する flexプログラムを作成せよ。
- 簡単にするために、囲まれた部分には「*」は出現しないと仮定して良い。（つまり、「/*」から始まって、「*」以外の任意の文字の繰り返しが続き、「*/」で終わる、という正規表現を定義せよ。）
- 入れ子になっている括弧は考慮しなくても良い。例えば「/* ABC /* DEF */ GHI */」のようになっている場合は、「/* ABC /* DEF */ GHI */」でも、「/* ABC /* DEF */ GHI */」でも、どちらでも良い。（前者の方が簡単）
- 逆に/*から*/に囲まれていない部分を囲ってはいけない。特に、入力の最後が、対応する「*/」なしに「/*」... という形になっているときに注意せよ。
 
 また「/* ABC */ DEF /* GHI */」は、「/* ABC */ DEF /* GHI */」であって、「/* ABC */ DEF /* GHI */」になってはいけない。

その 3

例題: 演算子順位法による構文解析のプログラムをコンパイルして実行してみてください。これは、1+2*3のような入力を受け取って、その答を計算するプログラムです。そしてこの例題を参考にして、次の問題をやってください。

引き算（-）と割り算（/）にも対応した計算プログラムを作成せよ。（単項演算子の-は考慮しなくて良い。）
1. に加えて、さらに累乗の演算子（^）にも対応した計算プログラムを作成せよ。
ただし ^は右結合（例えば 2^2^3は、2^(2^3)、つまり 256のこと）で、 *や/よりも、優先順位が高いものとする。（ちなみに ^で累乗の演算子を表わすのは、Fortranなどの記法で、 C言語では、^は累乗を計算する演算子ではない。 xの y乗を計算する Cの関数は double pow(double x, double y)である。この関数を使うには #include <math.h>が必要である。）

提出などについて

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

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

オンラインの提出場所は

\\stfile\Report\kagawa\2004\SysProg\Report1\

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

レポートのファイル
その1, その3の場合は Cのソースファイル
その2の場合は flexのソースファイル（.lまたは.lexファイル）

です。ソースファイルは、どの問に対する解答かすぐにわかるようなファイル名をつけてください。（ファイル名は英数字のみを用いること。）

レポート作成上の注意

最初のページに表題「システムプログラム第1回レポート」・名前・学籍番号が入っていること。
各問に対して、
1. オンライン提出したソースのファイル名
2. プログラムソース（長い場合は自分で作成した部分（とその周辺）のみを抜粋すること）
  良くない例
  - 長過ぎる --- 自分が変更した部分と関係ない部分が長々とのっている
  - 短過ぎる --- 自分が変更した部分が全体のどの部分にあたるかわからない
3. 各問につき実行例 2個以上（問の要件を満たしているということが判るような実行例にすること。）
が入っていること。
最後に（授業とレポートの）感想が数行入っていること。

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

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

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

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