ソースコード中のコメント除去問題と状態遷移
- 作者: B.W.カーニハン,D.M.リッチー,石田晴久
- 出版社/メーカー: 共立出版
- 発売日: 1989/06/15
- メディア: 単行本
- 購入: 28人 クリック: 721回
- この商品を含むブログ (199件) を見る
Cプログラムから全てのコメントを除去するプログラムを書け。引用符で囲まれた文字列や文字定数を正しく扱うことを忘れないこと。Cのコメントは入れ子になっていない。
この問題、ハマりました…。ということで自分の理解のため、説明を試みます。
Cのコメントは
/* コメント */
という形式です。また" (double quotation mark)に囲まれた部分は文字列リテラル、' (single quotation mark)に囲まれた部分は文字リテラルです。'と’の間には1文字しか入れられないんだからこれはコメントの削除という問題では考慮する必要は無いのでは、と思いましたが、試しに'と'の間に複数の文字を入れるとコンパイラが
warning: multi-character character constant
という警告を出してきます*1。ところがこれもコンパイルできるので不正ではなく、従ってこの場合も考慮する必要があります。といっても実は’”’というパターンも考えられるので、いずれにしろ考慮しなくてはいけないのですが。
また、コメントの中ではどんな文字も特別な扱いを受けず、コメントの終わりが\*/という形であってもそこはちゃんとコメントの終わりになるようです。
さて、どうやって解くかですが、やはり安全にストリームからgetchar()で1文字ずつ読む方法にしたいと思います。ただし連続する最低でも2文字分の情報がないとコメント始まりと終わりを認識できませんから、文字を格納する変数は2つ必要です（要素数2の配列でもいいですが）。
そして「今はdouble quotationの中だから/*が出てきてもスルー」だとかいう判断をするために、"や'、\など特別な1文字の入力によって状態が遷移していく形になります。状態遷移を表現するための状態変数を用意します。
その状態ですが、最初は「double quotationの中」「single quotationの中」「コメントの中」「それ以外」の4状態かな、と思ったのですがbackslashを受け取ったあとや、それからコメントやquotationの外で/が出てきた時もまだ意味がはっきりしないので、これらの状態も考える必要があると思いました。
結局、次のようになります。
入力の分類
- ", ', /, *, \, [a]の6種類（ただし[a]はその前の5文字とは違う、普通扱いする文字の意味）
状態
状態遷移表
| " | ' | / | * | \ | [a] | |
| (0) | 1 | 2 | 3 | - | 6 | - |
| (1) | 0 | - | - | - | 7 | - |
| (2) | - | 0 | - | - | 8 | - |
| (3) | 0 | 0 | 0 | 4 | 6 | 0 |
| (4) | - | - | - | 5 | - | - |
| (5) | 4 | 4 | 0 | 4 | 4 | 4 |
| (6) | 0 | 0 | 0 | 0 | 0 | 0 |
| (7) | 1 | 1 | 1 | 1 | 1 | 1 |
| (8) | 2 | 2 | 2 | 2 | 2 | 2 |
これを図にすると以下のようになります。
出力の注意
普通はgetchar()で得た文字をそのまま出力するのですが、コメントに相当する部分は出力しないようにする必要があります。ここでちょっと注意しなければいけないのが(0)の状態で/が登場したとき、つまり状態(3)のときです。
状態(3)の時はコメントが始まるかそうでないか不定なので、このときはgetchar()で得た文字を出力せず、バッファとなる変数に保存しておきます。次の文字でコメントが始まるのが確定したら何も出力せず、そうでなければバッファに格納されている文字とその次の文字を一度に出力します。
また状態(4)からコメントを抜けた時点での文字は/ですが、これは不要なので飛ばします。そのために前の状態を覚えておく変数を作らなくてはならなくなり、個人的にはちょっと気に入ってない部分です。
以上をプログラムとして表現するとこのようになります。
#include <stdio.h> int next_state(int current_state, char c); int main(void) { int c, buf = -1, state = 0, former_state = -1; while ((c = getchar()) != EOF) { former_state = state; state = next_state(former_state, c); switch (state) { case 3: buf = c; break; case 4: case 5: break; default: if (former_state == 3) printf("%c%c", buf, c); else if (former_state == 5) ; else putchar(c); break; } } return 0; } int next_state(int state, char c) { switch (state) { case 0: if (c == '"') state = 1; else if (c == '\'') state = 2; else if (c == '/') state = 3; else if (c == '\\') state = 6; break; case 1: if (c == '"') state = 0; else if (c == '\\') state = 7; break; case 2: if (c == '\'') state = 0; else if (c == '\\') state = 8; break; case 3: if (c == '*') state = 4; else if (c == '\\') state = 6; else state = 0; break; case 4: if (c == '*') state = 5; break; case 5: if (c == '/') state = 0; else state = 4; break; case 6: case 7: case 8: state -= 6; break; default: break; } return state; }
