自動機程式設計

自動機程式設計的自動機為其模型。有限狀態機程式設計大致上等同於自動機程式設計，但有限狀態機程式設計專指以有限狀態機為模型的程式。自動機程式設計有以下的二項特徵：自動機程式設計的執行過程是一個由自動機步驟形成的迴圈。自動機程式設計中處理問題的思考方式很類似在利用圖靈機、馬爾可夫演算法處理問題時的思考方式。歷史.自動機程式設計的技術常用在以自動機原理為基礎的演演算法中，例如形式語言分析。約翰遜等在1968年發表的《Automatic generation of efficient lexical processors using finite state techniques》論文是早期提到自動機程式設計的論文。Peter Naur在1963年的論文將自動機程式設計當成一種通用的軟體技術。作者將此技術稱為「圖靈機的方法」，不過此論文是以自動機的狀態及步驟為基礎，沒有提到圖靈機。範例.考慮一個C語言的程式，由標準輸入流一行一行的讀取資料，列印各一行的第一個英文單字。因此一開始需確認第一個英文單字之前是否有空白，若有，需讀取所有空白後略過不列印，讀取第一個英文單字然後列印，之後讀取其他內容略過不列印，直到讀到換行符號為止。任何情形下只要讀到換行符號，就重新開始此演演算法，任何情形下只要讀到檔案結束的符號，就結束程式。傳統C語言的程式.以下是傳統指令式程式設計的C語言程式：int main(void)int c;do {c = getchar();while(c == ' ')c = getchar();while(c != EOF &amp;&amp; c != ' ' &amp;&amp; c != '\n') {putchar(c);c = getchar();putchar('\n');while(c != EOF &amp;&amp; c != '\n')c = getchar();} while(c != EOF);return 0;自動機程式設計的程式.上述問題也可以用有有限狀態機的方式處理，此程式有三個不同的階段：讀取並跳過第一個單詞前的空白、讀取第一個單詞並且列印、跳過後續的所有字元。以下將這三個階段定義為三個狀態codice_1、codice_2及codice_3。自動機程式設計的程式如下：int main(void)enum states {before, inside, after} state;int c;state = before;while((c = getchar()) != EOF) {switch(state) {case before:if(c == '\n') {putchar('\n');} elseif(c != ' ') {putchar(c);state = inside;break;case inside:switch(c) {case ' ': state = after; break;case '\n':putchar('\n');state = before;break;default: putchar(c);break;case after:if(c == '\n') {putchar('\n');state = before;return 0;雖然此程式較長，至少有一個明顯的好處，程式中只呼叫一個讀取字元的getchar()函式，而且程式中只有一個迴圈，不像之前程式使用四個迴圈。此程式中codice_4迴圈內的程式即為自動機的步驟，而迴圈本身即可重覆的執行自動機的程式。此程式實現如右圖所示的有限狀態機，其中N表示換行字元、S表示空白、A表示其他的字元。自動機依目前狀態及讀取的字元不同，會執行圖中一個箭頭所示的動作，可能是由一個狀態跳到下一個狀態，也者停在原來的狀態。其中有些箭頭有標示星號，表示需列印讀到的字元。自動機程式設計中，不一定要為每一個狀態撰寫獨立的處理程式，而且有時狀態是由許多變陣列成，無法針對每一個狀態規劃個別的處理程式。此想法有時有助於程式的精簡，例如在上述程式中，不論是在哪一個狀態，針對換行字元的處理都一様，因此程式可以先處理換行字元，其他輸入字元時才依不同狀態進行處理，簡化後變成以下的程式：int main(void)enum states {before, inside, after} state;int c;state = before;while((c = getchar()) != EOF) {if(c == '\n') {putchar('\n');state = before;} elseswitch(state) {case before:if(c != ' ') {putchar(c);state = inside;break;case inside:if(c == ' ') {state = after;} else {putchar(c);break;case after:break;return 0;獨立的自動機步驟程式.上述程式的一個重要特點是自動機步驟的程式區塊都只使用區域變數，以下的例子將自動機步驟整合為一個獨立的函式codice_5，更可以突顯上述的特點：enum states { before, inside, after };void step(enum states *state, int c)if(c == '\n') {putchar('\n');*state = before;} elseswitch(*state) {case before:if(c != ' ') {putchar(c);*state = inside;break;case inside:if(c == ' ') {*state = after;} else {putchar(c);break;case after:break;}int main(void)int c;enum states state = before;while((c = getchar()) != EOF) {step(&amp;state, c);return 0;此例清楚的呈現自動機程式設計程式的基本特點：顯式的狀態轉換表.自動機程式設計可以用顯式的狀態轉換表來表示。以下的程式中的codice_6陣列即為狀態轉換表，其列表示三個不同的狀態，其每一欄對應輸入的字元。對於每一種可能的狀態及輸入字元的組合，表中有其對應的新狀態及一個決定是否否顯示輸入字元的旗標。在實務的專案中狀態轉換表可能更為複雜，例如可能包括所有可能條件組合下需呼叫的函式指標。enum states { before = 0, inside = 1, after = 2 };struct branch {unsigned char new_state:2;unsigned char should_putchar:1;struct branch the_table[3][3] = {/* ' ' '\n' others *//* before */ { {before,0}, {before,1}, {inside,1} },/* inside */ { {after, 0}, {before,1}, {inside,1} },void step(enum states *state, int c)int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;struct branch *b = &amp; the_table[*state][idx2];*state = (enum states)(b-&gt;new_state);if(b-&gt;should_putchar) putchar(c);int main(void)int c;enum states state = before;while((c = getchar()) != EOF)step(&amp;state, c);return 0;自動化技術和自動機.自動機程式設計相當類似自動化技術領域需要的程式。製造週期一般會用以下的方式定義：許多程式語言可以用類似的方式撰寫程式。上述程式可以用此觀點改寫，以下是改寫後程式的虛擬碼，其使用關鍵字和符號說明如下：SPC : ' 'EOL : '\n'states : (before, inside, after, end)setState(c) {if c=EOF then set endif before and (c!=SPC and c!=EOL) then set insideif inside and (c=SPC or c=EOL) then set afterif after and c=EOL then set beforedoAction(c) {if inside then write(c)else if c=EOL then write(c)cycle {set beforeloop {c : readCharactersetState(c)doAction(c)until end上述程式中將更新狀態的程式獨立為codice_7函式，另外將依狀態和輸入更新輸出的程式獨立為codice_8函式，此作法可以產生較清楚及簡單的程式碼。自動化技術及事件.在自動化領域中，步驟之間的切換是依照機器本身的輸入資料，在本例中為讀到的輸入字元，在實務上可能是位置、速度、溫度等機器的關鍵資料。自動化領域有些設計方式類似圖形使用者介面的程式設計，機器狀態的改變可以視為由事件而造成，由於事件使機器由一個狀態變為下一個狀態，直到到達最後的狀態為止。可能出現狀態的組合可以產生許多的事件，因此可以定義較複雜的製造週期，其產生的製造週期一般會比線性循序流程複雜許多。一般常常會有一些同時執行的平行路徑，以及依不同事件決定執行方式的路徑，如下圖：s:狀態 c:條件s1|-c2s2----------|-c31 |-c32s31 s32|-c41 |-c42----------s4物件導向程式.若程式語言支援物件導向程式設計，就可以將自動機封裝為一個物件，隱藏自動機實現的細節。一種稱為「」的設計模式即包括了此作法。上述的程式可以改為為以下的物件導向程式，利用C++來實現：class StateMachine {enum states { before = 0, inside = 1, after = 2 } state;struct branch {enum states new_state:2;int should_putchar:1;static struct branch the_table[3][3];public:void FeedChar(int c) {int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;struct branch *b = &amp; the_table[state][idx2];state = b-&gt;new_state;if(b-&gt;should_putchar) putchar(c);};struct StateMachine::branch StateMachine::the_table[3][3] = {/* ' ' '\n' others *//* before */ { {before,0}, {before,1}, {inside,1} },/* inside */ { {after, 0}, {before,1}, {inside,1} },int main(void)int c;StateMachine machine;while((c = getchar()) != EOF)machine.FeedChar(c);return 0;註：為了減少和此主題不直接相關的修改，此處的輸入輸出函式使用C語言的標準函式庫，另外，其中的三元運算子?:也可以用if-else來實現。應用.自動機程式設計常用在詞法分析及語法分析器中。此外，用自動機的方式處理問題是事件驅動程式設計中必要的一部份，否則就要使用平行程式或是多執行緒的作法。狀態及狀態機的表示法常用在的領域。例如以統一塑模語言為基礎的軟體架構開發，會使用狀態圖表示程式的行為，許多通訊協定也利用顯式的狀態來加以定義，例如RFC 793。狀態機的思維也可以用來描述一些程式語言的語義，例如執行一個Refal語言的程式就可以描述為在抽象Refal機器上執行一連串的步驟，機器的狀態稱為view。Scheme程式語言不是一個和狀態機有關的程式語言需要以自動機的步驟及狀態的方式來思考。若要使的機能有效，需要可以記錄整個執行程式的狀態，只有在所有狀態都是顯式，不存在隱式狀態的情形下才可能達到。此處的「記錄完整狀態」即為延續性，可以視為一個較複雜自動機的狀態，自動機的步驟是由以前的延續性資料推斷下一個的延續性資料，而所執行的程式就是這些步驟的迴圈。亞歷山大·奧隆格羅的程式語言語義描述，完全以形式自動機為基礎。UCSB的STAT系統是一個使用自動機程式設計的範例，此係統還包括一種稱為「STATL」的嵌入式語言，是完全自動機導向的語言。和指令式程式設計及程式程式設計的比較.狀態不是自動機程式設計特有的概念。一般來說，狀態可視為所有在執行時會更改的資訊的結合，任何計算機程式執行時都有其對應的狀態。一傳統指令式程式設計程式的狀態包括：上述的狀態可分為顯式二種。以上述的觀點來看，自動機程式設計可視為一種特殊的指令式程式設計，其顯式的狀態減少到最少，因此二個不同時間點的程式的差異只在自動機狀態的不同，因此可以簡化程式的分析。和物件導向程式設計的關係.在物件導向程式設計的理論中，物件有其內部的狀態，而且可以接收訊息、回應訊息，傳送訊息給其他物件，且依訊息調整其內部的狀態。實際上，呼叫一個物件的方法也就是傳送訊息給此一物件。因此，物件導向程式設計的物件也可以視為是自動機，否則此物件就不能視為以自動機程式設計的方式來設計。當用物件導向程式設計來實現自動機程式設計時，也可以用類別來實現自動機模型，其中狀態為其私有成員，而步驟是物件的一個公開方法，是除了建構子及解構子外，唯一可以變更物件內容的公開方法。物件的其他公開方法可以查詢狀態，但不能變更其狀態。物件的其他方法會是物件的私有方法，無法由外界程式來呼叫。