用C语言采用模拟DFA算法编写一个扫描器

1、精选优质文档-倾情为你奉上用C语言采用模拟DFA算法编写一个扫描器/*第一章：相关知识DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中 K是一个有穷集，它的每个元素称为一个状态； 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表； f是转换函数，是K×K上的映射，即，如 f（ki，a）=kj， （kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj， 我们把kj称作ki的一个后继状态； S K是唯一的一个初态； Z?K是一个终态集，终态也称可接受状态或结束状态。第二章：题目用C语言采用模拟DFA算法

2、编写一个扫描器（词法分析器）用来识别：由任意个a或b开始后接aa再自加或自减1的字符串，即正规式r=(a|b)*aa(+|-)1描述的语言L（r）。该词法分析器的任务：（1）滤掉源程序中的无用成分，如空格；（2）识别正规式r=(a|b)*aa(+|-)1描述的字符串。从键盘读入或打开文件读入字符串，词法分析器读入字符ywe串后扫描源字符串，若发现符合符合正规式r描述的字符串时，输出“yes”或“可接受”或“可识别”，否则输出“no”或“不可识别”。第三章：分析第一节. 根据正规式(a|b)*aa(+|-)1，我们可以分析出 K有10个状态，也就是10个元素： 状态 s0:这时候已经识别的字符个

3、数为0，也就是开始状态 状态 s1:从状态s0开始接受连续的字母 'a'，转到状态 s1 状态 s2:从状态s0开始接受连续的字母 'b'，转到状态 s2 状态 s3:从s2开始接受了一个字母 'a'，转到状态 s3 状态 s4:从s3开始接受了一个字母 'a'，转到状态 s4 状态 s5:如果s1已经连续接受了至少两个字母 'a',从s4开始接受一个符号 '+'，转到状态 s5 。 或 从s4开始接受了一个符号 '+'，转到状态 s5 。 状态 s6:如果s1已经连续接受了至少两个

4、字母 'a',从s4开始接受一个符号 '-'，转到状态 s6 。 或 从s4开始接受了一个符号 '-'，转到状态 s6 。 状态 s7:从s5或s6开始接受了一个数字 '1'，转到 s7。 状态 s8:从s7开始接受了一个字符串结束符号 '0'，转到状态s8。【这是成功状态】。 状态 s9:【这是出错状态】。 第二节. 根据正规式(a|b)*aa(+|-)1，我们可以分析出包含的字母有：a,b,+,-,1第三节. 根据正规式(a|b)*aa(+|-)1，我们分析出转换函数 f 有： F0. s0 -(输入一个字母&

5、#39;a') -> s1 F1. s0 -(输入一个字母'b') -> s2 F2. s1 -(输入一个字母'a') -> s1 F3. s2 -(输入一个字母'b') -> s2 F4. s2 -(输入一个字母'a') -> s3 F5. s3 -(输入一个字母'a') -> s4 F6. 如果状态 s1中已经累积有至少两个字母'a' s1 -(输入一个符号'+') -> s5 F7h. s4 -(输入一个字母'+'

6、;) -> s5 F8. 如果状态 s1中已经累积有至少两个字母'a' s1 -(输入一个符号'-') -> s6 F9. s4 -(输入一个字母'-') -> s6 F10. s5 -(输入一个数字'1') -> s7 F11. s6 -(输入一个数字'1') -> s7 F12. s7 -(输入一个字符串结束符'0') -> s8(成功状态) F13. 其他情况，统一进入状态 s9(出错状态) 第四节. 根据正规式(a|b)*aa(+|-)1，我们分析出【唯一

7、的】初态S即K中的 s0第五节. 根据正规式(a|b)*aa(+|-)1，我们分析出结束状态有两个，即K中的 s8（成功状态）,s9(出错状态) */#include <stdio.h>/* 下面的一组全局参数是作为自动机的参数 */ 正则式const char regex="(a|b)*aa(+|-)1"/ 状态集合int states10=0;/ 状态总数const int statesAmount = sizeof(states)/sizeof(int);/ 可接受的字符集合const char letterSet="ab+-1"/ 开

8、始状态 const int startStateId=0;/ 可接受的结束状态集const int endStateIds=8,9;/ 可接受的结束状态总数const int endStatesAmount = sizeof(endStateIds)/sizeof(int);/ 成功状态集const int succeedStateIds = 8;/ 成功状态总数const int succeedStateAmount = sizeof(succeedStateIds)/sizeof(int);/ 当前状态int currentStateId = startStateId;/ 转换过程中的状态

9、变化堆栈const int MAX_STACK_SIZE = 2000;int statesTransStackMAX_STACK_SIZE;int statesTransStackTop = -1;/ 是否输出状态变化日志开关（开:1，关：0）。根据需要选择。const int isStateChangLogOn = 0; / 初始化自动机void init() int i; / 当前状态号重置 currentStateId = startStateId; / 所有状态数组清零 for(i=0;i<statesAmount;i+) statesi=0; / 记录状态出现次数 state

