编程思想总结状态机.doc

编程思想总结状态机 篇一：状态机的编程思想 状态机的编程思想 Kamp;R习题1-23中，要求“编写一个程序，删除C语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在C语言中，注释不允许嵌套”。 如果不考虑字符常量和字符串常量，问题确实很简单。只需要去掉//和/* */的注释。 考虑到字符常量#39;\#39;#39;和字符串常量he\/*hehe*/，还有类似secure/_stdio.h的头文件以及表达式5/3中的除号/，情况就比较复杂了。 我想，这种问题最适合用正则表达式来解析，perl之类的语言应当很好处理，问题是这里让你用C语言实现，但是C语言对正则表达式并没有显式的支持。 学过编译原理的应该知道，正则表达式对应三型文法，也就对应着一个有限状态自动机（可以用switch偏重算法来实现，或者用状态转换矩阵/表偏重数据结构来实现）， 所以这里的问题其实是设计一个状态机，把输入的字符流扔进去跑就可以了。 【一个简单的状态机】 先看《Kamp;R》第一章的一个简单习题1-12：编写一个程序，以每行一个单词的形式打印其输入 在这个题目之前，1.5.4节的单词计数示例中，其实Kamp;R已经展示了一个非常简单的状态机。但没有提到这种编程思想。 当然这个题目也可以状态机的思想来编程。 回到题目，我们设初始的状态state为OUT，表示当前字符不在单词中（不是单词的组成字符），如果当前字符在单词中（属于单词的一部分），则state设为IN。 显然字符只能处于上述两种状态之一，有了这2个状态，我们就可以借助状态来思考问题 —— （1）当前状态为OUT：若当前字符是空白字符(空格、制表符、换行符），则维护当前状态仍为OUT；否则改变状态为IN。 （2）当前状态为IN：若遇到的当前字符是非空白字符，则维护当前状态为IN；否则改变状态为OUT。 处于不同的状态，根据题意可以给予相对应的动作—— 每当状态为IN的时候，意味字符属于单词的一部分，输出当前字符； 而当状态从IN切换为OUT的时候，说明一个单词结束了，此时我们输出一个回车符；状态为OUT则什么也不输出； 可以看出，借助自定义的状态，可以使编程思路更加清晰。 在遍历输入字符流的时候，程序（机器）就只能处于两种状态，对应不同状态或状态切换可以有相应的处理动作。 这样的程序不妨称为“状态机”。 按照上面的思路，代码实现就非常简单了—— 1 #include stdio.h 2 #define OUT 0 /* outside a word */ 3 #define IN 1 /* inside a word */ 4 5 int main(void) 6 { 7 int c, state; 8 9 state = OUT; 10 while ( ( c = getchar() ) != EOF ) { 11if (state == OUT) { 12 if (c == #39; #39; || c == #39;\t#39; || c == #39;\n#39;) 13 state = OUT; 14 else { 15 state = IN; 16 putchar(c); //action 17 } 18} else { 19 if (c != #39; #39; amp;amp; c != #39;\t#39; amp;amp; c != #39;\n#39;) { 20 state = IN; 21 putchar(c); //action 22 } else { 23 putchar(#39;\n#39;);//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中遇到/，说明进入单行注释部分，则进入状态4ex. int a = b; // 04）状态1中没有遇到*或/，说明/是路径符号或除号，则恢复状态0ex. secure/_stdio.h or 5/3