深圳大学编译原理实验报告蔡树彬实验二.doc

《深圳大学编译原理实验报告蔡树彬实验二.doc》由会员分享，可在线阅读，更多相关《深圳大学编译原理实验报告蔡树彬实验二.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、深 圳 大 学 实 验 报 告 课程名称： 编译原理 实验项目名称： 词法分析技术及其应用 学院： 计算机与软件学院 专业： 软件工程 指导教师： 蔡树彬 报告人 学号： 实验时间： 2015年11月4日至12月30日 实验报告提交时间： 2015年12月31日 教务处制实验目的与要求：目的：针对状态矩阵、NFA、DFA、正规式、确定化算法、最小化算法、Thompson算法等词法分析应用问题，设计并实现相应的解决方案，通过设计FA相关类族，以及实现前述几个重要的算法，既加深对抽象的词法、自动机、正规式等形式语言理论基础概念的理解与掌握，也加强对面向对象程序编写能力和计算思维的培养。要求: 第一

2、部分： 无符号数的识别及DFA的应用这部分又分为2个小实验1. 输入：一个文本文件（源代码文件）输出：将源代码中的无符号数识别出来并输出到另一个文件中示例：如果输入是“123*abc+def/99.2+9.9E+c”，那么输出是：（数字, 123），（其它，*abc+def/），（数字，99.2），（其它，+），（异常，9.9E+c）说明：其它是非数字打头的字符串；异常是数字打头，但最后却是不符合定义的无符号数。2. 假设：用字符“ABCDEFGHIJK”（大写）分别表示数字0.9和.、E、+、-，那么，字符串“BCLD”表示数字“12E3”=12000；输入：一个文本文件输出：将隐藏在文本文

3、件中的有效无符号数识别出来。示例：如果输入是“BCD*abc+def/JJKC+JKJL+c”，那么输出是：（数字, 123）、（数字，99.2），无效（异常）的无符号数不输出第二部分：DFA/NFA的读写及确定化、最小化算法这部分又分为3个小实验1. 输入：一个文本文件（格式自定义）输出：读入文件中的DFA/NFA，创建对应的DFA/NFA对象，再写回另一文件中。示例：如果输入是“f(S,a)=A, f(A,b)=B, B” /假设默认开始状态是S，那么输出是：K=S，A，B；=a,b；f(S,a)=A, f(A,b)=B；S；Z=B2. 输入：上一实验输出的NFA文件输出：将读入的NFA进

4、行确定化后，输出结果，需要考虑有/无e的情况。3. 输入：上一实验输出的DFA文件输出：将读入的DFA进行最小化后，输出结果。第三部分：正规式及其应用这部分又分为3个小实验1. Thompson方法的实现输入：一个正规式处理：创建与正规式对应的NFA对象，再将NFA对象写回文件，格式与前述实验相同，使得能够读回；示例：如果输入是“a*b”，那么输出是：K=A , B , C , D , E , F；=a, b；f(A,e)=B, f(B,a)=C, f(C, e)=B, f(C, e)=D, f(A, e)=D, f(D, e)=E, f(E, b)=F；A；Z=F说明：优先级处理可用栈或递归

5、，思路见算符优先分析法。概要来说，判断当前运算符与下一个运算符间的优先级，当前下一个则计算（产生NFA），否则入栈或递归。2. 从正规式到DFA将上述实验与前述实验连接起来，使得读入一个正规式文件，能输出一个DFA。正规式文件格式自定，通常每行一个正规式。示例：如果正规式文件包括2行，每行分别是“a”和“b”，那么，输出的DFA实际上是“a | b”对应的DFA。3. 字符串的识别输入：一个正规式文件和一个字符串文件输出：判断字符串文件中的每个字符串，能否被正规式对应的DFA所识别其次，再给每个正规式增加一个类别，识别到给定字符串符合某个特定正规式时，输出该类别。示例：如果输入a* 类Ab 类

6、B那么对字符串aaa输出：aaa，类A方法、步骤：要完成本实验，依据实验要求进行分解，需要完成的实验步骤是：1. 如何识别无符号数？如何判断一个输入的字符串中，包括无符号数字？如何判断无符号数的开始？中间字符及结束？首先定义一个数组，逐个判断输入的字符串中的字符是否属于数组，根据无符号数的定义和状态转移图进行识别。对输入的字符串从0状态开始，如果遇到d,E,+/-根据上图进行相应状态，扫描字符串结束后，如果处于状态1,2,6，代表能到达终态，即扫描到的字符串是无符号数。同时定义两个字符串储存扫描的字符串属于无符号数部分和其他部分的字符串，如果扫描到当前的字符为d(0-9的数字)或者.，当字符串

