杜林機-STATE 設計模式

今天早上看了電影 模仿遊戲(The Imitation Game)，其中提到「 圖靈機」讓我想起以前有寫過這樣的程式碼，原來發明人是二戰悲劇英雄，以下是我先前寫的

- - -
Design Patterns 的 STATE 設計模式算是比較常見或者說常須面對的問題，杜林機算是這問題的代表作，STATE 設計模式的例子，多見使用具有 OO 能力的程式語言編寫，以下這個例子採用純 C 來實作，取自 The C primer / Les Hancock, Morris Krieger。

/*
** remclr.c
**
** 這個程式可將 C 原始檔中的註解清除
** 用法：
**   remclr < C 原始檔名 [> 儲存檔名]
**       不指定 儲存檔名 將顥示於螢幕
*/

#include <stdio.h>

/* 給 table[] 用來記錄要執行的動作及要改變的狀態 */
struct table_entry
{
  void (*prtptr) (char C);
  int next_state;
};

void noprt(char C)
{  }

void charprt(char C)
{
  putchar(C);
}

void slsh(char C)
{
  putchar('/');
  putchar(C);
}

int main()
{
  int c;
  int col;  /* 目前讀取原始檔字元的分類：
                  0 ＝ / 字元
                  1 ＝ * 字元
                  2 ＝ 其他字元
             */

  int row;  /* 目前的狀態：
                0 ＝ 註解外
                1 ＝ 註解內
                2 ＝ 註解外碰到 / 字元的狀態
                3 ＝ 註解內碰到 * 字元的狀態
             */

  static struct table_entry table[][3] =
  {
    {{noprt,2}, {charprt,0}, {charprt, 0}},
    {{noprt,1},{noprt,3},{noprt,1}},
    {{slsh,0}, {noprt,1}, {slsh,0}},
    {{noprt,0}, {noprt,1}, {noprt,1}}
  };

  row = 0;
  while((c = getchar()) != EOF)
  {
    if(c == '/')
      col = 0;
    else if(c == '*')
      col = 1;
    else
      col = 2;

    (*table[row][col].prtptr)(c);
    row = table[row][col].next_state;
  }

  return 0;
}

因有人提出上一個程式不夠嚴謹，碰到註解位於引號內也會被刪除，所以以下修得嚴謹一點

/*
** remclr.c
**
** 這個程式可將 C 原始檔中的註解清除
** 用法：
**   remclr < C 原始檔名 [> 儲存檔名]
**       不指定 儲存檔名 將顥示於螢幕
*/

#include <stdio.h> 

/* 給 table[] 用來記錄要執行的動作及要改變的狀態 */
struct table_entry
{
  void (*prtptr) (char C);
  int next_state;
};

void noprt(char C)
{  }

void charprt(char C)
{
  putchar(C);
}

void slsh(char C)
{
  putchar('/');
  putchar(C);
}

int main()
{
  int c;
  int col;  /* 目前讀取原始檔字元的分類：
                  0 ＝ / 字元
                  1 ＝ * 字元
                  2 ＝ 其他字元
                  3 ＝ 雙引號
                  4 ＝ 單引號
             */

  int row;  /* 目前的狀態：
                0 ＝ 註解外
                1 ＝ 註解內
                2 ＝ 註解外碰到 / 字元的狀態
                3 ＝ 註解內碰到 * 字元的狀態
                4 ＝ 雙引號之內
                5 ＝ 單引號之內
             */

  static struct table_entry table[][5] =
  {
    {{noprt,2},{charprt,0},{charprt,0},{charprt,4},{charprt,5}},
    {{noprt,1},{noprt,3},{noprt,1},{noprt,1},{noprt,1}},
    {{slsh,0},{noprt,1},{slsh,0},{slsh,0},{slsh,0}},
    {{noprt,0},{noprt,1},{noprt,1},{noprt,1},{noprt,1}},
    {{charprt,4},{charprt,4},{charprt,4},{charprt,0},{charprt,4}},
    {{charprt,5},{charprt,5},{charprt,5},{charprt,5},{charprt,0}}
  };

  row = 0;
  while((c = getchar()) != EOF)
  {
    if(c == '/')
      col = 0;
    else if(c == '*')
      col = 1;
    else if(c == '"')
      col = 3;
    else if(c == '\'')
      col = 4;
    else
      col = 2;

    (*table[row][col].prtptr)(c);
    row = table[row][col].next_state;
  }

  return 0;
}

