第 1 回レポートの解答

はじめに

• プログラムのソースコードの部分については、 プロポーショナルフォント（例えば「MS P 明朝」）ではなく、 固定ピッチフォント（例えば「MS 明朝」）を使ってください。
• 例題のプログラムと変わらない部分を長々とレポートに載せる必要はありません。 紙資源を節約しましょう。

その 1

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

答

#define AC 0
#define B  1
#define D  2
#define E  3

int table[2][4] = {{B, B, B, B}, {AC, D, E, AC}}; /* 遷移表を配列として表現 */

int ababb(char* str) {
  int state=AC;
  while(*str) {
    char c = *str;
    state=table[c-'a'][state];
    str++;
  }
  return state==E; 
}

その 2

1. （難易度 A）入力中の「hello」という文字列を「sawadi」に書き換える flexプログラムを作成せよ。

   答

   %{ /* 動作記述のなかで用いる関数の定義や宣言をここに書く。 */ /* 次の 2行は決まり文句 */ #define YY_SKIP_YYWRAP int yywrap() { return 1; } %} %% /* ここに動作記述を書く。*/ /* ECHOはマッチした文字列をそのまま出力するマクロ */ [hH]ello { printf("sawadi"); } . { ECHO; } /* その他の文字はそのまま出力 */ %% /* その他の関数の定義などをここに書く。*/ int main () { return yylex(); }

   とくにコメントはありません。

2. （難易度 B）入力中の「/*」と「*/」に囲まれた部分を赤色で出力する flexプログラムを作成せよ。
   
   • 逆に囲まれていない部分は赤色になってはいけない。 特に、入力の最後が、対応する 「*/」なしに「/*」... という形になっているときに注意せよ。
   • 入れ子になっている括弧は考慮しなくても良い。

   ほとんど答

   %{ /* 動作記述のなかで用いる関数の定義や宣言をここに書く。 */ void ansi(int d) { /* 出力する文字の色を変える */ printf("\033[%dm", d); } /* 次の 2行は決まり文句 */ #define YY_SKIP_YYWRAP int yywrap() { return 1; } %} %% /* ここに動作記述を書く。*/ /* ECHOはマッチした文字列をそのまま出力するマクロ */ "/*".*"*/" { ansi(31); ECHO; ansi(0); } "." { ECHO; exit(1); } . { ECHO; } /* その他の文字はそのまま出力 */ %% /* その他の関数の定義などをここに書く。*/ int main () { return yylex(); }

   この解答はほとんど正解に近いですが、 「/* ABC */ DEF /* GHI */」が、 「/* ABC */ DEF /* GHI */」になってしまい、 「/* ABC */ DEF /* GHI */」 になってくれません。

   この問題については、第2回レポートで再度提出してもらうことにします。 その時、「/* / */」や「/* * */」が赤色になるかどうかについても、 確認してください。

その 3

1. （難易度 A）引き算（-）と割り算（/）にも対応した計算プログラムを作成せよ。（単項演算子の-は考慮しなくて良い。）

   答

   変更するところだけ抜粋します。

   int op_index(int token) { /* 表を引きやすいように連続した数値に写す。*/ switch (token) { case BGN: return 0; case '+': return 1; case '-': return 2; case '*': return 3; case '/': return 4; case '(': return 5; case ')': return 6; case NUM: return 7; case END: return 8; default: printf("不正な構文要素 (%d)。\n", token); exit(1); return 0; } } char prec_table[8][8] = { /* 演算子順位表 */ /* 行に ENDがないこと、列に BGNがないことに注意。*/ /* '+', '-', '*', '/', '(', ')', NUM, END */ /* BGN */ {LT, LT, LT, LT, LT, ERR, LT, EQ}, /* '+' */ {GT, GT, LT, LT, LT, GT, LT, GT}, /* '-' */ {GT, GT, LT, LT, LT, GT, LT, GT}, /* '*' */ {GT, GT, GT, GT, LT, GT, LT, GT}, /* '/' */ {GT, GT, GT, GT, LT, GT, LT, GT}, /* '(' */ {LT, LT, LT, LT, LT, EQ, LT, ERR}, /* ')' */ {GT, GT, GT, GT, ERR, GT, ERR, GT}, /* NUM */ {GT, GT, GT, GT, ERR, GT, ERR, GT}, }; /* 中略 */ switch (data2.token) { case '+': /* Expr -> Expr + Expr */ /* printf("Expr -> Expr '+' Expr\n"); */ yylval = d1+d2; push(Expr, yylval); break; case '-': /* Expr -> Expr - Expr */ /* printf("Expr -> Expr '-' Expr\n"); */ yylval = d1-d2; push(Expr, yylval); break; case '*': /* Expr -> Expr * Expr */ /* printf("Expr -> Expr '*' Expr\n"); */ yylval = d1*d2; push(Expr, yylval); break; case '/': /* Expr -> Expr / Expr */ /* printf("Expr -> Expr '/' Expr\n"); */ yylval = d1/d2; push(Expr, yylval); break; default: printf("エラー: 不正な演算子 (%d)。\n", data2.token); return 1; }

   「-」と「/」については、 「+」と「*」の真似をすれば良いだけです。

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

   答

   変更するところだけ抜粋します。

   #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <math.h> /* 中略 */ int op_index(int token) { /* 表を引きやすいように連続した数値に写す。*/ switch (token) { case BGN: return 0; case '+': return 1; case '-': return 2; case '*': return 3; case '/': return 4; case '^': return 5; case '(': return 6; case ')': return 7; case NUM: return 8; case END: return 9; default: printf("不正な構文要素 (%d)。\n", token); exit(1); return 0; } } char prec_table[9][9] = { /* 演算子順位表 */ /* 行に ENDがないこと、列に BGNがないことに注意。*/ /* '+', '-', '*', '/', '^', '(', ')', NUM, END */ /* BGN */ {LT, LT, LT, LT, LT, LT, ERR, LT, EQ}, /* '+' */ {GT, GT, LT, LT, LT, LT, GT, LT, GT}, /* '-' */ {GT, GT, LT, LT, LT, LT, GT, LT, GT}, /* '*' */ {GT, GT, GT, GT, LT, LT, GT, LT, GT}, /* '/' */ {GT, GT, GT, GT, LT, LT, GT, LT, GT}, /* '^' */ {GT, GT, GT, GT, LT, LT, GT, LT, GT}, /* '(' */ {LT, LT, LT, LT, LT, LT, EQ, LT, ERR}, /* ')' */ {GT, GT, GT, GT, GT, ERR, GT, ERR, GT}, /* NUM */ {GT, GT, GT, GT, GT, ERR, GT, ERR, GT}, }; /* ... */ switch (data2.token) { /* ... */ case '^': /* Expr -> Expr ^ Expr */ /* printf("Expr -> Expr '^' Expr\n"); */ yylval = pow(d1,d2); push(Expr, yylval); break; /* ... */ }

   「^」は他の四則演算より優先順位が高いこと、 「^」は右結合であることを考慮するとこのような答になります。

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

   この問の解答については、まだ公開を控えます。