10、scurrentStateId+; / 转换过程中的状态变化堆栈指针重置 statesTransStackTop = -1; / 状态变化堆栈中放入初始状态 statesTransStack+statesTransStackTop = currentStateId;/* 判断当前自动机是否已经进入结束状态 返回： 已经进入结束状态：1 还未进入结束状态：0*/int isEnd() int i; for(i=0;i<endStatesAmount;i+) if(currentStateId = endStateIdsi) return 1; return 0; /* 判断当前自动机是否已

11、经进入成功状态 返回： 已经进入成功状态：1 还未进入成功状态：0*/int isSucceed() int i; for(i=0;i<succeedStateAmount;i+) if(currentStateId = succeedStateIdsi) return 1; return 0; /* 自动机状态转换函数 参数： ch ：当前读到的字符*/void trans(char ch) if(isEnd() return ; /* F0. s0 -(输入一个字母'a') -> s1 F1. s0 -(输入一个字母'b') -> s2 F

12、2. s1 -(输入一个字母'a') -> s1 F3. s2 -(输入一个字母'b') -> s2 F4. s2 -(输入一个字母'a') -> s3 F5. s3 -(输入一个字母'a') -> s4 F6. 如果状态 s1中已经累积有至少两个字母'a' s1 -(输入一个符号'+') -> s5 F7h. s4 -(输入一个字母'+') -> s5 F8. 如果状态 s1中已经累积有至少两个字母'a' s1 -(输入一个符号&

13、#39;-') -> s6 F9. s4 -(输入一个字母'-') -> s6 F10. s5 -(输入一个数字'1') -> s7 F11. s6 -(输入一个数字'1') -> s7 F12. s7 -(输入一个字符串结束符'0') -> s8(成功状态) F13. 其他情况，统一进入状态 s9(出错状态) */ switch(currentStateId) case 0: / F0. s0 -(输入一个字母'a') -> s1 if(ch = 'a'

14、) currentStateId = 1; / F1. s0 -(输入一个字母'b') -> s2 else if(ch = 'b') currentStateId = 2; / F13 else currentStateId = 9; break; case 1: / F2. s1 -(输入一个字母'a') -> s1 if(ch = 'a') currentStateId = 1; / F6 . 如果状态 s1中已经累积有至少两个字母'a', / s1 -(输入一个符号'+') -&

15、gt; s5 else if(ch = '+' && states1>=2) currentStateId = 5; / F8 . 如果状态 s1中已经累积有至少两个字母'a' / s1 -(输入一个符号'-') -> s6 else if(ch = '-' && states1>=2) currentStateId = 6; / F13 else currentStateId = 9; break; case 2: / F3. s2 -(输入一个字母'b') -&

16、gt; s2 if(ch = 'b') currentStateId = 2; / F4. s2 -(输入一个字母'a') -> s3 else if(ch = 'a') currentStateId = 3; / F13 else currentStateId = 9; break; case 3: / F5. s3 -(输入一个字母'a') -> s4 if(ch = 'a') currentStateId = 4; / F13 else currentStateId = 9; break; cas

17、e 4: / F7 . s4 -(输入一个字母'+') -> s5 if(ch = '+') currentStateId = 5; / F9 . s4 -(输入一个字母'-') -> s6 else if(ch = '-') currentStateId = 6; / F13 else currentStateId = 9; break; case 5: / F10. s5 -(输入一个数字'1') -> s7 if(ch = '1') currentStateId = 7; /

18、 F13 else currentStateId = 9; break; case 6: / F11. s6 -(输入一个数字'1') -> s7 if(ch = '1') currentStateId = 7; / F13 else currentStateId = 9; break; case 7: / F12. s7 -(输入一个字符串结束符'0') -> s8(成功状态) if(ch = '0') currentStateId = 8; / F13 else currentStateId = 9; break;

19、 case 8: / 实际不可能执行这个分支 break; case 9: / 实际不可能执行这个分支 break; default: / 实际不可能执行这个分支 currentStateId = 9; / 记录状态出现次数 statescurrentStateId+; / 记录状态变化 statesTransStack+statesTransStackTop = currentStateId;/* 根据正则式 regex 进行识别字符串 str 参数： str ：要识别的字符串 返回： 识别成功，符合正则式 regex ：1 识别失败：0 */int recognize(char str) int i,len = strlen(str); / 每次开始识别前都要重新初始化自动机 init(); / 逐个字母识别，直到全部字母被识别完(包括字符串结束符'0')， / 或自动机进入结束状态 for(i=0;i<=len&&!isEnd();i+) trans(stri); / 如果需要输出转换状态变化的日志 if(isStateChangLogOn) printf(&