用于状态机
在哪些编程领域我会使用状态机？ 为什么？ 我怎么能实现呢？
编辑：请提供一个实际的例子，如果没有太多问。
在哪些编程领域我会使用状态机？
使用状态机来表示一个可以存在于有限数量的条件（“ 状态 ”）中的（真实的或逻辑的）对象，并根据一组固定的规则从一个状态进行到下一个状态。
为什么我会使用状态机？
状态机通常是一种非常紧凑的方式来表示一组复杂的规则和条件，并处理各种input。 您将看到内存有限的embedded式设备中的状态机。 很好的实现，状态机是自我logging，因为每个逻辑状态代表一个物理条件。 一个状态机可以体现在与其程序相当的极less量的代码中，并且运行效率非常高。 而且，pipe理状态变化的规则通常可以作为数据存储在表格中，从而提供一个易于维护的简洁表示。
我怎样才能实现呢？
微不足道的例子：
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 笔记：
-
为简单起见，示例使用带有明确的
case/break状态的switch()。 在实践中，case往往会“落入”下一个状态。 -
为了便于维护一个大型的状态机，每种
case所做的工作都可以封装在一个“工人”function中。 在while()的顶部获取任何input，将其传递给worker函数，并检查worker的返回值以计算下一个状态。 -
为了紧凑，整个
switch()可以用一个函数指针数组replace。 每个状态由一个函数体现，其返回值是指向下一个状态的指针。 警告：这可能会简化状态机或使其完全无法维护，因此请仔细考虑实施！ -
embedded式设备可以作为状态机来实现，仅在灾难性错误时退出，然后执行硬重置并重新进入状态机。
一些很好的答案已经。 对于略有不同的观点，可以考虑以较大的stringsearch文本。 有人已经提到了正则expression式，这实际上只是一个特例，尽pipe是一个重要的例子。
考虑下面的方法调用：
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
这里的不同状态直接代表我们search的单词中的所有不同的位置。 图中每个节点有两个转换：如果字母匹配，转到下一个状态; 对于其他input（即当前位置的每个其他字母），回到零。
这种轻微的重新configuration有一个巨大的优势：现在可以调整使用一些基本的技术来产生更好的性能。 实际上，每个先进的stringsearchalgorithm（目前折扣索引数据结构）都build立在这个状态机之上，并对其中的某些方面进行了改进。
什么样的任务？
任何任务，但从我所看到的，任何types的parsing经常作为状态机实现。
为什么？
parsing语法通常不是一个简单的任务。 在devise阶段，通常绘制状态图来testingparsingalgorithm。 将其转换为状态机实现是一项相当简单的任务。
怎么样？
那么，你只受到你的想象力的限制。
我已经看到它与案件陈述和循环完成 。
我已经看到它与标签和goto语句完成
我甚至看到它完成了代表当前状态的函数指针结构。 当状态改变时，一个或多个函数指针被更新。
我已经看到它只是在代码中完成的，状态的改变仅仅意味着你正在运行在不同的代码段。 （没有状态variables，必要时可以重新编写代码，这可以用一个非常简单的sorting方式来演示，这对于只有非常小的数据集是有用的。
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
没有状态variables，但代码本身代表状态
状态devise模式是通过有限状态机来表示对象状态的面向对象的方式。 通常有助于降低该对象实现的逻辑复杂性（嵌套if，许多标志等）
大多数工作stream可以作为状态机来实现。 例如，处理离开申请或订单。
如果您使用.NET，请尝试Windows Workflow Foundation。 你可以用它很快地实现一个状态机的工作stream程。
如果你使用C＃，每当你编写一个迭代器块时，你都要求编译器为你build立一个状态机（跟踪你在迭代器中的位置等）。
这是一个状态机的testing和工作的例子。 假设你在一个串行stream（串口，tcp / ip数据或文件是典型的例子）。 在这种情况下，我正在寻找一个特定的数据包结构，可以分成三个部分，同步，长度和有效载荷。 我有三个状态，一个空闲，等待同步，第二个是我们有一个很好的同步，下一个字节应该是长度，第三个状态是累积有效载荷。
这个例子是纯粹串行的，只有一个缓冲区，因为这里写的是从坏字节或数据包中恢复，可能丢弃数据包，但最终恢复，你可以做其他事情，如滑动窗口，以便立即恢复。 这将是你说的一个部分数据包被缩短，然后一个新的完整数据包开始，下面的代码将不会检测到这一点，将扔掉部分以及整个数据包，并在下一个恢复。 如果你真的需要处理所有的数据包，滑动的窗口会把你保存在那里。
我一直使用这种状态机是串行数据stream，tcp / ip，文件I / O。 或者也许是TCP / IP协议本身，比方说你想发送一个邮件，打开端口，等待服务器发送响应，发送HELO，等待服务器发送一个数据包，发送数据包，等待回复，基本上在这种情况下，以及在下面的情况下，您可能会空闲等待下一个字节/数据包进来。要记住您正在等待什么，也要重新使用等待您可以使用的代码状态variables。 与状态机用于逻辑的方式相同（等待下一个时钟，我在等什么）。
就像在逻辑中，你可能想为每个状态做一些不同的事情，在这种情况下，如果我有一个很好的同步模式，我重置偏移到我的存储，以及重置校验和累加器。 数据包长度状态说明您可能想要中止正常控制path的情况。 并不是所有的，事实上许多状态机可能会跳转或可能在正常path内循环，下面的几乎是线性的。
我希望这是有用的，并希望状态机在软件中使用更多。
testing数据有状态机从中恢复的故意问题。 在第一个好的数据包之后有一些垃圾数据，校验和不好的数据包和长度无效的数据包。 我的输出是：
好的数据包：FA0712345678EB无效同步模式0x12无效同步模式0x34无效同步模式0x56校验和错误0xBF无效数据包长度0无效同步模式0x12无效同步模式0x34无效同步模式0x56无效同步模式0x78无效同步模式0xEB好包：FA081234567800EA不再testing数据
尽pipe数据不好，stream中的两个好包仍然被提取出来。 不良资料被查出处理。
#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 } }
国家机器无处不在。 状态机是通信接口中的关键，在接收消息时需要parsing消息。 另外，在embedded式系统开发中，由于严格的时序约束，我们需要将任务分解为多个任务。
质量保证基础设施，旨在筛选或通过被testing的stream程。 （这是我特别的经验领域;我为我的上一个雇主构build了一个Python状态机框架，支持将当前状态推送到堆栈，并使用各种状态处理程序select方法在我们所有基于TTY的屏幕刮取器中使用） 。 这个概念模型非常适合，通过一个TTY应用程序运行，它通过有限数量的已知状态，并且可以移回到旧的状态（考虑使用嵌套菜单）。 这已经公布（经雇主许可）; 如果你想查看代码，可以使用Bazaar来查看http://web.dyfis.net/bzr/isg_state_machine_framework/ 。
票务，stream程pipe理和工作stream程系统 – 如果您的票据有一套规则确定其在新的，TRIAGED，正在进行的，NEEDS-QA，FAILED-QA和VERIFIED（例如）之间的移动，简单的状态机。
构build小型的，易于certificate的embedded式系统 – 交通信号灯是一个关键的例子，其中所有可能的状态列表必须被完全枚举和已知。
parsing器和词法分析器是基于状态机的，因为stream式传输的方式取决于当时所在的位置。
大量的数字硬件devise涉及创build状态机来指定电路的行为。 如果你正在编写VHDL，那么它会出现很多。
正则expression式是有限状态机（或“有限状态自动机”）发挥作用的另一个例子。
编译正则expression式是一个有限状态机，正则expression式可以匹配的string集恰好是有限状态自动机可以接受的语言（称为“正规语言”）。
有限状态机可用于任何自然语言的形态parsing。
从理论上讲，这意味着形态和语法在计算层次之间是分开的，一个是最多有限状态，另一个是最轻度的上下文敏感的（因此需要其他的理论模型来说明单词到单词而不是语素到语素关系）。
这在机器翻译和文字上光方面是有用的。 表面上看，它们是低成本的特性，可以在NLP中提取较less的机器学习应用程序，如句法或依赖关系parsing。
如果您有兴趣了解更多信息，可以查看Beesley和Karttunen的“ 有限状态形态学”以及PARCdevise的施乐有限状态工具包。
一个FSM在任何你有多个状态的地方使用，并且需要在刺激上转换到一个不同的状态。
（事实certificate这至less在理论上包含了大多数问题）
我正在做一个当前系统的例子。 我正在build立股票交易系统。 跟踪订单状态的过程可能很复杂，但是如果您为订单的生命周期构build状态图，则会使现有订单的新传入交易更为简单。 如果从现在的状态中知道新交易只能是三件事之一而不是二十件事之一，那么在应用该交易时需要比较less得多的比较。 它使代码更高效。
我在这里没有看到任何实际解释我看到他们使用的原因。
出于实际的目的，程序员通常不得不在操作中间返回一个线程/退出权限的时候添加一个。
例如，如果你有一个多状态的HTTP请求，你可能有这样的服务器代码：
Show form 1 process form 1 show form 2 process form 2
问题是，每次你展示一个表单时，即使你的代码全部在逻辑上汇合在一起并使用相同的variables，你也必须退出服务器上的整个线程（大多数语言）。
在代码中放置一段时间并返回线程的行为通常由一个switch语句完成，并创build一个称为状态机（Very Basic Version）的状态机。
当你变得越来越复杂的时候，搞清楚哪些状态是有效的就很难了。 然后人们通常定义一个“ 状态转换表 ”来描述所有的状态转换。
我写了一个状态机库 ，主要的概念就是你可以直接实现状态转换表。 这是一个非常干净的练习，不知道它会怎么过去，虽然…
状态驱动代码是实现某些types的逻辑（parsing器是一个例子）的好方法。 可以用几种方法来完成，例如：
-
状态驱动哪一个代码实际上是在一个给定的点执行的（也就是说，这个状态隐含在你正在写的那段代码中）。 recursion下降parsing器就是这种types的代码的一个很好的例子。
-
状态驱动在条件如switch语句中做什么。
-
显式状态机器，例如由parsing器生成的工具，如Lex和Yacc 。
并非所有的状态驱动代码都用于parsing。 一般的状态机生成器是smc 。 它吸收了一个状态机的定义（用它的语言），它将以各种语言吐出状态机的代码。
很好的答案。 这是我的2美分。 有限状态机是一种理论思想，可以用多种不同的方式来实现，比如表格，或者作为一个while-switch（但不要告诉任何人这是一种expression恐怖的方式 ）。 这是一个定理，任何有限状态机都对应一个正则expression式，反之亦然。 由于正则expression式对应于结构化程序，因此有时可以编写一个结构化程序来实现您的FSM。 例如，一个简单的数字parsing器可以写成：
/* implement dd*[.d*] */ if (isdigit(*p)){ while(isdigit(*p)) p++; if (*p=='.'){ p++; while(isdigit(*p)) p++; } /* got it! */ }
你明白了。 而且，如果有更快的方法，我不知道它是什么。
一个典型的用例是红绿灯。
在实现方面：Java 5的枚举可以有抽象方法，这是封装依赖于状态的行为的一个很好的方法。
