68

我会在哪些编程领域使用状态机？为什么 ？我怎么能实现一个？

编辑：请提供一个实际的例子，如果它不是太多的要求。

4

18 回答 18

89

我会在哪些编程领域使用状态机？

使用状态机来表示一个（真实的或逻辑的）对象，该对象可以存在于有限数量的条件（“状态”）中，并根据一组固定的规则从一个状态前进到下一个状态。

为什么要使用状态机？

状态机通常是一种非常紧凑的方式来表示一组复杂的规则和条件，并处理各种输入。您会在内存有限的嵌入式设备中看到状态机。实施得好，状态机是自记录的，因为每个逻辑状态代表一个物理条件。与其程序等效项相比，状态机可以包含在少量代码中，并且运行效率极高。此外，管理状态更改的规则通常可以作为数据存储在表中，提供易于维护的紧凑表示。

我该如何实施？

简单的例子：

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

笔记：

  • 为简单起见，该示例使用switch()带有显式case/break状态的 a。在实践中，acase将经常“失败”到下一个状态。

  • 为了便于维护大型状态机，每个状态机所做的工作都case可以封装在一个“worker”函数中。获取顶部的任何输入，while()将其传递给 worker 函数，并检查 worker 的返回值以计算下一个状态。

  • switch()为了紧凑，可以用函数指针数组替换整个。每个状态都由一个函数体现，该函数的返回值是指向下一个状态的指针。 警告：这可能会简化状态机或使其完全无法维护，因此请仔细考虑实现！

  • 嵌入式设备可以实现为仅在发生灾难性错误时退出的状态机，之后它执行硬重置并重新进入状态机。

于 2008-11-01T19:46:35.790 回答
22

已经有一些很好的答案。对于稍微不同的观点，考虑在更大的字符串中搜索文本。有人已经提到过正则表达式，这实际上只是一种特殊情况，尽管它很重要。

考虑以下方法调用：

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

你将如何实施find_in_string？简单的方法是使用嵌套循环，如下所示：

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

除了效率低下之外，它还形成了一个状态机！这里的状态有些隐藏；让我稍微重写一下代码，让它们更明显：

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

这里的不同状态直接代表了我们搜索的单词中的所有不同位置。图中每个节点都有两个转换：如果字母匹配，则进入下一个状态；对于每个其他输入（即当前位置的每个其他字母），回到零。

这种轻微的重新制定有一个巨大的优势：现在可以使用一些基本技术对其进行调整以产生更好的性能。事实上，每一个高级字符串搜索算法（暂时不考虑索引数据结构）都建立在这个状态机之上并改进了它的某些方面。

于 2008-11-01T20:00:28.243 回答
13

什么样的任务？

除了我所看到的任何任务之外，任何类型的解析都经常被实现为状态机。

为什么？

解析语法通常不是一项简单的任务。在设计阶段，绘制状态图来测试解析算法是相当普遍的。将其转换为状态机实现是一项相当简单的任务。

如何？

好吧，你只受到你的想象力的限制。

我已经看到它是用case statements 和 loops完成的。

我已经看到它使用标签和 goto语句完成

我什至看到它是用代表当前状态的函数指针结构完成的。当状态改变时，一个或多个函数指针被更新。

我已经看到它只在代码中完成，其中状态的变化仅仅意味着你在不同的代码部分中运行。（没有状态变量和必要的冗余代码。这可以被证明为非常简单的排序，这仅对非常小的数据集有用。

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

没有状态变量，但代码本身就代表了状态

于 2008-11-01T18:08:31.150 回答
9

状态设计模式是一种面向对象的方式，通过有限状态机来表示对象的状态。它通常有助于降低该对象实现的逻辑复杂性（嵌套的 if、许多标志等）

于 2008-11-01T18:06:28.457 回答
6

大多数工作流可以实现为状态机。例如，处理休假申请或订单。

如果您使用的是 .NET，请尝试使用 Windows Workflow Foundation。您可以使用它非常快速地实现状态机工作流。

于 2008-11-01T17:31:26.407 回答
6

如果您使用 C#，则任何时候编写迭代器块时，您都在要求编译器为您构建状态机（跟踪您在迭代器中的位置等）。

于 2008-11-01T17:43:02.123 回答
4

这是一个经过测试和工作的状态机示例。假设您在串行流上（串行端口、tcp/ip 数据或文件是典型示例）。在这种情况下，我正在寻找一个特定的数据包结构，它可以分为三个部分，同步、长度和有效负载。我有三种状态，一种是空闲，等待同步，第二种是我们同步良好，下一个字节应该是长度，第三种状态是累积有效负载。

该示例是纯串行的，只有一个缓冲区，如此处所述，它将从坏字节或数据包中恢复，可能会丢弃数据包但最终会恢复，您可以执行其他操作，例如滑动窗口以允许立即恢复。这就是您所说的部分数据包被缩短然后一个新的完整数据包开始的地方，下面的代码不会检测到这一点，并且会丢弃部分数据包和整个数据包并在下一个数据包中恢复。如果您确实需要处理所有整个数据包，则滑动窗口可以将您保存在那里。

