正规文法生成正规式

《正规文法生成正规式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、r32)r1àr2r3,r3à

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

4、ationget_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的产生式vectorv;for(inti=0;i

5、0]==c){v.push_back(rel[i]);}returnv;}voidprint(){cout<<"[RG->REC++2012/4/27COPYRIGHTFROMNINGYU]"<>

6、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);if(t==string::npos)VN+=c;}}}}stringdfs(charc){boolflag;vectorv1,v2,v3,v4;//v1是左部为c右

7、部为c的关系，v2是左部为c但是右部Vn不为c的关系，v3是左部为c，右部为re的关系v4=find_Vn(c);/////////////////////////////////////////////////////////////按照右部vn的关系分类;for(inti=0;i='A')v2.push_back(v4[i

8、]);elsev3.push_back(v4[i]);}/////////////////////////////////////////////////////////将递归关系合并relationr;r._left.push_back(c);for(inti=0;i

9、s;v3.push_back(r);}///////////////////////////////////////////////////////////////////将re的关系右部合并;relationr1;r1._left.