编译技术课程设计--正则式到有限自动机的转换.docx

编译技术课程设计--正则式到有限自动机的转换.docx编译技术课程设计一正则式到有限自动机的转换课程设计报告(2010--2011年度第一学期)课程名称:编译技术课程设计题0: 正则式到有限自动机的转换院系:控制与计算机工程学院2011年1月1口班级:软件0801学号:1081250115学生姓名:盛利指导教师:齐林海设计周数:1周成绩:口期:摘要用C语言实现的从正规式到有穷自动机的转化,包括正规式转化成NFA,NFA转化成DFA,DFA的最小化。从文件读入正规式,NFA或DFA。如果读入正规式,则先将其转换为NFA,再将此NFA转换为DFA并最小化。如果读入NFA,则将其转化为DFA并最小化。如果读入DFA,则直接将其最小化。通过编程实现正规式到有穷自动机的转化,让我们对课本上的转化过程更加清楚,明了。关键字:正规式NFADFA有穷自动机转化ABSTRACTClanguagefromregulartypetotherealizationofthetransformationoffiniteautomaton,includingregulartypeintoNFA,NFAintoDFA,,NFAorDFA・Ifreadinformaltype,thefirstconverttoNFA,thentheNFAconvertedtoDFAandminimizcd・IfreadNFA,,,1etusintheprocessoftransformationofthetextbook,moreclearlyunderstood・Keyword:Formaltype,NFA,DFA,finiteautomaton‘transformation目录一、 课程设计的目的 5二、 课程设计的要求5三、 系统设计5算法设计说明5数据结构设计说明6四、 系统实现8程序流程图8重要编码实现说明8五、 课程设计总结及结论13六、 参考文献14附录14课程设计的目的木次课程设计的时间为1周,目的是通过实际的题目如:词法分析、语法分析、代码优化等,使学生了解和掌握编译程序的工作原理,同时培养学生用相关的程序设计语言进行程序设计,实现编译的功能,从而提高学生的综合能力。课程设计的要求自己选一正规式;将其转换为DFA;编程实现此DFA;任意输入一串符号判断是否符合。系统设计算法设计说明程序可以以文件方式读取文法或自动机。NFA的确定化子集法先把DFAW中的/和V置为空集;M'的开始状态qO'[qO],把[qO]置为未标记后加入到Q'中;如果Q'中存在未标记的状态[ql,q2,・・・,qi],则对每个aeS定义:L[ql,q2,…,qi],a[pl,p2,…,pi]当且仅当5ql,q2,…,qi,且pl,p2,…,pi。如果[ql,q2,…,qi]不在Q'中,则把它置为为标记后加入到Q'中;如果pl,p2,…,pi中至少有一个是M的终态,则同吋把[pl,p2,…,pi]加入到F,中;然后给Q'中所有的状态都标记为止;重复执行(3),直到不能向Q'中加入新状态,并且Q'中所有的状态都有标记为止;重新命名Q'中的状态,最后获得等价的DFAW数据结构设计说明constintOP0; //操作符constint0P_D1; //操作数typedefclassEDGEpublic:intstart;charinput;intend;friendbooloperatorconst_EDGE&a,const_EDGE& &&;EDGE; //自动机的边typedefstruct_NFAintstart;intend;NFA;//classREManagcpublic:REManage;REManagestringre;virtualREManage;//处理新的输入voidProcess;//测试输入字符串,判断能否由生成的DFA识别boolTestStringstringstr;〃设置正规式voidsetREstringre;//设置NFAvoidsetNFAvectoredge,vectorstart,vectorend;〃设置DFAvoidsetDFAvectoredge,intstart,vectorend;private:〃清空所有容器变量voidclear;//输岀处理结果voidOutputRe