手作業でNFAを作る手順

簡単な例として、Ｃ言語のコメントの/**/の内側の文字だけを抽出する方法を説明します。
簡単でない例としてはこれと同じやり方でXMLをフェッチする図面がここにあります。

状態＼入力	'/'	'*'	else
S1	2	1	1
S2	1	3	1
S3	3	4	3
S4	1	3	3

表を見ると、
状態1の時に入力値が/であれば状態2へ
状態2の時に入力値が*であれば状態3へ、それ以外は１へ
状態3の時に入力値が*であれば状態４へ、それ以外は3へ
状態4の時に入力値が/であれば状態１へ、それ以外は3へ

以上の事をgraphvizに入力すると、状態遷移図を自動生成できます。

digraph G {
  graph [rankdir=LR];
  node [shape="circle"];
  S1->S2 [label="/"];
  S2->S1 [label="[^*]"];
  S2->S3 [label="*"];
  S3->S3 [label="[^*]"] ;
  S3->S4 [label="*"];
  S4->S1 [label="/"];
  S4->S3 [label="[^/]"];
}

んで、上の表と図を見ながら単純にプログラムに置き換えます。

  std::string val; // 結果
  int st = 1;
  for (i = 0; i < MAX; i++) {
    ch = buff[i];
    switch (st) {
    case 1:
      if (ch == '/') st = 2;
      break;
    case 2:
      if (ch == '*') st = 3;
      else st = 1;
      break;
    case 3:
      if (ch == '*') st = 4;
　　 else val += ch;
      break;
    case 4:
      if (ch == '/') st = 1;
      else {
        val += '*';
        val += ch;
        st = 3;
      }
      break;
    }
  }

これでパターンの照合は可能になりました。
コメント内部の文字列を抽出するタイミングは
状態3と4のelseのブロックです。
3から3への遷移では単純に一文字ずつ追加です。
3から4への遷移で先読みがあるので4から3で一文字戻します。

---

戻る