我一直使用这种状态机，无论是串行数据流、tcp/ip、文件 i/o。或者可能是 tcp/ip 协议本身，比如说你要发邮件，打开端口，等待服务器发送响应，发送 HELO，等待服务器发送数据包，发送数据包，等待回复，等等。基本上在这种情况下以及在下面的情况下，您可能正在等待下一个字节/数据包进入。要记住您在等待什么，还要重用等待您可以使用的东西的代码状态变量。与在逻辑中使用状态机的方式相同（等待下一个时钟，我在等待什么）。

就像在逻辑中一样，您可能希望为每个状态做一些不同的事情，在这种情况下，如果我有一个良好的同步模式，我会将偏移量重置到我的存储中，并重置校验和累加器。数据包长度状态演示了您可能希望退出正常控制路径的情况。并非全部，事实上许多状态机可能会在正常路径中跳跃或循环，下面的一个几乎是线性的。

我希望这很有用，并希望在软件中更多地使用状态机。

测试数据有故意的问题，状态机可以从中恢复。在第一个好的数据包之后有一些垃圾数据，一个带有错误校验和的数据包，一个具有无效长度的数据包。我的输出是：

好数据包：FA0712345678EB 无效同步模式 0x12 无效同步模式 0x34 无效同步模式 0x56 校验和错误 0xBF 无效数据包长度 0 无效同步模式 0x12 无效同步模式 0x34 无效同步模式 0x56 无效同步模式 0x78 无效同步模式 0xEB 好数据包：FA081234567800EA 没有更多测试数据

尽管有坏数据，但仍提取了流中的两个好数据包。并对不良数据进行检测和处理。

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

unsigned char testdata[] =
{
    0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,  
    0x12,0x34,0x56,  
    0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,  
    0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,  
    0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA  
};

unsigned int testoff=0;

//packet structure  
// [0] packet header 0xFA  
// [1] bytes in packet (n)  
// [2] payload  
// ... payload  
// [n-1] checksum  
//  

unsigned int state;

unsigned int packlen;  
unsigned int packoff;  
unsigned char packet[256];  
unsigned int checksum;  

int process_packet( unsigned char *data, unsigned int len )  
{  
    unsigned int ra;  

    printf("good packet:");
    for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
    printf("\n");
}  
int getbyte ( unsigned char *d )  
{  
    //check peripheral for a new byte  
    //or serialize a packet or file  

    if(testoff<sizeof(testdata))
    {
        *d=testdata[testoff++];
        return(1);
    }
    else
    {
        printf("no more test data\n");
        exit(0);
    }
    return(0);
}

int main ( void )  
{  
    unsigned char b;

    state=0; //idle

    while(1)
    {
        if(getbyte(&b))
        {
            switch(state)
            {
                case 0: //idle
                    if(b!=0xFA)
                    {
                        printf("Invalid sync pattern 0x%02X\n",b);
                        break;
                    }
                    packoff=0;
                    checksum=b;
                    packet[packoff++]=b;

                    state++;
                    break;
                case 1: //packet length
                    checksum+=b;
                    packet[packoff++]=b;

                    packlen=b;
                    if(packlen<3)
                    {
                        printf("Invalid packet length %u\n",packlen);
                        state=0;
                        break;
                    }

                    state++;
                    break;
                case 2: //payload
                    checksum+=b;
                    packet[packoff++]=b;

                    if(packoff>=packlen)
                    {
                        state=0;
                        checksum=checksum&0xFF;
                        if(checksum)
                        {
                            printf("Checksum error 0x%02X\n",checksum);
                        }
                        else
                        {
                            process_packet(packet,packlen);
                        }
                    }
                    break;
            }
        }

        //do other stuff, handle other devices/interfaces

    }
}
于 2008-11-01T22:05:42.983 回答
3

状态机无处不在。状态机是通信接口中的关键，其中需要在接收到消息时对其进行解析。此外，在嵌入式系统开发中，由于严格的时序限制，我曾多次需要将一个任务分成多个任务。

于 2008-11-01T17:37:36.970 回答
3

许多数字硬件设计都涉及创建状态机来指定电路的行为。如果您正在编写 VHDL，它会出现很多。

于 2008-11-01T18:29:51.250 回答
2

QA 基础设施，旨在筛选或以其他方式运行被测过程。（这是我的特定经验领域；我为我的上一个雇主用 Python 构建了一个状态机框架，支持将当前状态推送到堆栈上，并使用各种状态处理程序选择方法，用于我们所有基于 TTY 的屏幕抓取工具） . 概念模型非常适合，因为通过 TTY 应用程序运行，它会经历有限数量的已知状态，并且可以移回旧状态（考虑使用嵌套菜单）。已发布（经上述雇主许可）；使用Bazaar检查http://web.dyfis.net/bzr/isg_state_machine_framework/是否要查看代码。

