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

用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是一个终态集，终态也称可接受状态或结束状态。第二章：题目用C语言采用模拟DFA算法编写一个扫描器（词法分析器）用来识别：由任意个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:这时候已经识别的字符个数为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开始接受一个符号'-'，转到状态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有：F[0].s0--(输入一个字母'a')--s1F[1].s0--(输入一个字母'b')--s2F[2].s1--(输入一个字母'a')--s1F[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--(输入一个字符串结束符'\0')--s8(成功状态)F[13].其他情况，统一进入状态s9(出错状态)第四节.根据正规式(a|b)*aa(+|-)1，我们分析出【唯一的】初态S即K中的s0第五节.根据正规式(a|b)*aa(+|-)1，我们分析出结束状态有两个，即K中的s8（成功状态）,s9(出错状态)*/#includestdio.h/*下面的一组全局参数是作为自动机的参数*///正则式constcharregex[]=(a|b)*aa(+|-)1;//状态集合intstates[10]={0};//状态总数constintstatesAmount=sizeof(states)/sizeof(int);//可接受的字符集合constcharletterSet[]=ab+-1;//开始状态constintstartStateId=0;//可接受的结束状态集constintendStateIds[]={8,9};//可接受的结束状态总数constintendStatesAmount=sizeof(endStateIds)/sizeof(int);//成功状态集constintsucceedStateIds[]={8};//成功状态总数constintsucceedStateAmount=sizeof(succeedStateIds)/sizeof(int);//当前状态intcurrentStateId=startStateId;//转换过程中的状态变化堆栈constintMAX_STACK_SIZE=2000;intstatesTransStack[MAX_STACK_SIZE];intstatesTransStackTop=-1;//是否输出状态变化日志开关（开:1，关：0）。根据需要选择。constintisStateChangLogOn=0;//初始化自动机voidinit(){inti;//当前状态号重置currentStateId=startStateId;//所有状态数组清零for(i=0;istatesAmount;i++)states[i]=0;//记录状态出现次数states[currentStateId]++;//转换过程中的状态变化堆栈指针重置statesTransStackTop=-1;//状态变化堆栈中放入初始状态statesTransStack[++statesTransStackTop]=currentStateId;}/*判断当前自动机是否已经进入结束状态返回：已经进入结束状态：1还未进入结束状态：0*/intisEnd(){inti;for(i=0;iendStatesAmount;i++)if(currentStateId==endStateIds[i])return1;return0;}/*判断当前自动机是否已经进入成功状态返回：已经进入成功状态：1还未进入成功状态：0*/intisSucceed(){inti;for(i=0;isucceedStateAmount;i++)if(currentStateId==succeedStateIds[i])return1;return0;}/*自动机状态转换函数参数：ch：当前读到的字符*/voidtrans(charch){if(isEnd())return;/*F[0].s0--(输入一个字母'a')--s1F[1].s0--(输入一个字母'b')--s2F[2].s1--(输入一个字母'a')--s1F[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--(输入一个字符串结束符'\0')--s8(成功状态)F[13].其他情况，统一进入状态s9(出错状态)*/switch(currentStateId){case0://F[0].s0--(输入一个字母'a')--s1if(ch=='a')currentStateId=1;//F[1].s0--(输入一个字母'b')--s2elseif(ch=='b')currentStateId=2;//F[13]elsecurrentStateId=9;break;case1://F[2].s1--(输入一个字母'a')--s1if(ch=='a')currentStateId=1;//F[6].如果状态s1中已经累积有至少两个字母'a',//s1--(输入一个符号'+')--s5elseif(ch=='+'&&states[1]=2)currentStateId=5;//F[8].如果状态s1中已经累积有至少两个字母'a'//s1--(输入一个符号'-')--s6elseif(ch=='-'&&states[1]=2)currentStateId=6;//F[13]elsecurrentStateId=9;break;case2://F[3].s2--(输入一个字母'b')--s2if(ch=='b')currentStateId=2;//F[4].s2--(输入一个字母'a')--s3elseif(ch=='a')currentStateId=3;//F[13]elsecurrentStateId=9;break;case3://F[5].s3--(输入一个字母'a')--s4if(ch=='a')currentStateId=4;//F[13]elsecurrentStateId=9;break;case4://F[7].s4--(输入一个字母'+')--s5if(ch=='+')currentStateId=5;//F[9].s4--(输入一个字母'-')--s6elseif(ch=='-')currentStateId=6;//F[13]elsecurrentStateId=9;break;case5://F[10].s5--(输入一个数字'1')--s7if(ch=='1')currentStateId=7;//F[13]elsecurrentStateId=9;break;case6://F[11].s6--(输入一个数字'1')--s7if(ch=='1')currentStateId=7;//F[13]elsecurrentStateId=9;break;case7://F[12].s7--(输入一个字符串结束符'\0')--s8(成功状态)if(ch=='\0')currentStateId=8;//F[13]elsecurrentStateId=9;break;case8://实际不可能执行这个分支break;case9://实际不可能执行这个分支break;default://实际不可能执行这个分支currentStateId=9;}//记录状态出现次数states[currentStateId]++;//记录状态变化statesTransStack[++statesTransStackTop]=currentStateId;}/*根据正则式regex进行识别字符串str参数：str：要识别的字符串返回：识别成功，符合正则式regex：1识别失败：0*/intrecognize(charstr[]){inti,len=strlen(str);//每次开始识别前都要重新初始化自动机init();//逐个字母识别，直到全部字母被识别完(包括字符串结束符'\0')，//或自动机进入结束状态for(i=0;i=len&&!isEnd();i++){trans(str[i]);}//如果需要输出转换状态变化的日志if(isStateChangLogOn){printf(状态变化日志：);for(i=0;istatesTransStackTop;i++)printf(%d-,statesTransStack[i]);printf(%d\n,statesTransStack[i]);}returnisSucceed();}intmain(intargc,char*argv[]){//设置读入字符串的文件路径charfilePat