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

1、课程设计报告（20102011年度第一学期）课程名称：编译技术课程设计题目：正则式到有限自动机的转换院系：控制与计算机工程学院班级：学号：学生姓名：指导教师：设计周数：1周成绩：日期：2011年 1月1 日摘要用c语言实现的从正规式到有穷自动机的转化，包括正规式转化成nfa, nfa转化成dfa, dfa的最小化。从文件读入正规式，nfa或dfao如果读入正规式，则先将其转换为nfa,再将此nfa转换为dfa并最小 化。如果读入nfa,则将其转化为dfa并最小化。如果读入dfa,则直接将其 最小化。通过编程实现正规式到有穷自动机的转化，让我们对课本上的转化过程更 加清楚，明了。关键字： 正规式

2、nfa dfa 有穷自动机转化abstractc 1 anguage from regular type to the real ization 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 typc, the first convert to nfa, then the nfa converte

3、d to dfa and minimized. if read nfa, then con ver t 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, df

4、a, finite automaton , transformation目录一、课程设计的目的5二、课程设计的要求5三、系统设计51. 算法设计说明52. 数据结构设计说明6四、系统实现81. 程序流程图82. 重要编码实现说明8五、课程设计总结及结论13六、参考文献14附录14课程设计的目的本次课程设计的时间为1周，目的是通过实际的题目如：词法分析、语法分 析、代码优化等，使学生了解和掌握编译程序的工作原理，同时培养学生用相关 的程序设计语言进行程序设计，实现编译的功能，从而提高学生的综合能力。二、课程设计的要求白己选一正规式；将其转换为dfa；编程实现此dfa；任意输入一串符号判断是否符合

5、。三'系统设计1. 算法设计说明程序可以以文件方式读収文法或自动机。nfa的确定化子集法1. 先把dfam，中的q'和f置为空集；2. m，的开始状态qolqo,把qo置为未标记后加入到q中；3. 如果q'中存在未标记的状态ql,q2,，qi,则对每个ae e定义：各'（ql,q2,， qi,a） = pl, p2,pi当且仅当 § （ql,q2,，qi,a） = pl, p2, , pi o 如果ql,q2,qi不 在q中，则把它置为为标记后加入到q'中；如果pl, p2,pi中至少有一个是m的终态， 则同时把pl,p2, : pi加入到&q

6、uot;中；然后给q'中所有的状态都标记为止；4. 重复执行（3）,直到不能向q'中加入新状态，并且q'中所有的状态都有标记为止;5.重新命名q'中的状态，最后获得等价的dfa hiq22. 数据结构设计说明const int op=0;/操作符const int op_d=1;/操作数typedef class _edgepublic:int start;char input;int end;friend bool operator 二二(const edge& a, const edge& b)return (a. start二二b star

7、t)&&(a input二二b input)&&(a. endb. end); edge;/自动机的边typedef struct _nfaint start;int end;nfa;/class remanagcpublic:remanage ();remanage(string re); virtual "remanage();/处理新的输入void process();/测试输入字符串，判断能否由生成的dfa识别bool teststring(string str);/设置正规式void setre(string re);/设置nfavoid s

8、etnfa(vector<edge> edge, vector<int> start, vcctor<int> end);/设置dfavoid setdfa(vector<edge> edge, int start, vector<int> ond);private:淸空所有容器变量void clear ();/输出处理结杲void outputresult();!1!系统实现1.程序流程图2.重要编码实现说明/* * * * 分析 re 函数* * * */*正规式到nfa的转换*/void processretonfao ;int

