编译原理课程设计报告——正则到有限自动机的转换

编译原理课程设计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 ——正则到有限自动机的转换 课程设计报告 (2010——2011 年度第一学期) 课程名称: 编译技术课程设计 题 目: 正则式到有限自动机的转换 院 系: 控制与计算机工程学院 班 级: 学 号: 学生姓名: 指导教师: 设计周数: 1周 成 绩: 日期: 2011年 1 月 1 日 摘要 用c语言实现的从正规式到有穷自动机的转化，包括正规式转化成NFA， ，DFA的最小化。 NFA转化成DFA 从文件读入正规式，NFA或DFA。 如果读入正规式，则先将其转换为NFA，再将此NFA转换为DFA并最小化。 如果读入NFA，则将其转化为DFA并最小化。如果读入DFA,则直接将其最小化。 通过编程实现正规式到有穷自动机的转化，让我们对课本上的转化过程更加清楚，明了。 关键字:正规式 NFA DFA 有穷自动机 转化 ABSTRACT C language from regular type to the realization of the transformation of finite automaton, including regular type into NFA, NFA into DFA, DFA minimization. From the document into normal type, NFA or DFA. If read in formal type, the first convert to NFA, then the NFA converted to DFA and minimized. If read NFA, then convert it to DFA and minimized. If read DFA, is directly minimize. Through the programming formal type to the finite automaton transformation, let us in the process of transformation of the textbook, more clearly understood. Key word: Formal type， NFA， DFA， finite automaton ，transformation 目录 一、 课程设计的目的 ............................................................................................................... 5 二、 课程设计的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 ............................................................................................................... 5 三、 系统设计 ........................................................................................................................... 5 1. 算法设计说明 ................................................................................................................... 5 2. 数据结构设计说明 ........................................................................................................... 6 四、 系统实现 ........................................................................................................................... 8 1. 程序 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图 ............................................................................................................... 8 2. 重要编码实现说明 ................................................................................................... 8 五、 课程设计 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 及结论 ..................................................................................................... 13 六、 参考文献 ......................................................................................................................... 14 附录................................................................................................................................................. 14 一、 课程设计的目的 本次课程设计的时间为1周，目的是通过实际的题目如:词法分析、语法分析、代码优化等，使学生了解和掌握编译程序的工作原理，同时培养学生用相关的程序设计语言进行程序设计，实现编译的功能，从而提高学生的综合能力。 二、 课程设计的要求 自己选一正规式;将其转换为DFA;编程实现此DFA; 任意输入一串符号判断是否符合。 三、 系统设计 1. 算法设计说明 程序可以以文件方式读取文法或自动机。 NFA的确定化 子集法 1(先把DFA M’中的Q’和F’置为空集; 2(M’的开始状态q0’=[q0]，把[q0]置为未标记后加入到Q’中; 3(如果Q’中存在未标记的状态[q1,q2,…，qi]，则对每个a??定义:δ’([q1,q2,…，qi],a)=[p1,p2,…,pi]当且仅当δ({q1,q2,…，qi},a)={p1,p2,…,pi}。如果[q1,q2,…，qi]不在Q’中，则把它置为为标记后加入到Q’中;如果p1,p2,…,pi中至少有一个是M的终态，则同时把[p1,p2,…,pi]加入到F’中;然后给Q’中所有的状态都标记为止; 4(重复执行(3)，直到不能向Q’中加入新状态，并且Q’中所有的状态都有标记为止; 5( 重新命名Q’中的状态，最后获得等价的DFA M’ 1 0 q1q1,qf Q0 1 q q q2 Q22. 数据结构设计说明 q2 const int OP=0; //操作符 qconst int OP_D=1; //操作数 q2 typedef class _EDGE { public: int start; char input; int end; friend bool operator == (const _EDGE& a,const _EDGE& b) { return (a.start==b.start)&&(a.input==b.input)&&(a.end==b.end); } }EDGE; //自动机的边 typedef struct _NFA { int start; int end; }NFA; // class REManage { public: REManage(); REManage(string re); virtual ~REManage(); //处理新的输入 void Process(); //测试输入字符串，判断能否由生成的DFA识别 bool TestString(string str); //设置正规式 void setRE(string re); //设置NFA void setNFA(vector edge,vector start,vector end); //设置DFA void setDFA(vector edge,int start,vector end); private: //清空所有容器变量 void clear(); //输出处理结果 void OutputResult(); 四、 系统实现 1. 程序流程图 2. 重要编码实现说明 /********************分析RE函数**********************/ /*正规式到NFA的转换*/ void ProcessREToNFA(); int state; //计数状态 int type(char re); //判断输入字符的类型: OP,OP_D RE到NFA转换有关函数 /*对单个输入字符构造相应的NFA*/ void MakeNFA_S(char input,NFA* n,vector& edge); /*构造某个NFA的闭包*/ void MakeNFA_CL(NFA* result,NFA* op,vector& edge); /*构造两个NFA的或运算*/ void MakeNFA_OR(NFA* result,NFA* left,NFA* right,vector& edge); /*构造两个NFA的与运算*/ void MakeNFA_AND(NFA* result,NFA* left,NFA* right,vector& edge); /*****************NFA到DFA转换有关函数***********/ /*NFA到DFA的转换*/ void ProcessNFAToDFA(); /*找到集合input的$闭包，结果保存在集合output中*/ Void Find_NULL_Closure(vectorinput, vector&output,vector edge); /*计算集合input在输入为in时的所能达到的状态集合result*/ void Move(vector input,char in,vector&result,vector edge); /****************DFA最小化有关函数*****************/ /*最小化DFA*/ void MinimizeDFA(); /*在DFA中当初态为start，输入为input时，返回终态*/ int MovdDFA(int start,char input); /*找到输入终态end所在的集合*/ int FindGather(int end,vector > gather); /*消除DFA中的无用状态*/ void RemoveFutility(); /*合并DFA中的等价状态*/ void CombineEquality(); /*************************************End****************************** ****/ ofstream out; //正规式对应的变量 string re; //输入的正规式 vector REInput; //正规式的输入符 bool isREUpdate; //正规式是否已更新 //NFA对应的变量 vector NFAInput; //NFA的输入符 vector startNFA; //NFA的起始状态集 vector endNFA; //NFA的终态集 vector NFA_EDGE; //构造出的NFA的所有边的集合 bool isNFAUpdate; //NFA是否已更新 //DFA对应的变量 vector DFAInput; //DFA的输入符 int startDFA; //DFA的起始状态 vector endDFA; //DFA的终态集 vector nonEndDFA; //DFA的非终态集 vector DFA_EDGE; //由NFA所构造成的DFA的边的集合 vector > DFAStateGather; //DFA中各个状态对应于NFA中的状态集 bool isDFAUpdate; //DFA是否已更新 //DFA最小化后对应的变量 vector miniDFAInput; //最小化后DFA的输入符 int miniStartDFA; //最小化后DFA的起始状态 vector miniEndDFA; //最小化后DFA的终态集 vector miniNonEndDFA; //最小化后DFA的非终态集 vector MiniDFA_EDGE; //最小化后DFA中的边的集合 vector > miniStateGather; //最小化后DFA中各个状态对应于初始DFA中的状态集 1( 程序运行效果截图说明 五、 课程设计总结及结论 编译原理是一门很重要的课程。我们平常写小的C语言程序会感到困难，而编译原理则是关于编写编译器的技术，难度之大可想而知。编译器的编写一直被认为是十分困难的事情，难怪第一Fortran的编译器据说花了18年的时间才完成。当然编译原理和编译技术并不是相同的，编译原理更注重理论方面的知识，编译技术更注重实际编写编译器过程中用到的技术。以前我不重视数学的学习，现在发现好的数学基础对整个计算机的学习都是极有帮助的。数学分析能力强的同学，对编译原理中的各种算法，各种理论理解起来就要容易些。因为它们之间的许多东西是相通的，只是 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现形式不一样而已。还有好的语言功底也是很重要的，在编程序的过程中，有时会和一个小小的错误叫上半天的劲，等到最后才发现只是由于语法用的不正确，算法是可行的。这样在一个小小的语法错误上浪费许多时间是很不值得，所以在今后的语言学习中，我会重视语法的细节。另外在 程序设计上，以前自己倾向于直接写程序，很少使用流程图。后来发现先设计出流程图，那么程序的结构就会清晰的多，编写的时候也会更节省时间。 六、 参考文献 1(陈意云，马万里编著。编译原理与技术。中国科学技术大学出版社，1989 2(肖军模编著。程序设计语言编译方法(第三版)。大连理工大学出版社，2000 3(蒋宗礼，姜守旭。形式语言与自动机理论。清华大学出版社，2002 4(郑阿奇，丁有和。Visual C++教程。机械工业出版社，2005 5(张素琴，吕映芝。编译原理(第二版) 清华大学出版社，2004. 附录(设计流程图、程序、表格、数据、运行结果等) main.cpp #pragma warning(disable:4786) #include #include #include #include using namespace std; #include "REManage.h" void waitForInput() { cout<>re; } void ReadTestString(vector& str) { ifstream in("TestString.txt"); string temp; for(;getline(in,temp),temp.size()>0;) { str.push_back(temp); } } void ReadNFA(vector& edgeGather,vector& start, vector& end) { ifstream inNFA("NFA.txt"); EDGE edge; int edgeNum,startNum,endNum,temp; edgeGather.clear(); start.clear(); end.clear(); inNFA>>edgeNum; for(int i=0;i>edge.start>>edge.input>>edge.end; edgeGather.push_back(edge); } inNFA>>startNum; for(i=0;i>temp; start.push_back(temp); } inNFA>>endNum; for(i=0;i>temp; end.push_back(temp); } } void ReadDFA(vector& edgeGather,int start, vector& end) { ifstream inDFA("DFA.txt"); EDGE edge; int edgeNum,startNum,endNum,temp; edgeGather.clear(); end.clear(); inDFA>>edgeNum; for(int i=0;i>edge.start>>edge.input>>edge.end; edgeGather.push_back(edge); } inDFA>>startNum; inDFA>>start; inDFA>>endNum; for(i=0;i>temp; end.push_back(temp); } } void OutTestResult(vector str,vector isPass) { ofstream out("TestResult.txt"); for(int i=0;i stringGather; //test string gather vector edgeGather; //edge gather for both NFA and DFA int startDFA=0; //start state for DFA vector startNFA; //start state gather for NFA vector end; //end state gather for both NFA and DFA vector isPass; for(;;) { stringGather.clear(); edgeGather.clear(); startNFA.clear(); end.clear(); isPass.clear(); int choice=0; cout<<"选择你的输入方式:"<>choice; switch(choice) { case 1: ShellExecute(NULL,"open","RE.txt",NULL,NULL,SW_SHOWNORMAL); waitForInput(); ReadRE(re); test.setRE(re); test.Process(); break; case 2: ShellExecute(NULL,"open","NFA.txt",NULL,NULL,SW_SHOWNORMAL); waitForInput(); ReadNFA(edgeGather,startNFA,end); test.setNFA(edgeGather,startNFA,end); test.Process(); break; case 3: ShellExecute(NULL,"open","DFA.txt",NULL,NULL,SW_SHOWNORMAL); waitForInput(); ReadDFA(edgeGather,startDFA,end); test.setDFA(edgeGather,startDFA,end); test.Process(); break; case 0: exit(0); default: cout<<"输入错误!"<>choice; if(choice==1) { ShellExecute(NULL,"open","TestString.txt",NULL,NULL,SW_SHOWNORMAL ); waitForInput(); ReadTestString(stringGather); for(int i=0;i