正规文法生成正规式.doc

《正规文法生成正规式.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学号：专业：姓名：实验日期：2012.4.27教师签字：成绩：实验名称：试验三：由正规文法构造正规式实验目的：掌握上下文无关文法类型的定义，及与其他类型文法的区别；２.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例；３.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、间接左递归。实验原理：1.对于任意一个正规文法G[S],都存在一个正规式与其等价，故可以使用RG构造RE。2.对于RGàRE,可遵循以下三种规则。1)r1àr2,r1àr3→r1

2、àr2

3、r32)r1àr2r3,r3àr4→r1àr2r43)r1àr2r1,r1àr3→r1àr2*r33.对于任意的RE，实验内容：１.实验要求：输入任意的正规文法,输出相应的正规式。２.实验代码：#include#include#include#include#include#includeusingnamespacestd;structrelation{string_left,_ri

4、ght;};vectorrel;stringVN;relationget_realation(stringstr){//将一个字符串生成式分为左右部输入格式为->，返回生成式结构体intt=str.find('-');relationr;r._left=str.substr(0,t);r._right=str.substr(t+2,str.length()-t);returnr;}vectorfind_Vn(charc){//查找左部为c的产生式vecto

5、rv;for(inti=0;iREC++2012/4/27COPYRIGHTFROMNINGYU]"<

6、dwithCtrl+Z(note:beginwithS)"<>strPath){rel.push_back(get_realation(strPath));//得到左部与右部;if(rel[rel.size()-1]._left.length()==1){//得到左部的非终结符charc=rel[rel.size()-1]._left[0];if(c<='Z'&&c>='A'){intt=VN.find(c

7、);if(t==string::npos)VN+=c;}}}}stringdfs(charc){boolflag;vectorv1,v2,v3,v4;//v1是左部为c右部为c的关系，v2是左部为c但是右部Vn不为c的关系，v3是左部为c，右部为re的关系v4=find_Vn(c);/////////////////////////////////////////////////////////////按照右部vn的关系分类;for(inti=0;i

8、+){chart=v4[i]._right[v4[i]._right.length()-1];if(t==c)v1.push_back(v4[i]);elseif(t<='Z'&&t>='A')v2.push_back(v4[i]);elsev3.push_back(v4[i]);}/////////////////////////////////////////////////////////将递归关系合并relationr;r._left.push_back(c);for(inti=0;i<

9、v2.size();i++){chart=v2[i]._right[v2[i]._right.length()-1];strings=v2[i]._right.substr(0,v2[i]._right.length()-1);s+=dfs(t);r._right=s;v3.push_back(r);}///////////////////////////////////////////////////////////////////将re的关系右部合并;relationr1;r1._left.