9、 type (char re);/判断输入字符的类型：op, op_dre到nfa转换有关函数/*对单个输入字符构造相应的nfa*/void makenfa_s(char input, nfa* n, vector<edge>& edge);/*构造某个nfa的闭包*/void makenfa_cl(nfa* result, nfa* op,vector<edge>& edge);/*构造两个nfa的或运算*/void makenfa_or(nfa* result,nfa* left,nfa* right, vector<edge>&

10、 edge);/*构造两个nfa的与运算*/void makenfa_and(nfa* result, nfa* left, nfa* right, vector<edge>& edge);/*nfa到dea的转换*/void processnfatodfao ;/*找到集合input的$闭包，结果保存在集合output屮*/void find_null_closure (vector<int>input, vector<int>&output, vector<edge> edge);/*计算集合input在输入为in时的所能达到

11、的状态集合result*/void move(vector<int> input, char in, vector<int>&result, vector<edge> edge);/*最小化dfa*/void minimizedfao ;/*在dfa中当初态为start,输入为input时，返回终态*/ int movddfa(int start, char input);/*找到输入终态end所在的集合*/int findgather(int end,vector<vector<int> > gather);/*消除dfa中

12、的无用状态*/void removefutility();/*合并dea中的等价状态*/void combineequality();fl y<k j/ r 1( 1彳彳彳彳彳彳彳彳彳*/ofstream out;止规式对应的变量string re;/输入的正规式vector<char> reinput;/正规式的输入符bool isreupdate;/正规式是否已更新/nfa对应的变量vector<char> nfalnput;/nfa的输入符vector<int> startnfa;/nfa的起始状态集vector<int> endnf

13、a;/nfa的终态集vector<edge> nfa_edge;/构造出的nfa的所有边的集合bool isnfaupdate;/nfa是否已更新/dfa对应的变量vector<char> dfalnput;/dfa的输入符int startdfa;/dfa的起始状态vector<int> enddfa;/dfa的终态集vector<int> nonenddfa;/dfa的非终态集voctor<edge> dfa_edge;/由nfa所构造成的dfa的边的集合vector<vector<int> > dfast

14、ategather;/dfa 中各个状态对应于nfa 中的状态集bool isdfaupdate;/dfa 是否已更新/dfa最小化后对应的变量 vector<char> minideainput; int ministartdfa; vector<int> minienddfa; voctor<int> mininonenddfa; vector<edge> minidea_edge;/最小化后dfa的输入符/最小化后dfa的起始状态/最小化后dfa的终态集/最小化后dfa的非终态集/最小化后dfa'p的边的集合vector<ve

15、ctor<int> > ministategather;/最小化后 dfa 中各个状态对应于初始dfa中的状态集1. 程序运行效果截图说明说 详见 instruct ions .txt航卖后按任意键开始文件e）编辑11）格式© 查看辺 帮助）frk(a|b)*abb选择你的織入方式：1. 输关正规式2. 输入nfa3. 输入dfa0-退岀输入你的选择14： 1输入完毕后，请按任意犍开始处理.文件（£） 褊辐（£） 格式（q） 査着q£） 帮助qp正规比 (a|b)*abb 正规式输入符« m b=zfqi ndex70： 1i

16、 ndex4 0：8b 1235527667123 456789i ndex4 0i ndex12 二12b -iu-dfar荟o态集匸j*dfa的也箱i ndexo： oi ndex-| : oi ndex2 : 1i ndex3 : ii ndexm:2i ndex5 :2i ndex6 :3i ndex7 z 3i ndex8 : ui ndex9 二 u1213121u42最小化的dfa竺 *c: docu>ent s and sett ingsvadaii c testresult.事本说明:instruct ions .txt请阅读后按任意犍开始选择你的織入方式：1. 输人正

17、规式2. 输入nfa3-喻入dfa0退岀输入你的选择14）： 1输入完毕后，请按任意键开始处理 结杲己经生成，请选择：1.测试生成串2 -完成请输入徐的选择：1输入完毕后，请按任意键开始处理 结杲己经生成，请选择：测试生成串2完成请输入你的选择：文件g）编辑g）格式）查看匹）帮助qdabbabb passabababab faileabbbbaaaabb pass五、课程设计总结及结论编译原理是一门很重要的课程。我们平常写小的c语言程序会感到困难，而 编译原理则是关于编写编译器的技术，难度z大可想而知。编译器的编写一直被 认为是十分困难的事情，难怪第一 fortran的编译器据说花了 18年的

18、时间才完 成。当然编译原理和编译技术并不是相同的，编译原理更注重理论方面的知识， 编译技术更注重实际编写编译器过程屮用到的技术。以前我不重视数学的学习， 现在发现好的数学基础对整个计算机的学习都是极有帮助的。数学分析能力强的 同学，对编译原理屮的各种算法，各种理论理解起来就要容易些。因为它们z间 的许多东西是相通的，只是表现形式不一样而已。还有好的语言功底也是很重要 的，在编程序的过程中，有时会和一个小小的错误叫上半天的劲，等到最后才发 现只是由于语法用的不正确，算法是可行的。这样在一个小小的语法错误上浪费 许多时间是很不值得，所以在今后的语言学习屮，我会重视语法的细节。另外在程序设计上，以前

19、自己倾向于直接写程序，很少使用流程图。后来发现先设计出 流程图，那么程序的结构就会清晰的多，编写的时候也会更节省时间。六、参考文献1. 陈意云，马万里编著。编译原理与技术。中国科学技术大学出版社，19892. 肖军模编著。程序设计语言编译方法（第三版）。大连理工大学出版社，20003. 蒋宗礼，姜守旭。形式语言与自动机理论。清华大学岀版社，20024. 郑阿奇,丁有和。visual c+教程。机械工业出版社,20055. 张素琴，吕映芝。编译原理（第二版）清华大学出版社，2004.附录（设计流程图、程序、表格、数据、运行结果等）main, cpp#pragma warning（disable:

20、4786）ttinclude <iostream>ttinclude <fstream>ttinclude <windows. h>#include<conio.h>using namespace std;ttinclude "remanage h"void waitforlnput（）cout<<endl;cout«，z输入完毕后，请按任意键开始处理”;coutendlendl;getcho ;hwnd note二findwindow("notepad", null);:sendme

21、ssage(note, wm_close, 0, 0);void readre(string& re)ifstream in(retxt");in>>re;void readteststring(vectorstring>& str)ifstream in("teststring.txt");string temp;for(;getline(in, temp), temp size()>0;)str. push_back(temp);start,void readnfa(vector<edge>& edg

22、egather,vector<int>& vector<int>& 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<edgenum;i+)innfa>>edge. start>>edge. input>>edge. end; edg

23、egather. push_back(edge);innfa>>startnum;for (i=0; i<s tartnum; i+)innfa»temp;start. push_back(temp);innfa»endnum;for (i=0; i<endnum; i+)innfa»temp;end. push_back(temp);void readdfa(vector<edge>& edgegather, int start, vectorint>& end)辻stream indfa("d

24、fa txt");edge edge;int edgenum, startnum, endnum, temp; edgegather clear ();end clear ();indfa»edgenum;for(int i=0;i<edgenum;i+)indfa»edge start>>edge. input>>edge end; edgegather. push_back (edge);indfa»startnum;indfa>>start;indfa»endnum;for (i=0; i<

25、endnum; i+)indfa»temp;end push_back(temp);void outtestresult(vectorstring> str, vector<bool> ispass)ofstream out ("testresuit. txt");for (int i=0; i<strsize();i+)out«stri«" “；if(ispassi)out«'passz，«endl;elseout«"faile/，«endl;void

26、 main()remanage test;shellexecute(null,"open", "instructions, txt', null, null, sw_show normal);cout<</z说明：详见 instructions. txt/z<<endl;cout«z，请阅读后按任意键开始；getcho ;hwnd note二findwindow("notepad", null);:sendmessage(note, wm_close, 0, 0);cout<endl<<

27、;endl;string re;/regular expressionvector<string> stringgather;/test string gathervector<edge> edgegather; /edge gather for both nfa and dfaint startdfa=o;/start state for dfavector<int>startnfa;/start state gather for nfavector<int>and dfaend;/end state gather for both nfave

28、ctor<bool>ispass;for(;)stringgather. clear ();edgegather. clear ();startnfa. clear ();end. clear ();ispasse clear ();int choice二0;cout«z，选择你的输入方式：/z«endl;cout «1.输入正规式/z«endl;cout«"2.输入 nfa"«endl;cout«/z3.输入 dfa，z«endl;cout<</z0.退出"&

29、#171;endl;cout«"输入你的选择(p4)： zz；cin»choice;switch(choice) case 1:shellexecute(null, "open", re txt', null, null, sw_shownormal);waitforlnput ();readre(re);test setre (re);test. process ();break;case 2:shellexecute(null, "open", nfa txt", null, null, sw_shownormal);waitforlnput ();readnfa (edgegather, startnfa, end);test. setnfa(edgegather, startnfa, end);test. process ();break;case