资源描述:
《用C语言采用模拟DFA算法编写一个扫描器.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、用C语言采用模拟DFA算法编写一个扫描器/*第一章:相关知识DFA定义:一个确定的有穷自动机(DFA)M是一个五元组:M=(K,Σ,f,S,Z)其中 ①K是一个有穷集,它的每个元素称为一个状态; ②Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号字母表; ③f是转换函数,是K×Σ→K上的映射,即,如f(ki,a)=kj,(ki∈K,kj∈K)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态; ④S∈K是唯一的一个初态; ⑤Z??K是一个终态集,终态也称可接受状态或结束状
2、态。第二章:题目用C语言采用模拟DFA算法编写一个扫描器(词法分析器)用来识别:由任意个a或b开始后接aa再自加或自减1的字符串,即正规式r=(a
3、b)*aa(+
4、-)1描述的语言L(r)。该词法分析器的任务:(1)滤掉源程序中的无用成分,如空格;(2)识别正规式r=(a
5、b)*aa(+
6、-)1描述的字符串。从键盘读入或打开文件读入字符串,词法分析器读入字符ywe串后扫描源字符串,若发现符合符合正规式r描述的字符串时,输出“yes”或“可接受”或“可识别”,否则输出“no”或“不可识别”。第三章:分析第一节.根据正规式(a
7、b)*aa(+
8、-)1,
9、我们可以分析出K有10个状态,也就是10个元素:状态s0:这时候已经识别的字符个数为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已经连续接受了至少两个字母'a',从s4开始接受一个符号'-',转
10、到状态s6。或从s4开始接受了一个符号'-',转到状态s6。状态s7:从s5或s6开始接受了一个数字'1',转到s7。状态s8:从s7开始接受了一个字符串结束符号' ',转到状态s8。【这是成功状态】。状态s9:【这是出错状态】。第二节.根据正规式(a
11、b)*aa(+
12、-)1,我们可以分析出Σ包含的字母有:a,b,+,-,1第三节.根据正规式(a
13、b)*aa(+
14、-)1,我们分析出转换函数f有:F[0].s0--(输入一个字母'a')-->s1F[1].s0--(输入一个字母'b')-->s2F[2].s1--(输入一个字母'a')-->s1F[
15、3].s2--(输入一个字母'b')-->s2F[4].s2--(输入一个字母'a')-->s3F[5].s3--(输入一个字母'a')-->s4F[6].如果状态s1中已经累积有至少两个字母'a's1--(输入一个符号'+')-->s5F[7]h.s4--(输入一个字母'+')-->s5F[8].如果状态s1中已经累积有至少两个字母'a's1--(输入一个符号'-')-->s6F[9].s4--(输入一个字母'-')-->s6F[10].s5--(输入一个数字'1')-->s7F[11].s6--(输入一个数字'1')-->s7F[12].s7-
16、-(输入一个字符串结束符' ')-->s8(成功状态)F[13].其他情况,统一进入状态s9(出错状态)第四节.根据正规式(a
17、b)*aa(+
18、-)1,我们分析出【唯一的】初态S即K中的s0第五节.根据正规式(a
19、b)*aa(+
20、-)1,我们分析出结束状态有两个,即K中的s8(成功状态),s9(出错状态)*/#include/*下面的一组全局参数是作为自动机的参数*///正则式constcharregex[]="(a
21、b)*aa(+
22、-)1";//状态集合intstates[10]={0};//状态总数constintstate
23、sAmount=sizeof(states)/sizeof(int);//可接受的字符集合constcharletterSet[]="ab+-1";//开始状态constintstartStateId=0;//可接受的结束状态集constintendStateIds[]={8,9};//可接受的结束状态总数constintendStatesAmount=sizeof(endStateIds)/sizeof(int);//成功状态集constintsucceedStateIds[]={8};//成功状态总数constintsucceedStateAm
24、ount=sizeof(succeedStateIds)/sizeof(int);//当前状态intcurrentStat