其實還要再考慮在引號內用跳脫字元使用引號的狀況，再搞下去 table 會越弄越大，以下不再用純 C 寫了，而且也比較人性化，另外發現純 c 也支援 // 註解，也一併加上

/*
** remclr.cpp
**
** 這個程式可將 C/C++ 原始檔中的註解清除
** 用法：
**   remclr < C 原始檔名 [> 儲存檔名]
**       不指定 儲存檔名 將顥示於螢幕
*/

#include <iostream>
using namespace std;

class remclr
{
  istream &m_Src;
  ostream &m_Dest;

  // 處於註解外所用的函數
  void Remark_Out()
  {
    char c = m_Src.get();

    switch(c)
    {
    case '/':
      pmFunc_Ptr = &remclr::Remark_S;
      break;
    case '"':
      m_Dest << c;
      pmFunc_Ptr = &remclr::DoubleQuote;
      break;
    case '\'':
      m_Dest << c;
      pmFunc_Ptr = &remclr::SingleQuote;
      break;
    default:
      m_Dest << c;
    }
  }

  // 處於註解內所用的函數
  void Remark_In()
  {
    char c = m_Src.get();

    if( c == '*')
      pmFunc_Ptr = &remclr::Remark_E;
  }

  // 處於註解外碰到 / 字元時所用的函數
  void Remark_S()
  {
    char c = m_Src.get();

    if(c == '*')
      pmFunc_Ptr = &remclr::Remark_In;
    else if(c == '/') // 碰到 // 時
      pmFunc_Ptr = &remclr::TwoSlash;
    else
    {
      m_Dest << '/';
      m_Dest << c;
      pmFunc_Ptr = &remclr::Remark_Out;
    }
  }

  // 處於註解外碰到 // 時所用的函數
  void TwoSlash()
  {
    char c = m_Src.get();
    if(c == '\n')
      pmFunc_Ptr = &remclr::Remark_Out;
  }

  // 處於註解內碰到 * 字元時所用的函數
  void Remark_E()
  {
    char c = m_Src.get();

    if( c == '/')
      pmFunc_Ptr = &remclr::Remark_Out;
    else if( c != '*')
      pmFunc_Ptr = &remclr::Remark_In;
  }

  // 處於單引號時所用的函數
  void SingleQuote()
  {
    char c = m_Src.get();

    m_Dest << c;
    if( c == '\'')
      pmFunc_Ptr = &remclr::Remark_Out;
    else if( c == '\\')
      pmFunc_Ptr = &remclr::Escape_SQ;
  }

  // 處於雙引號時所用的函數
  void DoubleQuote()
  {
    char c = m_Src.get();

    m_Dest << c;
    if( c == '"')
      pmFunc_Ptr = &remclr::Remark_Out;
    else if( c == '\\')
      pmFunc_Ptr = &remclr::Escape_DQ;
  }

  // 在雙引號內有跳脫字元時
  void Escape_DQ()
  {
    m_Dest << (char)m_Src.get();
    pmFunc_Ptr = &remclr::DoubleQuote;
  }

  // 在單引號內有跳脫字元時
  void Escape_SQ()
  {
    m_Dest << (char)m_Src.get();
    pmFunc_Ptr = &remclr::SingleQuote;
  }

  void (remclr::*pmFunc_Ptr)(); // 記錄現所處狀態所要用的成員函數指標

public:
  remclr(istream &Src,ostream &Dest)
    :m_Src(Src),m_Dest(Dest)
  {
    pmFunc_Ptr = &remclr::Remark_Out;
  }

  ~remclr()
  {
  }

  void Start()
  {
    while(m_Src.eof() == false)
      (this->*pmFunc_Ptr)();
  }
};


int main()
{
  remclr Turing(cin,cout);
  Turing.Start();
  return 0;
}

不過 C 版的 table 法還是比較好的，那算是一種窮盡法，或叫暴力法，可以把所有的狀況都表列出來，可以幫忙分析