编程思想总结状态机

1 / 29 编程思想总结状态机 状态机的编程思想 K&R 习题 1-23 中，要求“编写一个程序，删除 C 语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在 C语言中，注释不允许嵌套”。 如果不考虑字符常量和字符串常量，问题确实很简单。只需要去掉 /和 /* */的注释。 考虑到字符常量 和字符串常量 he/*hehe*/，还有类似的头文件以及表达式5/3中的除号 /，情况就比较复杂了。 我想，这种问题最适合用正则表达式来解析， perl之类的语言应当很好处理，问 题是这里让你用 C语言实现，但是 C语言对正则表达式并没有显式的支持。 学过编译原理的应该知道，正则表达式对应三型文法，也就对应着一个有限状态自动机， 所以这里的问题其实是设计一个状态机，把输入的字符流扔进去跑就可以了。 【一个简单的状态机】 先看 K&R第一章的一个简单习题 1-12： 编写一个程序，以每行一个单词的形式打印其输入 在这个题目之前，节的单词计数示例中，其实 K&R已经展示了一个非常简单的状态机。但没有提到这种编程思想。 当然这个题目也 可以状态机的思想来编程。 2 / 29 回到题目，我们设初始的状态 state为 OUT，表示当前字符不在单词中，如果当前字符在单词中，则 state设为IN。 显然字符只能处于上述两种状态之一，有了这 2 个状态，我们就可以借助状态来思考问题 当前状态为 OUT：若当前字符是空白字符 6 7 int c, state; 8 9 state = OUT; 10 while ) != EOF ) 11if 12 if 13 state = OUT; 14 else 15 state = IN; 16 putchar; /action 17 18 else 19 if 20 state = IN; 21 putchar; /action 3 / 29 22 else 23 putchar;/action 24 state = OUT; 25 26 27 28 return 0; 29 让我们回到主题吧 【“编写一个程序，删除 C 语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在 C 语言中，注释不允许嵌套”】 按照注释的各方面规则，我们来设计一个状态机 00）设正常状态为 0，并初始为正常状态 每遍历一个字符，就依次检查下列条件，若成立或全部检查完毕，则回到这里检查下一个字符 01）状态 0 中遇到 /，说明可能会遇到注释，则进入状态 1 ex. int a = b; / 02）状态 1 中遇到 *，说明进入多行注释 部分，则进入状态 2ex. int a= b; /* 03）状态 1 中遇到 /，说明进入单行注释部分，则进4 / 29 入状态 4ex. int a = b; / 04）状态 1 中没有遇到 *或 /，说明 /是路径符号或除号，则恢复状态 0ex. or 5/3 05）状态 2 中遇到 *，说明多行注释可能要结束，则进入状态 3 ex. int a = b; /*heh* 06）状态 2 中不是遇到 *，说明多行注释还在继续，则维持状态 2 ex. int a = b; /*hehe 07） 状态 3 中遇到 /，说明多行注释要结束，则恢复状态 0 ex. int a = b; /*hehe*/ 08）状态 3 中不是遇到 /，说明多行注释只是遇到 *，还要继续，则恢复状态 2 ex. int a = b; /*hehe*h 09）状态 4 中遇到回车符 n，说明单行注释结束，则恢复状态 0 ex. int a = b; /hehe 10）状态 0 中遇到 ，说明进入字符常量中，则进入状态 5 ex. char a = 11）状态 5 中遇到 ，说明遇到转义字 符，则进入状态 6 a = 12）状态 6 中遇到任何字符，都恢复状态 5 a = n 还有如 t, , 等 主要是防止，误以为结束 5 / 29 13）状态 5 中遇到 ，说明字符常量结束，则进入状态 0 a = n 14）状态 0 中遇到 ，说明进入字符串常量中，则进入状态 7 s = ex. char ex. char ex. char ex. char 15）状态 7 中遇到 ，说明遇到转 义字符，则进入状态 8 ex. char s = 16）状态 8中遇到任何字符，都恢复状态 7 ex. char s = n 主要是防止 ，误以为结束 17）状态 7 中遇到 字符，说明字符串常量结束，则恢复状态 0 ex. char s = hehe 前面说过，不同状态可以有相应的动作。比如状态 0、5、 6、 7、 8都需要输出当前字符，再考虑一些特殊情况就可以了。 读者实现时可以借助 debug 宏定义，将测试语句输出到标准错误输出，需要 时可以重定位到标准输出，即 2&1，然后通过重定向 |到 more进行查看。 上面的状态机涉及到了 0, 8一共 9 种状态，对应的状态转换图如下： 有了这些状态表示，编写代码就很容易了 1 /* 6 / 29 2 *Copyright Zhang Haiba 3 *Date 2016-02-26 4 *File exercise1_ 5 * 6 *this program removes all comments in grammatical C code, 7 *and as a integrity solution for exercise1-23 in 8 */ 9 10 #include 11 #define debug 12 /#define debug fprintf 13 14 void dfa; 15 16 int main 17 18 dfa; 19 return 0; 20 21 7 / 29 22 void dfa 23 24 int c, state; 25 26 state = 0; 27 while ) != EOF) 28if / ex. / 29 state = 1; 30else if / ex. /* 31 state = 2; 32else if / ex. / 33 state = 4; 34else if / ex. or 5/3 35 putchar; 36 state = 0; 37 38 39else if / ex. /*he* 40 state = 3; 41else if / ex. /*heh 42 state = 2; 43 44else if / ex. /*heh*/ 8 / 29 45 state = 0; 46else if / ex. /*heh*e 47 state = 2; 48 49else if / ex. /hehe 50 state = 0; 51 52else if / ex. 53 state = 5; 54else if / ex. 55 state = 6; 56else if / ex. n or or t etc. 57 state = 5; 58else if / ex. n or or t ect. 59 state = 0; 60 61else if / ex. 62 state = 7; 63else if / ex. 64 state = 8; 65else if / ex. n or or t ect. 66 state = 7; 9 / 29 67else if / ex. n or or t ect. 68 state = 0; 69 70/debug; 71 72if | state = 5 | state = 6 | state = 7 | state = 8) 73 putchar; 74 75 【测试用例 】 如下： /* *This code make no sense, *but for exercise1_23 in to test remove all comments in C code. */ # include #include #include # include/Users/apple/blog/zhanghaiba/KandR/ #define debug 10 / 29 # define LESS 嵌入式系统中的状态机设计心得 2016-08-05 22:39:32| 分类： 状态机 | 标签： |字号大中小 订阅 在使用 iTRON 类 OS的嵌入式系统中，除了驱动程序以外，大多数模块也就是中间件和应用程序是以任务的形式设计的。 而 iTRON类 OS大多采用 C语言实现，于是用状态机的方式实现功能模块成为了主要的设计方法。 至于说面向对象，只要是 稍微严谨一点的嵌入式系统，设计上要求程序完全覆盖所有的可能情况。程序不可能在紧急情况下抛出异常等待调试。同时由于对硬件和其它应用模块的往往具有严重的耦合性，代码的重用和扩展也不是那么随心所欲。当然还有基于语 言的执行速度之类的考虑。这种情况下 C 语言往往取代大多数现代语言成为了主角吧。 iTRON 类 OS 的任务间通讯一般通过两种方法，事件或者消息。 事件处理快捷，但是无法附带任何参数且不能叠加。 消息虽然传递稍慢，不过却可以通过内存池等方式附带一定数量的参数。而且 多个同样的消息可以累积在消息栈中依次处理。 11 / 29 如果形象得比喻一下： 事件就是一串比特码，由特定为的 0 或 1 状态来判断事件是否发生，而任务以它自己的优先级别处理各种事件。 消息就是一个缓冲区， OS以 FIFO的方式把消息依从旧到新的顺序分发给任务进行对应处理。 说到这里，我想强调一下本文讨论的重点是通过状态机的方式处理消息的模型。至于事件的对应，可能今后会另外展开讨论。 一个由 OS管辖的嵌入式系统中的应用模块，在程序角度上是没有 main 函数，也不会被退出的。只要做过 任何 GUI程序，就不难理解这一点。程序被执行的瞬间，OS调用程序的初始化部分，然后每隔一个固定的时间片程序 的执行部分，当程序被关闭时休止部分会被调用。 而嵌入式系统与桌面 GUI系统的不同之处在于： 系统的电源被加载， OS 完成初始化动作之后，往往会启动一个电源管理模块，而这个模块则会调用所有应用模块的初始化部分。 另一方面， OS 或者电源管理模块在监测到电源即将被切断时，则调用所有应用模块的休止部分。 在系统正常运行时， OS 会依据各个任务的优先级依次 调用它们的执行部分，并且向它们分发各自所属的消息。 应用模块在收到消息后并不是立刻进行处理。设计12 / 29 良好的应用模块往往内部划分为多个状态，简单来说可以有种四到五种状态：睡眠状态，初始状态，空闲状态，繁忙状态和故障状态。当然了，根据不同的设计要求可以做相应的修改和扩充。应用模块内部根据不同的状态和可能接收到的所有消息编织出一张状态对应表。在表中填入适当的函数指针以响应不同状态下对各种消息的处理过 程。这就是嵌入式系统中普遍的状态机模式。 举一个状态机实现的简单例子： 我们将建立一个假象的小机器人，这个机器人能坐能走还能打架，打坏了还能自己修复。我打算用状态机的模式来实现这些功能的 框架。 /* 机器人能接受的事件 */ enum EVENT_POWERON = 0, EVENT_POWEROFF, EVENT_WALK, EVENT_FIGHT, EVENT_REST, EVENT_REPAIR EVENT_SIZE ; /* 机器人的状态 */ enum 13 / 29 STATUS_SLEEP, STATUS_INITIAL, STATUS_NORMAL, STATUS_FIGHTING, STATUS_BROKEN, STATUS_MAX ; /* 状态机函数指针的原型 */ typedef void /* 状态机函数表格 */ const MATRIX_FP s_Robot_Matrix EVENT_SIZESTATUS_SIZE = /* EVENT_POWERON */ Robot_PowerOn, Robot_NoProcess, Robot_NoProcess, Robot_NoProcess, Robot_NoProcess, /* EVENT_POWEROFF */ Robot_NoProcess, Robot_PowerOff, Robot_PowerOff, Robot_PowerOff, Robot_PowerOff, /* EVENT_WALK */ Robot_NoProcess, Robot_NoProcess, Robot_Walk, Robot_Walk, Robot_NoProcess, /* EVENT_FIGHT */ Robot_NoProcess, Robot_NoProcess, Robot_BattleMode, Robot_Fight, Robot_NoProcess, /* EVENT_REST */ Robot_NoProcess, Robot_NoProcess, Robot_Rest, Robot_NormalMode, Robot_NoProcess, /* EVENT_REPAIR */ Robot_NoProcess, Robot_NoProcess, Robot_Repair, Robot_NoProcess, Robot_Repair, ; /* 机器人事件接受分发函数 */ void Api_Robot_Execute byEvent = Api_GetRobotEvent; byStatus = Api_GetRobotStatus; 14 / 29 if ; else Robot_NoProcess; return; 以上是状态机的雏形。 我申明了机器人能响应的各种事件和机器人内部的各种状态。 同时用它们编织起一个状态 /事件响应函数指针二维数组，也就是一直说到现在的状态机的矩阵。 最后我设计了一个对外来事件进行解释，对内部状态进行读取，并最终确定调用矩阵中具体哪个函数的事件分发函数。 下面在简单列举一下填写在矩阵中所有成员函数将实现什么样的功能。 /* 没有任何功能的空函数 */ void Robot_NoProcess; /* 电源加载，初始化操作 */ void Robot_PowerOn; /* 电源关闭，休止操作 */ 15 / 29 void Robot_PowerOff; /* 步行动作 */ void Robot_Walk; /* 切换到战斗模式 */ void Robot_BattleMode; /* 战斗动作 */ void Robot_Fight; /* 休息动作 */ void Robot_Rest; /* 切换到一般模式 */ void Robot_NormalMode; /* 修理动作 */ void Robot_Repair; 机器人在启动和停止时要进行初始化处理和休止处理。 初始化处理完成后，默认为一般状态。 一般状态下可以行走，休息和修复战斗伤害。 在一般状态下执行收到攻击指令可以切换到攻击状态。 攻击状态 下可以行走和攻击，并且可以通过休息指令切换回一般状态。 当机器人的对手太强大，自己被打得七零八落的时16 / 29 候，会强制切换到破损状态。 在破损状态下就只能进行修复动作了。 具体的实现我就不说了，如果有兴趣可以想象一下各个函数该怎么实现，一定会很有意思的。 另外还有两个函数没有交代： /* 消息 /事件转换函数 */ int Api_GetRobotEvent; /* 内部状态取得函数 */ int Api_GetRobotStatus; 消息事件转换函数把外部的消息转换成状态机矩阵能够识别的事件代码。 而内部状态取得函数就像它的名字一样，只管返回内部状态，供调用状态机矩阵中的函数指针而使用。 在一个状态机系统的设计过程中，根据我自己的体会，我觉得以下几点一定要严格遵守。 在每一次将消息转化成事件后，读且仅读一次内部状态。并由此决定调用哪个成员函数。 成员函数中绝对不能再次读取状态并以它为分枝条件进行不同的处理。 一个外部模块绝对不能通过本模块的公开 API 直接修改本模块的内部状态。 状态机矩阵的成员函数宁可数量偏多内容类似，而17 / 29 切勿追求统一，盲目精简代码。 必要的时候一个状态 /事件，响应一个成员函数，也比一个函数通过内部无数的分歧判断条件进行不同的处理来的容易维护。 关于状态机的内容有很多前人的研究成果。我只是在实时操作系统下的嵌入式环境中得到了一些微不足道的经验。 本文旨在抛砖引玉，希望有更多的朋友能够一起参与讨论。 AVR 红外解码 2016-06-26 18:10:09| 分类： | 标签： |字号大中小 订阅 红外遥控器解说 : 主函数 : /* AVR 红 外 遥 控 器 解 码 程 序 * * 版本 : * 作者 : 沈金春 * 目标 : ATmega16 * 文件名 : * 编译器 : WinAVR-100110 * 开发环境 : AVRStudio 18 / 29 * 创建日期 : * 最后 修改 ： */ #include #include #include #include #define F_CPU 16000000UL #define _125US_COUNTER /* F_CPU = 2M */ #define DLED_DATA_PORT PORTA #define DLED_DATA_DDRDDRA #define DLED_BIT_PORTPORTC #define DLED_BIT_DDR DDRC unsigned char IrCode5; /存放接收数据 unsigned char dat_code2; /存放数据码 unsigned char time_counter1; unsigned char time_counter2; unsigned char ir_ok; 19 / 29 unsigned char time_125us_ok; unsigned char time_1ms_ok; unsigned char led_counter; unsigned char buffer8; const unsigned char led_tab10 PROGMEM =0xC0,0xF9,0xA4,0xB0,0x99,0x92,0x82,0xF8,0x80,0x90; void led_display DLED_DATA_PORT = pgm_read_byte; DLED_BIT_PORT =; if led_counter=0; int main DLED_DATA_DDR = 0xff; DLED_DATA_PORT = 0xff; DLED_BIT_DDR = 0xff; DLED_BIT_PORT = 0xff; 20 / 29 IR_DQ_1; IR_DQ_IN; TCNT0 = 0; TCCR0 = 0x01; /不分频 t = 255 * TIMSK |= ; sei; while if time_125us_ok = 0; if time_counter2 = 0; time_1ms_ok = 1; IrDecode; if time_1ms_ok = 0; led_display; 21 / 29 if dat_code0= + ; dat_code1= + IrCode4; 状态机编程 【转载 1】有限状态机的实现 有限状态机 switch/case 或者 if/else 这无意是最直观的方式，使用一堆条件判断，会编程的人都可以做到，对简单小巧的状态机来说最合适，但是毫无疑问，这样的方式比较原始，对庞大的状态机难以维护。 2） 状态表 维护一个二维状态表，横坐标表示当前状态，纵坐标表示输入，表中一个元素存储下一个状态和对应的操作。这一招易于维护，但是运行时间和存储空间的代价较大。 3） 使用 State Pattern 使用 State Pattern使得代码的维护比 switch/case方式稍好，性能上也不会有很多的影响， 但是也不是 100完美。不过 Robert C. Martin 做了两个自动产生 FSM 代码的 工 具 ， for java 和 for C+ 各 一 个 ， 在/resources/index 上有免费下载，这个工具的输入是纯文本22 / 29 的状态机描述，自动产生符合 State Pattern 的代码，这样 developer 的工作只需要维护状态机的文本描述，每必要冒引入 bug的风险去维护 code。 4） 使用宏定义描述状态机 一般来说， C+编程中应该避免使用 #define，但是这主要是因为如果用 宏来定义函数的话，很容易产生这样那样的问题，但是巧妙的使用 ,还是能够产生奇妙的效果。 MFC就是使用宏定义来实现大的架构的。 在实现 FSM 的时候，可以把一些繁琐无比的 if/else还有花括号的组合放在宏中，这样，在代码中可以 3）中状态机描述文本一样写，通过编译器的预编译处理产生 1）一 样的效果，我见过产生 C代码的宏，如果要产生 C+代码，己软 MFC可以，那么理论上也是可行的。 【评】：状态表的实现方法， C专家编程第 8 章有具体说明，转载【 6】 传说中的分隔符 来源 2： http:/juneshine/blog/item/ 【转载 2】有限状态机的 c 实现 XX-05-11 15:12 網絡上可以搜索到很多有限狀態機的代碼和理論分23 / 29 析，這兒僅僅是做一個簡單的例子，僅供入門參考。 这儿以四位密码校验作为状态机的例子，连续输入2479就可以通过密码测试。一个非常简单的例子，在实际的状态机实例中， 状态转移表要更復雜一些，不過方式非常 類似。在狀態查詢的地方可以做優化，同時對于輸入量也可以做有效性優化。具體代碼如下： view plaincopy to clipboardprint? typedef enum STATE1 = 1, STATE2, STATE3, STATE4, STATE5,/password pass /.ADD here STATE; typedef enum INPUT1 = 2, INPUT2 = 4, INPUT3 = 7, INPUT4 = 9, INPUT; 24 / 29 typedef struct STATE cur_state; INPUT input; STATE next_state; STATE_TRANS; typedef enum STATE1 = 1, STATE2, STATE3, STATE4, STATE5,/password pass /.ADD here STATE; typedef enum INPUT1 = 2, INPUT2 = 4, INPUT3 = 7, INPUT4 = 9, INPUT; typede