状态机的编程思想[资料]

状态机的编程思想[资料]状态机的编程思想[资料] 状态机的编程思想 K&R习题1-23中，要求“编写一个程序，删除C语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在C语言中，注释不允许嵌套”。如果不考虑字符常量和字符串常量，问题确实很简单。只需要去掉//和/* */的注释。考虑到字符常量'\''和字符串常量"he\"/*hehe*/"，还有类似的头文件以及表达式5/3中的除号/，情况就比较复杂了。我想，这种问题最适合用正则表达式来解析，perl之类的语言应当很好处理，问题是这里让你用C语言实现，但是C语言对正...

状态机的编程思想[资料] 状态机的编程思想 K&R习题1-23中，要求 “编写一个程序，删除C语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在C语言中，注释不允许嵌套”。如果不考虑字符常量和字符串常量，问题确实很简单。只需要去掉//和/* */的注释。考虑到字符常量'\''和字符串常量"he\"/*hehe*/"，还有类似的头文件以及表达式5/3中的除号/，情况就比较复杂了。我想，这种问题最适合用正则表达式来解析，perl之类的语言应当很好处理，问题是这里让你用C语言实现，但是C语言对正则表达式并没有显式的支持。学过编译原理的应该知道，正则表达式对应三型文法，也就对应着一个有限状态自动机(可以用switch偏重算法来实现，或者用状态转换矩阵/表偏重数据结构来实现)，所以这里的问题其实是设计一个状态机，把输入的字符流扔进去跑就可以了。【一个简单的状态机】先看《K&R》第一章的一个简单习题1-12:"编写一个程序，以每行一个单词的形式打印其输入" 在这个题目之前，1.5.4节的单词计数示例中，其实K&R已经展示了一个非常简单的状态机。但没有提到这种编程思想。当然这个题目也可以状态机的思想来编程。回到题目，我们设初始的状态state为OUT，表示当前字符不在单词中(不是单词的组成字符)，如果当前字符在单词中(属于单词的一部分)，则state设为IN。显然字符只能处于上述两种状态之一，有了这2个状态，我们就可以借助状态来思考问题 —— (1)当前状态为OUT:若当前字符是空白字符(空格、制表符、换行符)，则维护当前状态仍为OUT;否则改变状态为IN。 (2)当前状态为IN:若遇到的当前字符是非空白字符，则维护当前状态为IN;否则改变状态为OUT。处于不同的状态，根据题意可以给予相对应的动作—— 每当状态为IN的时候，意味字符属于单词的一部分，输出当前字符; 而当状态从IN切换为OUT的时候，说明一个单词结束了，此时我们输出一个回车符;状态为OUT则什么也不输出; 可以看出，借助自定义的状态，可以使编程思路更加清晰。在遍历输入字符流的时候，程序(机器)就只能处于两种状态，对应不同状态或状态切换可以有相应的处理动作。这样的程序不妨称为“状态机”。按照上面的思路，代码实现就非常简单了—— 1 #include 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 ) { 11 if (state == OUT) { 12 if (c == ' ' || c == '\t' || c == '\n') 13 state = OUT; 14 else { 15 state = IN; 16 putchar(c); //action 17 } 18 } else { 19 if (c != ' ' && c != '\t' && c != '\n') { 20 state = IN; 21 putchar(c); //action 22 } else { 23 putchar('\n');//action 24 state = OUT; 25 } 26 } 27 } 28 return 0; 29 } 让我们回到主题吧—— 【“编写一个程序，删除C语言程序中所有的注释语句。要正确处理带引号的字符串与字符常量。在C语言中，注释不允许嵌套”】按照注释的各方面规则，我们来设计一个状态机—— 00)设正常状态为0，并初始为正常状态每遍历一个字符，就依次检查下列条件，若成立或全部检查完毕，则回到这里检查下一个字符 01)状态0中遇到/，说明可能会遇到注释，则进入状态1 ex. int a = b; / 02)状态1中遇到*，说明进入多行注释部分，则进入状态2 ex. int a= b; /* 03)状态1中遇到/，说明进入单行注释部分，则进入状态4 ex. int a = b; // 04)状态1中没有遇到*或/，说明/是路径符号或除号，则恢复状态0 ex. 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*/ )状态3中不是遇到/，说明多行注释只是遇到*，还要继续，则恢复状态2 ex. int 08 a = b; /*hehe*h 09)状态4中遇到回车符\n，说明单行注释结束，则恢复状态0 ex. int a = b; //hehe 10)状态0中遇到'，说明进入字符常量中，则进入状态5 ex. char a = ' 11)状态5中遇到\，说明遇到转义字符，则进入状态6 ex. char a = '\ 12)状态6中遇到任何字符，都恢复状态5 ex. char a = '\n 还有如'\t', '\'', '\\' 等主要是防止'\''，误以为结束 13)状态5中遇到'，说明字符常量结束，则进入状态0 ex. char a = '\n' 14)状态0中遇到"，说明进入字符串常量中，则进入状态7 ex. char s[] = " )状态7中遇到\，说明遇到转义字符，则进入状态8 ex. char 15 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 /* 2 *Copyright (C) Zhang Haiba 3 *Date 2014-02-26 4 *File exercise1_23.c 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(fmt, args...) fprintf(stderr, fmt, ##args) 13 14 void dfa(); 15 16 int main(void) 17 { 18 dfa(); 19 return 0; 20 } 21 22 void dfa() 23 { 24 int c, state; 25 26 state = 0; 27 while ((c = getchar()) != EOF) { 28 if (state == 0 && c == '/') // ex. [/] 29 state = 1; 30 else if (state == 1 && c == '*') // ex. [/*] 31 state = 2; 32 else if (state == 1 && c == '/') // ex. [//] 33 state = 4; 34 else if (state == 1) { // ex. [ or 5/3] 35 putchar('/'); 36 state = 0; 37 } 38 39 else if (state == 2 && c == '*') // ex. [/*he*] 40 state = 3; 41 else if (state == 2) // ex. [/*heh] 42 state = 2; 43 44 else if (state == 3 && c == '/') // ex. [/*heh*/] 45 state = 0; 46 else if (state == 3) // ex. [/*heh*e] 47 state = 2; 48 49 else if (state == 4 && c == '\n') // ex. [//hehe] 50 state = 0; 51 52 else if (state == 0 && c == '\'') // ex. ['] 53 state = 5; 54 else if (state == 5 && c == '\\') // ex. ['\] 55 state = 6; 56 else if (state == 6) // ex. ['\n or '\' or '\t etc.] 57 state = 5; 58 else if (state == 5 && c == '\'') // ex. ['\n' or '\'' or '\t' ect.] 59 state = 0; 60 61 else if (state == 0 && c == '\"') // ex. ["] 62 state = 7; 63 else if (state == 7 && c == '\\') // ex. ["\] 64 state = 8; 65 else if (state == 8) // ex. ["\n or "\" or "\t ect.] 66 state = 7; 67 else if (state == 7 && c == '\"') // ex. ["\n" or "\"" or "\t" ect.] 68 state = 0; 69 70 //debug("c = %c, state = %d\n", c, state); 71 72 if ((state == 0 && c != '/') || state == 5 || state == 6 || state == 7 || state == 8) 73 putchar(c); 74 } 75 } 【测试用例(1)a.out < test.c > test2.c】 test.c如下: /* *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/test.h" #define debug # define LESS(i) ( ((i) << 31) / 2 ) # define STRING "\"string\"" //to ensure legal #define CHAR '\'' int main(void) { #ifdef A "hehe..." #else /*hehe*/ "blala" #endif ///*testing*/ int idx; if (idx > 3 && idx < 6) idx = idx/100; /* // */ char a = '/'; // / char b = '*'; // * char c = '\''; // ' char d = '\n'; // enter char e = '\"'; // " char f = '\\'; // \ char g = '<'; // < char h = '>'; // > char i = '"'; // " /* special***string */ char special0[] = "\"hello, world!\""; char special1[] = "//"; char special2[] = "he\"/*hehe*/"; char *special = " \' hi \0\b\t \\\\ \a\e\f\n\r\v wolegequ \\ "; return 0; } 测试截图对比如下——

                    本文档为【状态机的编程思想[资料]】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

状态机的编程思想[资料]

你可能还喜欢