还剩11页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
试验一
(一)程序设计语言及其编译器实现概览(小时)试验目的学习一门简洁的程序设2计语言的定义及其编译器实现试验任务针对一门简洁的程序设计语言,阅读其定义文档,初步了解其编译器的源代码试验内容()选择一门语言或其它语言也可(需自备其编译器的源代码)1TINY()阅读其定义文档,了解语言定义的方法,包括词法、语法、语义、运行时环境、目标2机器、目标语言等内容()了解其编译器源代码3对语言编译器,其源代码由多个文件组成,请弄清晰每个文件的作用是什么详TINY情请见《编译原理及实践》第1,7节请做一个工程文件(C++Win32Console Application,)把它们组织起来,然后编译成可执行文件()即为语言编译器tiny.dsp,tiny.exe,TINY然后用它编译语言示例源代码(」”)看看编译生成的目标文件()TINY samplesample.tm是怎样的要运行目标程序,还须要一个虚拟机,名为机机是以软件形式存在TM TM的,其源代码为须要编译生成可执行文件然后将目标程序作为机的输tm.c,tm.exe TM入运行机即可得到所期盼的结果要求读懂和、TM main.c.globals.h util.h scan.h util.c等文件,三人一组进行探讨,给每一行加上注释,总结你们各自对程序的理解和阅scan.c读程序的收获,每组提交份加了注释的文件和心得有实力的同学可加上1tm.c试验一
(二)的编程实现(小时)DFA2试验目的通过本次试验,加深对及其识别的语言的理解,学习对一般的的表达方DFA DFA法与编程实现方法试验任务编写一个语言程序,模拟实现识别字符串的过程C DFA试验内容()的输入;()的存储与读写;()的正确性检查;()1DFA2DFA3DFA4DFA的语言集列表显示;()的规则字符串判定;5DFA内容说明()的输入1DFA分别输入的“字符集”、“状态集”、“起先状态”、“接受状态集”、“状态转DFA换表”等内容,并保存在设定的变量中()的存储与读写2DFA将上述的五元组保存在一个文本文件中,扩展名指定为请自行设计文件DFA.dfa DFA的存储格式,并说明其含义能将保存在内存变量中的写入文件,也能将文件DFA DFA DFA读入内存中(思索对稀疏(转换表中为空的地方较多)或用“或”表达转换的(如DFA DFA下的测试用例三),如何改进转换表的表达)DFA()的正确性检查3DFA检查全部集合的元素的唯一性检查“起先状态”是否唯一,并是否包含在“状态集”中检查“接受状态集”是否为空,并是否包含在“状态集”中present=P;next=D;input=I;;class DFApublic:DFA cout«nl手动输入,
2、读取txt文件vvendl;int select;cin»select;ifselect==l inti;ifselect==2read;〃状态集string States;〃起先状态char StartStates;〃结束状态集string FinalStates;//字符集string Alphabet;转换函数vectorTransitionTable Trans;//〃初始化自动机void inti”请输入有限状态集cout Sendl;cin»States;cout«请输入字符集A n«endl;cin»Alphabet;〈”请输入转换函数格式为当前状态-输入字符-下一状态输入#结束coutv MOVE-输入vvendl;int j=0;whiletrue char input
[4];cin»input;ifstrcmpinput,n#n==O break;TransitionTable Tempinput[O],input
[1],input
[2];Trans.push_backTemp;〈”请输入起先状态集coutv SOendl;cin»StartStates;cout〈”请输入结束状态集F H«endl;cin»FinaIStates;//识别字符串void identify请输入字符串coutvv”“vvendl;string str;cin»str;int i=0;char present=S tartStates;whileistr.length函数即去遍历转换表,返回下个状态present=movepresent,str[i];//move〃即为返回错误的状态,ifpresent==N Nmovebreak;;i++〃假如返回的状态用函数属于最终状ifFinalStates.findpresent!=FinalStates.npos find态集则表示识别该自动机识别此字符串“co-Wendi;else该自动机不识别此字符串coutvv”“endl;;转换函数char movecharP,char I//moveforint i=O;iTrans.size;i++ifTrans[i].prcscnt==PTrans[i].input==I returnTrans[i].next;return N1;〃从文件中读取的信息void readtxt DNFchartempi10];fstream ffnDNEtxtn,ios::in;ff.getlinetemp,10;Alphabet=temp;ff.getlinetemp,l0;States=temp;ff.getlinetemp,10;S tartStates=temp
[0];ff.getlinetemp,10;FinalStates=temp[O];while!ff.eof ff.getlinetemp,10;TransitionTable Temptemp
[0],temp[l],temp
[2];Trans.push_backTemp;/*将的信息写入文件中,DNF第一行字符集;其次行状态集;第三行起先状态;第四行结束状态集;以下行写入状态转换表*/void writefstreamffnDNF.txtn,ios::out;ff«Alphabet«endl;ff«States«endl;ff«StartStates«endl;ff«FinalStates«endl;forint i=O;iTrans.size;i++ff«Trans[i].present«Trans[i].input«Trans[i].next«endl;ff.close;void Traversalchar present,int N,string strass=,H,〃遍历DFA的语言集列表显示ifpresent==,N11|N0return;N--;ifFinalStates.findpresent!=FinalStates.npos”该自动机识别字符串:cout vstrass«endl;else ifFinaiStates.findpresent==FinalStates.nposN0return;forint i=0;iAlphabet.length;i4-+string temp;temp=strass;strass4-=Alphabet[i];Traversalmovepresent,Alphabet[i],N,strass;strass=temp;;int mainDFAexample;example.identify;int N;请输入cout N«endl;cin»N;example.Traversalexample.Starts tates,N;example.write;systemCpause;return0;/*测试用例输入状态转换表Oa10b2lb22a1la32b33a33b3#Oal0b22a1lb2la32b53a35b53b45a66b44a66a34b5*/检查“状态转换表”是否满意的要求DFA检查”状态转换表”并非填满时的处理是否得当…()的语言集列表显示4DFA输入待显示的字符串的最大长度输出以上定义的的语言集中长度的全部规N,DFA WN则字符串(提示留意算法中循环的次数)while()的规则字符串判定5DFA输入(或用字符集随机生成)一个字符串,模拟识别字符串的过程判定该字符串是DFA否是规则字符串(属于的语言集)DFA测试用例:(―)DFA
(二)DFAother
(三)DFA试验要求根据《编译原理及实践》参考书其次章中描述的循环+双层选择”的算法编程“while case实现一般的DFA要求能通过以上三个测试用例的测试完成内容中部分,可得15C完成内容中部分,可得125B完成内容中部分,可得1245A完成全部内容,可得嘉奖判定算法概要打算起先状态接受状态集状态转换表so,F,Ts,c,s S,cc=getchar;起先状态;s=So输入未结束则循环…while c!=EOF//s=Ts,c;ifs=NULLerror;c=getchar;接受状态集ifs Faccept;elseerror;通用存储格式的建议用以上的第三个测试为例DFA DFA字符集中的字符个数以下两行也可合并成一行3//〃以空格分隔的字符集代表随意非/和*的字符/*o O状态个数以下两行也可合并成一行5//〃状态编号若约定总是用从起先的连续数字表示,则此行可省略123451〃起先状态的编号若约定为则此行可省略11,结束状态个数若约定为则此行可省略1//1,结束状态的编号5//状态的全部出去的转换按字符集中的字符依次给出-表示出错状态2-1-1//11-13-1343543-1-1-1试验报告同时上交纸质报告与电子版报告纸质报告以试验分析、试验中遇到的问题及解决方法、试验测试含屏幕截图、试验心得等为主,不得大量引用源程序引用源程序总行数不得超过行电子版报告以源程序、测试用例、输出文件等为主,包括纸质报告的电子版,须确10保提并的源程序能编译运行,否则不要上交电子版请发送到邮件标题请写明248133074@qq,学号、姓名与试验编号,形如<试验一><学号><姓名不得抄袭试验报告与源程序,否则后果自负!提高内容()图形化的用户界面;1()随意的状态转换图、状态转换表的图形绘制;2DFA附试验报告源码试验一的编程实现DFA试验目的通过本次试验,加深对及其识别的语言的理解,学习对一般的的表达DFADFA方法与编程实现方法试验任务编写一个语言程序,模拟实现识别字符串的过程C DFA试验内容()的输入;()的存储与读写;()的正确性检查;1DFA2DFA3DFA()的语言集列表显示;()的规则字符串判定;4DFA5DFA试验分析的初始化DFA一个的基本信息状态集、字符集、起先状态、结束状态集、状态转换表;DFA’在程序中状态集、字符集、起先状态、结束状态集都用类型来表示,即string可不用考虑用户输入内容的长度但缺点是字符集只能是字符而不行以是字符串状态转换表为三个字符的字符串,第一个为当前状态,其次个为输入字符,第三个为下一状态用容器存放转换函数的内容vector〃状态集string States;//开始状态char Startstates;//结束状态集string Finalstates;〃字符集string Alphabet;,/手专换国数vectorTransitionTable Trans;字符串推断初始化一个后可以通过一下算法推断一个字符串是否符合该DFA,DFAo判定算法概要打算起先状态接受状态集状态转换表sO,F,Ts,c,seS,ceS c=getchar;=起先状态s sO;//输入未结束则循环…whilec!=EOF s=T s,c;if s==NULL error;c=getchar;接受状态集if se Faccept;else㊀rror;在实际编写代码中的体现为//推断字符串void identify〈”请输入字符串coutv endl;string str;cinstr;int i=0;char present=StartStat㊀s;whileistr.length函数即去遍历转换表,返回下个状态present=move present,str[i];//mov㊀if present==1N1//N即为mov㊀返回错误的状态,break;;i++}//假如返回的状态用函数属if Finalstates.find pres㊀nt!=FinalStates.npos find于最终状态集则表示识别〈”该自动机识别此字符串〈㊀ncil;elsecout〈〈”该自动机不识别此字符串n«endl;DNF.txt-记事本对的存储与读写DFA文件F编辑E格式O查看V帮助用hb将的信息写入文件中,DNF0123第一行字符集;03Oal0b2lb22al其次行状态集;第三行起先状态;第四行结束状态集;以下行写入状态转换表根据既定的规定读取文件中的数据将其赋值,然后初始化即可;DFA的语言集列表显示DFA这一个模块应当是这个试验中比较难的一部分了我并没有运用循环的这while个做法而是用函数递归,通过全部字符集的路径去遍历整个最终将符合DFA条件的字符串输出;//遍历的语言集列表void Traversalchar present,int stringstrass=DFA//若路径已经大于或者当前状态错误,停止递归if present==»N|I N0N return;N——;ifFinalstates.findpresent!=FinalStates.npos该自动机识别字符串:strassendl;for inti=0;iAlphabet.length;i++string temp;temp=strass;strass+=Alphabet[i];Traversalmovepresent,Alphabet[i],N,strass;strass=temp;递归终止条件的推断当时,小于或者遍历到无路可走是便终止N--N0,遇到的问题对于递归的终止条件写得不够明确递归前对字符串赋值赋值,递归后应当还原,这一strass点没有想到调试了很久总结,对递归的详细编写还是不熟识目前的代码,字符集和状态只能是一个字符,若要优化可以用‘《$皿〉容器存储即可;39试验用例other试验结果的初始化DFA叫=回■J G:\MyProjects\DFA\Debug\DFA.exe_“1卜手动输入,、读取文件2txt1情输入有限状态集S0123用输入字符集Aab括输入转换函数桢一格式为当前状态-输入字符-下一状态(输入结束输入)UE M0al0b2lb22alla32b33a33b3褊入开始状态集S中输入结束状态集F:输入字符串推断字符串:请输入结束状态集F3请输入字符串aabbb鬻如识别此字符串显示小于的语言集:NT G:\MyProjects\DFA\Debug\DFA.exe该动识军该动」识工该动识工三该动识匠该动识工aaabaabaabaaabbabaaabbabba该动识工abbb该动识在该动识是该动识土」该动识工该动」识工babb bb该动识二bba「工该动识bbaa bbabbbb bbbabbbb工该动识击该动识工该动识该动识读取DFA文件:工该动识工该动键G:\MyProjects\DFA\Debug\DFA.exe孟该动子、手动输入,、读取文件该动」12txt1咚一纥请输入有限状态集S识」识「识0123识请输入字符集A ab请输入转换函数一格式为当前状态-输入字符-下一状态〈输入结束输入〉MOUE M0al0b2lb22al la32b33a33b3卷输入开始状态集S00请输入结束状态集F3请输入字符串4LrnTnTT-nTLrnTnn;4TrrnTEnTLnn-nTLnn4Tn-nTLnTLnTLrnTrnTnTLnn-nTLrnTnr J~1JJ1JJrr^J1JJJw试验总结在这次试验中,学习对一般的的表达方法与编程实现方法对课本供应DFA的算法有了更深刻的相识在编写和调试代码的过程中对自身的编程实力也有了很大的提高对自动机和其识别语言有了更透彻的理解在动手编程之前肯定要好好明确试验的理论打算和思路的理清,能帮助我们在试验过程中少走更多的弯路总之在这次试验中收获许多,提高了动手实力和分析问题的实力源代码〃构造一个DFA#includeiostream#includestring#includevector#includefstreamusing namespacestd;class TransitionTablepublic:〃当前状态charpresent;〃下一状态char next;〃输入字符charinput;TransitionTablechar P,char I,char D。