システムプログラム'03 演習問題（1）

準備

まず、Bison と Flexのインストールを読んで、 flexと bisonというプログラムを各自のノート PCにインストールしてください。（ハードディスクに 3MB程度の空きが必要です。）

その 1

（難易度 A） (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についてを読んで、その中の例題をコンパイルし実行してみてください。そしてこれらの例題を参考にして、次の問題をやってください。

（難易度 A）入力中の「hello」という文字列を「sawadi」に書き換える flexプログラムを作成せよ。
（難易度 B）入力中の「/*」と「*/」に囲まれた部分にのまわり～というタグを挿入する flexプログラムを作成せよ。
- 入れ子になっている括弧は考慮しなくても良い。例えば「/* ABC /* DEF */ GHI */」のようになっている場合は、「/* ABC /* DEF */ GHI */」でも、「/* ABC /* DEF */ GHI */」でも、どちらでも良い。（前者の方が簡単）
- 逆に/*から*/に囲まれていない部分を囲ってはいけない。特に、入力の最後が、対応する「*/」なしに「/*」... という形になっているときに注意せよ。

その 3

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

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

これで物足りない人は

（難易度 B）入力された通常の記法の算術式の、逆ポーランド記法を出力するプログラムを作成せよ。

もやってください。

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

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