工单、流程管理和工作流系统——如果您的工单有一组规则来确定其在 NEW、TRIAGED、IN-PROGRESS、NEEDS-QA、FAILED-QA 和 VERIFIED（例如）之间的移动，那么您有一个简单的状态机。

构建小型、易于证明的嵌入式系统——交通灯信号是一个关键示例，其中必须完全枚举和了解所有可能状态的列表。

解析器和词法分析器在很大程度上是基于状态机的，因为确定流入的方式取决于您当时所处的位置。

于 2008-11-01T17:38:54.580 回答
2

正则表达式是有限状态机（或“有限状态自动机”）发挥作用的另一个例子。

编译的正则表达式是一个有限状态机，正则表达式可以匹配的字符串集正是有限状态自动机可以接受的语言（称为“正则语言”）。

于 2008-11-01T18:24:29.857 回答
2

FSM 用于您有多个状态并且需要在刺激时转换到不同状态的任何地方。

（事实证明，这涵盖了大多数问题，至少在理论上如此）

于 2008-11-01T18:33:18.060 回答
2

我有一个来自我正在使用的当前系统的示例。我正在建立一个股票交易系统。跟踪订单状态的过程可能很复杂，但是如果您为订单的生命周期构建状态图，则可以将新传入交易应用于现有订单变得更加简单。如果您从当前状态知道新事务只能是三件事之一而不是 20 件事之一，那么应用该事务所需的比较就会少得多。它使代码更加高效。

于 2008-11-01T19:38:59.707 回答
2

我在这里没有看到任何可以解释我看到它们被使用的原因的东西。

出于实际目的，当程序员在操作中间被迫返回线程/退出时，通常必须添加一个。

例如，如果您有一个多状态 HTTP 请求，您的服务器代码可能如下所示：

Show form 1
process form 1
show form 2
process form 2

问题是，每次显示表单时，您都必须退出服务器上的整个线程（在大多数语言中），即使您的代码在逻辑上都流在一起并使用相同的变量。

在代码中插入中断并返回线程的行为通常使用 switch 语句完成，并创建所谓的状态机（非常基本版本）。

随着您变得越来越复杂，很难弄清楚哪些状态是有效的。人们通常然后定义一个“状态转换表”来描述所有的状态转换。

我写了一个状态机库，主要概念是你可以直接实现你的状态转换表。这是一个非常巧妙的练习，虽然不知道它会有多好......

于 2008-11-18T22:36:07.090 回答
1

有限状态机可用于任何自然语言的形态分析。

从理论上讲，这意味着形态和句法在计算级别之间被分割，一个至多是有限状态，另一个至多是温和的上下文敏感的（因此需要其他理论模型来解释词对词而不是语素与语素的关系）。

这在机器翻译和文字修饰领域很有用。从表面上看，它们是在 NLP 中为不太琐碎的机器学习应用程序提取的低成本特征，例如句法或依赖项解析。

如果您有兴趣了解更多信息，可以查看Beesley 和 Karttunen 的 Finite State Morphology ，以及他们在 PARC 设计的 Xerox Finite State Toolkit。

于 2008-11-01T18:08:13.913 回答
0

状态驱动代码是实现某些类型逻辑的好方法（解析器就是一个例子）。它可以通过多种方式完成，例如：

  • 状态驱动在给定点实际执行的代码位（即状态隐含在您正在编写的代码段中）。 递归下降解析器是这类代码的一个很好的例子。

  • 状态驱动在条件（例如 switch 语句）中执行的操作。

  • 显式状态机，例如由Lex和Yacc等解析器生成工具生成的状态机。

并非所有状态驱动代码都用于解析。通用状态机生成器是 smc。它吸入状态机的定义（以其语言），并以各种语言为状态机输出代码。

于 2008-11-01T19:08:11.373 回答
0

很好的答案。这是我的 2 美分。有限状态机是一种理论上的想法，可以以多种不同的方式实现，例如表格，或作为一个 while-switch（但不要告诉任何人这是一种说 goto恐怖的方式）。任何 FSM 都对应一个正则表达式是一个定理，反之亦然。由于正则表达式对应于结构化程序，因此您有时可以只编写结构化程序来实现您的 FSM。例如，一个简单的数字解析器可以这样写：

/* implement dd*[.d*] */
if (isdigit(*p)){
    while(isdigit(*p)) p++;
    if (*p=='.'){
        p++;
        while(isdigit(*p)) p++;
    }
    /* got it! */
}

你明白了。而且，如果有一种运行速度更快的方法，我不知道它是什么。

于 2008-11-18T23:08:38.410 回答
0

一个典型的用例是交通信号灯。

关于实现说明：Java 5 的枚举可以有抽象方法，这是封装状态相关行为的绝佳方式。

于 2010-08-20T09:56:14.853 回答