7、为空时，证明此字符为无符号数的开始，否则为无符号数的组成元素。如果扫描到的元素属于无符号数的元素，又不属于开始符号，就属于无符号数的中间。如果扫描到了不属于无符号数的元素，就是无符号数的结束。2. 如何实现简单的字符映射加解密算法？实验中通过定义一个字符串数组来存储无符号数的元素，解密过程中如果遇到一个加密后的字符，利用字符和数组下标的关系进行解密。3. 如何定义DFA/NFA对象，特别的，对自动机里面的映射函数f如何定义、存储？通过C语言中的结构体来定义DFA/NFA对象，定义DFA中，对于状态集、条件集和终态集用string类型定义，状态关系数组用string类型数组定义。定义NFA中，状

8、态节点和终态节点用int类型定义，状态映射函数用int类型二维数组存储。4. 如何实现确定化算法？确定化算法需要把一个旧的状态集合作为一个新的状态，这种情况如何处理？又如何求某个状态的e闭包？ 假设字符串s=AB表示状态集合AB，可以定义个新的状态集合数组，如果q0=s， 则表示新状态q0=A，B；对于某个状态的e闭包，可以利用递归的方法求某个状态的闭包，比如状态A能通一次e到达B，则A的e闭包肯定包含B的e闭包，这里就递归调用了B的e闭包5. 如何实现最小化算法？最小化算法需要对原状态集进行等价类划分，这个划分要如何处理？实现最小化算法，可以通过利用数据结构类库中的set来存储运算。如通过定

9、义一个集合数组 set s30; 其中的si表示当前划分的第i个集合。6. 汤普森方法需要处理算符的优先级，该如何处理？如何进行递归调用？ 可以先构造一张算符优先顺序表，然后定义两个栈。最后再扫描正规式。7. 如何根据给定DFA，判断并输出给定输入串的类别？根据DFA建立对应的状态转移矩阵，从DFA的起始状态扫面字符串，根据状态矩阵做对应的装换，直到扫描字符串结束，并且最后状态是该DFA的终态，该字符串就是属于该类。实验过程及内容： 实验过程及内容，处理代码设计说明、代码及其注释外，特别关注编程过程。 要求，至少有一张照片，照片上出现你（正面）+正在写的代码（电脑要有外观）实验2_1_1代码：

10、#include #include #include using namespace std;int GetKind(char c); /分类函数int Convert(int s,int t); /状态转移函数int IsUnsignNum(string str); /判断一个字符串是否为无符号数int main()int i;string str;string num=,other=;ifstream fin(text2_1_1.txt);getline(fin,str);for(i=0;istr.length();i+)int k=GetKind(stri);char c=stri;if

11、(k=1 | k=2)if(other!=)cout(其它, other)endl;other=;num+=c;else if(k=3 | k=4)if(num!=)if(IsUnsignNum(num)cout(数字, num)endl;num=;other+=c;elsenum+=c;elseother+=c;else if(k=5)if(num!=)num+=c;elseother+=c;elseif(num!=)if(IsUnsignNum(num)cout(数字, num)endl;other+=c;elsenum+=c;cout(异常, num)endl;num=;elseothe

12、r+=c;if(num!=)if(IsUnsignNum(num)cout(数字, num)endl;elsecout(异常, num)endl;if(other!=)cout(其它, other)endl;return 0;/分类函数int GetKind(char c)if(0=c & c=9) /数字return 1;else if(c=.)return 2;else if(c=+)return 3;else if(c=-)return 4;else if(c=E | c=e)return 5;else return 0;/状态转移函数int Convert(int s,int t) s

13、witch(s)case 0:switch(t)case 1:s=1;break;case 2:s=3;break;default:s=-1;break;case 1:switch(t)case 1:s=1;break;case 2:s=2;break;case 5:s=4;break;default:s=-1;break;case 2:switch(t)case 1:s=2;break;case 5:s=4;break;default:s=-1;break;case 3:switch(t)case 1:s=2;break;default:s=-1;break;case 4:switch(t)

14、case 3:case 4:s=5;break;case 1:s=6;break;default:s=-1;break;case 5:switch(t)case 1:s=6;break;default:s=-1;break;case 6:switch(t)case 1:s=6;break;default:s=-1;break;return s;/判断一个字符串是否为无符号数int IsUnsignNum(string str) int s,t;s=0;for(int i=0;istr.length();i+)t=GetKind(stri);s=Convert(s,t);if(s=-1)retu

15、rn 0;switch(s)case 1:case 2:case 6:return 1;return 0;实验2_1_2代码：#include #include #include using namespace std;char words20=0,1,2,3,4,5,6,7,8,9,.,E,+,-;int GetKind(char c); /分类函数int Convert(int s,int t); /状态转移函数int IsUnsignNum(string str); /判断一个字符串是否为无符号数int main()int i;string str;string num,other;nu

16、m=;other=;ifstream fin(text2_1_2.txt);getline(fin,str);for(i=0;istr.length();i+)char c=stri;if(isupper(c) & c=N)c=wordsint(c-A);int k=GetKind(c);if(k=1 | k=2)if(other!=)other=;num+=c;else if(k=3 | k=4)if(num!=)if(IsUnsignNum(num)cout(数字, num)endl;num=;other+=c;elsenum+=c;elseother+=c;else if(k=5)if(

17、num!=)num+=c;elseother+=c;elseif(num!=)if(IsUnsignNum(num)cout(数字, num)endl;other+=c;elsenum+=c;num=;elseother+=c;if(num!=)if(IsUnsignNum(num)cout(数字, num)endl;return 0;/分类函数int GetKind(char c)if(0=c & c=9)return 1;else if(c=.)return 2;else if(c=+)return 3;else if(c=-)return 4;else if(c=E | c=e)retu

18、rn 5;else return 0;/状态转移函数int Convert(int s,int t) switch(s)case 0:switch(t)case 1:s=1;break;case 2:s=3;break;default:s=-1;break;case 1:switch(t)case 1:s=1;break;case 2:s=2;break;case 5:s=4;break;default:s=-1;break;case 2:switch(t)case 1:s=2;break;case 5:s=4;break;default:s=-1;break;case 3:switch(t)

19、case 1:s=2;break;default:s=-1;break;case 4:switch(t)case 3:case 4:s=5;break;case 1:s=6;break;default:s=-1;break;case 5:switch(t)case 1:s=6;break;default:s=-1;break;case 6:switch(t)case 1:s=6;break;default:s=-1;break;return s;/判断一个字符串是否为无符号数int IsUnsignNum(string str) int s=0,t;for(int i=0;istr.lengt

20、h();i+)t=GetKind(stri);s=Convert(s,t);if(s=-1)return 0;switch(s)case 1:case 2:case 6:return 1;return 0;实验2_2_1关键代码：struct NFA /*nfa数据结构*/string node,codi,end;string fun3030; /状态关系数组int edge; void init()int i,j;node=;codi=;end=;edge=0;for(i=0;i30;i+)for(j=0;j30;j+)funij=;void out()cout-读取的NFA为-endl;c

21、out状态集合：nodeendl条件集合：codiendl状态关系：endl;for(int i=0;i30;i+)for(int j=0;j30;j+)if(funij!=)if(j=26)coutf(char(i+A),*)=funijendl;elsecoutf(char(i+A),char(j+a)=funijendl;cout起始状态：Aendl终态集和：endendlendl;struct DFAint node30,end30;int f3030;string lagu;int num;void init()memset(node,0,sizeof(node);memset(en

22、d,0,sizeof(end);memset(f,-1,sizeof(f);lagu=;num=0;void out()int i;cout转换条件：laguendl状态关系：endl;for(i=0;i30;i+)for(int j=0;j30;j+)if(fij!=-1)coutf(qi,char(j+a)=qfijendl;cout起始状态：q0endl终态集：;for(i=0;i30;i+)if(endi)coutqi ;coutendl;struct Setbool flg;set ss;void init()flg=false;ss.clear();NFA nfa;DFA dfa;

23、Set ps30;void Reads(string s) /文件读取函数if(s0!=)nfa.edge+;char c1=s2;char c2=s4;char c3=s7;int a;a=nfa.node.find(c1,0);if(a=string:npos)nfa.node+=c1;a=nfa.node.find(c3,0);if(a=string:npos)nfa.node+=c3;a=nfa.codi.find(c2,0);if(a=string:npos)nfa.codi+=c2;if(c2=*)nfa.funint(c1-A)26+=c3;elsenfa.funint(c1-A

24、)int(c2-a)+=c3;elsenfa.end+=s1;实验2_2_2关键代码：string Getclo(int i) /求*-闭包函数string res=;string s1=nfa.funi26;res+=char(i+A);if(s1!=)for(int j=0;js1.length();j+)int a=s1j-A;if(a!=i)string s2=Getclo(a);for(int k=0;ks2.length();k+)if(res.find(s2k,0)=string:npos)res+=s2k;return res;void Closesure() /求各状态的*闭

25、包for(int i=0;infa.node.length();i+)int a=nfa.nodei-A;cloa=Getclo(a);/*for(int i=0;infa.node.length();i+)coutclonfa.nodei-Aendl;*/string Getsontras(string s,char a) /nfa子集状态转换函数set ns;string res=;for(int i=0;is.length();i+)string str=nfa.funint(si-A)int(a-a);for(int j=0;jstr.length();j+)char mid=strj

26、;ns.insert(mid);for(set:iterator it=ns.begin();it!=ns.end();it+)res+=(*it);return res;string Getsonclose(string s) /nfa子集的闭包函数set ns;string res=;for(int i=0;is.length();i+)int a=si-A;string str=cloa;for(int j=0;jstr.length();j+)char mid=strj;ns.insert(mid);for(set:iterator it=ns.begin();it!=ns.end()

27、;it+)res+=(*it);return res;void Makesure() /将nfa进行确定化string q30;int Dfun3030;int cnt,f,t;queue Q;q0=clo0;f=-1;cnt=1;Q.push(q0);memset(Dfun,-1,sizeof(Dfun);while(!Q.empty() /将产生的新状态放在一个队列中，知道队列为空string fs=Q.front();Q.pop();+f;for(int i=0;ilagu.length();i+)char a=nfa.codii;if(a!=*)string res=;res=Gets

28、ontras(fs,a);res=Getsonclose(res);int flg=1;if(res!=)for(int j=0;jcnt;j+)if(res=qj)flg=0;t=j;break;if(flg)qcnt=res;Q.push(qcnt);t=cnt;cnt+;Dfunfint(a-a)=t;cout-将NFA进行确定化-endl;/确定后dfa的输出cout确定化后的dfa为：endl;int i,j;for(i=0;ilagu.length();i+)if(lagui!=*)dfa.lagu+=lagui;for(i=0;icnt;i+)coutqi=qiendl;dfa.

29、nodei=1;for(int j=0;jnfa.end.length();j+)char mc=nfa.endj;if(qi.find(mc,0)!=string:npos)dfa.endi=1;break;for(j=0;j30;j+)dfa.fij=Dfunij;dfa.out();/- dfa最小化部分 -/void intital()for(int i=0;i30;i+)psi.init();int Getwhere(int k) /判断状态qk属于哪个现有的集合for(int i=0;inums;i+)set:iterator it=dsi.find(k);if(it!=dsi.e

30、nd()return i;void Part(set& s) /对当前集合s进行划分int nod30;int id=0;for(set:iterator it=s.begin();it!=s.end();it+)nodid+=(*it);for(int i=0;idfa.lagu.length();i+)char a=dfa.lagui;int cnt=0;intital();for(int j=0;j1)s.clear();for(int j=0;j30;j+)if(psj.flg=true)if(s.size()=0)for(set:iterator it=psj.ss.begin();

31、it!=psj.ss.end();it+)int mid=(*it);s.insert(mid);elsefor(set:iterator it=psj.ss.begin();it!=psj.ss.end();it+)int mid=(*it);dsnums.insert(mid);nums+;return;实验2_2_3关键代码：void Minions() /将dfa最小化 int i;coutendl-将DFA进行最小化-endl;for(i=0;i30;i+) /初始划分为2个集合if(dfa.nodei=1 & dfa.endi=0)ds0.insert(i);else if(dfa

32、.endi=1)ds1.insert(i);nums=2;int k;int cnt=1;dok=nums;for(i=0;i1)Part(dsi);cout第cnt次划分为：endl;for(i=0;inums;i+)cout;for(set:iterator it=dsi.begin();it!=dsi.end();it+)cout(*it) ;coutendl;cnt+;while(knums); /知道划分新的集合个数等于原来的个数时终止循环for(i=0;i1)set:iterator it=dsi.begin();int win=(*it);it+;for(;it!=dsi.end();it+)int fai=(*it);dfa.nodefai=0;dfa.endfai=0;for(int j=0;j30;j+)dfa.ffaij=-1;for(int k=0;k30;k+)if(dfa.fjk=fai)dfa.fjk=win;